Number of vertices present in all maximum matchings Given a graph $G$, we need to find the cardinality of the largest set of vertices so that each of them are present in every maximum matching possible.

Is there a solution beside the obvious remove each vertex and find the maximum matching to see it reduces?

Is your graph bipartite? Because, if it is: suppose that one side of the bipartition is left and the other is right. Find a maximum matching, and orient all matched edges left-to-right and all unmatched edges right-to-left. Then a vertex $v$ can be omitted from a maximum matching if and only if one of the three following (mutually exclusive) conditions holds:

$v$ is already unmatched
$v$ can be reached from an unmatched vertex on its side of the bipartition in the resulting digraph
$v$ can reach an unmatched vertex on its side of the bipartition in the resulting digraph.

By doing two breadth-first or depth-first searches, one to find the parts of the graph that can be reached from unmatched vertices and one to find the parts that can reach unmatched vertices, you can find the essential vertices in linear time once you already have the matching.

Probably something like this will also work for the non-bipartite case, using a blossom-contracting alternating path search, but the details will be more complicated.


Minor and subdivision It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$.

Moreover, a graph $G$ has one of $K_{3,3}$ or $K_5$ as minor if and only if it has one of $K_{3,3}$ or $K_5$ as topological minor.

Furthermore, in a writeup by Bruce Reed i saw the following theorem.

Theorem: For any graph $H$, there is a finite set $\mathcal{Z}(H)$ of graphs such that $G$ has $H$ as a minor if and only if $G$ contains a subdivision of some element of $\mathcal{Z}(H)$.

So, my question is under what condition $\mathcal{Z}(H)=\{H\}$ or in other words, what properties must $H$ have so that $\mathcal{Z}(H)=\{H\}$ ?

$\mathcal{Z}(H)$ is the set of graphs obtained from $H$ by splitting vertices of degree $>3$ (the reverse operation to contracting an edge between two vertices, both of degree $\ge 3$, and where the contracted edge is not in any triangle). So (at least when all graphs are assumed to be finite) $\mathcal{Z}(H)=\{H\}$ iff $H$ has maximum degree 3.


$ACC^0$ implementation of a boolean function Consider the symmetric boolean function
$$F(x_1,\dots,x_n)=1\iff\sum_{i=1}^nx_i\mbox{ is a square}.$$
It is implementable in $TC^0$.
Is there an $ACC^0$ implementation?
The reason I ask is there seems to be few tricks which can be deployed.

Square is sum of consecutive odd numbers.

Square is $0$ or $1$ mod $4$ (checkable by $\oplus$ gates).

Squares are the set of the integers having odd number of divisors.

Few are available in https://proofwiki.org/wiki/Category:Square_Numbers.
But is there a finite number of tricks which capture the function and place it in $ACC^0$?

Suppose $x \in \{0,\dots,2n\}$. Then we have $((2n)^2 - n) + x$ is square if and only if $x=n$. This is easily seen to imply that the square function is complete for $\mathrm{TC}^0$ under $\mathrm{AC}^0$ Turing reductions.


Inverse of transducer compositions Consider a Generalized Sequential Machine (GSM; or nearly equivalently -- an FSM transducer). These machines are closed under compositions. A composition of two GSMs $f(x)$ and $g(x)$ can be written as a function $h(x) = f(g(x))$.  I am interested in the inverse problem:

Given a transducer $h(x)$, decompose it into a composition of two transducers $f(g(x))$. (One of the $f,g$ might be given.)

Has this question been studied?

Motivation
This question that occurred to me many years ago and is similar to a recent question by Dave Lang. After some back-and-forth we agree that it seems basic, yet not to under-studied. Although, Dave Lang did find a potentially related paper: Weber, A. (1996). Decomposing a k-valued transducer into k unambiguous ones. Informatique théorique et applications, 30(5): 379-413.
I suspect that this is linked to the Krohn-Rhodes decomposition and that through the natural correspondence between TMs and transducers, we might find hidden structure that could be useful in termination analysis and automated theorem proving.

This is done in Chapter 6 "Decomposition of sequential functions" of

[1] S. Eilenberg, Automata, languages and machines, Vol. B, Academic Press, New York, 1976

and there is indeed a connection with the Krohn-Rhodes decomposition. However the decomposition is weaker than just $h = f \circ g$, just like in K-R decomposition, which works up to division. See also

[2] H. Straubing, Families of recognizable sets corresponding to certain
varieties of nite monoids, J. Pure Appl. Algebra, 15, (1979) 305{318.

for application to regular languages (or Google "wreath product principle" for more recent papers).


Lower bounds for formulae sizes for addition I am interested in the conversion of  $\sum_{i=1}^n x_i = y$ to 3-CNF.  Here $x_i$ is a binary 0/1 variable and $y$ is some positive integer. There are a number of practical methods for doing this, some of which are in this answer.  What is known about the minimum possible size however?

Define a function $f(n,y)$ as the minimum size of a logical formula which is equivalent to the question: does $\sum_{i=1}^n x_i = y$? What is known about  $f(n,y)$?   Is the exact value of $f(n,y)$ known for small values $n$ and $y$?

EDIT Kaveh has formalized my intended question in the final part of his answer. From there we learn that finding any lower bound might be hard. I am still interested to know what the best upper bounds are, especially for small problem sizes.

Counting the number of 1s in a given binary string is $\mathsf{TC^0}$-complete and cannot be decided using any polynomial-size CNF. In fact you need exponentially large CNFs to decide them. So if you want $y$ to be part of the input then the size is going to be exponential in $n$.

If $y$ is fixed, then there are CNF's with $O({n \choose y})$ gates: check if any $y$bits of $x$ are 1:
$$\exists I \in {n \choose y} \ \forall j \in I. \ x_{j} \land \forall j\notin I. \ \lnot x_j $$

For $y = \frac{n}{2}$ this gives an exponential-size CNF. I haven't checked it but I think the proof for parity not in $\mathsf{AC^0}$ can be adopted to prove an exponential size lower-bound for this function.

As I wrote before, in case we are interested in satisfiability and a reduction to 3CNF-SAT then the size is constant as we can decide in polynomial-time if the equality holds or not and depending on the answer return $\top$ or $\bot$.

Another question is to look for a CNF $\varphi(\vec{x}, \vec{y}, \vec{w})$ such that for all $\vec{a}$ and $\vec{b}$, $\Sigma_{1 \leq i \leq n} a_i = b$ holds iff $\varphi(\vec{a}, \vec{b}, \vec{w})$ is satisfiable, i.e. $\exists \vec{w} \ \varphi(\vec{a}, \vec{b}, \vec{w})$ holds. The lower-bound does not apply to such formula, in fact for any langauge $L \in \mathsf{NP}$ there is a polynomial-size CNF $\varphi(\vec{x},\vec{w})$ s.t.

$$ x \in L \Leftrightarrow \exists \vec{w} \ \varphi(\vec{x},\vec{w}).$$

I don't know what is the best known CNF size for
$\Sigma_{1 \leq i \leq n} x_i = y$ in this sense.
I don't think there is any good lower-bound for the following reason:
the reduction from circuit-SAT to 3CNF-SAT is very efficient: linear number of new variables, linear increase in size.
Any lower-bound would also give a similar lower-bound on the circuit size for deciding the equation and in general we don't have good circuit size lower-bounds.

An obvious upper-bound can be obtained from the same idea: the equation can be decided using two Threshold and one And, so this has a constant size $\mathsf{TC^0}$ circuit. The upper-bound follows from reducing evaluation of a $\mathsf{TC^0}$ circuit to 3CNF-SAT.


arithmetic circuits for polynomials (updated) I am concerned about the  following question, consider
$P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$

Is there a straight line program (or arithmetic circuits) of polynomial size (wrt $n$) for the  polynomial $P_{2^n}(x)$? The difficulty seems to lie in the factorial, as for example the polynomial $x^{2^n}$ has a polynomial size arithmetic circuit (by repeated squaring).

Sorry in my previous post I did not make the question clear, as it would become a very simple question.

I assume that you mean $P_n(x)= \sum_{i=0}^n \frac{x^i}{i!}$.

Peter Bürgisser shows that if this problem is hard, then computing the permanent
is hard (http://link.springer.com/article/10.1007/s00037-009-0260-x).
To my best knowledge, your problem is open.


Dynamic planar exact k-nearest neighbors for pathological data What are the best known results for a data structure offering the following operations on sets of points in 2-dimensional euclidean space:

$insert(x)$
$delete(x)$
$nearest(k,x)$ (where $k$ is an integer greater than 0) returns the $k$ closest points to $x$ that are in the set.

In this particular case, I'm not particularly interested in approximate nearest neighbor, Monte Carlo algorithms, or algorithms that assume the data is well-formed in some way.

I am not as prejudiced against Las Vegas algorithms, algorithms that assume the coordinates of the point have $O(\lg n)$ bits, or algorithms with running time depending on $k$.

According to TOPP 63, dynamic nearest neighbors can be answered in $O($polylog$)$ time per insert, delete, or query (that is, the case $k=1$). The general case can therefore also be answered in time $O(k$ polylog$)$ per query: to do a query for $k$ points, repeatedly find and delete the nearest neighbor, then once the query is done re-insert all the points you deleted.


Why REFL rule is primitive in HOL Light? HOL Light
assumed REFL as a primitive.
Why does it need to do so?
Can't REFL rule be deduced in this way using ASSUME twice and DEDUCT_ANTISYM_RULE once?

$$\frac{\overline{\{p\}\vdash p} \quad \overline{\{p\}\vdash p}}{\vdash p = p}$$

DEDUCT_ANTISYM_RULE only applies to propositions, while REFL applies to all terms of all types. Your suggestion only shows that every propositions is equal (equivalent) to itself, but it could not be used to show that ever number equals itself.


Proof for ACYCLIC PARTITION being NP-complete I'm new to this site, so please pardon me for any mistakes and please feel free to edit the question to help get better answers.

I'm interested in reading any proof of ACYCLIC PARTITION (Garey and Johnson) being NP-complete, and I'd love it if you could share a proof for the same here. It'd be great if you could also give an approximation algorithm for the problem.

EDIT:

The problem is defined as follows (Garey and Johnson):

Let $G = (V,A)$ be a directed graph, with a weight function $w(v)$ mapping each vertex $v$ to a positive integer, cost function $c(a)$ mapping each edge $a$ to a positive integer, and let there be two positive integers $B$ and $K$.

Is there a partition of V into disjoint sets $V1, V2,..., V_m$ such that the directed graph $G' = (V',A')$, where $V' = \{V1, V2,..., V_m\}$, and $(V_i, V_j)$ is in $A'$ if and only if $(v_i,v_j)$ is in $A$ for some $v_i \in V_i$ and some $v_j \in V_j$, is acyclic, such that the sum of the weights of the vertices in each $V_i$ does not exceed $B$, and such that the sum of the costs of all those arcs having their endpoints in different sets does not exceed $K$?

In the current formulation, your problem can be proved to be NP-complete by a direct reduction from PARTITION.

Given $n$ positive integers, $S = \{a_1,a_2,...,a_n\}$ the PARTITION problem asks to find two disjoint subsets $S_1 \cup S_2 = S$ such that $\sum_{i\in S_1} a_i = \sum_{j \in S_2} a_j$.

So, just pick: $G = \{ V, \emptyset \}$ with $|V| = n$, set $m = 2$ and assign weight $a_i$ to node $u_i$ for all $i = 1,...,n$; set $B = \frac{1}{2} \sum a_i$, and set $K=0$ (arc costs and the acyclic constraints are irrelevant).

NOTE: my old answer was related to a different ACYCLIC PARTITION problem, and you can find it in the edits history below.


On the stopping criterion of coordinate descent method I am trying to implement the coordinate descent method to solve the dual of linear SVM problem, but blocked at the stopping criterion.

Consider the optimization problem
\begin{equation}
\min f(\mathbf{x})
\end{equation}
under the constraints $x_i\in C_i$ for $i=1,2,\ldots,m$ where $\mathbf{x}=(x_1,x_2,\ldots,x_m)$.

At iteration $k$ we perform $m$ inner iterations where the $i$-th inner iteration updates $x_i$ by solving:
$$x_i^{k+1} = \arg\min_{y} f(x_1^{k+1},x_2^{k+1},\ldots,x_{i-1}^{k+1},y,x_{i+1}^{k},\ldots,x_{m}^{k})$$
under the constraint $y\in C_i$.

My question is, what is the stopping criterion of this algorithm if we want to obtain an $\epsilon$-accurate solution $\mathbf{x}$, i.e. $f(\mathbf{x}) - f(\mathbf{x}^*) \le \epsilon$ where $\mathbf{x}^*$ is the true optimal solution? If it's too general then let's consider in particular the dual of linear SVM problem: $$\min f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^\top K \mathbf{x} - C\mathbf{1}^\top\mathbf{x},\quad \mbox{s.t. } 0\le x_i\le C \quad i=1,\ldots,m$$
where $K$ is a positive semi-definite matrix and $C$ is a positive constant.

For the moment I take $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})<\epsilon$ but $f(\mathbf{x}^k) - f(\mathbf{x}^{k+1})$ is only the lower bound of $f(\mathbf{x}^k) - f(\mathbf{x}^*)$.

Thank you in advance.

Here's one possible solution:
$$\nabla f(x) = \left[ \frac{\partial f(x)}{\partial x_1} \cdots \frac{\partial f(x)}{\partial x_n}\right]^T$$
The coordinate descent algorithm is exploring all the coordinate axes, so you have an estimate of $\hat{\nabla} f_i(x_k)=\frac{\partial f(x^k)}{\partial x_i}$. In particular, when $\Big| \hat{\nabla} f_i(x_k) \Big| < \epsilon \,\forall i$, then $|\nabla f(x_k)| < n\epsilon$, so setting $\frac{\epsilon}{n}$ as the stopping criterion for the maximum slope along the coordinate axes is a reasonable strategy.

(This gives you guarantees about the gradient and not the actual decrease, but I believe it can be modified because your function is a convex quadratic, not sure how off the top of my head)


A fixed-depth characterization of $TC^0$? $NC^1$? This is a question about circuit complexity. (Definitions are at the bottom.)

Yao and Beigel-Tarui showed that every $ACC^0$ circuit family of size $s$ has an equivalent circuit family of size $s^{poly(\log s)}$ of depth two, where the output gate is a symmetric function and the second level consists of $AND$ gates of $poly(\log s)$ fan-in. This is a fairly remarkable "depth collapse" of a circuit family: from a depth 100 circuit you can reduce the depth to 2, with only a quasi-polynomial blowup (and one fancy but still restricted gate at the top).

My question: is there any known way to express a $TC^0$ circuit family, similarly? More ambitiously, what about an $NC^1$ circuit family? Potential answers would have the form: "Every $TC^0$ circuit of size $s$ can be recognized by a depth-two family of size $f(s)$, where the output gate is a function of type $X$ and the second level of gates have type $Y$".

It doesn't have to be depth-two, any sort of fixed-depth result would be interesting. Proving that every $TC^0$ circuit can be represented in depth 3 by a circuit consisting of only symmetric function gates would be very interesting.

Some minor observations:

If $f(n)=2^n$ the answer is trivial for any Boolean function (we can express any function as an $OR$ of $2^n$ $AND$s). For concreteness, let's require $f(n) = 2^{n^{o(1)}}$.
The answer is also trivial if either $X$ or $Y$ is allowed to be an arbitrary function computable in $TC^0$... :)
I'm obviously interested in "simpler" functions, whatever this means. It's a bit slippery to define because there are symmetric function families which are uncomputable. (There are unary languages which are uncomputable.) If you like, you may simply replace $X$ and $Y$ with symmetric functions in the statement, however I'd be interested in any other neat choices of gates.

(Now for some brief recollections of notation:

$ACC^0$ is the class recognized by a family of unbounded fan-in constant-depth circuits with $AND$, $OR$, and $MOD_m$ gates for a constant $m > 1$ independent of the circuit size. A $MOD_m$ gate returns $1$ iff the sum of its inputs is divisible by $m$.

$TC^0$ is the class recognized by constant-depth circuits with $MAJORITY$ gates of unbounded fan-in.

$NC^1$ is the class recognized by logarithmic-depth circuits with $AND$, $OR$, $NOT$ gates of bounded fan-in.

It is known that $ACC^0 \subseteq TC^0 \subseteq NC^1$ when the circuit size is restricted to be polynomial in the number of inputs.)

Barrington's Theorem ought to get you poly-size depth-3 circuits for $NC^1$ with a top gate that's not too strange (multiplies 5 cycles).


Generalizations of Dyck languages? The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and Visibly Pushdown Automata?
For example, Dyck languages require parenthesis to be paired, but visibly pushdown languages merely require that stack movement is controlled by the input tape, without any requirement that "call symbols" and "return symbols" are matched one-to-one.
It is easy to imagine an intermediate class, e.g. the class of visibly push down languages where the removal of all level symbols from each word results in a Dyck language, but I'm not sure if any such classes have useful properties or have been the subject of previous study.

I believe that a type of automata that your are looking for could be "visibly counter automata". It is easy to imagine what they should be - they are just standard automata but equipped with a set of non-negative unbounded counters that can be incremented/decremented after you read a specific letter (like in the case of VPA).
You might want to check the paper "Regularity Problems for Visibly Pushdown Languages" by Barany et al.: https://www.logic.rwth-aachen.de/~vbarany/BLS_stacs06_withAppendix.pdf


finding permutations which fulfills given conditions Let $K$ be an ordered finite set. Consider some function $g:K^2 \rightarrow R$ such that

$g(k1,k1') + g(k2,k2') \ge g(k1,k2') + g(k2,k1')$

where $k1 > k2$ (in order A1) and $k1' > k2'$ (in order A2) (*)

Is there exists some effective algorithm which for given function can find such orders A1,A2 where the function fulfill  the property (*) or verify that such orders A1,A2 doesn't exists.

REFORMULATION:

Let $K$ be a finite set.
Let $g\colon K^2 \rightarrow \mathbb{R}$.

We want to define the orders $>_1$ and $>_2$ on $K$ such that
$$s \, >_1 \,\, t \text{ and } x \, >_2 \,\, y$$ if and only if
$$g(s,x) + g(t,y) \ge g(s,y) + g(t,x).$$

Is there an efficient algorithm to prove the existence or non-existence of the two orders?

Jukka's comment reminds me of the following reference.

If we look at such a function g as a matrix, the condition is equivalent to one in the definition of a permuted inverse Monge matrix.  There is a polynomial-time algorithm to determine if a given matrix is a permuted inverse Monge matrix (and if so, that gives corresponding permutations).

The result was found by Deineko and Filonenko (1979) in their Russian paper, and it is explained (in a more general form) in the following survey by Burkard et al.

Rainer E. Burkard, Bettina Klinz, Rüdiger Rudolf: Perspectives of Monge Properties in Optimization. Discrete Applied Mathematics 70(2): 95-161 (1996) http://dx.doi.org/10.1016/0166-218X(95)00103-X


Relationship between context-free/decidable languages and NP As far as I understand all languages in NP are decidable. But not all decidable Languages are in NP, because NP only contains decision problems.
Are there also decision problems that are decidable but not in NP?

What is the relationship between NP and context-free/regular languages?
Are there context-free languages in NP?
Are there regular languages in NP?

Are there languages in NP that are not context-free?
Are there languages in NP that are not regular?

Basic Facts:

CYK-algorithm parses inputs of length $n$ for any CFG in Chomsky normal form in time in $\mathcal{O}(n^3)$
Every CFL is generated by a CFG in Chomsky normal form
Every regular language is (also) context-free.

That answers immediately all those questions:

  What is the relationship between NP and context-free/regular languages? Are there context-free languages in NP? Are there regular languages in NP?

$\{a^nb^nc^n \mid n \geq 0\}$ is not context-free (by pumping lemma). It can obviously be decided by a (D)TM in quadratic time. That answers:

  Are there languages in NP that are not
  context-free? Are there languages in
  NP that are not regular?

And as for

  Are there also decision problems that
  are decidable but not in NP?

Yes, see Problems that cannot be verified in polynomial time


Catalog of NP-complete problems, more up-to-date than Garey&Johnson? Is there some book or other reference that I can cite as a catalog of NP-complete problems, more up-to-date than the appendix of Garey&Johnson's book? I don't want to cite web sites, even though I know there are some excellent compendiums om the web.

The book http://www.csc.kth.se/~viggo/approxbook/ on which the site http://www.csc.kth.se/~viggo/wwwcompendium/ is based.


parallelizable fast matrix in-place transposition what is the current state of the art in fast and parallel matrix in-place transposition?

I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, they do not include very detailed descriptions.

Thanks!

PS:
Of course, we do not restrict to square matrices, but rather arbitrary rectangular matrices. Their memory layout is usually a linear sequence of entries in the memory (say, as in C) and it is a highly non-trivial task to convert this data block in-place/in-situ to the sequence that corresponds to the transposed matrix.

Some information can be found in this wikipedia article, whose references I did not find to be very helpful though: Wikipedia Entry.

Sorry, no pseudocode, but a recent paper with a fast parallel algorithm, to appear in ACM Transactions on Mathematical Software:

@Article{Gustavson:2011:PCE,
  author =       "Fred Gustavson and Lars Karlsson and Bo K{\aa}gstr{\"o}m",
  title =        "Parallel and Cache-Efficient In-Place Matrix Storage Format
                  Conversion",
  journal =      "{ACM} Transactions on Mathematical Software",
  accepted =     "8 July 2010",
  upcoming =     "true",
  abstract =     "
                  Techniques and algorithms for efficient in-place
                  conversion to and from standard and blocked matrix
                  storage formats are described. Such functionality is
                  required by numerical libraries that use different
                  data layouts internally. Parallel algorithms and a
                  software package for in-place matrix storage format
                  conversion based on in-place matrix transposition are
                  presented and evaluated. A new algorithm for in-place
                  transposition which efficiently determines the structure
                  of the transposition permutation a priori is one of the
                  key ingredients. It enables effective load balancing in
                  a parallel environment.",
}

Here is the journal page, and here is a pdf version of the paper.
I hope this can be useful.


Randomness and small circuits complexity classes Let $\mathcal{C}$ be a complexity class and $\textrm{BP-}\mathcal{C}$ be the randomized counterpart of $\mathcal{C}$ defined as $\textrm{BPP}$ with respect to $\textrm{P}$. More formally we provide polynomially many random bit and we accept an input iff the probability to accept is over $\frac{2}{3}$.

It is known that for non-uniform circuits class we have $\textrm{BPAC}^0=\textrm{AC}^0$:

  Miklós Ajtai, Michael Ben-Or: A Theorem on Probabilistic Constant Depth Computations STOC 1984: 471-474

Are generalizations of this theorem known ? For instance, do we know if $\mathrm{BPNC}^1=\mathrm{NC}^1$ (still in the non-uniform setting)? This last question seems somehow non trivial to me since it seems plausible that for instance $s,t\textrm{-Connectivity}$ is in $\textrm{BPNC}^1$.

A relevant post on the subject: https://mathoverflow.net/questions/35184/use-of-randomness-in-constant-parallel-time

Most nonuniform complexity classes—$\mathrm{NC^1}$ included—are closed under the $\mathrm{BP}$ operator by the same argument as $\mathrm{BPP\subseteq P/poly}$: using the Chernoff–Hoeffding bound, the probability of error can be reduced below $2^{-n}$ by running $O(n)$ instances of the circuit with independent random bits in parallel, and taking a majority vote; then by the union bound, a sequence of random bits gives the correct result for all $2^n$ inputs of length $n$ simultaneously with nonzero probability, and in particular, there exists such a sequence. We can hardwire it into the circuit.

This argument applies to any class of circuits that is closed under taking majority of $O(n)$ parallel copies of a circuit, and fixing input gates to constants. In practice, this means any decent nonuniform class above $\mathrm{TC^0}$, as majority is computable in $\mathrm{TC^0}$.

The proof is more complicated for $\mathrm{AC^0}$, because this class does not compute the majority function. (While I haven’t seen the Ajtai and Ben-Or paper, I’d guess they use some sort of approximate majority.)


Exact exponential-time algorithms for 0-1 programming Are there known algorithms for the following problem that beat the naive algorithm?

Input: A system $Ax \le b$ of $m$ linear inequalities.
Output: A feasible solution $x^*\in \{0,1 \}^n$ if one exists.

Assume that $A$ and $b$ have integer entries. I'm interested in worst-case bounds.

If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.

However, there is an algorithm due to Impagliazzo, Paturi, and myself that can solve such a system of inequalities if the number of wires, i.e. the number of nonzero coefficients in $A$ is linear. In particular, if the number of wires is $cn$, the algorithm runs in time $2^{(1-s)n}$, where $s=\frac1{c^{O(c^2)}}$.


Free theorems, where? I've found this webapp which lets you generate a free theorem for a given type.
The generated theorems quantify over types and relations on these types. These theorems (formulas) are theorems of which theory/logical system? How does this system relate to the equational theory of the language?

The formulas are formulas of Abadi-Plotkin logic, which they describe in their paper A Logic for Parametric Polymorphism.

The semantics of System F that Abadi and Plotkin used to interpret their logic can be found in Bainbridge, Freyd, Scedrov, Scott's paper Functorial Polymorphism.


Finding a minimal context free grammar that recognizes a finite set of strings of bounded length Problem:

Given a finite set of strings $\{x_1, x_2, ..., x_n\}$ of length $\ell$ or less from some finite alphabet $\Sigma=\{a_1, a_2, ..., a_k\}$, find the minimal context free grammar that recognizes all of these strings.

If $k$ is a constant, and $n = poly(\ell)$, what can one say about this problem's complexity as $\ell$ grows?

This seems similar to the smallest grammar problem, which is NP-Hard for the optimization problem. However it is a little different because of having multiple strings, since now one needs to recognize each string independently instead of recognizing all of them at once. The smallest grammar problem is clearly a subset of this, but for small $\ell$ this might be much easier to solve, I'm not sure.

Is there a way to approximately solve this problem efficiently?

If $\ell$ and $k$ are fixed, there are only finitely many possible problem instances, so you can write a program that has a hardcoded table of all possible instances and their solutions.  Consequently, the complexity will be $O(1)$, if you consider $\ell$ and $k$ as fixed and look at the asymptotics as $n$ increases.

Why are there only finitely many possible problem instances?  Because when $\Sigma$ and $\ell$ are fixed and $\Sigma$ is finite, there are only finitely many subsets of $\Sigma^1 \cup \Sigma^2 \cup \Sigma^3 \cup \cdots \cup \Sigma^{\ell}$.


Submatrix of small rank Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that

The rank of the sub matrix $M[A, V\setminus A] \leq k$
$|A|\geq |V|/c$, $|V \setminus A|\geq |V|/c$, for some constant $c>1$.

where  $M[A, V\setminus A]$ denote the submatrix $(m_{ij};i \in A, j \in V \setminus A)$.

Note: Assume that existence of such a subset $A$ is guaranteed. .

Essentially, you are asking for a graph "separator" of a certain kind, and while this doesn't answer your question directly, your question is likely related to the notion of the rankwidth of a graph. You can find more information in this paper, this paper or especially this paper

Note that the notion of rankwidth uses "rank over the finite field $\mathbb{F}_2$", which may or may not be the field you were asking about.


Recent TCS publications with philosophical aspects Many computer science publications from the 1950s and 1960s contain fascinating philosophical speculations on the nature of the mind and the meaning of information in relation to the physical world. Famous examples are the "Turing Test", Zuse's "Calculating Space", Wheeler's "it from bit" etc.

Today such themes are widely covered in popular science books, but seem all but gone from serious research publications. What are some examples of recent TCS publications with philosophical content or implications?

some of what you refer to is covered under a general heading known as "digital physics" or digital philosophy which has a continuing thread of research in physics albeit not always mainstream.

a notable example of a TCS paper/ survey with major philosophical angles/ analysis

Why Philosophers Should Care About Computational Complexity / Aaronson

another key area/ possibility you mention is AI which has generally broken off from TCS research as practiced in academia and is now regarded as either more applied or more abstract/ speculative, and few researchers cross that gap, but there are many books on the subject by respected researchers verging on the philosophical. eg, recently

The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World / Domingos (2015)


Big gaps between RAM and Turing machine complexity If we only consider problems in P, are there any big gaps between the fastest known word-RAM algorithm and the fastest known Turing machine algorithm for particular problems? I am particularly interested if there are wide gaps for natural problems of general interest.

It is known that any problem that you can compute on a RAM machine in time $T(n)$, you can do it in a Turing Machine in time at most $T(n)^2$. You need to notice that the total size of the memory used can not be more than $T(n)$, since that would mean that you did more write operations than $T(n)$, so each time you fetch something from RAM memory, the Turing machine would take in the worst case $T(n)$ time to find the desired element sequentially from the tape. Besides memory access, the rest of operations should take around the same time. And thus you get the bound.


Algorithm to Determine if (Union of Cartesian Products of Subsets) equals (Cartesian Product of Full Sets) I have already asked this question in StackOverflow (open bounty closing on Aug 25th).

Let's say I have some finite sets: A, B, ..., K

I also have A1, A2, ... An, which are subsets of A; B1, B2, ... Bn, which are subsets of B, etc.

Let's say S is the cartesian product A x B x ... x K

and Sn is the cartesian product of An x Bn x ... x Kn

Is there an algorithm to efficiently determine if the union of all Sn is equivalent to S?

Some pointers to literature where I can study this problem are greatly appreciated.

The problem is coNP-complete and so unlikely to have a poly-time algorithm.  (I'm sure the observation was made before; I don't know where, but look in Garey-Johnson.)

Here is a simple reduction from 3-UNSAT $= \{\psi: \psi$ is an unsatisfiable 3-CNF$\}$.

Say $\psi(x_1, \ldots, x_t) = \bigwedge_{j = 1}^m (y_{j, 1}\vee y_{j, 2} \vee y_{j, 3})$, where
each $y_{j, a}$ is either a variable or a negated variable.

In your notation, let $A = B = \ldots = K = \{0, 1\}$, with $t$ such sets (one for each variable).  Think of each element of $S = A^t$ as an assignment to $x_1, \ldots, x_t$.  For each $j \in [m]$, create a Cartesian product set $S_j$ which describes the set of assignments that will falsify the $j^{th}$ clause.  Note that this can easily be done: we restrict precisely the 3 components corresponding to the variables appearing in this clause.

The union of the $S_j$'s equals all of $S = \{0, 1\}^t$ iff every assignment to $\psi$ falsifies some clause, i.e., iff $\psi$ is unsatisfiable.


Using lambda calculus to derive time complexity? Are there any benefits to calculating the time complexity of an algorithm using lambda calculus?  Or is there another system designed for this purpose?

Any references would be appreciated.

There are quantitative results concerning $\lambda $-calculus, in the form of measuring the length of reductions in (typed-)lambda calculus. But this is of course far from saying anything about the complexity of algorithms (especially that the bounds obtained are fast-growing). See for example:  Arnold Beckmann, Exact bounds for lengths of reductions in typed $\lambda $-calculus, Journal of Symbolic Logic 2001, 66(3): 1277-1285.

For something closer to your question, there is a current project that develops and studies a type-system (a functional programing language) which by static-analysis can determine (polynomial) run-time bounds of programs (as well as other resources used by programs). So in some sense, this might hint that there might be some advantage in using functional-programing for analyzing  run-time complexity. The project homepage is here.

A possibly representative paper of this project is:
Jan Hoffmann, Martin Hofmann. Amortized Resource Analysis with Polynomial Potential - A Static Inference of Polynomial Bounds for Functional Programs.  In Proceedings of the 19th European Symposium on Programming (ESOP'10).link


An Interactive Proof of God's Number? I've been learning about interactive proofs lately and I've been wondering if the whole thing was nothing more than a theoretical curiosity, or if it had any practical applications. I thought I'd start off with an example which occurred to me in the shower:

It's been making the news lately that "God's Number"=20. (God's number is the minimal number of steps needed to solve the Rubik's Cube). While this is pretty interesting,  there seems to be a little twist ... This isn't a "normal" proof in the textbook, polynomial time verifiable sense. This proof has a distinctly "brute force" flavor to it - by this I mean, the dudes at Dr Morley's lab tried with billions and billions of combinations of cubes in Google's massive supercomputers to find this neat, tight lower bound.

Anyway, the question is: How can we be certain that Dr Morley Davidson and his team are honest? Well, right away can throw the argument from authority out of the window as it's not mathematically rigorous. The obvious alternative is to re-verify the proof, by checking the source code and running the whole thing again, which seems to be a terrible waste of computational resources, not to mention the fact that everybody who who wished to be convinced of this would need to do it on his own workstation - a very tedious and unpleasant proposition for the true skeptic. So this seems to be a kind of ontological deilema.

So what I believe is this is exactly a situation where we need an interactive proof. Google's Supercomputer could be the all powerful but deceptive Prover, and we the skeptical, if not anal members of the public are the Polynomially bounded Verifiers. If we could somehow query our "Oracle" a polynomial number of times, and be convinced of this lower bound, we could be convinced of the fact that he's right, beyond all reasonable doubt.

So it seems the Decision problem "God's Number is < 20" lies in $\Pi_2^p$ or can be restated as follows (informally)

For all starting combinations $\alpha$ in the Rubik's Cube, there exists a solution which takes <=20 steps, $\beta$ which solves it.

(not sure if that's correct, but $\alpha$ and $\beta$ are both small in size, given a starting configuration and a solution it's easy to verify that it does indeed solve the cube)

and the Decision problem "God's number is 20" can be restated as

God's number is <20 and there exists a solution for some starting combination of the Rubik's cube which takes 20 steps.

So there's probably a IP[n] proof for this. (once again, check my workings)

My question is twofold

Is there a actual way to do this?
What other examples of "pratical" uses of interactive proofs are there?

... it seems the Decision problem "God's Number is < 20" lies in $\Pi_2^p$.

That is enough for it to have an interactive proof. In fact, Lund et al. proved that every language in polynomial hierarchy (PH) has an interactive proof by using Toda's theorem ($\rm{PH} \subseteq P^{\#P}$). They reduced $L\in \rm{PH}$ to #P-complete language PERMANENT, and provided an algebraic method which can be used to prove PERMANENT interactively. (This is highly inaccurate; please refer to the paper for more info.)

Using their techniques, Shamir proved that IP=PSPACE.

It was previously proved that all IP has zero-knowledge proofs, so:

All languages in PSPACE have zero-knowledge interactive proofs.


Is there notation for converting a multi-set to a set? Suppose we have a multi-set $S$. For example,  $S = \{ 1,2,2,3 \}$. Suppose we also have a set $T$, e.g., $T=\{1,2,3\}$. I would like to say, compactly, that $S$, when its duplicates are removed, is equal to $T$. Is there a simple, standard notation to do this?

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here.

Multisets are an awkward case of a perfectly natural mathematical object which never really got a standard notation — likely because multisets took much longer to be interesting to logicians. As a corollary, there is no standard notation for extracting a set from a multiset.

There are some natural ways to go about defining a reasonable notation for set-extraction:

Intersection. If your multiset is drawn from a universe $\mathbf U$, you can simply take the intersection of your multiset $\mathcal M$ with the universe, $\mathcal M \cap \mathbf U$. This is to me already a good notation, and is a good way of describing any other notation you might want to define. For your example, we may write $\{1,2,3\} = \{1,2,2,3\} \cap \mathbb N$.
Multiplicity filtering. Perhaps you are sometimes interested in when there are at least n of some of the elements; you can consider the set of such elements. One standard(-ish) notation for "$a$ is an element of $\mathcal M$ at least $n$ times" is $a \in^n\! \mathcal M$.
Consider defining
$$ \big.^n\!\mathcal M := \Bigl\{ a \in \mathcal M \;\Big|\; a \in^n\! \mathcal M \Bigr\} $$
in which case you have the identity $\big.^1\!\mathcal M = \mathcal M \cap \mathbf U$.
A set (forgetful) functor. Don't make things hard on yourself! You want the set associated with a multiset $\mathcal M$? Define $\mathbf{Set}(\mathcal M) = \big.^1\!\mathcal M$ to be that set!

There are any number of approaches to doing this. Of course, you should Google long and hard to see if there is any convention which your target audience is likely to be using. But if there isn't, then bear in mind that — by that very fact — there is no notation which you can assume your audience will be familiar with: so define your notation explicitly!

Remarks

The following are really extended comments...

Notation

It's pretty clear that $\{1,2,2,3\}$ can be used to represent a multiset in which there are two 2s, it will actually get in the way of how some people learned sets: not just that it has no repetition, but that repitition doesn't matter. Some schools teach that $\{1,2,2,3\} = \{1,2,3\}$, and in the standard set-theoretic construction of the ordered pair $(a,b) := \{\{a\},\{a,b\}\}$, one situation which must be addressed is the case of  where $a = b$, in which case one obtains the set $\{\{a\}\}$. Bear this in mind, if you want to use multisets and sets side-by-side, and consider using a different notations entirely for multisets:

Square brackets notation (as noted by Wikipedia):$[1,2,2,3]$
Double-square brackets or double-set braces notation (as found here and here):$ [\![1,2,2,3]\!] \qquad \{\!\{ 1,2,2,3 \}\!\}$
(bearing in mind that $\{\!\{ 1,2,2,3 \}\!\}$ looks a lot like the singleton set containing $\{1,2,2,3\}$).
Bag notation as provided by the stmaryrd LaTeX package (as illustrated here):

Multisets versus characteristic functions

You could try to treat multisets as being identical with their characteristic functions, so that $\{1,2,2,3\}$ can be identified with a function $f$ such that $f(2) = 2$, $f(1) = f(3) = 1$, and $f(n) = 0$ otherwise. Just as we sometimes identify languages $L \subset \{0,1\}^\ast$ with their characteristic functions $L: \{0,1\}^\ast \to \{0,1\}$, this is okay as an abuse of notation.
But taking this too seriously has problems. For instance, you might not be pre-occupied with sums, but does $\mathrm{Sum}(f)$ represent $\sum_n f(n)$ (the sum of the values of $f$), or $\sum_n n\cdot f(n)$ (the sum of the elements of the multiset represented by $f$)? If you intend to act as though multisets "really are" their histograms, you must be prepared for such potential confusions by people who assume you have important reasons to choose that convention.

I would recommend that you treat multisets as first-class entities, which have characteristic functions, but are not the same as characteristic functions.
That is, that you should keep the distinction between the collection and the function, unless you feel that identifying the two is very useful or important.


Can differential equations be classed into their own complexity classes? Problems have been, as a whole, classified, thanks to Computational Complexity. But, in differential equations, is it possible to classify differential equations depending on their computational structure?

For example, if a first order non-homogeneous equation is comparatively difficult to solve than a, say, 100th order homogeneous equation, can they be classified as separate convexity classes, given the method to solve was same? If we vary the process of solving, how random shall the solutions, their existence and stability, and other properties vary?

I would assume that I am partly convinced that solving differential equations might be NP-Hard:

https://mathoverflow.net/questions/158068/simple-example-of-why-differential-equations-can-be-np-hard

This article:

http://www.cs.princeton.edu/~ken/MCS86.pdf

has been forcing me ask for the scope of computational complexity according to the solvabality of Differential Equations. Starting with ordinary differential equations, we could classify partial, delay, difference equations etc.

I had once thought of incorporating dynamic programming using the iterates that were calculated while approximating a solution, but lost myself somewhere.

A first observation in the direction of decidability of ODEs is this paper by Avigad, Clarke and Gao, which classifies the complexity of $\delta$-decidability, in which solutions are to be found within a certain bounded error (the "delta") in one direction.

one of the main results is that $\delta$-solvability of (Lipschitz-continuous) ODEs is $\mathrm{PSPACE}$-complete.


Minimal DFA satisfying a finite view of a language Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq L$ that are known to be in the language, and a finite set of strings $B \subseteq (\Sigma^* \setminus L)$ that are known to not be in the language.

For example, let's say I have the $A = \{ab, aaab, aaaaabb\}$ and $B = \{b, aab, aaaba\}$. I might have the language $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$, since $A$ and $B$ are consistent with $L$, or I might have a completely different language.

My question is: is there a known way to create a DFA (deterministic finite automata) that accepts the strings in $A$ and rejects the strings in $B$, with a minimal or almost-minimal number of states? What's the complexity of this problem? How good is it at approximating $L$ (assuming $L$ has a fairly low descriptive complexity, and $A$ and $B$ are large)?

Original question on math.stackexchange.com. I decided to repost here after getting no answers on the original question, and having no idea where to look for them. If someone could point me toward research in this area, it would be greatly appreciated.

As you already know from the comments, finding the minimal DFA satisfying a finite set of positive and negative examples is $\mathsf{NP}$-hard. However, not all hope is lost, if you are willing to modify your learning paradigm slightly then we can get back into $\mathsf{P}$.

Assume that you are trying to learn a an unknown DFA $W$ which is minimal for some language $L_W$. If you allow the oracle membership queries and to act as a teacher by answering the following question: Given a proposed DFA $G$ does it recognize $L_W$? If not, can you provide a counter-example?

Note that if the oracle has access to $W$ it can compare $G$ to $W$ in poly-time, since testing equality between regular languages is easy. Generating a counter-example can also be done in polynomial time.

In this framework, you can learn $W$ in polynomial time using Angluin's (1987; pdf) algorithm (or Schapire's refinement of it; see section 5.4.5). For more info about this model, here are two questions on cstheory and CS.SE about it:

Lower bounds for learning in the membership query and counterexample model
Are there improvements on Dana Angluin's algorithm for learning regular sets


Are uniqueness rules converse to introduction rules? I've seen many people connecting introduction rules and elimination rules, saying that they're dual notion. Indeed, like in the categorical model, these rules are symmetric morphisms. However, if we think of the introduction rules as 'theorems' (in the sense of CHK-correspondence), the uniqueness rules seem to fit better as a 'converse' of the introduction theorems. Am I right?
My reason: it's because the uniqueness rules take the return type of the introduction rules as input, while the elimination rules take the return value of the formation rule as input.
Examples (as AB asked):

Product type

Intro: given $a:A,b:B$ an instance of $A \times B$ can be uniquely constructed
Unique: given an instance of $A \times B$, it is uniquely constructed by some $a:A,b:B$
Elim (I'm just using the non-dependent version to make it simple): providing a function $A \to B \to C$, we could feed it with an instance of $A \times B$ and we could obtain an instance of $C$

Identity type a la Martin-Löf

Intro: given $x:A$ an instance of $\sum_{x:A}{x=_A x}$ can be uniquely constructed
Unique: given an instance of $\sum_{y:A}{x=_A y}$ must be uniquely constructed from some $x:A$
Elim: omitted

I'm asking to look for criticisms on my pov.

Uniqueness is not converse to introduction. Uniqueness rules in type theory are
components of isomorphisms. If a type former is specified with an isomorphism, then

Constructors form one map
Eliminators form the inverse map
β-rules express elim ∘ con = id
η-rules (uniqueness) express con ∘ elim = id

For example, function types are given as Tm Γ (Π A B) ≃ Tm (Γ, A) B.

lam : Tm (Γ, A) B → Tm Γ (Π A B)
app : Tm Γ (Π A B) → Tm (Γ, A) B

For Σ types, we have that internal Σ is isomorphic to metatheoretic Σ.

pair  : Σ(t : Tm Γ A) × (Tm Γ (B[t])) → Tm Γ (Σ A B)
proj  : Tm Γ (Σ A B) → Σ(t : Tm Γ A) × (Tm Γ (B[t]))

In extensional type theory, the identity type is specified to be isomorphic to
metatheoretic equality:

refl    : t = u → Tm Γ (Id t u)
reflect : Tm Γ (Id t u) → t = u

Here reflect is equality reflection. If the metatheory has UIP, the object
theory inherits it via the β and η rules (omitted above). If the
metatheory does not have UIP, the object theory also does not have it!
So UIP is not like η-rules for other negative type formers. UIP is something
that we get if assume UIP in the metatheory and try to weaken the above rules
just enough to get decidable definitional equality.
In intensional TT, Id is specified differently, since in that case we do
not think of Id as a negative type (a terminal algebra, specified by an
isomorphism), but as a positive type (initial algebra).
Can we define terms of positive types with isomorphisms? What about sum types:

inj  : Tm Γ A + Tm Γ B → Tm Γ (A + B)
elim : Tm Γ (A + B) → Tm Γ A + Tm Γ B

elim is unfortunately not feasible in a constructive and proof-relevant
way. If we have a variable x : A + B in the context, we cannot decide whether
A is provable or B is provable. This only works in the empty context, where
everything computes to inj1 or inj2.
In other words, the problem is that positive types are categorically defined by mapping out (like (A + B) → C ≃ (A → B) × (A → C)), but in type theory, terms always map from the context into the type former.


Efficient (non-crypto-grade?) pseudorandom permutations with arbitrary domain size I'm looking for an efficient/simple (even if not necessarily cryptographically strong) algorithm for implementing pseudorandom permutations with domain cardinality other than a power of 2.  (FWIW, the domain cardinality I'm interested in at the moment is $900,000$.)

All the algorithms I've found for doing this aim for cryptographic strength, and tend to be relatively slow and intricate.

One exception to the last point, arguably, is the standard Feistel network algorithm, which is at least fairly simple.  Unfortunately, AFAICT, this algorithm works only for permutations with domain size $2^{2m}$, with $m\in\mathbb{Z}^+$.

(I've found some generalizations of Feistel networks to arbitrary domain sizes, but they all aim for cryptographic strength, at the expense of performance (and simplicity).)

unbalanced numeric Feistel (page 10)

swap-or-not

FastPRP

Those are all cryptographically strong; I'm not aware of

any way to get better performance by sacrificing that.


How fast can we compute the set inclusion poset of a set family? Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.

I am looking for a data-structure that will allow me to quickly answer this.
My application is from graph theory where I want to see if deleting a vertex and its neighbourhood leaves any isolated vertices, and for each vertex list all isolated vertices it leaves.

I want to create the complete poset or eventually a $|\mathcal{F}|^2$ table storing true false telling exactly which sets are subset of eachother.

Let $m = \sum_{S\in \mathcal{F}} |S|$, $u = |U|$ and $n = |\mathcal{F}|$, assume $u,n \leq m$

We can generate the $n \times u$ containment matrix (the bipartite graph) in $O(un)$ time and then can create the table of all $n^2$ comparisons in $O(nm)$ time by for each set $S \in \mathcal{F}$, loop through all elements of all other sets and mark the set as not a subset of $S$ if they the element is not in $S$.
In total $O(nm)$ time.

Can we do anything faster?
In particular, is $O((n+u)^2)$ time possible or not?

I found some related articles:

A Simple Sub-Quadratic Algorithm for Computing the Subset Partial Order (1995)
which give an $O(m^2 / log(m))$ algorithm.

The Subset Partial Order: Computing and Combinatorics slightly improves the above but also claim that the above paper solves the problem in $O(md)$ time where $d$ is the max number of sets sharing a common element, but I could not understand this result.

In the article Between $O(nm)$ and $O(n^{\alpha})$ the authors show how to in a graph find the connected components after deleting the closed neighbourhood of a vertex by using matrix multiplication. This can be used to compute the set inclusion poset by finding all the components which are singletons with a runtime of $O((n+u)^{2.79})$.

Also this forum discussion is related:
What is the fastest way to check for set inclusion?
which implies a lower bound of $O(n^{2-\epsilon})$.

If randomness is in bounds, one rough idea would be to generate a bunch of "random monotonic signature" functions and use them to approximate the subset relation (a la Bloom filters).  Unfortunately, I don't know how to make this into a practical algorithm, but here are some estimates that don't immediately prove the idea impossible.  This is very far from a useful solution, but I'll write it out in case it helps.

Assume for simplicity that the sets are all nearly the same size, say $|S| = s \pm O(1)$, and that $s = o(u)$.  We can assume $1 \ll s$, otherwise we're done.  Define
$$\begin{aligned}
q &= [s/2] \\
p &= \left[\frac{u \choose q}{s \choose q}\right]
\end{aligned}$$
Note that $p \gg 1$.

Here is the wildly impractical part.  Randomly choose $p$ subsets $A_1, \ldots, A_p \subset U$ with replacement, each of size $q$, and define a function $f : 2^U \to \{0,1\}$ by $f(S) = 1$ iff $A_i \subset S$ for some $i$.  With $S$ fixed and $A_i,f$ varying randomly, we have
$$\begin{aligned}
\Pr(f(S) = 0) &= \Pr(\forall i. A_i \not\subset S) \\
              &= \Pr(A_1 \not\subset S)^p \\
              &= \left(1 - {s \choose q}/{u \choose q}\right)^p \\
              &= e^{-\Theta(1)}
\end{aligned} $$
Since $f(S)$ is monotonic, $S \subset T$ implies $f(S) \le f(T)$.  If $T \not\subset S$, fix some $t \in T-S$.  The probability that $f$ detects $T \not\subset S$ is
$$\begin{aligned}
\Pr(f(S) = 0 < 1 = f(T)) &= \Pr(f(S) = 0) \Pr(f(T) = 1 | f(S) = 0) \\
&= e^{-\Theta(1)} \Pr(\exists i. A_i \subset T, A_i \cap T-S \ne 0 | f(S) = 0) \\
&= e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T | f(S) = 0) \\
&\le e^{-\Theta(1)} \Pr(\exists i. t \in A_i \subset T) \\
&\approx e^{-\Theta(1)} p \Pr(t \in A_1 \subset T) \\
&\le e^{-\Theta(1)} p {s \choose q-1} / {u \choose q} \\
&\approx e^{-\Theta(1)} p \frac{q}{s-q} {s \choose q} / {u \choose q} \\
&= e^{-\Theta(1)}
\end{aligned}$$
Some of those steps are pretty tenuous, but I don't have time to improve them tonight.  In any case, if they all hold, then at least it's not clearly impossible to randomly generate signature functions that have reasonable likelihood of distinguishing subsets from nonsubsets.  A logarithmic number of such functions would then distinguish all pairs correctly.  If generating a signature function $f$ and computing $f(S)$ could be reduced to $\tilde{O}(n+u)$ time, the result would be an overall $\tilde{O}(n^2+u^2)$ algorithm.

Even if the above calculations are correct, I have no idea how to generate monotonic signature functions with the desired features quickly.  It's also likely that this technique doesn't extend to significantly different set sizes.


Dominating set problem I am looking for websites or articles where can I find a data with test graphs for domination set problem. In my heuristic algorithms I use undirected and unweighted graphs. So I search for some graphs which already have been tested from other people.

A quick google search revealed Experiments on Data Reduction for Optimal Domination in Networks. If you look at their tables they cite a number of data sets for which the actual dominating set is given. They also use a number of random graph generators and publish the average dominating set size for these.

There's another paper from 2002: Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. I couldn't find an online copy, but I'm sure this paper also documents data sets and actual DS sizes.


Why Asymptotic Equipartition Property theorem proofs assume the source is memoryless? I do not understand the assumption $X_1, X_2, \cdots$ are i.i.d. ~p(x) in the AEP proofs I have seen. I have read some different sources for understanding the Asymptotic Equipartition Property. Using Cover & Thomas[1] as an example (page 51):

  Theorem 3.1.1.(AEP): If $X_1, X_2, \cdots $ are i.i.d. ~p(x), then (...)

The proof is by using the weak law of large numbers and the fact that a statistic of independent random variables is also a random variable.

Shannon defines a Source X as an ergodic Markov chain of order k, therefore in the message $X^{(n)}=(X_1, X_2 ...X_n), X_i$ are not independent. The aforementioned AEP proof assumes a memoryless Markov chain.  Why?

How can I be sure that the proof of AEP holds for a source that is an ergodic Markov chain?

[1]T. M. Cover and Joy A. Thomas. Elements of Information Theory. 2nd ed. OCLC: ocm59879802. Wiley-Interscience, 2006. isbn: 9780-471-2419-5-9.

Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well

  Asymptotic for very large $n$, a lot of coin flips, after a long time, etc ...

  Equipartition Equally distributed amongst some boxes or bins, Uniformly random, Equilibrium state, "maximum entropy" (if you like statistical physics ... max. ent. is a misnomer if you don't ... see sec. 4.4 of Cover and Thomas), and here's a cool one heat death of the universe

Essentially (strong/weak) AEP is the Information Theory version of the (strong/weak) Law of Large Numbers. In general, if you satisfy some "Law of Large numbers", i.e. your deviations from the mean (or deviations from "typical behavior") decay "quickly" (say perhaps exponentially), then you satisfy an AEP of some kind.

There is a notion of Strong topicality that is used in Csiszár & Körner (Csiszár invented the method of types, a very powerful method in information theory) that might help you understand better i.e. strong typicality means that:

  Strong Typicality: The percentage of $a$'s in $(x_1,...,x_n)$ is approximately equal to $p(a)$.

But what is the probability $p$ in this case!!! That is exactly the point, you have some "equilibrium state" $p$ if you are "ergodic." The point is that you start to behave like a bunch of coin flips at the limit, "when the Markov Process stabilizes."

"Ergodic" is just a vast generalization of i.i.d. with respect to "typical behavior."

The inclusions are (roughly) as follows

  I.I.D. $\subset$ Stationary Markov $\subset$ "Ergodic" $\subset$ $Q$ is "isomorphic/asymptotically equivalent" to a free/independent product space $P^n$

If we keep trying to generalize further and further we eventually reach "abstract non-sense" land (which is a beautiful subject by the way, I personally recommend Aluffi and Awody).

Cover and Thomas are excellent expositors, they were trying to introduce you to the notion of "typical behavior" one baby step at a time. The point is not to jump to the most general possible statement of AEP but to understand the general principles behind the theory of Information; such as how one can "typically" communicate messages perfectly over a "noisy/imperfect" channel. For example, Csiszár & Körner introduce strong typicality early on so that they can get the best error bounds in their proofs right off the bat. Go ahead and try to read Csiszár & Körner casually; while Csiszár is one of the great giants of Information theory he is not necessarily the best expositor. As my fellow Peter (Peter$\cong$Pedro) was trying to point out it would just be poor exposition for him to have done that. The vast majority of applications in Network theory don't even use that, the noise in telephone networks is modeled as white noise in practice etc ...

By the way the proof you are looking for is Thm.16.8 in Cover and Thomas but I really don't recommend you try to attack that monster just yet. At least try out Sec.4.4 in Cover and Thomas first to get a rigorous explanation of some of the stuff I stated here.

Good luck on your mathematical adventures! Bon Voyage, Fred!


Is linearizability equivalent to consensus problem? In the introduction of this paper Eventually Linearizable Shared Objects (PODC'10), the authors have presented the following statement without references:

  Linearizability, however, can be achieved if and only if consensus can be solved.

Here, linearizability is the strongest known consistency property of shared objects, which is proposed in the paper Linearizability: A Correctness Condition for Concurrent Objects.

I get confused about the above statement due to the following arguments:

In the paper Sharing Memory Robustly in Message-Passing Systems (JACM95), we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes:

  Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected.

On the other hand, the paper Impossibility of Distributed Consensus with One Faulty Process (JACM85) has proved the impossibility result of consensus even with only one process crash:

  The consensus problem  involves  an asynchronous system of processes, some of which  may be unreliable. The problem is for the reliable processes to agree on a binary value. In this paper, it is shown that every protocol for this problem has the possibility of  nontermination, even with only one faulty process.

Therefore, can we reach the following conclusion:

  consensus is stronger than linearizability?

What is wrong with my arguments? Are there some direct references for the equivalence conclusion?

The thing you get wrong is "we know that linearizability can be achieved in the asynchronous message passing system, while tolerating a minority of process crashes." We don't know that, and in fact it is wrong.

What the quote from the JACM95 paper shows is that single-writer multi-reader registers can be implemented using message passing. And only this kind of registers, or any other objects that can be implemented (given a minority of crashes) from such registers. This includes for example multi-writer multi-reader registers (MWMR).

In contrast, linearizability is not limited to objects that can be implemented using single-writer multi-reader registers. One example of such objects are those that support (atomic) Read-Modify-Write operations.

In fact as Attiya et al point out (Section 7) such objects cannot be implemented by MWMR registers precicely because they allow solving consensus (cf. Wait-free synchronization by Herlihy) and thus implementability would contradict the FLP result.


Permutation pattern matching in strings Loosely speaking, permutation pattern matching deals with problems of the following kind:

  Given permutations $\pi$ in $S_n$ and $\sigma$ in $S_m$, with $m\leq n$, does $\pi$ contain a subsequence $\tau$ of length $m$ whose elements are ordered according to $\sigma$?

For example, if $\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$ and $\sigma=\langle 2\ 1\ 3\rangle$, then the subsequence $3\ 1\ 4$ matches $\sigma$. As you can see, we're not looking here for an exact match, but rather for something that "looks like" the specified pattern.

Does anyone know whether work has been conducted on extending permutation pattern matching problems to strings? Google unfortunately did not help, since the well-known pattern matching problem on strings has nothing to do with this.

I finally managed to dig out a nice survey by Kitaev and Mansour, which gives pointers to the literature related to permutation pattern matching on  "usual"/signed/coloured permutations and words.


On the sensitivity conjecture? The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial .

  Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?

From the paper: what is actually proven is, in Theorem 1.4,
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1}
$$
which cannot be improved (it is tight for some functions). Then it is combined with the previously known result of Nisan and Szegedy [1],
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad \deg f \geq \sqrt{\frac{1}{2}\operatorname{bs} f}
\tag{2}
$$
(a separation, incidentally, you asked about a few years back). From this survey [2] (see Table 1), referencing [3], (2) cannot be improved beyond
$$
\operatorname{bs} f \gtrsim (\deg f)^{\log_3 6}
$$
where $\log_3 6 \approx 1.63$. So this avenue of using the degree as a proxy cannot give a quadratic sensitivity upper bound on the the block sensitivity.

On the other hand, it's possible that using similar techniques (i.e., interlacing eigenvalues of signed matrices) but on different objects (first and foremost, without using the degree as a proxy) may lead to sharper bounds. This is explicitly stated as open question in Huang's paper [4]:

  Perhaps one could close this [quadratic vs. quartic] gap by directly applying the spectral method to boolean functions instead of to the hypercubes.

[1] Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Comput. Complexity, 4:462–467, 1992. doi:10.1007/BF01263419

[2] Pooya Hatami, Raghav Kulkarni, and Denis Pankratov, Variations on the Sensitivity Conjecture. Theory of Computing Graduate Survey, 2011. https://theoryofcomputing.org/articles/gs004/

[3] Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Combinatorica, 15:557–565, 1995. doi:10.1007/BF01192527

[4] Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. arXiv:1907.00847, 2019.  https://arxiv.org/abs/1907.00847


Are two-qubit unitaries necessary for universal quantum computation? I was going through Fast Universal Quantum Computation with Railroad-switch Local Hamiltonians by Daniel Nagaj. In the first sentence of the fifth paragraph on the fourth page, he said,

  Two-qubit unitaries $U_t$ are necessary for universal quantum
  computation

I understand that there are universal sets of two-qubit quantum gates but does it imply that the set must always consist of two-bit gates?

I think this question is probably better suited to cs.stackexchange.com, and I hesitate to answer it. That single qubit gates are not universal was stated by Deutsch, Barenco, and Ekert in 1995.  They point out that you cannot entangle un-entangled qubits with only single qubit operators.  You can also prove this without any appeal to entanglement or states in general by showing that at least one two qubit operator, namely $CNot$, cannot be constructed by single qubit operators.

Assume single qubit operators are universal. Then there must exist some $A$ and $B$  such that $A \otimes B = CNot = (P_0 \otimes I) + (P_1 \otimes X)$.  It follows then that that $A_{00}B = I$, $A_{11}B = X$, and $A_{01}B=A_{10}B=0$. For $A_{00}B$ to be $I$, it must be the case that $B$ itself is $I$. Similarly, for $A_{11}B$ to be $X$, $B$ itself must be $X$. This is a contradiction.  So, single qubit operators are not universal as they cannot carry out at least one two qubit unitary operation, namely $CNot$.


Determine the minimum number of coin-weighings In the paper On two problems of information theory,  Erdõs and Rényi give lower bounds on the minimum number of weighings one must do to determine the number of false coins in a set of $n$ coins.

More formally:

  The false coins have a smaller weight than the right coins; the
  weights $a$ and $b < a$ of both the right and false coins are known. A
  scale is given by means of which any number $\leq n$ of coins can be
  weighed together. Thus if we select an arbitrary subset of the coins
  and put them together on the scale, then the scale shows us the total
  weight of these coins, from which it is easy to compute the number of
  false coins among those weighed. The question is what is the minimal
  number, $A(n)$ of weighings by means of which the right and false coins
  can be separated?

The trivial lower bound they initially provide is:

$n / \log_2 (n + 1)$.

This isn't hard to see why through various information-theoretic or combinatorial arguments. The problem is how to construct such sets to do these weighings? Are there algorithms that utilize a constructive proof to achieve these lower bounds without relying on randomness? Are there randomized algorithms that achieve these bounds?

I had a brief look at this paper, and it appears that the answer to your question is yes (that is - no need for randomization). Also, the Introduction section surveys previous algorithms, information theoretic lower bounds and so on.


An algorithm for getting $n$ primes Is there any way to get $n$ primes efficiently? That is, is there any polynomial algorithm for doing this? ($n$ is the cardinality.)

Re-phrasing the question:

1) Suppose that at the input level, we insert $n$. This is the number of primes we want to obtain. (any set) (So, for example, getting five number of prime. The example output would be 2,3,5,7,11)

2) Is there any algorithm that does this efficiently? What would be its complexity (based on $n$)?

Given $n$, let $M = 2n\log n$ (here $2$ is any constant larger than $1$). Put all numbers from $2$ to $M$ in a linked list. Now implement Eratosthenes sieve, by repeatedly running the following algorithm, until you get $n$ primes. Look for the first unmarked number $p$ (they all start unmarked; start looking at the previous prime), take it as a prime, and mark every integer in hops of length $p$. The running time is roughly $M + \sum_p M/p = \Theta(M\log\log M) = \Theta(n \log n \log\log n)$, where $p$ goes over the first $n$ primes. Since the $k$th prime $p_k$ is about $k\log k$, heuristically indeed
$$ \sum_{k=1}^n \frac{1}{p_k} \approx \sum_{k=2}^n \frac{1}{k\log k} \approx \int_2^n \frac{dk}{k\log k} \approx \log\log n.$$
This approximation can be proved rigorously, this is one of the results known as Mertens' theorem.

See Emil's comment below or the Wikipedia article for improvements on this algorithm.

Edit: Before Emil's comment, I suggested implementing the algorithm using a linked list, but that's a bad suggestion since you can't "hop" in a linked list, causing the runtime to be $\Omega(n^2)$.


States and Probability distributions that the 5-qubits IBM computer can produce Update (January 2018) A new very interesting paper with various experiments on the IBM machine is Five Experimental Tests on the 5-Qubit IBM Quantum Computer by Diego García-Martín, Germán Sierra.

Update (July 2017) Extended question: Of course, the question extends to the newly built IBM 16-qubits quantum computer, and the 50-qubits quantum computers that IBM, Google and various other players expect to demonstrate in the near future. A natural conjecture is that all these computers can only approximate "noise-stable" pure states.  namely pure states that are stable under noise operator with exponential decay of high order Pauli terms, (see e.g. this paper by Montanaro and Osborne).

Original question:

IBM has recently built a 5-qubits quantum computers based on superconducting qubits. It is even possible to make experiments over the cloud.

The space of pure states for 5 qubits is the unit sphere in the 32-dimensional space over the complex number. When you measure the state of the computer you get a probability distribution on strings of 5 bits.

Give a "map" of the probability distributions and of the actual states that the IBM quantum computer can reach.

Of course, the boundary between what can be reached and what is beyond reach is of special interest. And also the case of 3 and 4 qubits.

My question is motivated by this comment over Lipton abd Reagan's blog by Alexander Vlasov.

I would expect that distributions that can actually be reached are characterized by "noise stability" which is equivalent to "low degree Fourier-type" expansion. The relevant "noise" here is independent depolarizing noise. The relevant "Fourier expansion" might be the one described by Ashley Montanaro and Tobias J. Osborne in the paper quantum Boolean function.

Vlasov referred to the paper by Daniel Alsina and  José Ignacio Latorre Experimental test of Mermin inequalities on a 5-qubit quantum computer. A sentence from the abstract reads "The experimental results obtained using the quantum computer show violation of all Mermin inequalitites, with a clear degradation of the results in the 5 qubit case."

Update: Andrew Morgan suggests in the comment below that the proposal for the threshold might be too naive. A specific question inspired by Andrew's comment is:

Can we well approximate with the IBM machine the state

$$\frac 14 |11111\rangle+\frac 14 |11100\rangle+ \frac 14 |11010\rangle+\frac 14 |11001\rangle+
\frac 14 |10110\rangle+\frac 14 |10101\rangle+ \frac 14 |01110\rangle+\frac 14 |01101\rangle+
\frac 14 |10011\rangle+\frac 14 |01011\rangle+ \frac 14 |00111\rangle+\frac 14 |10000\rangle+
\frac 14 |01000\rangle+\frac 14 |00100\rangle+ \frac 14 |00010\rangle+\frac 14 |00001\rangle.$$
(Superposition of the computational basis elements with an odd numbers of 1's)

(Later update: In view of Peter Shor's comment below I suppose we need to look more carefully for "noise-sensitive" states that we would like to explore.)

Also of interest are the states $$\frac {1}{\sqrt {5}} |10000\rangle +
\frac {1}{\sqrt {5}} |01000\rangle +\frac {1}{\sqrt {5}} |00100\rangle + \frac {1}{\sqrt {5}} |00010\rangle +\frac {1}{\sqrt {5}} |00001\rangle $$ and the superposition of all basis elements with two 1's. (If somebody reading this question actually tried to program the IBM 5-qubit computers I'd love to hear about it.)

I just ran the first state you suggest (i.e. the GHZ state with negative phase in the Hadamard basis). Basically what I did was to write a circuit which creates that state, apply one of 5 stabilizer generators (XIXII,IXXII,IIXXI,IIXIX or -ZZZZZ) and then inverted the creation process. The circuit is shown below for the -ZZZZZ stabilizer.

There seems to be problem with the calibration or something, since I am seeing a bit flip occurring on the first qubit with roughly probability 2/3 that should not happen. The expected result should be 00000 in all cases, however 10000 seems to be twice as likely in almost all cases (prob ~0.1 vs ~0.2 over 1024 runs for each stabilizer generator).

Below are the probabilities of obtaining 00000 for each stabilizer generator over 1024 runs each:
    XIXII:0.10840
    IXXII:0.15625
    IIXXI:0.11621
    IIXIX:0.10645
    ZZZZZ:0.09375

And the probabilities of obtaining 10000 for each stabilizer generator:
    XIXII:0.21777
    IXXII:0.21875
    IIXXI:0.17871
    IIXIX:0.14648
    ZZZZZ:0.19726


Avoiding overflow in finding a solution to $ax + by = c$ Can anyone come up with a nice way of computing a solution to the linear diophantine equation $ax + by = c$ where $a,b,c \in \mathbb{Z}$ and $\gcd(a,b) \mid c$, such that all the calculations are carried out without any of the intermediate results exceeding $\max\{|a|, |b|, |c|\}$ in absolute value?

I.e. if $a,b,c$ are 64-bit integers, all the calculations should be done using 64-bit integers only.

The standard method is of course to use Euclidean algorithm to first find a solution to $ax + by = \gcd(a,b)$ and then multiplying $x$ and $y$ by $\frac{c}{\gcd(a,b)}$. The Euclidean algorithm is fine, but this last multiplication might go out of range.

One way to solve this might be through an application of the Chinese remainder theorem and some kind of Hensel lifting.
Let's fix a constant $\alpha$ with the property that $2^\alpha 3^\alpha 5^\alpha > 2^{129}$ and $5^\alpha < 2^{64}$.  For instance, $\alpha=27$ would work fine.
Suppose $ax+by=c$ holds modulo $2^\alpha$, modulo $3^\alpha$, and modulo $5^\alpha$, i.e., $ax+by \equiv c \pmod{q}$ for $q=2^\alpha$, $q=3^\alpha$, and $q=5^\alpha$.  Then by the Chinese remainder theorem, it follows that $ax+by=c$ holds in the integers.  So, our goal will be to find $x,y$ that satisfy this equation modulo $2^\alpha$, modulo $3^\alpha$, and modulo $5^\alpha$.
Here are some observations that will help us find a solution that works modulo each of $2^\alpha$, $3^\alpha$, and $5^\alpha$:

Given a solution that is valid modulo $2^i$, $3^i$, and $5^i$, it is easy to find a solution that is valid modulo $2^{i+1}$, $3^{i+1}$, and $5^{i+1}$.  Here is how.  Given $(x,y)$ such that $ax+by \equiv c \pmod{q}$ (for $q\in \{2^i,3^i,5^i\}$), we consider the 3481 pairs $(x',y')$ such that $x' \in \{x,x+ d \cdot 2^i 3^i 5^i : |d| < 30, d \in \mathbb{Z}\}$ and $y' \in \{y,y+ d \cdot 2^i 3^i 5^i : |d| < 30, d \in \mathbb{Z}\}$.
One of these pairs will satisfy $ax+by \equiv c \pmod{q}$ (for $q\in \{2^{i+1}, 3^{i+1}, 5^{i+1}\}$) and will avoid overflow in $x',y'$ (i.e., we will have $0 \le x',y' < 2^{64}$).  So, you can check all 3481 candidates and find the one that you wanted.  Identifying the one you wanted is easy.  Given a candidate, it is easy to check for overflow and immediately rule out any $x',y'$ that trigger overflow or underflow in the expressions $x+ d \cdot 2^i 3^i 5^i,y+ d \cdot 2^i 3^ i5^i$.  Also, you can check whether $ax+by=c$ holds modulo $2^{i+1}$, $3^{i+1}$, and $5^{i+1}$ separately in 64-bit arithmetic without overflow, as long as each of $2^{i+1},3^{i+1},5^{i+1}$ is at most $2^{64}$.

It is also easy to find a solution that is valid modulo $2^0 3^0 5^0$: simply take $x=0,y=0$.

Given all of this background, we can now use induction to find a solution.  We start by forming a solution that works for $i=0$.  At each step, we increment $i$, until we reach $i=\alpha$.  Each step can be done in 64-bit arithmetic semi-efficiently (with a few thousand basic arithmetical operations), so the whole computation should be semi-efficient.

I feel like there ought to be some way to work modulo $2^i$, $3^j$, and $5^k$, and at each step separately increment either $i$, $j$, or $k$, but I haven't worked out the exact details of how to do that yet.  If you can make that work, the resulting scheme would be significantly more efficient.


Small graph with gap between chromatic and vector chromatic number? I’m looking for a small graph $G$ whose vector chromatic number is smaller than the chromatic number, $\chi_v(G)<\chi(G)$.

($G$ has vector chromatic number $q$ if there is an assignment $x\colon V \rightarrow \mathbf R^d$, where intuitively the vectors associated with neighbouring vertices are far apart. The requirement is $\langle x(v), x(w)\rangle \leq -1/(q-1)$. For example, for $q=3$, the vertices of a triangle suffice.)

A graph’s vector chromatic number is no larger than the chromatic number: $\chi_v(G)\leq \chi(G)$. Examples are known of graphs with $\chi_v(G)=3$ $\chi(G)=n^\delta$. (The original paper by Karger, Motwani, Sudan [JACM, 45:246-265] (manuscript) suggests generalised Kneser graphs, a more recent paper uses a construction based on random unit vectors.)

I think I have an example graph $K$ with $\chi_v(K)=4$ and $\chi(K)=8$ (based on computer calculation). This graph has 20 vertices and 90 edges.

Is there a smaller example? A tempting avenue would be to provide a concrete vector 3-colouring of the Chvatal or Grötzsch graph, if such a beast exists.

($\chi_v$ need not be an integer, but it would be nice. Update: As pointed out below, the nonintegral case is indeed easy. Thanks.)

Update: Grötzsch and Chvátal

I couldn’t resist thinking about vector 3-colouring the Chvátal and Grötzsch graphs.

The Grötsch graph can be vector 3-coloured as follows: Put the degree five node on the North pole. The 5 degree-4 nodes are evenly placed on the same latitude, around 77 degrees from North: imagine a pentragram painted on Earth’s northern hemisphere. The remaining 5 nodes (of degree 3) end up on the Southern hemisphere, around 135 degree from North. The have the same longitude as the 5 others. (I’ll upload a drawing when I have one, but it’s harder to draw geodesic lines in TikZ than I thought.)

According to an SDP solver, Chvátal also admits a vector 3-colouring, but the output is just a bunch of vectors in 5 dimensions that I have difficulties interpreting.

(A third attempt failed: Inspired by Yury’s construction, take the 5-cycle and add an apex vertex adjacent to all the others. This graph has chromatic number 4. But according to my solver it is not vector 3-colourable.)

I make my comment an answer.
If we don't require that $\chi_v(G)$ is an integer then the smallest example is $G=C_5$ (a cycle on 5 vertices):
$$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$

It's not hard to transform this example to an example where $\chi_v(G)$ is integer. Let $G_1$ be a union of two 5-cycles $C_5^{(1)}$ and $C_5^{(2)}$ in which every vertex from $C_5^{(1)}$ is connected to every vertex in $C_5^{(2)}$. Let $G_2=K_5$. Finally, let $G$ be the union of $G_1$ and $G_2$. Then
\begin{align*}
\chi(G) &= \max(\chi(G_1), \chi(G_2)) = \chi(G_1) = 6.\\
\chi_v(G) &= \max(\chi_v(G_1), \chi_v(G_2)) = \max(2\cdot \sqrt{5}, 5) = 5.
\end{align*}


Functional Completeness of 3-valued logic In the context of some recent work, we have been defining a language based on a three-valued logic à la Kleene, where $1$ stands for true, $0$ for false, and $\bot$ for error or don't-know. In order to show that our language was expressive, we wanted to prove that we could build a set of operators functionally complete.

It was quite hard to find existing results in the literature. We found one paper written in 1962 by Jobe, which states the following theorem:

  Jobe 1962 Theorem Paper (restricted access).

  The three-valued logic $E$ expressed over the set $\{1, 2, 3\}$ and defined by the operators $\bullet, E_1$ and $E_2$, given below, is functionally complete.

  $$
    \begin{array}{c|ccc|c|c}
        ~\bullet~ & ~3~ & ~2~ & ~1~ & ~E_1~ & ~E_2~ \\ \hline
        3     & 3 & 2 & 1 & 3   & 1 \\
        2     & 2 & 2 & 1 & 1   & 2 \\
        1     & 1 & 1 & 1 & 2   & 3
    \end{array}
$$

In our paper, we have used this result by showing a correspondance between our operators and those defined by Jobe (roughly speaking, we use the strong conjunction, the negation, and an operator that transforms don't-know in false).

My main concern is that I'm actually not able to understand the proof of functional completeness of Jobe, and we haven't been able to find any other result (positive or negative) after this date, which is somehow a bit surprising.

So my question is the following: are there some more known results about the functional completeness of 3-valued logics? Any info in this direction would be helpful.

Chapters 5 and 6 of the book [Function algebras on finite sets, Dietlinde Lau, 2006] contain an in depth treatment of functional completeness in many-valued logic (including proofs). In summary: Rosenbergs [1965, 1970] characterization of maximal clones (also called precomplete clones) give a criterion for functional completeness in k-valued logic for any k.

For the special case of 3-valued logic such a characterization (consisting of 18 maximal/precomplete classes) was given by Jablonskij already in 1954. Hence, in order to verify that your set of 3-valued "operators" are functionally complete, it is enough to check that they don't fall into any of the 18 precomplete classes.


complexity of greatest common divisor (gcd) Consider the following counting problem (or the associated decision problem): Given two positive integers encoded in binary, compute their greatest common divisor (gcd). What is the smallest complexity class this problem is contained in? Can you provide a reference?

In this question I am not primarily interested in asymptotic bounds on the running time, but rather in complexity classes. Is the problem in AC? Can it be proven not to lie in AC0? What are other complexity classes inside P that are of relevance here?

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

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

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


Can we get a sorted list from a sorted matrix in $O(n^2)$ I'm confused. I want to prove that that the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order is $\Omega(n^2\log n)$.
I proceed by assuming that it can be done faster than $n^2\log n$ and try to violate the $\log(m!)$
lower bound for comparisons needed to sort m elements.
I have two conflicting answers:

we can get a sorted list of the $n^2$ elements from the sorted matrix in $O(n^2)$
https://math.stackexchange.com/questions/298191/lower-bound-for-matrix-sorting/298199?iemail=1#298199
you can't get a sorted list from the matrix faster than $Ω(n^2\log(n))$
https://stackoverflow.com/questions/4279524/how-to-sort-a-m-x-n-matrix-which-has-all-its-m-rows-sorted-and-n-columns-sorted

Which one is right?

The lower bound is correct (2) - you can not do this better than $\Omega(n^2 \log n)$ and (1) is of course wrong. Lets us first define what is a sorted matrix - it is a matrix where the elements in each row and column are sorted in increasing order.

It is now easy to verify that each diagonal might contains elements that are in any arbitrary order - you just need to make them sufficiently large. In particular, sorting the matrix implies sorting each one of these diagonals. The $i$th diagonal has $i$ entries, and as such $i!$ possible ordering. As such, a sorted matrix could define at least $X = \prod_{i=1}^n i!$  different orderings. It is now easy to verify that $\log_2 X = \Omega(n^2 \log n)$,  implying that in the comparison model (and as Jeff points out below, in any binary decision tree model) at least this is a lower bound on the sorting time.


Encoding sets of permutations with a generating set and a set of excluded elements Polynomial-time algorithms are known for finding generating sets of permutation groups, which is interesting since we can then represent those groups succinctly without giving up on polynomial-time algorithms for answering many interesting questions related to these groups.

However, we may sometimes be interested in a set $R$ of permutations that does not form a group, so that set would be represented by $R=\langle S\rangle \setminus T$, where $\langle S\rangle$ is the group generated by a set $S$ of generators and $T$ is a set of permutations that are not in $R$, instead of just $\langle S\rangle$.

Has any work been done on computing such an encoding in the form of a pair $\{S,T\}$, possibly with the additional, natural goal of minimising $|S|+|T|$?

If you are storing random permutations with probability ${1\over2}$ then you are going to need $log_{2}(n!)$ bits per permutation, Kolmogorov complexity dictates it.

If the distribution is non-random it depends.

To understand the state space it might help to look at http://oeis.org/A186202 , the size of any min dominating set over $S_{n}$ using a monogenic inclusion relation between permutations (ignoring the identity which is in all subgroups).

You can encode the relevant prime order permutations in $log_{2}( OEIS\_A186202(n) )$ bits each. That will give you some savings over the usual $log_{2}(n!)$ needed for a random permuation.


graph coloring with 3 colors I'm searching for an algorithm that can calculate a suboptimal solution for:

color a graph with 3 colors
some vertices already have a color and can't be changed
the edges have values and the algorithm has to search for a solution where the sum of all the values of all the edges with vertices with the same color is smallest

this is for a practical problem:
a wireless network with wireless accesspoints (vertices)
you can ask the accespoints what neighbors they see and with what signal strength and i can create a graph out of that information
some accespoints are not part of the network, and already have a channel assigned

and accespoint can only have 3 channels that don't interfere (1,6,11) these are the 3 colors

does anyone know a good algorithm  that is powerful enough to solve this?

i heard this was used somewhere in cpu theory, where registers are already filled in (colored)
and you need to assign registers to some programs (colors)
but i can't find it

The variant of the problem you're referring to is very close to a problem called the $0$-extension problem: it's a special case of a class of problems called 'metric labelling'. In this class of problems, you're given a weighted graph $G = (V, E, w)$, a set of labels $L$, an assignment cost of labels to vertices $c : V \times L \rightarrow R$, and a "discrepancy cost" $d : L \times L \rightarrow R$. The goal is to assign labels to vertices so as to minimize the sum of the assignment costs and the discrepancy cost for the labels on an edge (weighted by the edge weight). In short, find a labelling $l : V \rightarrow L$ to minimize

$$ \sum_{i \in V} c(i, l(i)) + \sum_{(u,v) \in E} d(l(u), l(v)) \cdot w((u,v))$$

In your problem, the assignment cost is zero, and the label "discrepancy" function is the delta function on labels.

One complicating factor here is that the metric labelling family of problems, the label discrepancy is usually a distance, whereas here it's a similarity measure.