Can affine lambda calculus solve every problem in P? In Advanced Topics in Types and Programming Languages it is mentioned, in the chapter on sub-structural type systems, that a "carefully crafted" affine lambda calculus with a recursion combinator for lists can only type terms which have polynomial running time (it does not present the proof due to complexity). This would be super interesting if we could also solve every problem in P. I could try to find a solution to a P-complete problem using the calculus presented by I'm not sure this would actually prove anything. It doesn't seem to me to mean that it can preform all the reductions necessary to use a solution to a P-complete problem (although it sure does seem likely).

If an affine lambda calculus is not known to be able to solve exactly the problems in P, is there any known calculus that can solve exactly the problems in P?

Edit: my guess in the first paragraph below is wrong!  Ugo Dal Lago pointed out to me a later paper by Martin Hofmann (appeared in POPL 2002), of which I was unaware, showing (as a corollary of more general results) that the system from the ATTPL book is in fact complete for $\mathsf P$ (in spite of not being able to compute every function in $\mathsf{FP}$).  So, to my surprise, the answer to the main question is yes.

Concerning the system you are referring to (from the ATTPL book), I am pretty sure it cannot decide every language in $\mathsf P$.  It certainly cannot compute every function in $\mathsf{FP}$: as mentioned in the notes of that chapter, that system is taken from Martin Hofmann's LICS 1999 paper ("Linear types and non-size-increasing polynomial time computation"), in which it is shown that the representable functions are polytime and non-size-increasing, which excludes lots of polytime functions.  It also seems to give a serious limitation on the size of the tape of the Turing machines you can simulate in that language.  In the paper, Hofmann shows that you can encode linear space computation; my guess is that you will not be able to do much more, i.e., the class corresponding to that system is roughly the problems solvable simultaneously in polytime and linear space.

Concerning your second question, there are several $\lambda$-calculi that can solve exactly the problems in $\mathsf P$. Some of them are mentioned in the notes of the ATTPL chapter you are referring to (Sect. 1.6): Leivant's tiered $\lambda$-calculus (see his POPL 1993 paper, or the paper with Jean-Yves Marion "Lambda Calculus Characterizations of Poly-Time", Fundamenta Informaticae 19(1/2):167-184, 1993), which is related to Bellantoni and Cook's characterization of $\mathsf{FP}$; and the $\lambda$-calculi derived from Girard's light linear logic (Information and Computation, 143:175–204, 1998) or from Lafont's soft linear logic (Theoretical Computer Science 318(1-2):163-180, 2004). Type systems arising from these latter two logical systems and ensuring polytime termination (while still enjoying completeness) may be found in:

Patrick Baillot, Kazushige Terui. Light types for polynomial time computation in lambda calculus. Information and Computation 207(1):41-62, 2009.

Marco Gaboardi, Simona Ronchi Della Rocca. From light logics to type assignments: a case study. Logic Journal of the IGPL 17(5):499-530, 2009.

You'll find lots of other references in those two papers.

To conclude, let me expand on Neel Krishnaswami's remark.  The situation is a bit subtle.  All of the above $\lambda$-calculi may be seen as restrictions of more general calculi, in which you can compute much more than just the polytime functions, say for example system F.  In other words, you define a property $\Phi$ of system F programs $P:\texttt{string}\rightarrow\texttt{bool}$ such that:

soundness: $\Phi(P)$ implies that the language decided by $P$ is in $\mathsf P$;

completeness: for every $L\in\mathsf P$, there is a system F program $P$ deciding $L$ such that $\Phi(P)$.

The interest is that the property expressed by $\Phi$ is purely syntactic and, in particular, decidable.  Therefore, completeness can only hold in an extensional sense: if $L$ is your favorite language in $\mathsf P$ and if $P$ is your favorite algorithm for deciding $L$ expressed in system F, it may be that $\Phi(P)$ does not hold. All you know is that there is some other system F program $P'$ deciding $L$ and such that $\Phi(P')$ holds.  Unfortunately, it may happen that $P'$ is much more contrived than your $P$.  Indeed, completeness is proved by encoding polynomially-clocked Turing machines as system F terms satisfying $\Phi$. Therefore, the only guaranteed way of solving $L$ using your favorite algorithm is implementing that algorithm on a Turing machine and then translating it in system F using the encoding given in the completeness proof (your own encoding may not work!).  Not exactly the most elegant solution in terms of programming...  Of course, in many cases the "natural" program $P$ does satisfy $\Phi$.  However, in many other cases it does not: in the LICS 1999 paper mentioned above, Hofmann gives insertion sort as an example.

Intentionally complete type systems, which are able to type exactly the polytime programs of the wider language (system F in my example above) do exist.  Of course, they are undecidable in general.  See

Ugo Dal Lago, Marco Gaboardi. Linear Dependent Types and Relative Completeness. Logical Methods in Computer Science 8(4), 2011.


Approximating transitive reduction of a transitive closure of a dag Let's suppose a transitive closure $G^+$ of a dag $G$ is given and we want to compute an approximation of the transitive reduction $G^-$ such that the full transitive reduction is a subgraph of the approximation.

My idea is to compute a topological sort $TS$ of the dag and then for each edge $u \rightarrow v$ look at ~10 nodes $w$ such that $TS(w) > TS(v)$, $u \rightarrow w$ and $TS(w)$ are as large as possible. If $w \rightarrow v$ then edge $u \rightarrow v$ is redundant ($u \rightarrow w \rightarrow v$) and can be removed.

An implementation of this algorithm can be found here. The algorithm has complexity $O(m + n)$ and from my experiments the number of edges in the approximation is 3-5 times larger than in the full transitive reduction.

I have a couple of questions:

Can I prove any upper bound for the number of edges in the approximation?
How can I improve the algorithm (except looking at more $w$-s) in terms of time and/or number of edges left?

Due to [Aho, Garey, and Ullman, The transitive reduction of a directed graph, 1972]; $G^t = G - GG^+$, where $G^t$ is the transitive reduction of $G$. In this particular case, $G = G^+$. So, we can conclude $G^t = G - G^2$. Although this result does not lead to a linear non-approximate algorithm, I hope such an observation would be helpful in this context.


Data processing inequality for interaction information The interaction information is defined as $I(X;Y)-I(X;Y|Z)$. Let $Z-(X, Y) -(X', Y')$  be a Markov chain. Is there an inequality similar to the data processing inequality, relating $I(X';Y')-I(X';Y'|Z)$ to $I(X;Y)-I(X;Y|Z)$? Thanks in advance.

Since the interaction information can be either negative or positive, and a Markov chain that erases everything can be used to take the interaction information to $0$, without further conditions the answer is "no".


Survey on Erdős-Pósa? Does anyone know of any good surveys on Erdős-Pósa?
I am particularly interested in what are the latest results for the bounding function for directed and even cycles in planar and minor free graphs down to the constant factor.

I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written:
Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-11828
The first chapter gives a summary of the problem, known proof techniques and provides references to recent research. I am not an expert on this problem and only skimmed the first chapter briefly, so YMMV.


Term for a "rooted" directional graph? Consider an acyclic directed graph in which a traversal from any node in the graph must eventually end at some terminal node R.  Borrowing from tree-based vocabulary, I would tend call this the "root" of the graph, since all traversals eventually terminate there.  However, the term "rooted graph" seems to already be in use for something else.

Is there a term I can use to describe this property?  The best way I can describe the graph at present is a "multi-parented directed tree" -- all nodes point toward the root, but, unlike a directed tree, nodes may have more than one parent. I don't like this terminology, though, as it seems like an abuse of the term "tree".

I considered "hierarchical graph", but a node can have more than one outgoing vertex, so I think that may disqualify it from being hierarchical.

I don't know if these graphs have a common name. But I think, one would call vertices with no outgoing edge rather a sink than a root.

This paper studies acyclic orientations of grid graphs. They call an orientation, which would correspond to the graphs you consider, acyclic orientations with a unique sink.


Choose term of coproduct type We work in homotopy type theory. Denote the propositional truncation of a type $A$ by $\|A\|$ and the function type between types $A$ and $B$ by $A \to B$.
Can you construct a term of the following type:
$$
\prod_{A:U_0}\prod_{B:U_0}
(\|A\| \to A) \times (\|B\| \to B) \to (\|A + B\| \to A + B)
\quad?
$$

We are going to show that in MLTT with propositional truncation the type
$$\textstyle
\prod_{A:U_0}\prod_{B:U_0}
(\|A\| \to A) \times (\|B\| \to B) \to (\|A + B\| \to A + B)
$$
has no inhabitants. Assume it did.
We shall work in a specific model of MLTT with propositional truncation, namely  assemblies over number realizability. It is not too important what this model is precisely, except for the following facts:

there is an object of reals $\mathbb{R}$ in which
$\Pi (x : \mathbb{R}) \; \|(x < 1) + (x > 0)\|$, and
every map $\mathbb{R} \to \mathsf{bool}$ is constant.

Hoever, using the above type, we may inhabit
$$\Pi(x : \mathbb{R}) \; \|x < 1\| + \|x > 0\|,$$
contradicting the fact that every map $\mathbb{R} \to \mathsf{bool}$ is constant.
To do so, consider any $x : \mathbb{R}$ and instantiate $A = \|x < 1\|$ and $B = \|x > 1\|$ (and use the fact that $<$ maps into propositions).


Technical question about random walks (My original question still has not been answered. I have added further clarifications.)

When analyzing random walks (on undirected graphs) by viewing the random walk as a Markov chain, we require the graph to be non-bipartite so that the fundamental theorem of Markov chains applies.

What happens if the graph $G$ is instead bipartite? I am specifically interested in the hitting time $h_{i,j}$, where there is an edge between $i$ and $j$ in $G$. Say the bipartite graph $G$ has $m$ edges. We can add a self-loop to an arbitrary vertex in the graph to make the resulting graph $G'$ non-bipartite; applying the fundamental theorem of Markov chains to $G'$ we then get that $h_{i,j} < 2m+1$ in $G'$, and this is clearly also an upper bound for $h_{i,j}$ in $G$.

Question: Is it true that the stronger claim $h_{i,j} < 2m$ holds in $G$? (It have seen this claimed in analyses of the random walk algorithm for 2SAT.) Or do we really have to go through this extra step of adding the self-loop?

This answer proved something different from what the questioner was actually interested in. Leaving it here so others won't repeat the same mistake.

  In most cases, one can formally justify the intuitive notion that
  "self loops can only slow down the walk" by a coupling argument.  In
  this case for example, one can couple the walk with the self loops
  (let's call it $A$) and the one without the self loops (let's call
  that $B$) so that $A$ takes the same steps as $B$, but delayed in
  time.  This can for example be done as follows:  Suppose that $B$
  starts at $u = x_0$ and goes through $x_i: i =1,2,\ldots,k$. Now, we
  implement $A$ as follows: $A$ also goes through the same vertices as
  $B$, except that vertex $x_i$, it waits for Geometric($p_i$) time
  where $p_i$ is the self loop probability at $x_i$.  Note that this is
  a correct implementation of $A$ (all transition probabilities are
  correct), and the form of the coupling ensures that $A$ never reaches
  any vertex before $B$, that is, we have coupled $H_t^A$ and $H_t^B$
  (the random hitting times in the two walks) so that $H_t^A \geq H_t^B$
  with probability $1$. Thus, the inequality for the expected hitting
  time follows.


Perfect Matching with ``set-over-like" constraints? Problem Description:

Let k and n be some natural numbers. We are given a complete bipartite graph G where each side of G has n vertices. G is edge-labeled with labels being subsets of {1,...,k}. We are looking for a perfect matching G' such that the union of sets labeling edges of G' equals {1,...,k}.

The problem is clearly NP-hard in k, but is it also NP-hard in n? I.e. can one achieve an algorithm that is polynomial in n while possibly being exponential in k (maybe via adaptation of the Dynamic Programming algorithm for set cover..)?

Many thanks,
Amir

The problem can be solved in $O(n^k \, \text{poly}(n))$ time, so it's not "NP-hard in $n$" unless P=NP.

Here's one simple algorithm.  Enumerate all subsets $E'$ of $E$ such that $|E'|\le k$.  Check whether the union of labels of $E'$ is equal to $\{1,2,\dots,k\}$; if not, move on to the next candidate for $E'$.  Then, check whether there's a perfect matching of $G$ that includes all edges of $E'$.  This can be done as follows: check that no pair of edges in $E'$ meets in a common vertex; let $V^*$ be the set of vertices that don't touch any edge of $E'$, and $E^*$ the set of edges both of whose endpoints are in $V^*$; then check whether $G^*=(V^*,E^*)$ has a perfect matching.  If such a perfect matching exists, you have found a valid solution to your original problem.  There are $O(n^k)$ possible subsets $E'$, so the entire procedure runs in $O(n^k \, \text{poly}(n))$ time.  Correctness follows because if there is a set of edges whose labels have union equal to $\{1,2,\dots,k\}$, then there is a set of size $\le k$ with this property.


On which classes of graphs is resource constrained shortest path (RCSP) NP-hard? I'm looking to link a problem I'm working on to a known NP-hard problem.  I think I can model my problem as a resource constrained shortest path problem.  However, the structure of my graph is not completely arbitrary.  Thus, it will be useful to know when RCSP becomes hard.  Is it hard for a DAG, for a planar DAG, for a DAG with bounded degree?  Any help would be greatly appreciated!

I don't know if you're still interested in this (old) question, and if I understood well the resource constraints you gave in the comment; however it seems that your problem (which is slightly different from usual RCSP problems) is NP-complete for planar (undirected or directed or directed acyclic) graphs of max-degree 3.

The easy reduction is from 3-SAT. Given a formula $\varphi$ with $n$ variables $x_1,...x_n$ and $m$ clauses $C_1,...C_m$:

add a resource constraint set $M_k^+$ with two vertices for each positive literal $x_k$ in $\varphi$ and a resource constraint set $M_k^-$ with two vertices for each negative literal $\bar{x}_k$ in $\varphi$;
start building a graph from a source node $s$ and for each variable $x_i$ split the path in two lines: the upper one traverses one vertex of all the $M_k^-$ that correspond to a negative literal $\bar{x}_k$; the lower one traverses one vertex of all the $M_k^+$  that correspond to a positive literal $x_k$;
then for each $C_j$ split the path in 3 lines that traverse in parallel the 3 vertices corresponding to the literals of $C_j$ and that are picked from the corresponding $M_k^+$ or $M_k^-$;
finally add a sink node $t$.

A path from $s$ to $t$ exists if and only if the original formula is satisfiable (i.e.  without loss of generality you can ask for a path of length $\leq |V|$).

Informally when traversing the variable section $x_i$, if you pick the upper line (true assignment) then you must "use" one of the vertices of all the $M_k^-$ resource constraint sets that also contain a vertex that can be used later to traverse (satisfy) a clause containing $\bar{x}_i$. If you pick the lower line (false assignment) then you must "use" one of the vertices of all the $M_k^+$ resource constraint sets that also contain a vertex that can be used later to traverse (satisfy) a clause containing $x_i$. When traversing each clause at least one of the three vertices must be contained in a $M_k$ that has not be "used" yet (i.e. at least one of them can be used to satisfy the clause).

The following figure should make the reduction clearer. The resource constraint sets $M_k$ are represented with distinct colors (and for every color there are exactly 2 vertices).

$C_1 = x_1 \lor \bar{x}_2 \lor x_3$
$C_2 = x_2 \lor \bar{x}_3 \lor x_4$
$C_3 = \bar{x}_1 \lor x_3 \lor \bar{x}_2$

You can also easily make the graph directed, acyclic and bipartite. Let me know if you need further details (or if I completely misunderstood the problem :-).

As noted by Saaed the problem is fixed-parameter tractable with respect to $k$ (just consider all possible subsets of constrained nodes and for each combination run the shortest path algorithm).


Pruning a strongly connected digraph Given a strongly connected digraph G with weighted edges, I would like to identify edges that are provably not part of any minimal strongly connected subgraph (MSCS) of G.

One method for finding such edges is a modified Floyd-Warshall algorithm. Using the Floyd-Warshall algorithm, one can identify which edges are never the best option for going from vertex i to j. These nodes can't be part of a MSCS because it's better to replace them with two or more other edges.

The Floyd-Warshall pruning technique works quite well when edge weights vary significantly, but very poorly when edge weights are similar but large in magnitude.

Do you know any effective pruning methods for large, similar edge weights? Is this problem equivalent to a more common problem that I don't recognize? Has this sort of pruning been studied before in the literature?

We assume that edge weights are positive integers.  Given a directed graph G with edge weights, call an edge e redundant if e does not belong to any minimum-weight strongly-connected spanning subgraphs of G.

We claim that unless P=NP, there is no polynomial-time algorithm that always finds a redundant edge in a given directed graph with edge weights as long as there is one.  More precisely:

Theorem.  Given a directed graph G with edge weights, it is NP-hard to find a redundant edge in G or declare that G does not have a redundant edge.

Proof.  The key observation is that if G has a unique minimum-weight strongly-connected spanning subgraph, then you can compute that subgraph by removing the redundant edges one by one.  Therefore, it remains to show that the uniqueness does not make the minimum-weight strongly-connected spanning subgraph problem any easier, but this is proved by the next Lemma.  QED.

Lemma.  Given a directed graph G with edge weights, it is NP-hard to compute the weight of the minimum-weight strongly-connected spanning subgraph of G even under the promise that G has a unique minimum-weight strongly-connected spanning subgraph.

Proof.  As you know, the problem without the promise is NP-hard (even for the unit-weight case) by a reduction from the Hamiltonian circuit problem.  We reduce the problem without the promise to the problem with the promise.

Let G be a directed graph with edge weights.  Label the edges of G by e0, e1, …, em−1, where m is the number of edges in G.  Let wi be the given weight of the edge ei.  Let the new weight w′i=2mwi+2i.  Then it is easy to verify that G with the new weights has a unique minimum-weight strongly-connected spanning subgraph.  It is also easy to verify that the minimum weight W of a strongly-connected spanning subgraph in G with the original weights can be computed from the minimum weight W′ in G with the new weights as W=⌊W′/2m⌋.  QED.


Are there strongly normalizing lambda terms that cannot be given a System F type? I know that all well-typed System F terms are strongly normalizing, but is the converse true as well? In other words, does System F typeability precisely characterize program termination? (And if so, how to prove it?) Or are there lambda terms that are strongly normalizing but cannot be given a System F type?
A System F interpreter cannot be implemented in System F. On the other hand, a System F interpreter can be implemented in untyped lambda calculus, but that's not enough. Can a strongly normalizing System F interpreter be implemented in untyped lambda calculus? If yes, this answers our question positively, but I am not sure about it.

As you found out yourself, the answer to your question is yes.  You found a rather convoluted example, a much simpler example is the following:
$$(\lambda zy.y(zI)(zK))(\lambda x.xx)$$
where $I$ and $K$ are the identity and first-projection combinators.  This may be found at p. 204 of Sørensen and Urzyczyn's Lectures on the Curry-Howard Isomoprphism.  They attribute it to Ronchi Della Rocca and Giannini, and also give a seemingly even simpler example, which is $c_2c_2K$, where $c_2$ is, I believe, the Church integer 2 (I'm not sure about their notation so I may be wrong).


Algorithm: Find the first k longest substrings between two similar strings Consider two strings, S and T. Find the first k longest common non-overlapping substrings of S and T.

Depending on your application (and assuming I have correctly understood your general aim), a standard practical method will be to find all maximal repeated substrings between the two strings, number those substrings and then compute the longest increasing subsequence.  This is exactly what the bioinformatics tool Reputer does. See http://bibiserv.techfak.uni-bielefeld.de/reputer/ and
http://bioinformatics.oxfordjournals.org/content/15/5/426 for an original reference.

This is is slightly super-linear time overall as you have to compute the longest increasing subsquence (see e.g. http://en.wikipedia.org/wiki/Longest_increasing_subsequence ).


Why is the circuit class AC0 unavoidable? Take AC0.
What is a natural thought process that leads to the definition of AC0?
Does this class arise intrinsically anywhere?

My problem is that in the case of unbounded fan-in, AND and OR gates behave very differently. Why do we take these gates along with NOT to define a circuit class?

The class $\mathbf{AC}^0$ arises very naturally as the circuit characterization of problems definable by formulas of first-order logic. A language over the alphabet $\{ 0,1 \}$ is in $\mathbf{AC}^0$ if and only if it is definable in first-order logic in the language of word structures.
See e.g. Immerman's book for more details.

$\mathbf{AC}^0$ also arises naturally when studying theories of bounded arithmetic. The simplest of these theories $\mathbf{V}_0$ corresponds precisely to $\mathbf{AC}^0$ in that the functions and relations definable in the theory are exactly those in uniform $\mathbf{AC}^0$. See the book of Cook and Nguyen for more details.


Subclasses or characterizations of modular or pseudo-modular planar graphs We say that a graph G is modular if for every three vertices x,y,z there exists a vertex w that lies on a shortest path between every two of x, y, z. Pseudo-modular (or "3-Helly") graphs are defined in the following link: http://www.graphclasses.org/classes/gc_203.html.

I am wondering if there are interesting examples of planar graphs which are modular or pseudo-modular, or an interesting characterization of planar graphs which have these properties.

The median graphs are a subclass of modular graphs with almost the same definition but where the vertex w is always unique. The squaregraphs (plane graphs in which all bounded faces are quadrilaterals and all vertices either have degree 4 or belong to the unbounded face) form a natural and interesting subclass of the planar median graphs. I believe that all planar median graphs can be constructed by gluing together cubes and squaregraphs, but I don't think this result has been published.


Zero Knowledge proofs of knowledge Is there Zero Knowledge Proof of Knowledge protocol for Hash function? (If h(v)=w) without revealing v to the anyone can we prove that we know 'v')

Yes. The simplest way to understand this is to understand the zero-knowledge proof that you know a 3-coloring of a graph. 3-coloring is NP-complete, so an arbitrary hash function $h$ and target value $w$ can be represented as a graph where knowing a 3-coloring for that graph is equivalent to knowing a $v$ such that $h(v) = w$.

That isn't the most efficient way to do it; for that you'd want zk-snarks or one of the zillion similar encodings. That approach is similar but you're modeling your hash function as a modular matrix multiplication instead of a graph coloring. But the answer is yes, there is a zero-knowledge protocol for proving you know the preimage of a value for a hash function.


Is the basis of parity functions the only orthonormal basis for Boolean functions? Is there another orthonormal basis of functions for Boolean functions? Or, more specifically, besides the parity functions, is there another explicit function (which is common and has a name) that can form an orthonormal basis for Boolean functions?

If not, why not?

I don't think parities are the only orthonormal Boolean basis, for example Paley basis provides a Boolean orthonormal basis in some cases. It's natural to ask if such bases, interpreted as Boolean functions, have any interesting applications.


Is it possible to encrypt quantum states under reasonable assumptions? Is it possible to encrypt a quantum state, such that a $BQP$ attacker who does not know the secret key cannot obtain any information about the original state, but a $BQP$ decryptor with the key can recover the original state?

Assume (classical) one-way functions that are hard for quantum attackers to break exist (as is believed to be the case).

One can encrypt an n-qubit state using a 2n-bit classical secret key. The idea is to use the key to select a random Pauli operator, and apply that operator to the secret as an encryption. (The inverse operator is applied to decrypt.)

The resulting scheme is perfectly secure -- if the key is selected uniformly at random, then even an attacker who know a state entangled with the plaintext cannot distinguish the true ciphertext from an independent random state.

This observation was first made in
A Ambainis, M Mosca, A Tapp, R de Wolf. "Private quantum channels", FOCS 2000.

They also showed that 2n bits of key are necessary for encryption of entangled quantum states.

If you have a classical PRG secure against quantum distinguishers, then you can get away with a much shorter key (as short as seed length required by the generator to generate 2 n output bits).


Misunderstanding the Church-Turing thesis? My understanding of the Church-Turing thesis is the:

It puts a limit on what can be computed by any discrete and finite process.
Although still a thesis, not a theorem, if it were to be disproven, this wouldn't mean just an update to our current models of computation. It would be a paradigm shifting result for mathematics and physics in general.

Yet many discussions on the Philosophy SE (where I usually hang out) turn to the possibility of "Super-Turing" computation, and arguments in philosophy of mind question are frequently hinged on the proposition that Church-Turing is just a thesis and the there are several proposals for super-Turing computation or hypercomputation.

The mostly frequently cited source for this is the Stanford Encyclopedia of Philosophy  (SEP) article on the Church-Turing thesis.

In particular the article has a section titled "Misunderstandings of the thesis", which states the following:

  A myth seems to have arisen concerning Turing's paper of 1936, namely that he there gave a treatment of the limits of mechanism and established a fundamental result to the effect that the universal Turing machine can simulate the behaviour of any machine. The myth has passed into the philosophy of mind, generally to pernicious effect.

  [...] Turing did not show that his machines can solve any problem that can be solved "by instructions, explicitly stated rules, or procedures", nor did he prove that the universal Turing machine "can compute any function that any computer, with any architecture, can compute". He proved that his universal machine can compute any function that any Turing machine can compute; and he put forward, and advanced philosophical arguments in support of, the thesis here called Turing's thesis. But a thesis concerning the extent of effective methods -- which is to say, concerning the extent of procedures of a certain sort that a human being unaided by machinery is capable of carrying out -- carries no implication concerning the extent of the procedures that machines are capable of carrying out, even machines acting in accordance with ‘explicitly stated rules’. For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.

The above mentioned section and especially the quoted passages seem blatantly wrong to me, as if the author doesn't even get the concept of a Turing machine or what the Church-Turing thesis is. And yet, the article is constantly cited as a source by those who argue against the Church-Turing thesis, not just in the Philosophy SE, but even by relatively well known philosophers like Massimo Pigliucci. The main reasons why the article carries so much weight is that the SEP is considered a reputable source in the philosophy community, and the articles there are subject to review, and that the article's author, Jack Copeland, is an established philosopher who has published extensively on Turing and on AI.

And yet the way I see it, the article is fundamentally wrong in its presentation of the thesis, reputability of the source and the author not withstanding.

My questions:

Is my interpretation of the Church-Turing thesis correct?
How could one refute those who use that article's "Misunderstandings" section as a justification for the idea that computing beyond the Turing limit is a realistic prospect?
Is hyper computation taken seriously by mainstream computability theorists, or is it the CS equivalent of cold fusion and perpetual motion?

The fields of philosophy and CS apparently have different definitions/interpretations of the thesis. In CS, I believe it is standard/accepted to define the Church-Turing thesis as the article's "Misunderstandings" section's "Thesis M" (under the narrow/worldly view). However, the article claims that this is an incorrect definition of Church-Turing. So we simply disagree. (And let's try to avoid starting an argument with them about it ... pointless arguments are their forte, after all.)

The approach taken by philosophers is unfortunate, as the average layman is probably interested in the CS Church-Turing thesis, not the philosophy one espoused in the article. So they will cite the article while thinking it refers to our practical/reasonable definition, when it doesn't.

So my answers to your specific questions:

Yes, as far as I can tell.
I'd tell them that the article refers to a highly specialized philosophy-definition of Church-Turing. But regardless of what one calls the "true" Church-Turing thesis, the following thesis is almost universally believed among computer scientists: "Any usable machine of computation that can be built in this universe can be simulated by a Turing Machine".
If by hypercomputation you mean physically possible/realizable, then no, it's not taken seriously. But it is interesting to study hypercomputation models even if they cannot appear in the real world, and we do so all the time. For instance, we may consider a Turing Machine that has access to an oracle that solves the halting problem. This object is studied all the time in theory and is uncontroversial, but nobody believes that one can actually be built.


Is square removal easier than factoring? It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, i.e. some commonly believed hypothesis which would be violated if factoring could be reduced to square removal? But if square removal should indeed be easier than factoring (in the sense outline above), then the next question is whether it is an NP-intermediate problem (i.e. whether a polynomial time algorithm for it is known or not).

Here is a clumsy description of the square removal and factoring tasks:

Let $n\in\mathbb{N}^*$ be given in binary representation. Let $n=\prod_i p_i^{\alpha_i}$ with $p_i$ prime, $\alpha_i\in\mathbb{N}^*$, and $p_i\neq p_j$ for $i\neq j$ be the prime factorization of $n$.

For square removal, the binary representation of $m=\prod_i p_i$ is requested.
For factoring, finding (the binary representation of) a non-trivial factor of $n$ is requested, i.e. a number $q=\prod_j p_j^{\beta_j}$ with $1<q<n$, $\beta_j\in\mathbb{N}$, and $\beta_j\leq\alpha_j$.

We can show that if all $\alpha_i$ are different, then square removal and factoring of $n$ are equally hard.

It is obvious, that if we can factor $n$, we can also compute square removal of $n$.

The other direction is a bit more tricky. First compute the square removal of $n$ and let's call this $m$. From the definition it follows that $m$ divides $n$. Divide by $m$ repeatedly until we reach a number, which is not divisible by $m$, I'll call this $x$

$$x = \frac{n}{m^b}$$

Now compute $p = \frac{m}{\gcd(x, m)}$, if $p$ had more than one prime factor, those would have identical $\alpha_i$ in the original product $n$, which contradicts the assumption about all $\alpha_i$ being different, hence $p$ is a prime factor in $n$.

Knowing one prime factor in $n$ it is possible to reduce the problem to factoring a smaller $n'$, which satisfy the same criteria, so the algorithm can be repeated.

We can also show that if all $\alpha_i$ are equal, then square removal is easy. That's because $\alpha_i$ can only have logarithmic size in $n$, and every possible $\alpha_i$ can be tested by computing the $\alpha_i$th root of $n$.

However the result obtained that way will be incorrect if the $\alpha_i$ were not equal. The obtained result will be correct iff it is square free. And @joro pointed out, that no polynomial algorithm is known to decide if a number is square free.

So for some $n$ square removal and factoring is equivalent. For other $n$ square removal is easy. Telling those two cases apart appears to be hard.


Complexity of Model Enumeration in function free, equality free, First Order Logic with only Unary Predicates? This question has inspired the following two questions.
Given a first order logic language, with only unary predicates, finite number of variables, $\forall$ and $\exists$ i.e no equality and functions.

what is the complexity class of model enumeration in monadic first order logic ?
How expressive is this language, are there sentences in this language which cannot be expressed in function-free, equality free fragment of  $FO^{2}$  ?

I have asked a similar (but not the same) question here but after reading the linked question, I felt TCS-SE was probably a better choice for this question. And I did not delete it because it has an upvoted answer.

Reading the discussion below the other answer made me realize that it’s not immediately obvious what is the complexity of translation of FO sentences in this language to equivalent FO1 sentences. While the quoted fact that satisfiability of these sentences is NEXP-complete (whereas satisfiability of FO1 sentences is in NP) implies that any such translation has an at least exponential blow-up, common methods establishing the collapse of FO to FO1 only give a doubly exponential upper bound: any sentence is equivalent to a boolean combination of sentences of the form $\exists x\,\bigl(\bigwedge_{i\in I}P_i(x)\land\bigwedge_{j\in J}\neg P_j(x)\bigr)$; there are $2^n$ such existential sentences, hence their boolean combinations may have size $\approx2^{2^n}$.
So, let me show that one can perform the translation in time $2^{O(n)}$ after all. I will work more generally with any FO language without equality using at most unary symbols (relations and functions, including constants).
Given an FO sentence $\phi$, we first rewrite it so that no variable is quantified more than once, and then we construct an equivalent FO1 sentence $\phi^*$ by induction on the complexity of $\phi$:

If $\phi$ is quantifier-free, $\phi^*=\phi$.

If $\phi$ is a boolean combination of $\phi_0,\dots,\phi_{n-1}$, we make $\phi^*$ the corresponding boolean combination of $\phi_0^*,\dots,\phi_{n-1}^*$.

If $\phi=\exists x\,\psi(x)$, let $A_x$ be the set of all atomic subformulas of $\psi$ that contain $x$ (and therefore no other variable). For each $I\subseteq A_x$, let $\psi_I$ denote the sentence obtained from $\psi(x)$ by replacing all occurrences of $\alpha\in I$ with $\top$, and all occurrences of $\alpha\in A_x\smallsetminus I$ with $\bot$. Then we define
$$\phi^*=\bigvee_{I\subseteq A_x}\Bigl[(\psi_I)^*\land\exists x\,\Bigl(\bigwedge_{\alpha\in I}\alpha(x)\land\bigwedge_{\alpha\in A_x\smallsetminus I}\neg\alpha(x)\Bigr)\Bigr].$$

The soundness of this translation follows from the tautologies
$$\bigwedge_{\alpha\in I}\alpha(x)\land\bigwedge_{\alpha\in A_x\smallsetminus I}\neg\alpha(x)\to(\psi(x)\leftrightarrow\psi_I).$$
Let $n=|\phi|$. Since we expanded each quantifier to a disjunction of $2^n$ formulas, the size of the formula is roughly multiplied by $2^n$ for each quantifier, giving a total size about $2^{n^2}$. But counting more precisely, the expansion of $\exists x$ multiplied the size by $2^{|A_x|}$; since each element of $A_x$ is an atomic subformula of the original formula, and distinct quantifiers correspond to disjoint sets $A_x$ by our assumption on quantified variables, the overall multiplicative factor is only $2^{\sum_x|A_x|}\le2^n$, thus $|\phi^*|=2^{O(n)}$, and it is easy to see that it is computable in time polynomial in $|\phi^*|$.
One can also show using a similar argument that given an FO sentence with equality in a language with unary predicates and constants, we can compute in time $2^{O(n)}$ an equivalent sentence that is a boolean combination of sentences of the form $\exists^{\ge k}x\,\theta(x)$, where $\theta$ is a conjunction of atomic and negated atomic formulas, and $k\le n$.

Concerning the model enumeration problem: I assume the problem is, given a sentence $\phi$ and a number $n$ in unary, count the number of models of $\phi$ with domain $[n]$, but it is not clear to me if you want $\phi$ to be fixed, or to be part of the input.
If $\phi$ is part of the input, the problem is in PSPACE (more precisely, FPSPACE) by the brute force enumeration algorithm (this works for arbitrary FO languages). Conversely, it is PSPACE-hard even if $n=2$ is fixed, and the language consists of a single unary predicate: indeed, a QBF
$$Q_0p_0\,Q_1p_1\,\dots\,Q_mp_m\,\theta(p_0,\dots,p_m)$$
is true iff the sentence
$$\exists x\,P(x)\land\exists x\,\neg P(x)\land Q_0x_0\,Q_1x_1\,\dots\,Q_mx_m\,\theta(P(x_0),\dots,P(x_m))$$
has a model (of size $2$).
If $\phi$ is fixed, the enumeration problem is solvable in polynomial time, and even in $\mathrm{TC}^0$: in fact, the number of models of size $n$ is
$$\sum_{i=0}^Kc_ii^n$$
for some integer constants $K$ and $c_0,\dots,c_K$ determined by $\phi$. To see this, a model with $k$ unary predicates on domain $[n]$ can be identified with a mapping $M\colon[n]\to[2^k]$, assigning to each element the bitstring stating which unary predicates it satisfies. The truth of a sentence $\exists x\,\bigl(\bigwedge_{i\in I}P_i(x)\land\bigwedge_{i\notin I}\neg P_i(x)\bigr)$ in $M$ is then determined by the presence of the corresponding bitstring in $\mathrm{Im}(M)$. Thus, there is a set $T_\phi\subseteq\mathcal P([2^k])$ such that
$$M\models\phi\iff\mathrm{Im}(M)\in T_\phi,$$
and the number of models of $\phi$ of size $n$ is
$$\sum_{E\in T_\phi}\bigl|\{M\colon[n]\to E\mid M\text{ is onto}\}\bigr|
=\sum_{E\in T_\phi}|E|!\,S(n,|E|)
=\sum_{E\in T_\phi}\sum_{i=0}^{|E|}\binom{|E|}i(-1)^{|E|-i}i^n$$
where $S(n,k)$ are Stirling numbers of the second kind.


Complexity of relaxed edge colouring A (proper) $k$-edge colouring of a graph $G(V,E)$ is a function $f:E\to\{1,2,\dots,k\}$ such that adjacent vertices are mapped to different colours; that is, $f(e)\neq f(e')$ if $e$ and $e'$ are incident on the same vertex. It is known that the minimum number of colours required for edge colouring is between $\Delta(G)$ and $\Delta(G)+1$, and yet it is NP-complete to distinguish between the two cases.
Let us define a relaxed $k$-edge colouring of $G$ as a function $f:E\to\{1,2,\dots,k\}$ such that for every vertex $v$ of $G$, at most two edges incident on $v$ have the same colour.
What is the complexity of relaxed edge colouring?
I am particularly interested in the complexity of relaxed $k$-edge colouring for graphs of maximum degree $k$.
Edit: The part below was part of the question earlier. But, it is wrong because proper $k$-edge colouring and thus relaxed $k$-edge colouring are trivially in P for graphs with maximum degree $k-1$.

I am particularly interested in the complexity of relaxed $k$-edge
colouring for graphs of maximum degree $k-1$. I have a hunch the
problem is going to be computationally hard, which is interesting
because $k$-edge colouring is polynomial time solvable for the class.

If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891.
Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be augmented to a $2k$-regular graph $G'$ (by adding extra vertices and edges if necessary) and any 2-factorization of $G'$ restricts to a relaxed edge coloring of $G$.
So relaxed edge coloring is easy: the optimal number of colors is always $\lceil\Delta/2\rceil$.


Krivine's notation for lambda-terms Krivine in his book (Lambda-calculus: Types and Models) introduces the grammar of lambda-terms and then abbreviations to denote them. The grammar itself is not ambiguous:  Lambda-terms are
obtained by applying, a finite number of times, the following rules :

any variable x is a λ-term ;
whenever t and u are λ-terms, then so is (t)u ;
whenever t is a λ-term and x is a variable, then λx t is a λ-term.

Then: "the term $(...(((t)u_1)u_2)...)u_k$ will also be written "$(t)u_1 u_2 ...u_k$". But let us consider the two following different $\lambda$-terms:

$v_1 = ((x)\lambda y. (y)z)w$
$v_2 = (x)\lambda y. ((y)z)w$

($w, x, y, z$ are variables)
and now it seems that I have two ways to interpret the notation $(x)\lambda y. (y)z w$:

either $t = x$, $k = 2$, $u_1 =\lambda y. (y)z$ and $u_2 = w$
or $t = x$, $k= 1$ and $u_1 = \lambda y. ((y)z)w$

It seems that the notation "$(t)u_1 u_2 ...u_k$" is ambiguous. Which rule am I violating in my interpretation?

Here's a quote from this version which can be found on the author's page (emphasis mine):

  The term $(t)u$ should be thought of as “$t$ applied to $u$” ; it will also be denoted by $t u$ if there is no ambiguity ; the term $(\dots (((t)u_1)u_2)\dots)u_k$ will also be written $(t)u_1u_2\dots u_k$ or $tu_1u_2\dots u_k$. Thus, for example, $(t)uv$, $(tu)v$ and $tuv$ denote the same term.

I'd expect the "if there is no ambiguity" condition to also apply to the second notation (which is just the first notation applied $k-1$ times).


Intuition for the UP class UP class is defined as such:

  The class of decision problems solvable by an NP machine such that

  If the answer is 'yes,' exactly one computation path accepts.

  If the answer is 'no,' all computation paths reject.

I'm trying to develop intuition for this definition.

Can one say that UP problems are the problems with unique solutions (e.g. prime factorisation)?

That seems close to the truth to me; but I can't help thinking that that would mean, since UP contains P and is contained in NP, that in case P = NP we'd get that P = UP = NP, so all problems in NP have unique solutions as well, which seems like something provably not true: P != NP by reductio ad absurdum. I hope there's not too much conjectures and hand-wavery in this paragraph for your taste.

Your confusion appears to be over the fact that $\mathsf{NP}$ problems have more than one way to define a "solution" (or witness). The type of the solution is not part of the definition of the problem. For instance, for graph coloring, the obvious type of solution is an assignment of one color for each vertex (using at most the required number of colors); however, by the Gallai–Hasse–Roy–Vitaver theorem another type of solution that works equally well is an assignment of an orientation to each edge (creating directed paths of at most the required number of vertices). These two types of solutions can both be checked in polynomial time, but by different algorithms, and they also have different combinatorial properties. For instance, for a typical problem instance, the number of vertex color assignments will be different from the number of edge orientations. A lot of research on speeding up exponential algorithms for NP type problems can be interpreted as finding a new family of solutions to the same problem that has fewer possibilities to check.

Every problem in $\mathsf{P}$ has an $\mathsf{NP}$ "solution" consisting only of the empty string. To verify that this is a solution, just check that the solution string is empty and then run the polynomial time algorithm for the problem instance. With this type of solution, every yes instance has exactly one valid solution and every no instance has zero, meeting the definition of $\mathsf{UP}$ and showing that $\mathsf{P}\subset\mathsf{UP}$. If $\mathsf{P}=\mathsf{NP}$ then the same empty-string solution would also work for every problem in $\mathsf{NP}$, showing that $\mathsf{NP}=\mathsf{UP}$. So there is no contradiction between the fact that the empty-string solution is unique and the fact that some other type of solution for the same problem is non-unique.


Easy to optimize but hard to evaluate Are there any known natural examples of optimization problems for which it is much easier to produce an optimal solution than to evaluate the quality of a given candidate solution?

For the sake of concreteness, we may consider polynomial-time solvable optimization problems of the form: "given x, minimize $f(x, y)$", where $f:\{0,1\}^*\times\{0,1\}^* \to \mathbb{N}$ is, say, #P-hard. Such problems clearly exist (for instance, we could have $f(x, 0) = 0$ for all $x$ even if $f$ is uncomputable), but I am looking for ``natural'' problems exhibiting this phenomenon.

Here is an example, where one can produce a solution in polynomial time, but evaluating a given solution is NP-hard.

Input: Positive integers $n,k$ (in unary encoding), with $k\leq n$.

Task: Maximize the number of edges in an $n$-vertex graph under the  constraint that its maximum clique size is at most $k$.

Solution: It is known from extremal graph theory that the optimal graph will be  the Turan graph $T(n,k)$ (see here), which can be easily constructed in polynomial time. On the other hand, checking the quality of a given candidate solution (a given graph) involves checking that its maximum clique size is at most $k$, which is NP-hard.

Note: If we only want to check whether the solution is optimal, then it is easy, because the Turan graph is known to be the unique optimum, so it is enough to compare the candidate graph with the Turan graph, which has a simple structure. On the other hand, if we want to evaluate the quality of a candidate solution, as requested in the question, that is, whether it is feasible and how far it is from the optimum, then we have to check whether it satisfies the maximum clique constraint.


Razborov's Approximation methods The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.

People in parameterized complexity theory strongly believe that k-colooring is strictly harder than the k-clique problem, because k-clique problems can be solved by an exhaustive search of all ${n \choose k}$ potential cliques while k-coloring is NP-complete for a fixed k (k=3). k-coloring is also monotone function.

It seems to be natural that the approx method is appropriate for deriving lower bounds of the problem but I haven't seen a paper which justifies this intuition.

Is Razborov's method useful to derive the exponential monotone lower bound of k-coloring?

Let $f(G)=1$ iff $G$ is not $(k-1)$-colorable. Then $f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs, just like the $k$-clique function does. So, the lower bounds for clique hold also for $f$.


How many words of length $k$ on $l$ letters avoid a partial word? EDITED TO ADD: This question is now essentially answered; please see this blog entry for more details.  Thanks to everyone who posted comments and answers here.

ORIGINAL QUESTION

This is a hopefully smarter and better-informed version of a question I asked on MathOverflow.  When I asked that question, I did not even know the name of the area of mathematics my problem was in.  Now I am pretty sure it lies in Algorithmic Combinatorics on Partial Words.  (Recent book on the subject here.)

I want to make a list of words on $l$ letters.  Each word has length exactly $k$.  The deal is, if $a \lozenge ^j b$ is in the list, where $\lozenge$ is a wildcard/don't-care symbol, then $a \lozenge ^j b$ can never appear again in the list.  (The same holds true if $a=b$, or if $j=0$ and hence the prohibited subword is $ab$.)

Example where $k=4$ and $l=5$:

$abcd$
$bdce$
$dcba$ <-- prohibited because $dc$ appeared in the line above
$aeed$ <-- prohibited because $a \lozenge \lozenge d$ appeared on the first line

The literature on "avoidable partial words" that I have found has all been infinitary -- eventually some word pattern is unavoidable if the word size is large enough.  I would like to find finitary versions of such theorems.  So, question:

  Given a partial word of form $a \lozenge^j b$ in an alphabet of $l$ letters, how many words of length $k$ avoid it, and can they be explicitly produced in polynomial time?

I don't expect the above question to be difficult, and, unless there is a subtlety I am missing, I could calculate it myself.  The real reason I am posting on this site is because I need to know a lot more about the properties of such word lists for my application, so I am hoping someone can answer the followup question:

  Has this been studied in generality?  What are some papers that consider, not just whether a partial word is eventually unavoidable, but "how long it takes" before it becomes unavoidable?

Thanks.

Here's a special case: the number of binary words of length $k$ such that no two ones appear consecutively is $F(k+3)$, where $F(n)$ is the $n^{th}$ Fibonacci number (starting with $F(1)=1, F(2)=1$). Proof is via the Zeckendorf representation.

EDIT: We can extend this initial special case into the slightly larger special case of $a\lozenge^0a$. Consider strings of length $k$ over an alphabet of size $l+1$ such that the letter $a$ does not appear twice consecutively. Let $f(k)$ be the number of such strings (which we will call "valid"). We claim that: $$f(k) = l*f(k-1) + l*f(k-2)$$
$$ f(0) = 1, f(1) = l+1$$
The intuition is that we can construct a valid string of length $k$ by either: a) adjoining any of the $l$ letters that are not $a$ to a valid string of length $k-1$, or b) adjoining the letter $a$ and then any other letter but $a$ to a valid string of length $k-2$.

You can verify that the following is a closed form for the above recurrence:
$$f(k) = \sum_{i=0}^{k} {{k+1-i}\choose{i}} l^{k-i}$$
where we understand ${{n}\choose{i}} = 0$ when $i>n$.

EDIT #2: Let's knock out one more case -- a $\lozenge^0 b, a \neq b$. We'll call strings over an $l$-element alphabet that do not contain the substring $ab$, "valid" and let $S_k$ denote the set of valid strings of length $k$. Further, let's define $T_k$ to be the subset of $S_k$ consisting of strings starting with $b$ and $U_k$ to be those not starting with $b$. Finally, let $f(k) = |S_k|$, $g(k) = |T_k|$, $h(k) = |U_k|$.

We observe that $g(0)=0, h(0)=1, f(0)=1$ and $g(1)=1, h(1)=l-1, f(1)=l$. Next, we infer the following recurrences:
\begin{eqnarray}
g(k+1) &=& f(k) \\
h(k+1) &=&(l-1)*h(k) + (l-2)*g(k)
\end{eqnarray}
The first comes from the fact that adding a $b$ to the start of any element of $S_k$ produces an element of $T_{k+1}$. The second comes from observing that we can construct an element of $U_{k+1}$ by adding any character but $b$ to the front of any element of $U_{k}$ or by adding any character but $a$ or $b$ to the front of any element in $T_k$.

Next, we rearrange the recurrence equations to obtain:
\begin{eqnarray}
f(k+1) &=& g(k+1) + h(k+1) \\
&=& f(k) + (l-1)*h(k) + (l-2)*g(k) \\
&=& f(k) + (l-1)*f(k) - g(k) \\
&=& l*f(k) - f(k-1)
\end{eqnarray}

We can get a rather opaque closed-form solution to this recurrence by mucking around a bit with generating function stuff or, if we're lazy, heading straight to Wolfram Alpha. However, with a little bit of googling and poking around in OEIS, we find that we actually have:
$$f(k) = U_k(l/2)$$
where $U_k$ is the $k^{th}$ Chebyshev polynomial of the second kind (!).


how to define "correlation" between languages? How does one define the concept of correlation between languages?
Is there any 'standard' measure of 'correlation' between two (possibly inf) sets of strings / an analogue of the concept in this setting?
Was thinking could use the algorithmic mutual information between their descriptions--maybe this works for languages with finite descriptions?

Your idea only works on languages with finite descriptions; here is an approach that's well defined for all languages, but it requires choosing some probability distribution $\mu$ on the set of all finite words, $\Sigma^*$. Assuming that you've chosen one, let $A$ and $B$ be your two languages. Let $X$ be the random variable corresponding to the event that a $\mu$-random word belongs to $A$, and define $Y$ analogously for $B$. Now you can define correlation between $A$ and $B$ as the correlation between $X$ and $Y$ in the classical sense:
$$ cov(X,Y) = E[XY]-E[X]E[Y] =
\sum_{x\in\Sigma^*}1[x\in A\cap B]\mu(x)
-
\sum_{x,y\in\Sigma^*}1[x\in A]1[y\in B]\mu(x)\mu(y)
,
$$
and $cor(X,Y)=\frac{cov(X,Y)}{\sigma_X\sigma_Y}$, where
$$
\sigma_X^2 = \sum_{x\in\Sigma^*}1[x\in A]\mu(x)
-
\left(
\sum_{x\in\Sigma^*}1[x\in A]\mu(x)
\right)^2.
$$
A reasonable choice of $\mu$ would be to let word length be distributed, say, geometrically (or any other distribution on the integers), and within each fixed word length, $\mu$ is uniform. But of course the "reasonableness" or usefulness of this definition will depend entirely on your purposes.


Can a NEXP machine simulate invalid queries to a promise problem oracle? Let $A=(A_{YES},A_{NO})$ be some promise problem (such as xSAT, the Local Hamiltonian problem, etc). Suppose we want to show that a P machine with access to a the oracle A can always have its output predicted by a NEXP machine, i.e. $P^A\subseteq$ NEXP. We adopt the convention that if P submits a query  which doesn't satisfy the promise of A (that is, $x\not\in A_{YES}\cup A_{NO}$), then the oracle for A randomly returns 0 or 1 $^*$.
Suppose further that for all valid queries (i.e. those satisfying the promise, $x\in A_{YES}\cup A_{NO}$) there exists a single witness which (when run by an EXP machine) allows all queries to the oracle A to be predicted.
Finally, let it is be trivial (i.e. in P) to determine whether a query $x$ satisfies the promise or not.
Then is it correct to say $P^A\subseteq$ NEXP?
If the P machine were guaranteed to only make valid queries, then it seems like this is trivial as the NEXP machine is (by assumption) capable of simulating the oracle outcomes and any processing done by the P machine. However, the fact that the P machine can make invalid queries which return 0 or 1 randomly could potentially throw a problem in the simulation.
So far all I've found is Oded Goldreich's notes on promise problems. These don't give a direct answer, but do introduce smart reductions: http://www.wisdom.weizmann.ac.il/~oded/PSX/prpr-r.pdf
Smart reductions seem to force the P machine to only make valid queries. So in this case it would perhaps be correct to say $P_S^A\subseteq$NEXP, where $P_S$ is a ``smart TM'' which only makes valid queries. But is it correct to state the stronger result that $P^A\subseteq$NEXP?
$^*$As I understand it, this is standard (see the link to Oded Goldreich's notes above).

Let's define what P$^A$ means in the promise setting: A language L is in P$^A$ if there is a polytime oracle machine $M$ such that for all sets $B$ such that $B$ contains $A_{YES}$ and $B\cap A_{NO}=\emptyset$, $L=L(M^B)$. In other words, the polytime machine can ask queries that are not part of the promise but its output cannot depend on whether those queries are answered yes or no.
For example, consider unique SAT where $A_{YES}$ are the formula with exactly one satisfying assignment and $A_{NO}$ are the formula with no satisfying assignment. Then $P^A$ is contained in $\oplus P$. We also have $NP\subseteq BPP^A$ by Valiant-Vazirani. Both these tools are used in the proof of Toda's theorem.


What is the "right" definition of upper and lower bounds? Let $f(n)$ be the worst case running time of a problem on input of size $n$. Let us make the problem a bit weird by fixing $f(n) = n^2$ for $n=2k$ but $f(n) = n$ for $n=2k+1$.

So, what is the lower bound of the problem? The way I understood it is just the lower bound of $f(n)$. But we know that $f(n) = \Omega(n^2)$ implies that there exists constant $k$, $n_0$ such that for all $n > n_0$, $f(n) > kn^2$, which is not true. Thus it seems that we can only say $f(n) = \Omega(n)$.
But usually, we will call the problem has a lower bound of $\Omega(n^2)$, right?
Assuming that $g(n) = \Omega(n^2)$, which means that there exists constant $k$, $n_0$ such that for all $n > n_0$, $g(n) > kn^2$. Let's also assume a problem has running time $g(n)$. If we can reduce this problem for all the primes $n$ to another problem (with same input size), can we say the running time of the other problem has a lower bound of $\Omega(n^2)$?

The right definition of $f(n)=\Omega(n^2)$ is that there exists some $k>0$ such that for infinitely many $n$, $f(n)\geq kn^2$. The infinitely-often definition for lower bounds handles your issues and is how we use it in practice.

I did a post on this back in 2005.

Some textbooks get this definition right, some don't.


(False?) proof for computability of a function? Consider $f(n)$, a function that returns 1 iff $n$ zeros appear consecutively in $\pi$. Now someone gave me a proof that $f(n)$ is computable:

  Either for all n, $0^n$ appears in $\pi$, or there is a m s.t. $0^m$ appears in $\pi$ and $0^{m+1}$ does not.
  For the first possibility $f(n) := 1$; For the second one $f(n) := 1$ iff $n \leq m$, 0 otherwise.

The author claims that this proves computability of $f(n)$, as there exists an algorithm to compute it.

Is this proof correct?

Think of it this way, Mike: This proof is "branching" into multiple possible cases, one of which has to be true (using the law of excluded middle that for every proposition $p$, either $p$ is true or $\neg p$ is true). But at the end of each of these branches, you always manage to prove that the function $f$ is computable. Therefore, no matter which of the cases actually holds in real life, $f$ must be computable. (However, the precise reason why $f$ is computable will be different, depending on the branch.)


Translation of context-free parsing into SAT Is there a published algorithm for translating a context-free parsing problem into SAT? That is, an algorithm that translates a context-free grammar and an input string into a set clauses that is satisfiable iff the input string is well-formed according to the grammar.

(I guess the important word in the original question is ``published''.)  There is such an encoding of context-free parsing (more exactly of CYK-style parsing) in  Roland Axelsson, Keijo Heljanko, and Martin Lange, Analyzing Context-Free Grammars Using an Incremental SAT Solver, ICALP 2008, Lecture Notes in Computer Science vol. 5126, pp. 410--422, doi:10.1007/978-3-540-70583-3_34.  They use it in particular to detect ambiguity of words $w$ in context-free grammars for growing word lengths.


Efficient DAG comparison over a network In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in hearing about theoretical work that discuss the time- and network-complexity of comparing two DAGs.

The DAGs in question are formed by the revisions recorded. Revisions are uniquely identified by a hash value. Each revisions depend on zero (initial commit), one (normal commit) or more (merge commit) of the previous revisions. Here is an example where revisions a to e were made one after each other:

a --- b --- c --- d --- e

The graph comparison comes into the picture when someone has only part of the history and wants to retrieve the missing part. Imagine I had a to c and made x and y based on c:

a --- b --- c --- x --- y

In Mercurial, I would do hg pull and download d and e:

a --- b --- c --- x --- y
              \
                d --- e

The goal is to identify d and e efficiently when the graph has many (say, more than 100,000) nodes. Efficiency concerns both

network complexity: the number of bytes transferred and the number of network round-trips needed
time complexity: the amount of computation done by the two servers that exchange changesets

Typical graphs will be narrow with few parallel tracks like above. There will also typically be only a handful of leaf nodes (we call them heads in Mercurial) like e and y above. Finally, when a central server is used, the client will often have a couple of changesets that are not on the server, while the server can have 100+ new changesets for the clients, depending on who long ago the client last pulled from the server. An asymmetric solution is preferred: a centralized server should do little computation in comparison to its clients.

In this context, the graph nodes have some sort of unique identifier (a hash or checksum), right? So you don't need to do any kind of subgraph isomorphism testing, you just need a list of the nodes that differ between your two versions, and the edges aren't really useful at all for this step. My SIGCOMM 2011 paper "What's the difference? Efficient set reconciliation without prior context" (with Goodrich, Uyeda, and Varghese) considers exactly this problem: it turns out that you can determine the identities of the nodes that are held by one but not both of the two communicating servers, using an amount of communication that is proportional only to the number of changed nodes and using only a single round-trip. Once you have that information, it's easy to pull the changes themselves in a second round-trip, again with optimal communication.


What is the algorithmic speed up for Counting Perfect Matchings in Dense Bipartite Graphs (equivalent to Permanent of Dense 0/1 Matrices)? The Idea is this:

The Decision problems Max Cut for graphs is APX-Hard and therefore does not have a PTAS.

However Dense versions of Max Cut do have a PTAS!

This suggest that Counting Perfect Matchings for Dense Bipartite Graphs could have some sort of speed up.

Does such a speedup exists in the complexity literature?

Further to the above, I am aware of the expectional work done on NonNegative Matrices. However I was really thinking about General matrices and expecting exponential algorithms. Of course #P is by standard complexity theory intractable!

What about

http://portal.acm.org/citation.cfm?doid=1008731.1008738

?

If you are looking for exact algorithms, the only speedup I'm aware of is

http://www.springerlink.com/content/ar7jwwy01qleny8e/fulltext.pdf

Which also can be used to show you can do c^n time for c<2 for sparse 0/1 matrices or the UP-hard mod 3 permanent.


Complexity of propositional LTL with past operators and freeze quantifier? In "A Really Temporal Logic", by R.Alur and A.Henziger, they introduce an extension of Linear Temporal Logic with a freeze quantifier $x.\phi$, which allows to "give a name" to the current time point to later compare it with others. An example formula from the paper is

$$
\Box x.(p \to \Diamond y.(q \land y \le x + 10))
$$

which means that whenever $p$ holds, $q$ must eventually hold within 10 time points. This logic has been proved to be EXPSPACE-complete in the above paper.

Since the paper is very old, I'm wondering which developments have been done on this logic.
Specifically, I'm asking if it has been proved whether this logic augmented with LTL past operators is still EXPSPACE-complete, as is the case for classic LTL+past which remains PSPACE-complete as the future-only version.

I've found something by searching for "freeze quantifier" but recent works such as this paper talk about further extensions with registers that I'm not interested about (or maybe I am but I'm misunderstanding).

So is this logic augmented with past operators still EXPSPACE-complete?

The answer was buried in a small section of the same paper that I was citing. Adding past operators to TPTL, in contrast of what happens with LTL, causes a huge increase in complexity as the satisfiability problem becomes non-elementary.

The fact is proven in the paper by showing how a mixture of future and past operators, combined with the freeze quantifier, can emulate an arbitrary first-order existential quantifier.


Approximation schemes for P-complete problems? What work has been done on approximation schemes for $\mathsf{P}$-complete optimization problems? Would the desired approximation algorithms here be "fully log-space approximation schemes" or "fully $\mathsf{NC}$ approximation schemes", analogous to $\mathsf{FPTAS}$ for $\mathsf{NP}$ optimization problems?

This one seems related, although it focuses more on parallel time (NC) rather than the closely related space (L): http://www.springerlink.com/content/8hn2q8lvf3ukbbx0/


Question on the Prize-Collecting TSP's ratio related to inapprox. of general TSP The Prize-Collecting TSP (PCTSP) is defined as the ordinary TSP with the difference that penalties are added to nodes; so we may avoid visiting a node paying its penalty, which is added to the overall cost. It currently admits a $2-\epsilon$ approximation ratio, where edge costs are considered to satisfy the triangle inequality. Obviously, ordinary TSP is PCTSP where all node penalties are set to inf.

I would like to ask, in the case a graph which does not satisfy the triangle inequality is chosen and ALL of its edges are deleted, replaced by 2 new edges connected to a 2-degree new node for each case of deleted edge, where each edge cost is equal to the deleted edge's cost/2 and having Euclidean distance equal to that (so the new graph is metric), don't we get a $(2-\epsilon)$ approximation ratio for the original (general and therefore non-approximable) graph? (Penalties for old nodes are set to inf and to new 2-degree nodes equal to 0).

Of course, there is a mistake in my thought, since this can't be true, so if somebody finds it, I would be pleased to listen to that. Thank you in priori.

Edited may answer, I hope it becomes clearer now (or I find out what I did not understand):

Your process is as follows: If you have an edge $e = \{u,v\}$ with weight $t$ you replace $e$ by a path of length two with edges $\{u,z_e\}$ and $\{z_e,v\}$. $z_e$ is a new node and each of the two new edges get weight $t/2$. For each edge, we introduce a new node.

So far, we do not have a metric instance, because there is no edge between $u$ and $v$ so far and the distance between $u$ and $v$ is infinite. Therefore, you take the shortest path metric to get these distances. (I suppose that this is what you mean by "having Euclidean distances equal to that". Otherwise, you should clarify this.)

My point is that after adding distances according to the shortest path metric, the distance between $u$ and $v$ might not be $t$ anymore, so you do not get your original instance back:
Consider a triangle with edge lengths $1$, $1$ and $t$. Let $u$ and $v$ be the nodes of the edge with weight $t$. Apply your construction. The shortest path between $u$ and $v$ is $2$ (it takes the four edges with weight $1/2$) and not $t$.

Btw: Euclidean distance should just be distance in the question.


Minimum Degree Spanning Tree Without Restricting Vertices Searched This is reposted from cs.stackexchange. I asked the question more than two weeks ago and got no answers, so I thought to repost here.
I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. Given a graph $G$, we need to find a spanning tree $T$ that minimizes the maximum degree of any vertex in $T$.
I understand that the local search algorithm attempts to look at vertices with degree at least $\Delta(T)-\lceil \log_2(n)\rceil $ and try to improve it, and only stops when one cannot improve any such vertex. I understand that this restriction is done to polynomially bound the run time of the algorithm.
My question is, what approximation ratio can we get if we try to improve any vertex? I understand that we cannot show that it runs in polynomial time, but what approximation ratio would hold? Obviously the $2OPT+\lceil \log_2(n)\rceil$ still holds, but can we improve the ratio by trying all vertices? I tried to read the original paper which had another local search algorithm with cost $OPT+1$, but I am not able to prove that this locally optimal tree for all vertices is also an $OPT+1$ algorithm.

This is not an answer, but some experimental evidence on why I think this might be an $OPT+1$ approximation.
I wrote some python code that runs the local search algorithm (without restricting the vertices searched) and solves the problem optimally with ILP. I tried it on thousands of small random graphs and the local search was always $OPT$ or $OPT+1$. Here is the code:
import networkx as nx
from pulp import *

def local_search(G):
    T = nx.algorithms.tree.mst.minimum_spanning_tree(G)

    while True:
        noChange = True
        for w in G:
            for u,v in G.edges():
                Tset = set(T.edges())
                if (u,v) not in Tset:
                    T.add_edge(u,v)
                    C = nx.algorithms.cycles.find_cycle(T)
                    T.remove_edge(u,v)
                    C_vertices = set([x for y in C for x in y ])
                    if w in C_vertices and T.degree[w]>=max(T.degree[u], T.degree[v])+2:
                        T.add_edge(u,v)
                        for x,y in C:
                            if x==w or y==w:
                                T.remove_edge(x,y)
                                break
                        noChange = False
        if noChange:
            break
    return max([T.degree[u] for u in G]), T

def opt_soln(G):
    prob = LpProblem("The Minimum Degree Spanning Degree",LpMinimize)
    z = LpVariable("maxIndegree",1,None,LpInteger)
    variables = {
        tuple(sorted([u,v])) : LpVariable(f"x_{(u,v)}",0,1,LpInteger) for u,v in G.edges()
    }
    vertex_to_edges = {
        u : [variables[tuple(sorted([u,v]))] for v in G.neighbors(u)] for u in G
    }
    prob += z
    prob += lpSum(variables.values()) == (len(G)-1)
    for u in G:
        prob += lpSum(vertex_to_edges[u]) <= z
    prob.solve()
    return value(prob.objective)

tries = 1000
for _ in range(tries):
    n = 34
    p = 0.1
    d = 10
    G = nx.generators.random_graphs.fast_gnp_random_graph(n, p)
    #G = nx.generators.random_graphs.random_regular_graph(d, n)
    if not nx.is_connected(G):
        continue
    delta_T, T = local_search(G)
    delta_star = opt_soln(G)
    if delta_T-  int(delta_star)>1:
        print(delta_star, delta_T)
    #nx.draw(T)


What's the relation between OOP and category theory? What's the relation between OOP and category theory?  Is there some related work on this topic one can read?

There are absolutely some relationships between the semantics and practice of OOP and category theory. This is somewhat unsurprising since both fields attempt to give a principled generic account of structure and behavior in a synthetic manner.

The most apparent work I am aware of is the categorical semantics of UML, which is admittedly different from OOP in the large, but I think captures much of the crux of the debate on the semantics of objects themselves. One example is Zinovy Diskin's Mathematics of UML.


Sufficient Statistics of $X$ from $Y$ I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger.
In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they claim that $f(X)$ is the sufficient statistics of $X$ from $Y$. This means that $I(Y; X)=I(Y; f(X))$ where $I(\cdot; \cdot)$ is the mutual information.

I don't understand the definition of $f$. What does $f(X)=c$ mean?

The above implies that we have the two Markov chains $Y\to X\to f(X)$ and $Y\to f(X)\to X$. I don't understand the second Markov chain. Is there any intuition behind this? (The proof is given in the paper but I am looking for some intuition.)

Is the entropy of $f(X)$ equal to $H(Y|X)$?

The function $f$ maps $x$ to the conditional distribution of $Y$ given that $X = x$. This is a "deterministic" function. The expression $f(X)$ is a random variable depending on $X$. When $X = x$, the value of this random variable is $f(X) = f(x)$. In words, the random variable $f(X)$ gives the distribution of $Y$ conditional on the value of $X$.

Given $f(X)$, the variables $X,Y$ become independent. Suppose that $f(X) = \phi$. For each $x$ such that $f(x) = \phi$, the conditional distribution of $Y$ given that $X = x$ is $\phi$, that is, $\Pr[Y = y | X = x] = \phi(y)$. This doesn't depend on the value of $x$ as long as $f(x) = \phi$. In particular, the value of $X$ tells us nothing on $Y$, so the conditional mutual information is zero.


Empirical Rademacher averages versus Hoeffdings bound Let $M$ be finite set with $n$ distinct elements. I want to probalistically  approximate the relative counts $\frac{|P(Q)|}{|M|}$ of $Q \subseteq M$, where $P(Q) = |P \cap M|$.

An upper-bound for the number of samples need to get an (additive) $\varepsilon$-approximation can be derrived using the Hoeffding bound.

I am interested in achieving (empirical) better bounds using empirical Rademacher averages. My idea is to adaptability sample from $M$, to fulfill
    \begin{equation}
  \sup_{f \in \mathcal{F}}\,| L_{\mathcal{D}}(f) - L_{S}(f) | \leq 2\cdot\mathcal{R}_{\mathcal{F}}(S) + 3 \sqrt{\frac{ \log (2/\delta)}{2m}} \leq \epsilon,
 \end{equation}
where
\begin{equation*}
 \mathcal{F} = \{ \mathbf{1}_{Q} \mid Q \subseteq M \},
\end{equation*}
and $\mathbf{1}_{Q}$ equals $1$ if the current sample is in $Q$, and otherwise $0$.
It follows that
\begin{equation*}
 L_{\mathcal{D}}(\mathbf{1}_{Q}) =  \frac{|P(Q)|}{|M|}.
\end{equation*}

Can one achieve better bounds using this approaches, e.g., by using Massart's Lemma to approximate $\mathcal{R}_{\mathcal{F}}(S)$?

The answer depends on whether you want a bound for a single, fixed $Q\subseteq M$ or uniformly over all such $Q$. For a single, fixed $Q$, the Chernoff-Hoeffding bound is essentially the best you can do (see also empirical Bernstein's inequality for "fast rates").

If you want the bound to hold simultaneously for all $Q\subseteq M$, you need apply the union bound, which amounts to multiplying the deviation probability by $2^{|M|}$ (or the sample complexity by $|M|\log 2$).

You have nothing to gain here by using Rademacher complexities. The latter are useful at capturing the combinatorial properties of VC classes, and are sharper than naive union bounds (though Massart's lemma of course has a union bound inside). In your case, the VC structure is very simple -- it's all subsets -- and so you might as well just use the simple union bound.


Computing the approximate population of a bloom filter Given a bloom filter of size N-bits and K hash functions, of which M-bits (where M <= N) of the filter are set.

Is it possible to approximate the number of elements inserted into the bloom filter?

Simple Example

I've been mulling over the following example, assuming a BF of 100-bits and 5 hash functions where 10-bits are set...

Best case scenario: Assuming the hash functions are really perfect and uniquely map a bit for some X number of values, then given 10-bits have been set we can say that there has only been 2 elements inserted into the BF

Worst case scenario: Assuming the hash functions are bad and consistently map to the same bit (yet unique amongst each other), then we can say 10 elements have been inserted into the BF

The range seems to be [2,10] where abouts in this range is probably determined by the false-positive probability of filter - I'm stuck at this point.

Yes.  From Wikipedia:

If you have inserted $i$ elements into a filter of size $n$ using $k$ hash functions, the probability that a certain bit is still 0 is

$$
z = \left(1 - \frac{1}{n}\right)^{ki}
$$

You can measure this probability as the proportion of 0 bits in your filter.  Solving for $i$ gives

$$
i = \frac{\ln(z)}{k\ln\left(1 - \frac{1}{n}\right)}
$$

I have used this in practice, and as long as your filter does not exceed its capacity, the error is generally less than 0.1% for filters up to millions of bits.  As the filter exceeds its capacity, the error of course goes up.


Fooling arbitrary symmetric functions A distribution $\mathcal{D}$ is said to $\epsilon$-fool a function $f$ if $|E_{x\in U}(f(x)) - E_{x\in \mathcal{D}}(f(x))| \leq \epsilon$. And it is said to fool a class of functions if it fools every function in that class.
It is known that $\epsilon$-biased spaces fool the class of parities over subsets. (see Alon-Goldreich-Hastad-Peralta for some nice constructions of such spaces). The question I want to ask is a generalization of this to arbitrary symmetric functions.

  Question: Suppose we take the class of arbitrary symmetric functions
  over some subset, do we have
  distribution (with small support) that
  fools this class?

Some small observations:

It is sufficient to fool exact thresholds ($\text{ETh}^S_k(x)$ is 1 if and only if $x$ has exactly $k$ ones amongst the indices in $S$). Any distribution that $\epsilon$-fools these exact thresholds will $n\epsilon$ fool all symmetric functions over $n$ bits. (This is because every symmetric function can be written as a real linear combination of these exact thresholds where the coefficients in the combination are either 0 or 1. Linearity of expectation then gives us what we want)
A similar argument also works for general thresholds ($\text{Th}^S_k(x)$ is 1 if and only if $x$ has at least $k$ ones amongst the indices in $S$)
There is an explicit construction of a distribution with support $n^{O(\log n)}$ via Nisan's PRG for LOGSPACE.
Arbitrary $\epsilon$-biased spaces will not work. For example if $S$ is the set of all $x$ such that the number of ones in x is non-zero mod 3, this is actually $\epsilon$-biased for very small $\epsilon$ (from a result of Arkadev Chattopadyay).   But clearly this does not fool the MOD3 function.

An interesting subproblem may be the following: suppose we just want to fool symmetric functions over all n indices, do we have a nice space? By the above observations, we just need to fool the threshold functions over $n$-bits, which is just a family of $n+1$ functions. Thus one can just pick the distribution by brute-force. But are there nicer examples of spaces that fool $\text{Th}^{[n]}_k$'s for every $k$?

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

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

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


Grid $k$-coloring without monochromatic rectangles Update: The obstruction set (i.e. the NxM "barrier" between colorable and uncolorable grid sizes) for all monochromatic-rectangle-free 4-colorings is now known.

Anyone feel up to trying 5-colorings? ;)

The following question arises out of Ramsey Theory.

Consider a $k$-coloring of the $n$-by-$m$ grid graph. A monochromatic rectangle exists whenever four cells with the same color are arranged as the corners of some rectangle. For example, $(0,0), (0,1), (1,1),$ and $(1,0)$ form a monochromatic rectangle if they have the same color. Similarly, $(2,2), (2,6), (3,6),$ and $(3,2)$ form a monochromatic rectangle, if colored with the same color.

Question: Does there exist a $4$-coloring of the $17$-by-$17$ grid graph that does not contain a monochromatic rectangle? If so, provide the explicit coloring.

Some known facts:

$16$-by-$17$ is $4$-colorable without a monochromatic rectangle, but the known coloring scheme does not appear to extend to the $17$-by-$17$ case. (I'm omitting the known $16$-by-$17$ coloring because it would very likely be a red herring for deciding $17$-by-$17$.)
$18$-by-$19$ is NOT $4$-colorable without a monochromatic rectangle.
$17$-by-$18$ and $18$-by-$18$ are also unknown cases; an answer to these would be interesting as well.

Disclaimer: Bill Gasarch has a $289 (USD) bounty on a positive answer to this question; you can reach him through his blog. A note on etiquette: I'll make sure he knows the source of any correct answer (should one arise).

He brought it up again during a rump session at Barriers II, and I find it interesting, so I'm forwarding the question here (without his knowledge; though I highly doubt he would mind).

Some of you are probably aware of this, but the 17 x 17 coloring problem has been solved by Bernd Steinbach and Christian Posthoff.  See Gasarch's blog post here.


A parity learning question Let us define a class of functions over a set of $n$ bits. Fix two distributions $p, q$ that are "reasonably" different from each other (if you like, their variational distance is at least $\epsilon$, or something similar).

Now each function $f$ in this class is defined by a collection of $k$ indices $S$, and is evaluated as follows: If the parity of the selected bits is 0, return a random sample from $p$, else return a random sample from $q$.

Problem: Suppose I'm given oracle access to some $f$ from this class, and while I know $\epsilon$ (or some other measure of distance), I don't know $p$ and $q$.

  Are there any bounds on the number of calls I need to make to
  PAC-learn $f$ ? Presumably my answer will be in terms of $n, k$ and $\epsilon$.

Note: I didn't specify the output domain. Again, I'm flexible, but for now let's say that $p$ and $q$ are defined over a finite domain $[1..M]$. In general, I'd also be interested in the case when they are defined over ${\mathbb R}$ (for example, if they're Gaussians)

The discussion in the comments below indicades that I have misunderstood the question.  My answer is premised on the Oracle taking no input and returning $(x, f(x))$ where $x \sim p$ or $x \sim q$, depending on $f \in F$. This is apparently not what's being asked.

Because the target distribution is fixed for every target $f^* \in F$, the PAC-sample upper bound applies (this follows from the fact that the target distribution for this bound can even completely depend on $f^*$). Hence,
$$
m \le \tilde{O}\left(\frac{1}{\epsilon}\left(\mathrm{VC}(F) + \log(1/\delta) \right) \right)
$$
examples should suffice to find a hypothesis of error $\le \epsilon$ w.p. $\ge 1-\delta$. Note -- after seeing these examples, one needs to find a consistent hypothesis from $F$, and this may not be tractable.

On the other hand, one can get a nearly matching lower bound even for the case of $p=q=U$, the uniform distribution, where $m \ge \Omega(\mathrm{VC}(F))$ examples are still required (this can be improved slightly).

The variational distance between $p$ and $q$, as well as $k$ may play a role in the small gap between these bounds, but I doubt it.


Assistance in showing computational equivalence between software and hardware computing systems I'm in the middle of a discussion regarding the equivalence of software and hardware computing systems, and I would like some comment. Any arguments and/or documentation (supporting or dissenting) would be appreciated.

My position is that the implementation of a computational processing system can be separated from the act of logical computation, i.e. the agent performing logical processing (i.e., computation) can be distinctly separated from the process.  My line of reasoning is more observational at the moment. For example,

A PID controller may be implementing in pure (analog or digital) hardware or software.
It is now routine to compile a C program into VHDL, then write the resulting "hardware" configuration into an FPGA.
Computational systems have been constructed from fluidics and other mechanical systems.
Computations systems have been constructed from molecular biology (i.e., DNA computing.)

From these observations, one might conclude that hardware computational systems, from simple collections of basic gates to FPGAs, are functionally equivalent to software programs.

The question is not entirely academic: the US FDA places dramatically different validation and verification (V&V) requirements on a medical device depending upon its use of hardware or software for logical operations.  Software systems are subject to a number of standards and regulations, and the resulting testing procedure and documentation burden is heavy.  On the other hand, simple hardware-only implementations, such as a PID controller, are subject to much less federal regulation.

As a result, a bias is introduced into the design process.  A system designer is inherently pushed toward a hardware solution - simply due to the regulatory burden. The assertion that "computational hardware and software do the fundamental same things" is rendered heretical.  It implies that hardware solutions are challenged with the issues of software development, and that hardware solutions should be subject to the same V&V processes applied to software.  (Note that the US FDA is slowly coming around to this viewpoint - some of their more recent guidelines sound like early software guidelines.)

Can someone suggest a theoretical strategy for establishing this equivalence or a logical argument for divorcing the process of computation from the agent of computation?

These issues are clearly and accessibly covered in Sanjeev Arora and Boaz Barak's Computational Complexity: A Modern Approach, specifically in the chapters "The computational model and why it doesn't matter", "NP and NP completeness", and "Boolean circuits" (respectively chs. 1,2,6).

Very generously, an on-line draft of this book has been provided by the authors ... this has been a big help to me in my own researches!

From the viewpoint of complexity theory, the various theorems and proof technologies in Arora and Barak's exposition provide little grounds for  "divorcing the process of computation from the agent of computation"  (in the phrasing of the question).

From a regulatory perspective, however, it is well to keep in mind the legal maxim:

  "Justice is the tolerable accommodation of the conflicting interests of society, and I don't believe there is any royal road to attain such accommodation concretely."

  --  Judge Learned Hand

In real-world medical practice, and in many other regulatory contexts such as aircraft safety, commonly it is legally and practically necessary to distinguish between hardware and software, even though all parties recognize that the mathematical foundations for this distinction are highly imperfect.


NP-hardness of an optimization problem While studying a problem in algorithmic game theory I got interested
in the complexity of the following optimization question:
Problem
Given:

ground set $U = [n] = \{1,\ldots,n\}$ given by $n$,
$m$ rankings given as total orders $\langle S_i, \sigma_i \rangle$
where $S_i \subseteq U$ ($1 \leq i \leq m$),
weight vector for $U$ given by $w \in \mathbb{R}^n$.

Goal:
find a subset $L \subseteq U$ maximizing the following sum:
$$r(L) = \sum_{i \in [m],\  S_i \cap L \neq \emptyset} w(t_i(L))$$
where $t_i(L)$ is the highest ranked item in $L\cap S_i$ according to
$\sigma_i$.
I suspect that the problem is $\mathsf{NP}$-hard. In fact the problem
seems to be hard even when all the $S_i$'s are of size $2$. However I
haven't been able to prove this.
What I know
It easy to see that the following restrictions make the problem easy:

all of the weights are uniform: selecting all of the elements is
clearly optimal.
all of the rankings are complete rankings over $U$: the best
solution is obtained by taking the element with the maximal weight.
the weights are just binary ($w \in \{0,1\}^n$), then selecting all
of the $1$-weighing elements is optimal.

However I haven't been able to find a polynomial time algorithm for
the general case (for example using LP).
On the other hand proving the problem to be $\mathsf{NP}$-hard doesn't
look easy. The structure of the problem instances doesn't allow easy
encoding of other problems. (Note that the hardness of the problem
will come from using the same $L$ for all partial orders, however
using the same weight vector for all of them makes proving hardness
not straight forward). I have unsuccessfully tried reducing some
$\mathsf{NP}$-hard problems like Subset-Sum, NAND-Circuit-SAT, etc. to
the decision version of this problem (is there a subset such that
$r(L) \geq k$).
A matching IP can be constructed quiet easily for a given instance of
the problem, but I don't see any sufficient resemblance to any problem
that I know of.
Question
Do you know the complexity of this problem?
Are there any references studying the complexity of similar optimization problems?
How would you prove that this optimization problem is $\mathsf{NP}$-hard? (if it is indeed hard).

Well, here's a possible solution:

The reduction will be from 3SAT.

Input: $m$ DNF clauses $(\varphi_1,\ldots,\varphi_m)$ over $n$ variables $(x_1,\ldots,x_n)$.

Reduction:
Create a set of items composed of two items for every variable: $x_i, \overline x_i$, corresponding to a $True$ assignment to either the variable $x_i$ or its negation, plus one auxiliary item $t$.
Let the price of all items $\{x_i,\overline x_i\}_{i=1,…,n}$ be $1$, and the price of $t$ be $1.5$.

Create two sets of consumers:

Set 1: Validity rankings: this set of consumers will encode the validity constraints on the assignments to $x_1,\ldots,x_n$. Namely, that exactly one out of every $\{x_i,\overline x_i\}$ is set to $True$ (i.e., taken by the algorithm).
For every $i=1,\ldots,n$ create four partial rankings:

$\sigma_{i1}: x_i\succ t\\
\sigma_{i2}: \overline x_i \succ t \\
\sigma_{i3}: x_i \succ \overline x_i \\
\sigma_{i4}: x_i \succ \overline x_i$

Taking $t$ can never hurt, so we assume that it's always chosen. If both $x_i$ and $\overline x_i$ are selected, we get a payoff $4$. If none of them is selected, we get a payoff of $3$. If one of them is chosen, we get a payoff of $4.5$.

Set 2: Clause rankings.
For each clause of the form $\varphi_j=\ell_{j1} \vee \ell_{i2} \vee \ell_{j3}$, we create a ranking: $\sigma_j: \ell_{j1} > \ell_{j2} > \ell_{j3}$. If $\varphi_j$ is satisfied, it means that at least one of the items corresponding to $\ell_{j1}, \ell_{j2}$, and $\ell_{j3}$ is selected, which gives an extra payoff of $1$ from ranking $\sigma_j$.

Now, the 3CNF formula is satisfiable if and only if there is a set of items that gives a payoff of $m+4.5n$.


Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain? Consider the following variant of a zero-knowledge proof that two graphs, $G_1$ and $G_2$, given by adjacency matrices $M_1$ and $M_2$, respectively, are not isomorphic.

Here Peggy the prover wants to show Vicky the verifier that $G_1 \not\cong G_2$, where both $G_1$ and $G_2$ have $n$ vertices.

Peggy and Vicky agree on a small number, say $r$, of generators $\pi_1,\pi_2,\cdots,\pi_r$ of the symmetric group $S_n$ on the $n$ vertices
Vicky (secretly) tosses a fair coin $i\in \{0,1\}$ to determine to which graph $G_i$ she will permute the vertices
Vicky (secretly) chooses $t$ random numbers $g_1,g_2,\cdots,g_t\in[r]$, and applies the (concatenated) permutation $\pi_{g_1}\pi_{g_2}\dots\pi_{g_t}$ to the vertices $M_i$, to generate a new matrix, $M_3$
Vicky presents $M_3$ to Peggy
Peggy must deduce $i$ from $M_3$, that is, she must deduce which of the graphs $G_1$, $G_2$ Vicky chose in step 1

A difference between a standard graph non-isomorphism protocol and the present protocol is in step 3.  That is, conventionally in step 3, Vicky just randomly chooses any old element $\pi\in S_n$ to apply to the graph $G_i$, but in the above protocol in step 3, Vicky walks along the Cayley graph of $S_n$ with generators $\langle\pi_1,\pi_2,\cdots,\pi_r\rangle$ a total of $t$ times.

Notice that because each step of the Markov chain is, by definition, an invertible permutation of the configuration space (the configuration space being the set of all adjacency matrices equivalent to $M_i$), such a walk is a doubly-stochastic Markov chain, meaning each column (resp. row) of the transition matrix sums to $1$.  Thus, after the selected adjacency matrix $M_i$ is properly mixed, the matrix that Vicky will present to Peggy is uniformly distributed over all matrices isomorphic to $G_i$.  Accordingly, if $G_1\cong G_2$, then Peggy would not have better than even chance of deducing $i$, because she will just be given two random matrices isomorphic to $G_i$; hence, the protocol is sound.

A key concern is that we need to make sure that the matrices are properly mixed, that is, that the number of steps $t$ along the Cayley graph is large enough to mix the given graphs to the limiting distribution.  I believe, although I can't prove it for now, that for most generating sets $\{\pi_1,\pi_2,\cdots,\pi_r\}$ of the symmetric group $S_n$, $t$ is probably $O(\log n)$.

But, now to generalize, given any two elements chosen from any discrete configuration space, not just adjacency matrices representing graphs, I think we have a sound zero-knowledge protocol to show that the two elements are not in the same equivalence class, as long as we can construct a fast-mixing doubly-stochastic Markov chain to walk through the configuration space.

  Has such an approach to zero-knowledge proofs using doubly-stochastic Markov chains been studied before?

As one example,  we may apply such a protocol to some problems in discrete robot motion non-equivalence, rather than adjacency matrices of graphs. That is, we can have a sound zero-knowledge protocol that a discrete robot in a particular position cannot be converted to another position, using a fixed set of invertible generators.  Rather than deciding only one element of the symmetric group $S_n$, Vicky must choose a particular path along a Markov chain, where each state is an element of the configuration space and each transition is given by one of the generators of the robot.  After mixing, the test element of the configuration space will be chosen uniformly from all elements of the configuration space in the same equivalence class as the given robot configuration.

This seems to be explicit or at least implicit in Lutomirski's 2011 "Component mixers and a hardness result for counterfeiting quantum money" - arXiv

Lutomirski formally defines component mixers as a family $\{M_i\}$ of one-to-one maps between elements of a set $S$ partitioned into $\{S_1,S_2,\cdots,S_c\}$.

He gives a number of example $S$'s, such as the set of all graphs on $n$ vertices, where each partition $S_1,S_2,\cdots,S_c$ corresponds to different isomorphism classes of graphs.  Each element $g\in S$ is a given graph on $n$ vertices, and is a member of only one partition $S_g$.  "Mixing" means to randomly draw another element $g'$ from the same $S_g$.

He notes that for many sets $S$ one can mix easily enough, with permutations or straight-line-programs.  Otherwise, he comments that:

  "In general, given a Markov chain over $S$ that does not mix between components but mixes rapidly over each component, each step of which consists of choosing uniform random sample from a set of invertible rules and applying that rule, then iterating that Markov chain to amplify its spectral gap will give a component mixer."

Lutomirski goes on to provide a $\mathsf{coAM}$ protocol for determining whether the number of components (partitions) is greater than $1$.