What is simplest polynomial algorithm for PLANARITY?

I am going to describe an algorithm. I am not sure it qualifies as "easy" and some of the proofs are not so easy.

First we break the graph into 3-connected components, as mentioned by Chandra Chekuri.

Break the graph into connected components.
Break each connected component into 2-connected components. This can be done in polynomial time checking for each vertex $v$ of each 2-connected component $G_i$ whether $G_i-v$ is connected.
Break each 2-connected component into 3-connected components. This can be done in polynomial time checking for two distinct vertices $v,u$ of each 2-connected component $G_i$ whether $G_i-\{ v,u \}$ is connected.

We have reduced the problem to checking whether a 3-connected component of the graph is planar. Let $G$ denote a 3-connected component.

Take any cycle $C$ of $G$.
Pin the vertices of $C$ as vertices of a convex polygon. Put each of the other vertices in the barycenter of its neighbors. This leads to a system of linear equations telling the coordinates of each vertex. Let $D$ be the resulting drawing; it may have crossings.
If $D$ has no crossings, we are finished.
Take the vertices $U$ in any connected component of $G-V(C)$. The restriction of $D$ to the induced subgraph $G[U\cup V(C)]$ should be planar. Otherwise, $G$ is not planar. Take any face $F$ in the drawing $D$ restricted to the induced subgraph $G[U\cup V(C)]$, and let $C'$ be the cycle defining $F$. If $G$ is to be planar, then $C'$ must be a facial cycle. (When $C$ is a Hamiltonian cycle, then $C'$ should be constructed using an edge.)
Repeat step 2 with C' instead of C. If the resulting drawing is planar, then $G$ is planar. Else $G$ is not planar.

Remarks:

Arguing that Tutte's spring embedding gives a planar embedding is not straightforward. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology, but it is only for triangulations. Colin de Verdiere discusses the spring embedding in http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , section 1.4. A general reference is Linial, Lovász, Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988).
Solving a linear system of equations in a polyomial number of arithmetic operations is easy via Gaussian elimination. Solving it using a polyonomial number of bits is not that easy.


Suppose that every circuit of depth $C\log^{k+1} n$ and size $Dn^\ell$ can be converted to an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$.

Now suppose we are given a circuit of depth $C\log^{k+2} n$ and size $Dn^\ell$, and assume furthermore that it's a levelled circuit (making a circuit levelled only increases the size polynomially). Make a list of all nodes at levels $C\log^{k+1} n,2C\log^{k+1} n,\ldots,C\log^{k+2} n$. A node at level $\alpha C\log^{k+1} n$ is the value of a circuit of depth $C\log^{k+1} n$ and size at most $Dn^\ell$ whose leaves are nodes at level $(\alpha+1)C\log^{k+1}n$. We can replace each of these circuits by an equivalent circuit of depth $C'\log^k n$ and size $D' n^{\ell'}$. In total, the new circuit will have depth $C'\log^{k+1} n$ and size at most $DD' n^{\ell+\ell'}$. This shows that $NC^{k+1} = NC^k$ implies $NC^{k+2} = NC^{k+1}$.


Has parameterized complexity led to better algorithms?

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems.
In the $k$-Path problem where we are looking for a simple path of length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has applications in computational biology and the biologically interesting paths have length at most 20. Several of the implemented algorithms successfully use the color coding technique [2].
The Clique problem parameterized by the solution size $k$ has presumably no FPT algorithm, but Clique parameterized by the degeneracy $d$ of the input graph has an FPT algorithm. More precisely, all maximal cliques of an $n$-vertex graph can be enumerated in $O(3^{d/3}\cdot n)$ time [3]. Since many real-world graphs (e.g. social networks) have small degeneracy, this running time bound explains why clique enumeration is feasible on these graphs.
I would say there is a crucial difference between the two results. In the case of $k$-Path, the color coding technique is an FPT technique that was developed in theory and was later turned into a practical algorithm. In the case of Clique, the central technique of the FPT algorithm, which, roughly speaking, is to enumerate first the cliques containing a minimum-degree vertex $v$ and then enumerating all cliques not containing $v$, was already known, in some form, before the theoretical analysis and probably used in several implementations. Hence, I would say that for $k$-Path, parameterized algorithmics has led to better algorithms, and for Clique, parameterized algorithmics rather explains why algorithms are good.
[1]: Alon, Yuster and Zwick: Color Coding.  J. ACM 42(4): 844-856 (1995) https://doi.org/10.1145/210332.210337
[2] Jacob Scott, Trey Ideker, Richard M. Karp, Roded Sharan: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. J. Comput. Biol. 13(2): 133-144 (2006)
[3] David Eppstein, Maarten Löffler, Darren Strash:
Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM J. Exp. Algorithmics 18 (2013)


Factoring Cartesian bitwise join of bit vectors

Passing to the dual hypergraphs to look for products.

As you mention in the comments, we may interpret the bitstrings contained in $A$, $B$, and $C$ as edges in hypergraphs.

Vertices are the elements of $[n]$;
An edge $x \in \{0,1\}^n$ contains a vertex $v \in [n]$ if $x_v = 1$.

(Because these are multi-sets, they're actually multi-hyper-graphs. We may consider the edges to have some generic labels to distinguish them.) We may consider the dual hypergraph $H$ in which the vertices and the edges are interchanged; that is, where

The (labelled) bitstrings $x \in \{0,1\}^n$ now distinct vertices, and
A bitstring $x \in \{0,1\}^n$ belongs to an edge represented (that is, labelled) by $e \in [n]$ if and only if $x_e =1$;

— that is, a bitstring $x \in \{0,1\}^n$ describes all of the edges which are incident to it; of which there are always $n$ in this graphical model, albeit some of them may be the "empty edge".
This puts us in a much better position to describe the hypergraph as a product in some conventional manner. The hypergraph $H_C$ obtained from a multiset $C$ now has a composite number of vertices $m$:  we would like hypergraphs $H_A$ and $H_B$ such that $V(H_C)$ has some particular bijective correspondance with $V(H_A) \times V(H_B)$.

A diagonally restricted tensor product of hypergraphs.

Consider the alternative formulation of the problem, replacing bit-wise OR with bit-wise AND, alluded to in the recent revision of the problem. (To do this, we take the bitwise complement of all of the bitstrings.)  The Cartesian bit-wise meet condition (rather than "join", as we're using "$\wedge$" now in place of "$\vee$") corresponds to the existence of a particular bijection $$\varphi: V(H_A) \times V(H_B) \to V(H_C)$$ such that the edge labelled $e \in [n]$ in $H_C$ contains only the vertices $\varphi(a,b) \in V(H_C)$ such that both $a \in V(H_A)$ and $b \in V(H_B)$ are contained in the respective edges labelled by $e$ in $H_A$ and $H_B$. This seems somewhat different from most graph products, in that we do not take combinations of arbitrary edges, but only those with consistent labels.

If we suspended this label consistency condition, the join construction would correspond to a hypergraph tensor product (generalizing the tensor product of graphs, also commonly known as the direct product in the literature), in which we define edge-pairs $(e,f) \in E(H_A) \times E(H_B)$ which contain all vertices $(a,b) \in V(H_A) \times V(H_B)$ such that $a \in e$ and $b \in f$. This glosses over some issues to do with edges which contain $(a,b)$ and $(a,b')$ for a fixed co-ordinate $a$; but the construction we consider is appropriate to hypergraphs, taking the tensor product of the incidence matrices (characteristic functions of the edges, ranging over the vertices) to form the incidence matrix of $H_A \otimes H_B$.
To re-obtain the Cartesian bit-wise join of $H_A$ and $H_B$, we must
restrict to the diagonal edges $(e,e) \in E(H_A) \times E(H_B) =
   [n] \times [n]$, which we re-label by $(e,e) \mapsto e$. Note that $H_A$ and $H_B$ are edge-labelled hypergraphs, as their edges are non-negotiably labelled by the elements of $[n]$ from the formulation of the vertices as bitstrings with a fixed order. (Of course, when we are searching for hypergraphs $H_A$ and $H_B$, re-labelling the edges simply corresponds to considering a different hypergraph.) Selecting the diagonal is a plausible restriction, if somewhat unnatural in the context of graph products.

The resulting reformualtion.

From this, asking "does $C$ arise from the Cartesian bitwise join of $A$ and $B$?" is equivalent to asking:

  Is an edge-labelled hypergraph $H_C$ with $m$ vertices and at msot $n$ edges, with distinct edge-labels selected from $[n]$ isomorphic to the diagonal subgraph (i.e. taking only the diagonally labelled edges) of the tensor product $H_A \otimes H_B$ of two labelled hypergraphs $H_A$ and $H_B$, which also have at most $n$ edges each and also have edges labels over $[n]$?

I'm not sure if you're going to come closer to a natural graph product formulation of than this. I rather suspect that if this does play a deep role in computational complexity that someone has studied something like this; but without knowing what areas of complexity theory it is pertinent to, I would not be able to tell you where to look, beyond perhaps investigating tensor products of hypergraphs.


Bounding Rademacher Averages, with and without chaining

Converting the comment to an answer: See the notes here:
cs.cornell.edu/~sridharan/dudley.pdf
with the dependence on $\sup_f \hat E[f^2]$


Intuitive explanation behind Goemans-Williamson randomized rounding

Great intuitive explanations above by Sasho Nikolov and Neal Young. Here's another one Eden Chlamtáč emailed in:

Well, the intuition is that the SDP solution assigns greater weight in
the objective function to edges whose endpoints that are placed
farther apart in the vector solution, so it makes sense to cluster the
set of vertices geometrically into two contiguous sets. A random
hyperplane is the simplest way of doing that, and it happens to work
well.


You can use essentially any centroid-based clustering algorithm to define a notion of "coherence" or "purity" of a cluster. Let's say you've chosen some particular metric $||\cdot||$ on $\mathbb{R}^n$ (I'm using norm notation but any metric will do). Using your notation, $S_i$ is the $i$th "cluster". For each $S_i$, find the* point $c_i\in\mathbb{R}^n$ that minimizes
$$ F(c):=\sum_{x\in S_i}||x-c||\qquad(*)$$
over all $c\in\mathbb{R}^n$. Let $F(c_i)$ be the purity score of $S_i$; it might actually be better to consider the normalized version $F(c_i)/|S_i|$. Smaller values means more homogeneity or "purity".

*How to do this computationally? Try (sub)gradient descent. If the minimum is not unique then break ties arbitrarily.


$\mathsf{NP} \cap \mathsf{coNP}$ as oracle

Yes. Indeed, an oracle $A$ satisfies $\mathsf{NP}^A=\mathsf{NP}$ if and only if $A \in \mathsf{NP} \cap \mathsf{coNP}$. This class is called $\mathsf{Low(NP)}$ or sometimes $\mathsf{L_1 P}$ (see the link and the paper cited there for more of an explanation of the low hierarchy in general).

Your intuition about "determinism" is actually somewhat correct (although it's not deterministic enough for us to conclude $\mathsf{P} = \mathsf{NP} \cap \mathsf{coNP}$). Try this as an exercise and you'll see this intuition vindicated: first show - carefully, spelling out the details - that if $A \in \mathsf{P}$, then $\mathsf{NP}^{A} = \mathsf{NP}$. Figure out exactly the part of your proof that doesn't work if you only assume $A \in \mathsf{NP}$, and then realize why that part does work when $A \in \mathsf{NP} \cap \mathsf{coNP}$.

(Showing the converse is not too difficult either: $\mathsf{NP}^A = \mathsf{NP}$ implies $A \in \mathsf{NP} \cap \mathsf{coNP}$.)


Busy beaver candidate elimination: Minimum space requirements

There are many methods for detecting that specific TMs will run infinitely. As Marzio mentioned, Heiner Marzen's page and papers provide almost all of the currently used methods.

The method you describe is a great simple requirement. Specifically, if we know that the TM has only moved around on a small tape of size $N_{tape}$, then the exact configuration at every step so far can be described by (1) the symbols at each of these $N_{tape}$ cells, (2) the position of the reading head and (3) the TM state. Thus there are $|Q| \cdot N_{tape} \cdot |S|^{N_{tape}}$ possible configurations (Where $|Q|$ is the number of states and $|S|$ is the number of symbols). So, if the TM has taken more than that many steps of computation, you know that it must have been in one configuration at least twice and thus that it will infinitely repeat.

However, I don't think this method works very often in practice because it is more common for TMs to run off infinitely in one direction than to stay on a small section of tape.


Added: After reading Per’s comments, I think that this answer is just a (poor) variation of the Tillich-Zemor hashing algorithm which is already mentioned in the question.  I withdraw this answer, but I leave it hoping that it (and the comments) may be informative for some readers.

Edit: An earlier revision of this answer suggested to use a monoid operation on [m], but as Per pointed out in a comment, it is desirable to use a group operation.

This answer is about building a hash function for hash tables which is easy to implement.  A provable guarantee on the quality is not expected.

Assuming that you already have a hash function for each element of a sequence to a finite set [m]={1, …, m}, how about interpreting each element of [m] as an element in a finite group G and using the group operation on G?  You can use any mapping from [m] to G, but it is desirable that the mapping be injective so that we do not lose the information in the hash value of each element.  It is also desirable that the group not be commutative so that the hash function can catch the difference in the order of the elements in a sequence.

I do not know much about finite groups which allow fast operations, but I guess that such groups are known in coding theory.  Using the symmetric group of order at least m may not be so bad.


If you weaken the time bound very slightly from linear, the answer is definitively no. Probably a more delicate construction will work for linear time.

Let $f(n)$ be any monotone increasing time-constructible function $\geq n$. Then there is a language $L \in \mathsf{DTIME}(n^2)$ (in fact, in time $n f^{-1}(n)$, e.g. when $f(n)=2^n$ this is $n \log n$) such that any enumerator for that language requires $f(n)$ delay between enumerating the $n$-th and $(n+1)$-st strings. In particular, $L = \{0^{f(m)} : m \geq 0\}$ has this property.

$L$ can be decided in time $n f^{-1}(n)$: if $x \neq 0^{n}$ then $x \notin L$. Otherwise, compute $f(1), f(2), \dotsc$ until $f(k) \geq n$. In fact, in the computation of $f(k)$, if the counter ever surpasses $n$, stop. This ensures that each computation of $f(i)$ takes at most time $n$. The largest $k$ for which such a computation needs to be done is $\lceil f^{-1}(n) \rceil$, giving the claimed runtime.

Finally, any enumerator for $L$ requires delay $f(n)$ between strings in the worst case. If the enumerator enumerates $L$ in lexicographic order, this clear because it takes time $f(n)$ to just write down the next string. If the enumerator is out of order finitely often, the same is still true after the finitely many. If the enumerator is out of order infinitely often, then infinitely often it is enumerating longer strings earlier than otherwise, hence takes time more than $f(n)$.


Why is lambda calculus so "function" oriented?

The idea of how to 'mechanize mathematical proof' was a hot topic at the time; more specifically, Hilbert posed the Entscheidungsproblem - could we have a machine in some factory somewhere that takes mathematical statements in, and outputs proofs of the truth or falseness of those statements, as easily as machines might weave cotton or drill holes in steel?

If one was 'merely' dealing with the mathematical concept of a function, then we can define such a function whose input is a mathematical statement (formally, a first order sentence in the language of number theory) and whose output is either 'True' or 'False'.

This is perfectly satisfactory as a mathematical function (once one has properly defined what it means for a statement to be true or false) but now one has a constructibility problem; the mere existence is not useful when your main goal is to actually evaluate this function on given inputs.

The purpose of the lambda calculus, and equivalent models such as Turing machines, is to provide this construction. When a mathematical function matches the input/output behavior of a Turing machine, or (equivalently) has a representation in terms of the lambda calculus, then such a function is called 'computable'.

Gödel's Incompleteness Theorem states that the true/false function described above is not computable. It is generally believed that the only mathematical functions that can be evaluated in the 'real world' are exactly the computable ones (this is the Church-Turing Thesis). Therefore, despite existing as a mathematical function, we have absolutely no way to evaluate that function in general (of course, there are still specific inputs where we can evaluate that function)


Can a non-competitive deterministic algorithm be k-competitive if randomized?

Imagine having to predict 0 or 1 on every round, and we are counting the number of correct predictions.  Every deterministic strategy has an adversarial sequence that makes it always predict incorrectly. Hence, no competitive ratio is possible.

However, the randomized strategy of flipping a coin on every round will be $2$-competitive with the best constant prediction (in expectation).


I think a general polynomial time solution to this would be able to be used to solve k-SAT.

For each variable create two vertexes corresponding to true and false and connect them by an edge. Start by assigning k to to the number of variables (half the number of vertexes), and each of their f values to 1. Let not being in S mean true or false. Now we have a graph where each variable has to be either true or false.

For each OR operation on x variables create one vertex and connect it to the appropriate true/false vertexes.

For each OR operation create a large number Z of auxilary vertexes with an f value of 1, and connect each by an edge to the OR vertex. Increment k by Z for each OR operation. We can see this will force the OR operation vertex to not be a member of S, and all the auxilary vertexes to be in S.

Now assign the f value of each OR vertex to Z+x-1. Z of these will be taken by the auxilary vertexes.  The OR vertex is not in S, so this means at maximum x-1 of the connected variable vertexes can be in S, so at least one of the variable nodes connected to an OR vertex will have to not be in S.


Complexity of DFA intersection in this specific case?

The precise bound is $2^n$. The lower bound was given in the comments: the state complexity of $A^*a_1A^* \cap \dotsm \cap A^*a_nA^*$ is $2^n$.
For the upper bound, it suffices to observe that if $B$ and $C$ are subsets of the alphabet $A$, then the language $B^*CA^* = (B - C)^*CA^*$ is recognised by a 2-state DFA. It follows that the complexity of the intersection of $n$ such languages is upper bounded by $2^n$.


Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

This answer is incorrect.

Your friend is right. Your problem (as interpreted by Sasho) does not place any restriction on the cardinality of the matching $C$. Therefore, choose $C$ to be a matching between the pairs in $R$. Then for any positive integer $k$, the distance between every pair in $R$ is less than $k$.

Your problem becomes interesting if you force paths to contain edges from both the matching $C$ and the path $P$.


Distributed Consistency using Quorum approach

The idea behind implementing consistency with a quorum is to maintain consistency in one group (that contains the majority of replicas) and forcing, by construction, that reads and writes cannot violate the consistency within that group.

This is done by only allowing updates within a group of replicas that contains the majority of replicas, so that at least one node witnesses all the updates; this is related to the second condition you've mentioned. In more details, consider a scenario for writing:

To complete a write, a client must successfully place the updated data item on more than N/2 (i.e. a majority of) replicas. (The updated data item will be assigned a new version number that is obtained by incrementing its current version number.)
Since the write quorum engages a majority of the replicas, two distinct write operations cannot succeed at the same time. (There do not exist two distinct groups that contain majorities of replicas.)
Therefore, all write operations are serialized and therefore consistency is guaranteed. (At least one node has to be included in two consecutive write operations, while that node will have the highest current version number.)

Note that consistency overall, has to be ensured with respect to both writing and reading. (As an extreme example, a system that does not perform reads will always be consistent.) To that end, mechanisms for distinguishing newer from older values is needed (e.g. a simple version number, as mentioned before) for achieving consistent read operations. This is related to the first condition you've mentioned:
in turn, reading can be achieved with N + x - Nw replicas (where Nw + Nr = N + x, since Nw + Nr > N). Thus the intersection
of the read quorum (of Nr nodes) and the write quorum (of Nw nodes) cannot be empty, so reads cannot overlap with writes, i.e. each read will have to consult at least one replica with the current data item (determined by it's version number).

Note that to control concurrency, mechanisms such as two-phase locking can be used -- for initial query from a set replicas, a reader can use read locks and a writer can use write locks. The locks are released after the operation completes or aborts.

The read/write quorum scheme was first proposed in [1] and it was later generalized into the form you've mentioned in [2]. (These papers cover the topic in more detail.)

[1] Thomas, Robert H. "A majority consensus approach to concurrency control for multiple copy databases." ACM Transactions on Database Systems (TODS) 4.2 (1979): 180-209.

[2] Gifford, David K. "Weighted voting for replicated data." Proceedings of the seventh ACM symposium on Operating systems principles. ACM, 1979.


Circuit and Formula Lower Bounds for Separating Sparse Sets of Strings

Yes, any such pair can be separated by a formula of size $O(n)$. More generally, any disjoint pair $P,N\subseteq\{0,1\}^n$ of size $s=|P|+|N|$ can be separated by a decision tree of size $O(s)$, which can be implemented as an $O(s)$-size formula by replacing each query node with $(p\land\cdots)\lor(\neg p\land\cdots)$.
It suffices to observe that there exists a decision tree such that every path to a leaf is consistent with exactly one element of $P\cup N$ (which means that it has $s$ leaves and $s-1$ inner nodes). One way to show this is to consider the full binary tree of height $n$ that queries all variables along every path, take its subtree consisting of the union of paths to leaves in $P\cup N$, and eliminate inner nodes that do not branch.
Another way is to build it inductively. Start with the trivial one-element decision tree, and repeat: pick a leaf $x$ that is consistent with $\ge2$ elements of $P\cup N$, and make $x$ into a query node for some variable $p$ such that each of the $p$ and $\neg p$ branches is still consistent with an element of $P\cup N$. Notice that this actually gives a polynomial-time algorithm to construct the decision tree, given $P$ and $N$.
[The first version of this answer presented a different construction, using a linear hash function $h\colon\mathbb F_2^n\to\mathbb F_2^{O(\log s)}$ such that $h(P)\cap h(N)=\varnothing$. This only gives a separating circuit of size $O(n\log n)$, or $O((n+s_0)\log s)$ in the general case, where $s_0=\min\{|P|,|N|\}$.]
For $s\le n$, the $O(s)$ bound is optimal up to a multiplicative constant: it is easy to see that any circuit separating $P=\{0^n\}$ from $N=\{0^i10^{n-1-i}:i<s-1\}$ must
include all of the first $s-1$ variables, and as such it has size at least $s$.
For larger $s$, an optimal bound is given by Theorem 1.1 of Andreev, Clementi, and Rolim [1] (with $\varepsilon=1/2$): the maximum circuit size required to separate $P,N\subseteq\{0,1\}^n$ with $|P|+|N|=s$ is
$$\Theta\left(\frac s{\log s}\right)+O(n).$$
They do not seem to particularly care about the case of small $s$, but combined with the discussion above, we obtain the following complete characterization:

Theorem: The maximum circuit size required to separate disjoint pairs $P,N\subseteq\{0,1\}^n$ with $|P|+|N|=s$ is
$$\begin{cases}\Theta\left(\frac s{\log s}\right)&\text{if }n\log n\le s,\\
\Theta(n)&\text{if }n\le s\le n\log n,\\
\Theta(s)&\text{if }s\le n.\end{cases}$$

And while it does not yield improvement on any of the above, let me mention the following fun fact: for every nonempty $X\subseteq\{0,1\}^n$ of size $s=|X|$, there exists $I\subseteq[n]$ of size $|I|<s$ such that the restrictions $x\restriction I\in\{0,1\}^I$ of the elements $x\in X$ are pairwise distinct. To see this, fix $I$ of minimal size with this separation property. For each $i\in I$, the minimality of $I$ implies that there exist $x_i,y_i\in X$ such that $x_i\restriction I$ and $y_i\restriction I$ differ only at the $i$-th position. Put $E=\{\{x_i,y_i\}:i\in I\}$. Then $(X,E)$ is a graph with $s$ vertices and $|I|$ edges, and it is acyclic (if we start from a $\{0,1\}$ vector, and flip a sequence of distinct bits, we cannot arrive where we started from). Thus, $s>|I|$.
Reference:
[1] Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim: Optimal bounds for the approximation of boolean functions and some applications, Theoretical Computer Science 180 (1997), no. 1–2, pp. 243–268, doi: 10.1016/S0304-3975(96)00217-4.


K-NN or matrix factorization for discovering correlated features?

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

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

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


Upper bound to number of closed itemsets

The bound is $2^{\min(n, m)}$. It is an upper bound because no two "formal concepts" (i.e., closed itemsets with their respective transaction sets) can have the same subset of items or the same subset of transactions. Considering $D$ as an $n$ by $m$ matrix of $0$ or $1$ such that each cell indicates whether item $i$ is part of the $j$-th transaction of $D$, you can reach the bound by filling the matrix to '1' and setting to '0' a "diagonal" (well, not really a diagonal since the matrix is rectangular). If you wish, you can then permute the rows and/or the columns and the number of closed itemsets obviously remains the same. Any number of '1' out of the square matrix where there is the diagonal can be turned into '0' too.

Quite recently, Richard Émilion published in Discrete Applied Mathematics the average and the variance of the number of (frequent) closed itemsets in a rectangular 0/1 matrix with a Bernoulli distribution of the '1's: http://www.univ-orleans.fr/mapmo/membres/emilion/publ/sizeofgl.pdf

That is interesting because real-life datasets usually are very sparse. I am not aware of any bound of the number of (closed) itemsets w.r.t. the density. I believe the formula would not be beautiful at all!

I have already told that to a3nm at ICDT'14: you guys (I am not a theorist, just a data miner) want to read about the so-called "Formal Concept Analysis" (FCA): https://en.wikipedia.org/wiki/Formal_concept_analysis


Embedding a graph in the euclidean space

I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/Semidefinite_embedding. The paper introducing this approach is "Learning a kernel matrix for nonlinear dimensionality reduction" by Weinberger, Sha, and Saul if I am not mistaken.


Why are folded Reed Solomon Codes considered non linear?

Suppose we consider $s$-folded Reed-Solomon codes that are based on polynomials over a field $\mathbb{F} = \mathrm{GF}(p^t)$. Then the alphabet of those codes is of size $p^{t \cdot s}$. Hence, in order to be linear, those codes should be closed under multiplication by scalar from the field $\mathbb{F}' = \mathrm{GF}(p^{t \cdot s})$. There is no apparent reason why they should be closed under such operation.

However, it is true that they are closed under multiplication by scalar from $\mathbb{F}$. In other words, the codes are $\mathbb{F}$-linear.


Was the reason that Computers were invented to solve a philosophical question about the foundations of mathematics?

Just an extended comment, for those who didn't notice that "This guy" in the question is not the author of the linked blog, but refers to Gregory Chaitin.

The sentence is from the lecture: A Century of Controversy over the Foundations of Mathematics; the transcription can be found here.

It seems interesting (I'm going to read it now)!

...
Okay, I'd like to talk about some crazy stuff. The general idea is that sometimes ideas are very powerful. I'd like to talk about theory, about the computer as a concept, a philosophical concept.

We all know that the computer is a very practical thing out there in the real world! It pays for a lot of our salaries, right? But what people don't remember as much is that really---I'm going to exaggerate, but I'll say it---the computer was invented in order to help to clarify a question about the foundations of mathematics, a philosophical question about the foundations of mathematics.

Now that sounds absurd, but there's some truth in it. There are actually lots of threads that led to the computer, to computer technology, which come from mathematical logic and from philosophical questions about the limits and the power of mathematics....


an efficient algorithm for mismatch profile

Upd: Space complexity improved to just $O(2^LML)$ which makes the solution much more practical.

The problem can be solved at least in $O(M^2NL + 2^L MNL)$ time and $O(2^L ML)$ additional memory as follows.

Let's denote by $S^j$ the prefix $s_1 s_2 \ldots s_j$ of $S$. First, for each binary string $s$ of length $L$ precompute mismatch profile $mp'(s, i, j, k) = mp(s, S_i^j, k)$ of that string with all prefixes of length $j$ of all strings $S_1, S_2, \ldots, S_M$. That will require $O(2^L MNL)$ memory to store and can be done in $O(2^L MNL)$ in straightforward way.

Then iteratively build mismatch profiles $mp_j(i,i',k)$ for each pair of $j$-prefixes of $S_1, S_2, \ldots, S_M$ for $j=L,L+1,\ldots,N$, so $mp_N(i,i',k)$ will be your desired answer. Let's denote by $end(S)$ the suffix of $S$ of the length $L$ (i.e. $S[(length(S)-L+1) \ldots length(S)]$). Notice that $$
\begin{align*}
mp_j(i,i',k) = &mp(S_i^{j-1},S_{i'}^{j-1},k) + mp(end(S_i^j), S_{i'}^{j-1}, k) + \\&mp(S_i^{j-1}, end(S_{i'}^j),  k) + mp(end(S_i^j), end(S_{i'}^j),k)
\end{align*}
$$ which is indeed
$$
\begin{align*}
&mp_{j-1}(i,i',k) + mp'(end(S_i^j), i', j-1, k) + \\ &mp'(end(S_{i'}^j), i, j-1, k) + mp(end(S_i^j), end(S_{i'}^j),k)
\end{align*}

$$

The first 3 terms of that sum are already computed and the last one can be computed in amortized $O(1)$ time (it is $O(L)$ but you need to compute it only once for all values of $k$ with fixed $j,i,i'$). Thus you can compute $mp_j$ using $mp_{j-1}$ and $mp'$ in $O(M^2L)$ time, which leads to $O(M^2NL)$ term in the total complexity.

Notice that you need values of $mp'$ only for a fixed prefix length on each iteration. Thus you can compute $mp'$ not all of a piece at the beginning but rather iteratively for $j=L,L+1, \ldots, N$ in between of $mp_j$ computations. That can be easily done in $O(2^LML)$ time per iteration (so total complexity does not change) but requires only $O(2^LML)$ additional memory.

The main issue of this solution is exponential in $L$ time.

P.S. If $L$ is too small ($2^L < N$) then the naive method can be improved to $O(M^2 4^L)$ time by calculating the number of occurrences of each string $s$ of length $L$ in $S_i$. This allows you to process all different substrings of $S$ of length $L$ in $O(2^L)$ time instead of $O(N)$ (you will need to precompute pairwise differences between all such substrings first).


Assuming your polytopes are closed, I don't think this is true. Each of your polytopes $P_1,P_2,Q$ is a product of (possibly unbounded) intervals $I_i^1$, $I_i^2$, or $I_i^Q$, respectively, for $i=1,\dots,d$. Then $CH(P_1\cup P_2)$ is axis-parallel iff there are no $i,j$ with $i\neq j$ such that one of the following holds:

$I_i^1\not\subseteq I_i^2$, $I_j^1$ has a lower bound $a_j^1$, and $I_j^2$ has a lower bound $a_j^2<a_j^1$,
$I_i^1\not\subseteq I_i^2$, $I_j^1$ has an upper bound $b_j^1$, and $I_j^2$ has an upper bound $b_j^2>b_j^1$,
$I_j^2\not\subseteq I_j^1$, $I_i^1$ has a lower bound $a_i^1$, and $I_i^2$ has a lower bound $a_i^2<a_i^1$,
$I_j^2\not\subseteq I_j^1$, $I_i^1$ has an upper bound $b_i^1$, and $I_i^2$ has an upper bound $b_i^2>b_i^1$.

These are the cases in which $P_1\cup P_2$ (and therefore the convex hull) contains points $x,y$ with $x_i\neq y_i, x_j\neq y_j$, but at least one of the points obtained by replacing e.g. $x_i$ with $y_i$ in $x$ is not in the convex hull. This can be checked in polynomial time.

If the convex hull is axis-parallel, then it equals $Q$ iff $I_i^Q=I_i^1\cup I_i^2$ for all $i$, which also can be checked in polynomial time.


Number of subgraphs with given edge parity

This problem is tractable.

Let $G = (V,E)$ be the input graph with $|V| = n$ and let $e$ and $o$ be the number of vertex-induced subgraphs of $G$ with an even and odd number of edges respectively. Of course, $e + o = 2^n$. In polynomial time, we can compute $e - o$, which I explain below.  With two equations and two unknowns, we can solve the linear system to determine the value of $e$.

From $G$, we create an instance of a counting constraint satisfaction problem (#CSP). Every vertex in $V$ is a Boolean variable and every edge in $E$ a constraint $f$ that depends on its incident vertices. The constraint $f$ evaluates to 1 unless the both vertices are assigned 1, in which case, $f$ evaluates to -1. The symmetric notation for this constraint is $[1,1,-1]$.

Now the answer to this #CSP instance is (by definition)
$$\sum_{\sigma : V \to \{0,1\}} \prod_{e \in E} f(\sigma|_{I(e)}),$$
which is a sum over all vertex subsets, the product of the outputs of every constraint $f$, where $I(e)$ is the vertices incident to $e$ and $\sigma|_{I(e)}$ is the restriction of $\sigma$ to $I(e)$.

Fix a subset of $V$. Assigned 1 to the vertices in the subset and 0 to the vertices not in the subset. If either vertex incident to the same edge is assigned 0, then this edge is not in the vertex-induced subgraph and the constraint $f$ on this edge contributes a 1 to the product, which has no effect. If both vertices incident to the same edge are assigned 1, then this edge is in the vertex-induced subgraph and the constraint $f$ on this edge contributes a -1 to the product.

Vertex-induced subgraphs with an even number of edges contribute a 1 to the sum while vertex-induced subgraphs with an odd number of edges contribute a -1. Thus, the answer to this #CSP instance is exactly $e - o$.

Since the constraint $f$ is affine, this #CSP is tractable. The polynomial algorithm for any set of affine signatures is given in The Complexity of Complex Weighted Boolean #CSP by Jin-Yi Cai, Pinyan Lu, and Mingji Xia. There may be a simpler algorithm for this particular case. If such an algorithm is known, it is probably contained in one of the references cited in the above paper.


You're right to look for a reduction from the subset-sum problem. The subset problem is to find a subset $S'$ of $S$ such that $\Sigma_{s' \in S'} s' = t$. But this can be reduced to your interval cover problem with intervals $\{(0, s) : s \in S\}$, $k = t$, $L = 1$. Therefore the interval cover problem is NP-hard.

PS Why don't you make all the intervals, input and output, half-open at the same end? That way you eliminate the finite set of points at which the sum of indicator functions is different.


Does BQP contain any NP-Complete problem?

To the best of my knowledge this is still open.


The particular minimization version which you mentioned does not make much sense, because even deciding whether all triples can be satisfied simutaneously or not is NP-comlpete.  Also, it is easy to see that unless P=NP, for every choice of constants k1 and k2, there is no polynomial-time approximation algorithm for the minimization version of the betweenness problem in the sense that it produces an assignment which violates at most (k1⋅OPT + k2) triples, where OPT is the minimum number of violated triples.  (Just consider the case where OPT=0.)  [Edit: In an earlier revision, I stated that this follows from [CS98], but [CS98] was overkill for it.]

On a tangentially related topic, if you consider the additive approximation of the ratio of (un)satisfied triples, the problem becomes much more interesting.  Chor and Sudan [CS98] showed that for every s∈(47/48,1), it is NP-complete to decide whether a given instance of the betweenness problem is satisfiable or no assignment satisfies more than s fraction of constraints.  In particular, the ratio version is NP-hard to approximate within any constant additive error less than 1/48, and this clearly applies equally to both the maximization version and the minimization version.

For more on approximation of a satisfaction ratio within an additive error, see my answer to the question “Hardness of approximation - additive error” by Raphael Clifford.

[CS98] Benny Chor and Madhu Sudan.  A geometric approach to betweenness.  SIAM Journal on Discrete Mathematics, 11(4):511–523, Nov. 1998.  DOI: 10.1137/S0895480195296221.


The existence of planar distance preserver?

Many years later, it looks like OP has finally answered his own question: Near-Optimal Distance Emulator for Planar Graphs by Hsien-Chih Chang, Paweł Gawrychowski, Shay Mozes, and Oren Weimann was just posted on the arxiv.

The answer to the original question is yes: it is shown that $\widetilde{O}(\min\{t^2, \sqrt{tn}\})$ edges suffice to preserve distances between $|T| =: t$ terminals, which is optimal up to log factors.  In particular $\widetilde{O}(n^{3/4})$ edges suffice for the setting in the OP.  This preserver can also be computed in $\widetilde{O}(n)$ time; I would strongly suspect that the log factors in the size can be removed if we care only about existence and not computation time of the preserver, but I have not rigorously verified this.

(On a less formal note, I find this result really amazing.  Congrats!)


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

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.


Can Merlin convince Arthur about a certain sum?

I am posting this seperately from my earlier special case, because I believe it is a different approach to the problem, and has little relation to my other answer. It may not be exactly what you are looking for, but it is simple, and gets close.

There is a proof which Arthur will always accept whe the proof is correct, but will reject with probability $\frac{1}{(\log \log N)^{2+o(1)}}$. Here's how it works: Merlin sends Arthur the pair $(p_i,c_i = p_i^k\mbox{ mod }m)$ for each prime $p\leq N$. Arthur verifies the sum (taking time $O(N/\log(N)) \times O(\log(N)) = O(N)$). Arthur the checks that the correct number of primes was supplied (by calculating $\pi(N)$) which is sublinear in $N$. Lastly, for $S N$ random pairs, he confirms that $p$ is prime and that $p_i^k \equiv c_i \mbox{ mod }m$. This takes time $SN~O((\log \log N)^{2+o(1)})$. Taking $S = (\log \log N)^{-(2+o(1))}$, we obtain a linear time scaling. Thus, a fraction $S$ of all pairs are verified. If any of these fail, Arthur will of course reject. For Arthur to accept an incorrect proof, there must be at least one pair which fails one of these two tests (or the number of pairs must be less than $\pi(N)$ which was earlier checked). Thus as a fraction $S$ of all pairs are checked, the test will fail for an incorrect proof with probability at least $S$.

Note that for large $N$ this is much much better than random guessing, which succeeds with probability $\frac{1}{m} = \frac{1}{O(N)}$.


I'm posting my comment as an answer, at the request of the OP.

Arithmetic Hierarchy AH is a class of decision problems defined as below:

Let $Δ_0 = \Sigma_0 = \Pi_0 = R$. Then for $i>0$, let

$Δ_i = R^ {\Sigma_{i-1}}$.
$\Sigma_i = RE ^{\Sigma_{i-1}}$.
$\Pi_i = coRE ^{\Sigma_{i-1}}$.

Obviously, AH $\subseteq$ ALL. On the other hand, "each level of AH strictly contains the levels below it." (As pointed by Robin Kothari in a comment above). Therefore, $ALL\setminus(RE \cup coRE)$ is nonempty.


I don't think one can make a blanket statement on whether primal decomposition methods or dual decomposition methods are more efficient. The efficiency is dictated by the structure of the problem; primal decomposition and dual decomposition are ways of exploiting this structure to develop efficient algorithms.

The key aspect in making a choice between these methods is the kind of parametrization the master brings about on the slaves. Fo e.g., sometimes it is convenient (in terms of theory or practice) to have the parametrization in the objective function of the slave problems instead of having it in the constraints. If the parametrization happens to appear in the constraints (and it has suitable structure), one can try to dualize the slave problem to get in the objective.

In the slides you have linked, the effort seems to be in exploiting the structure for parallelization of the solution of subproblems. For parallelization one would require subproblems that are independent of each other. If there is a natural separability in the constraints, dual variables can be used to parametrize the problem and thereby create such subproblems.

Edit: I repeat once again that structure is important in determining the choice of the method. I am still not completely clear on the structure afforded by the problems you have in mind. Based on the information given, this is my best attempt at answering your question.

From the examples you have added, the problems appear to be what can be called "nearly separable". In essence, these problems appear to be variants of the problem $\min \{\sum_{i=1}^n f_i(x_i) : (x_1,...,x_n) \in K\}$, where $K$ is a constraint that has a separable structure. For example, the constraint $(x_1,...,x_n) \in K$ may be $\sum_ix_i =b$, where $b$ is a vector of appropriate size. By separable structure I mean that the optimal values of variables $x_1,...,x_n$ can be chosen independently of each other. If one looks at the problem as a whole, the objective functions are decoupled in individual variables, but because of the coupling in $K$ these variables cannot be independently optimized. However because this coupling in $K$ is mild, one can still salvage separability. Dual decomposition lets you separate the variables when they are coupled in the constraints. If the variables were coupled in the objective, one may have to employ primal decomposition (as in Boyd's slides). One may of course try to reformulate problems to bring them in some or the other form that one is comfortable using.

To demonstrate separation by dual decomposition, define the Lagrangian $L(x,\lambda) =\sum_i f_i(x_i) + \lambda^T(\sum_i x_i)$. If $(x,\lambda)$ is a saddle point of $L$, then $x$ solves the original problem. A dual decomposition method would for each value of $\lambda$, minimize $L(x,\lambda)$ over $x$, altering $\lambda$ until a saddle point is found. The minimization in $x$ is easier, in particular separable and parallelizable.


Complexity of optimization over unitary group

Sorry I'm late!  In quantum computing theory, there are lots of examples of optimization problems over the unitary group that, surprisingly (at least to me), are solvable in (classical) polynomial time by reduction to semidefinite programming.

Here was an early example: solving a problem of mine from 2000, in 2003 Barnum, Saks, and Szegedy showed that Q(f), the quantum query complexity of a Boolean function f:{0,1}n→{0,1}, can be computed in time polynomial in 2n (i.e., the size of f's truth table).  I had thought about this but couldn't see how to do it, since one needs to optimize the success probability over all possible quantum query algorithms, each one with its own set of (possibly 2n-sized) unitary matrices.  Barnum et al. reduced to SDP by exploiting a "duality" between unitary matrices and positive semidefinite matrices, the so-called Choi-Jamiolkowski isomorphism.  For a more recent and simpler SDP characterizing Q(f), see Reichardt's 2010 paper showing that the negative-weight adversary method is optimal.

Another important case where this trick has been exploited is in quantum interactive proof systems.  While it's not intuitively obvious, in 2000 Kitaev and Watrous proved that QIP ⊆ EXP. by reducing the problem of optimizing over the exponential-sized unitary matrices that arise in a 3-round quantum interactive proof system, to solving a singly-exponential-sized SDP (again, I think, using the Choi-Jamiolkowski isomorphism between mixed states and unitary matrices).  The recent QIP=PSPACE breakthrough came from showing that that particular SDP could be approximately solved even better, in NC (i.e., by log-depth circuits).

So, whatever your specific optimization problem involving the unitary group, my guess is that it can be solved faster than you think -- if not in some even simpler way, then by reduction to SDP!


Upper bound on the size of a Concept Lattice (Galois Lattice)?

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound.

When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$


Solving linear program with 1 quadratic constraint complexity

Based on posts from or-exchange and some internet reading, the following algorithm works. We adapt the cutting plane method to binary search for variable $y$. For my problem, the upper and lower bounds for all variables are known (but if these are not known, one can find a bound on $y$ by solving the LP by removing the first constraint). Let $l \leq y \leq u$.

Fix $y = (l+u)/2$. This converts the program to a linear program. If the resulting constraints are feasible, update $u(l) = (l+u)/2$. Keep performing the binary search until we reach the optimal solution with an additive $\epsilon_0$. The running time of the algorithm is $O(PTIME)\log\frac{u-l}{\epsilon_0}$.

While this algorithm can find the optimal solution within a small additive constant, I am still not sure about the hardness of the problem for solving exactly. Any comments regarding complexity are welcome!


Why do NP-complete problems not have similar approximation ratios?

Reductions are defined with respect to the decision version of the problems.  Approximation ratios for their optimization versions are a separate question, which seems related but doesn't necessarily have to be.  So to answer your question with a question, from a philosophical perspective, why should you expect the class NPC to preserve approximation ratios when it isn't defined with respect to them in the first place?


Completeness of Constraint Typing (type inference) question regarding $\sigma'$

Assuming that this is from Chapter 22 of Pierce's book, what's going on is that Pierce had to strengthen the statement of the theorem slightly to deal with all the fresh constraint variables tracked in $\mathcal{X}$.

The naive statement of completeness  would be is that

  If $\Gamma \vdash t:S|_{\mathcal{X}}C$ and $(\sigma, T)$ is a solution for $(\Gamma, t)$, then $(\sigma, T)$ is a solution for $(\Gamma, t, S, C)$.

Basically, this says that if $(\sigma, T)$ is a solution to the type inference problem, then it will be a solution of the generated constraints $C$. However, the inference rules in Figure 22-1 sometimes will create some new contraint variables (for example, rule CT-App), all of which are recorded in $\mathcal{X}$.

If the domain of $\sigma$ overlapped with the new variables constraint generation introduced, then you're in trouble, because now we have the possibility of inconsistencies between $\sigma$ and the constraints in $C$. So, instead Pierce proves that:

  If $\Gamma \vdash t:S|_{\mathcal{X}}C$ and $(\sigma, T)$ is a solution for $(\Gamma, t)$ and $\mathrm{dom}(\sigma) \cap \mathcal{X} = \emptyset$, then there exists a $\sigma'$ such that $(\sigma', T)$ is a solution for $(\Gamma, t, S, C)$ and $\sigma'/\mathcal{X} = \sigma$.

So he says that if $(\sigma, T)$ is a solution for $(\Gamma, t)$ that doesn't overlap with $\mathcal{X}$, then there is a solution $(\sigma', T)$ for $(\Gamma, t, S, C)$ such that $\sigma'$ is an extension of $\sigma$ to cover the variables in $\mathcal{X}$.


Please check Theorem 21.5, Section 21 in the book "A probabilistic Theory of Pattern Recognition (1996)" from Devroye, Gyorfi, and Lugosi. I think the following upper bound is valid: VC $\leq$ $k + (d+1)k^2\log k$.


Why did Kolmogorov publish Karatsuba's algorithm?

This paper, in Russian,

  Gricenko, S. A., Karatsuba, E. A., Korolyov, M. A., Rezvyakova, I. S.,
  Tolev, D. I., & Changa, M. E. (2012). Scientific contributions of A. A.
  Karatsuba / Научные достижения Анатолия Алексеевича Карацубы.
  Современные проблемы математики, 16(0), 7-30.

states the following (items 1—3).

Karatsuba presented his algorithm at a seminar led by Kolmogorov.
Kolmogorov prepared an article that had two results of his students, Karatsuba and Ofman. One of the results was Karatsuba's algorithm, the other was an unrelated result of Ofman.
The article clearly attributed the results. It stated that the multiplication algorithm is due to Karatsuba and the other result is due to Ofman.

We can only guess why Kolmogorov did that. I am afraid that the only person who could answer the question why Kolmogorov published the paper without Karatsuba's permission or knowledge was Kolmogorov himself.  Perhaps he thought that it was a good way to publish the results of his students. Note that the article correctly attributed all results. The article of Karatsuba and Ofman was published in the Proceedings of the USSR Academy of Sciences; it is my understanding that it had to be submitted/presented by a member of the USSR Academy of Sciences.

Here is the relevant quote from the paper of Gricenko et al (in Russian):

  Этот результат был доложен Анатолием Карацубой на семинаре А. Н.
  Колмогорова в МГУ в 1960 г., после чего семинар был Колмогоровым
  закрыт. Первая статья с описанием этого метода [2] была подготовлена
  самим Колмогоровым. Там он представил два разных и не связанных друг с
  другом результата двух своих учеников, и хотя в статье Колмогоров
  четко отметил, что одна теорема (не связанная с быстрым умножени- ем)
  принадлежит Ю. Офману, а другая теорема (с первым в истории быстрым
  умножением) принадлежит А. Карацубе, эта публикация под именами двух
  авторов надолго сбила с толку читателей, которые полагали, что оба
  автора внесли вклад в создание быстрого умножения, и даже называли
  этот метод двумя именами.

English translation:

  This result was presented by Anatoly Karatsuba in A. N. Kolmogorov's seminar at the Moscow State University in 1960, after which the seminar was closed by Kolmogorov. The first article with the description of this algorithm [2] was prepared by Kolmogorov himself.  In it he presented two different results from his two students that were unrelated to each other, and although Kolmogorov clearly noted in the article that one theorem (unrelated to fast multiplication) belonged to Y. Ofman, and the other theorem (with the first fast multiplication algorithm in history) belonged to A. Karatsuba, this publication on behalf of the two authors for a long time confused readers, who supposed that both authors had stake in the invention of fast multiplication, and even referred to the algorithm using both names.


(How) can you model broadcasts in the pi-calculus?

About a decade ago, Ene and Muntean showed that broadcasting has no reasonable compositional encoding into the $\pi$-calculus [1]. The essence of their separation between point-to-point communication and message passing is easy to understand: point-to-point is "too asynchronous". That means that in a broadcasting system, a broadcasting sender can send to $n$ processes in one atomic step for arbitrary $n$. OTOH, if a process wants to communicate with $n$ processes using point-to-point communication, this can only be done using $n$ (or more) separate message exchanges, which have intermediate states (e.g. the sender has sent messages to 100 receivers, and needs to send another 150). A context can observe, interact and interfere with these intermediate states, which is not possible with the atomic broadcast messages. To deal with this shortcoming of $\pi$-calculus (or indeed any calculus based on point-to-point message passing), Ene and Muntean propose a broadcasting variant b$\pi$ [2, 3], based on earlier work by Prasad on CBS, a variant of CCS with broadcasting [4].

More technically, [1] calls an encoding $e$ reasonable if the following is the case.

The encoding preserves parallel composition, i.e. $e(P|Q) = e(P) | e(Q)$.
The encoding preserves injective renaming, i.e. $e(P\sigma) = e(P)\sigma$
for any injective renaming $\sigma$.
The encoding satisfies some technical conditions about the preservation of input and output actions, see [1] for details.

Then [1] shows that no reasonable encoding from b$\pi$ to $\pi$ can exist. They establish this separation result using a variant of Palamidessi's electoral systems proof technique [5].

There has been work on this subject since [1-4] were published, e.g. by M. Hennessy, but those are the pioneering papers.

As an aside, broadcast is usually understood as one sender communicating with many receivers, but it is also possible to generalise point-to-point communication in the other direction where you have one receiver synchronising with multiple senders (this is used in e.g. Petri nets), or hybrid forms of both. I. Phillips has established a separation result that shows that this form of broadcasting can also not be encoded in  $\pi$-calculus. I am not sure whether this result is published or not.

[1] C. Ene, T. Muntean, Expressiveness of Point-to-Point versus Broadcast Communications.

[2] C. Ene, T. Muntean, A Broadcast-based Calculus for Communicating Systems.

[3] C. Ene, T. Muntean, Testing theories for Broadcasting Processes.

[4] K. V. S. Prasad, A Calculus of Broadcasting Systems.

[5] C. Palamidessi, Comparing the Expressive Power of the Synchronous and the Asynchronous $\pi$-calculi.


How important is knowing how to program for TCS?

Theoretical computer science is a broad field and the importance of programming depends on what you do in TCS.  I will mention two ways in which programming can help you, without implying that these are the only ways.

First, if you design algorithms for problems of practical importance, implementing your algorithms and making the code available to others can be a big plus.  For example, the convex hull problem arises in many fields, and people use software packages such as cdd by Komei Fukuda and lrs by David Avis to solve this problem.  If they had published their algorithms only in papers, probably less people would have used their algorithms.  More users mean more feedback and probably also more opportunities to collaborate, which is invaluable.

Second, even if you do not work in algorithms, writing a one-time code helps you to test a simple conjecture when the conjecture is suitable to numerical calculation.  For example, if you wonder whether the product of three positive definite matrices always has a positive trace, it is easy to write a code to test it for some random choices of 2×2 or 3×3 positive definite matrices and find a counterexample.  Although you do not advertise that you wrote any program to test the conjecture, programming can save the time which would have been spent in vain trying to prove a false statement.

The programming language to choose depends on what you want to do with programming, and it can be a topic for a whole book in my opinion.  But if you design algorithms and want to implement your algorithms so that other people can use the implementation, then one important factor is availability.  Although you can expect that most potential users of your code have access to a C compiler, you cannot expect that the same people have access to a Haskell compiler.  For one-time programs, the choice is more based on available libraries, and includes the environments such as Matlab.

By the way, programming can also be fun.


Nonlocal Games and Quantum Communication

What about "Consequences and Limits of Nonlocal Strategies" by Cleve, Hoyer, Toner and Watrous? It gives a pretty good introduction and then you can check e.g. other paper by Watrous


Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?

[Since it's been a while and no one has added any further answers, I'm reposting my comment as an answer.]

${\sf US}$ contains ${\sf coNP}$, so ${\sf P^{US}}$ is at least as powerful as ${\sf P^{coNP}} = {\sf P^{NP}}$. The (mostly) common wisdom suggests that ${\sf P^{UP}}$ is strictly contained in ${\sf P^{NP}} \subseteq {\sf P^{US}}$.


Inductive definition of ECTL*: how are recursive formulas forbidden?

The formula in your statement

  Obviously E(A(F1)) with F1=E(A(F1)) is not well-defined for some Büchi automata. So what does inductively defined exactly mean in this case?

cannot arise if you built ECTL* inductively. This means, in standard academic parlance, we would present a syntax definition of the form below.

Let $Prop$ be a set of propositions and $p$ range over $Prop$. If $\varphi_1, \ldots, \varphi_n$ are formulae of ECTL* let $\mathcal{A}[\varphi_1, \ldots, \varphi_n]$ denote an automaton $\mathcal{A}$ over the alphabet $\mathcal{P}(\{\varphi_1, \ldots, \varphi_n\})$ of subsets of the $n$ formulae shown.

$ \varphi ::= p ~\mid~ \varphi \land \varphi ~\mid~ \neg \varphi ~\mid~ \mathsf{E}(\mathcal{A}[\varphi_1, \ldots, \varphi_n])$

I believe there is some confusion in how you may be reading the presentation above. In academic terms this qualifies as BNF. I see that the Wikipedia page gives a slightly different presentation.
However, the definition above
is equivalent to the BNF grammar you give below. It is not a "relaxed BNF" to use your terminology. It is just an inductive definition where some BNF is used where convenient.

  BNF: $\langle\text{sf}\rangle::=\;   \langle\text{atomic prop}\rangle\;\big\vert\; \langle\text{sf}\rangle \vee
\langle\text{sf}\rangle\;\big\vert
\neg\langle\text{sf}\rangle\;\big\vert\; \text{E }\langle
\text{Buechi}\;\mathcal{A}\rangle
(\langle\text{sf}\rangle,\dots,\langle\text{sf}\rangle); $

Academic writing mixes English and BNF when we make inductive definitions because it is convenient. To see the need for convenience, consider your grammar. It does not inform the reader what $\langle\mathrm{atomic~prop}\rangle$ and what $\langle \mathrm{sf}\rangle$ are. You have chosen an intuitive naming convention, so one can guess the first represents atomic propositions. But in general, we want to have short symbols in our papers, so we prefer a one-time cost of verbose English, which is why we write something like "where $\varphi$ is an ECTL* formula". This text does not in any way change the language being defined.

To your specific question:
Your formula $F$ with $F = E(A(F))$ is not a formula of ECTL*. This type of formula cannot arise as the result of an inductive of the form above. This impossibility has nothing to do with the difference in presentation between BNF as you write it and inductive definitions in papers. To derive your formula, you need some atomic propositions, and a sequence of syntactic compositions to build up the more complex formula.

Now about fixed points. There is some confusion here too. BNF grammars are specific ways to present certain inductive definitions. They are not the only way and they do not cover all inductive definitions. Inductive definitions are a more general class and can be presented in many ways. Least fixed points are a strict generalisation of inductive definitions. Below I will only give an example of how both the BNF grammar above and the inductive definition I gave define a least fixed point. I emphasise that both definitions give rise to the same least fixed point.

Let's assume that $Prop = \{q,r,s\}$ is a set of atomic propositions and $p$ ranges over $Prop$. Consider a lattice $L$ which contains all sets of sequences of symbols appearing in the definitions above. The formulae of ECTL* are one specific element of this lattice. Consider a function $G:L \to L$, which is generated by the definitions above.

$G(\emptyset) = Props$, which accounts for $q$, $r$ and $s$ being formulae, or for the instantiation of $\langle \mathrm{atomic~prop}\rangle$ in BNF.

$G(G(\emptyset)) = G(Props)$, which is the set containing elements, $q \land r$, $q \land s$, $r \land s$, $\neg q$, $\neg s$, $\neg r$, $E(\mathcal{A}(\{q\}))$, $E(\mathcal{A}(\{r\}))$, $E(\mathcal{A}(\{s\}))$, $E(\mathcal{A}(\{q,r\}))$, $E(\mathcal{A}(\{q,s\}))$, $E(\mathcal{A}(\{r,s\}))$, $E(\mathcal{A}(\{q,r,s\}))$.
This is equivalent to applying the formation rules $\langle \mathrm{sf} \rangle \lor \langle \mathrm{sf} \rangle$, $\neg \langle \mathrm{sf} \rangle $ and the others with $\langle \mathrm{sf} \rangle$ being replaced by $\langle \mathrm{atomic~prop}\rangle$. Alternatively, this is equivalent to one unwinding of the inductive definition where we say, if $\varphi_1$ and $\varphi_2$ are atomic propositions, then $\varphi_1 \land \varphi_2$, $\neg \varphi_1$, $E(\mathcal{A}(\{\varphi_1, \varphi_2\}))$, etc are formulae.

The set $G(G(G(\emptyset)))$ contains $q \land r\land  s$, $r \land \neg s$, $\neg (q \land s)$, $\neg E(\mathcal{A}(\{r\}))$,  $E(\mathcal{A}(\{q \land s, \neg r\}))$ and so on.

The set of ECTL* formulae is the least fixed point of the function $G$ above. Note that I have not explicitly defined it, but this is possible to do and might be an insightful exercise to work out the details. Equivalently, you can obtain exactly the same fixed point by the BNF grammar or the inductive definition I give.

The kind of formula you suggest will occur in a fixed point that is not a least fixed point. I emphasise that both the BNF grammar and the inductive definition I give generate the same function $G$, hence they have the same least fixed point and the same set of fixed points. So, if the inductive definition allows for a certain formula, your BNF must allow for the at formula, and vice versa.


How to extend Solomonoff Induction to continuous domain

The set of computable real functions is also recursively enumerable. Assume it is enumerated by $(f_i)_{i\in\omega}$. Then the Solomonoff prior of $f_i$ is $p(f_i)=2^{-K(i)}$. So there is no difference whether the function is defined over natural numbers or real numbers, as long as it is computable.


This is a nice question. I don't know of approximation algorithms, but the known hardness results for approximating minimum distortion (and related problems such as metric labeling) should also show that $\epsilon^2$ is hard to approximate.

The reason is that they give a reduction from an NP-hard problem such that in the YES case the distortion is $O(1)$ and in the NO case the distortion is $\Omega(k)$ for at least a constant fraction of the edges. Hence, in the YES case $\epsilon^2$ will be a factor $k$ smaller than in the NO case. For details, see for instance the paper by Khot-Saket: www.cs.cmu.edu/~rsaket/pubs/approx.pdf

I'm not exactly sure which hardness factor follows from their paper, but it shouldn't be difficult to figure out. (I would guess at least the $\log^c(n)$ factor that you get for metric labeling should follow.)


Average Regret Bounds for Linear Stochastic Bandits

Using the "doubling trick," you can turn your favorite high probability algorithm (e.g. LinUCB) to be an anytime algorithm with expected regret as a function of $T$, usually giving a $\tilde{O}(\sqrt{T})$ dependence without knowing $T$ in advance.

This turns out to be tight, i.e. in Chu et al. (2011), we give lower bounds on expected regret of $\Theta(\sqrt{dT})$ for the $d$-dimensional linear stochastic bandit problem.  Hence, the expected regret, in the worst case, will indeed still be a function of $T$.


How to format author information in research papers?

I think you should keep in mind how people are going to use this information and for what purpose.

You use it to advertise yourself and your identity. You hope that little by little, people learn to recognise your name and know what kind of work you do.
Other researchers will use the information to find more information about you and your work. If they find a relevant paper written by you, they might want to find your home page and see if you have done more recent research on the same topic. Or they might want to contact you and ask more about your work.
Various organisations will use it to construct bibliography databases (DBLP, ACM Portal, MathSciNet, etc.) and to come up with all kinds of statistics (how many papers were published by university X). The editors of the bibliography databases typically want to figure out which papers are written by the same person (far from trivial, as the names are not unique).

Some advice based on the above use cases:

Please try to include your full name. Do not abbreviate your first name. Use the same version of your name in all research papers, and use the same version on your home page. For example, if you decide to use middle initials, do it consistently.
An email address might be a good idea (at least if you are not worried about spam email). Not that I would ever send email blindly to an address that I see in a paper, but googling for the email address might be much faster than googling for your name if you happen to have lots of namesakes.
Affiliations (the names of the universities, departments, institutes, and/or companies) are a must to keep your employers happy... They also help with disambiguation if you happen to have lots of namesakes. (Unfortunately people change universities often or have double-affiliations, and this will also create some confusion in the bibliography databases.)

I have no idea who would ever use your full postal address for anything nowadays – if they need it, they can google for up-to-date information. However, it might be nice to include the town and country, especially if your university does not happen to be named after (a well-known) city.


The Cost of an Equivalence Query for DFA

According to Garey and Johnson (p. 174), REGULAR EXPRESSION NON-UNIVERSALITY is PSPACE-complete. This is the problem of deciding whether a regular expression over $\{0,1\}$ does not generate all strings. So your problem is also PSPACE-complete.

Here is one way to see that the OP's problem is in PSPACE. Given a DFA $A$ and a regular expression $r$, construct an NFA $B$ for $r$, and use the power set construction to virtually construct a DFA $C$ equivalent to $B$; we will not keep $C$ in memory, but we have oracle access to $C$ using only polynomial space. Now virtually construct a DFA $D$ for the symmetric difference of $A$ and $C$ using the product construction. This DFA accepts no strings (and so $L(A) = L(r)$) if there is no path from the starting state to an accepting state. Since reachability is in NL and $D$ has size $2^{\mathrm{poly}(n)}$, we can check whether $L(D) = \emptyset$ in $\mathrm{NSPACE}(\mathrm{poly}(n)) = \mathrm{NPSPACE} = \mathrm{PSPACE}$, the latter equality due to Savitch's theorem.


Is the computation of a satisfying variable assignment for a Boolean formula $FP^{NP}$-hard?

$\let\mr\mathrm$Let me denote the problem as $S$. Gottlob and Fermüller state that if $S$ is solvable in $\mr{FP}^{\mr{SAT}[\log n]}$, then $\mr{P}=\mr{NP}$. However, the argument actually shows more generally that if $S$ is in $\mr{FP}^{\mr{SAT}[q(n)]}$, then SAT is solvable in time $\mr{poly}(n2^{q(n)})$. In particular, assuming the exponential time hypothesis, $S$ cannot be solved with a sublinear number of $\mr{NP}$ queries.

On the other hand, $S$ shouldn’t be hard for $\mr{FP}^\mr{SAT}$—or even $\mr{FP}^{\mr{SAT}[2]}$—under many-one search-problem reductions. For definiteness, let me assume (following Gottlob and Fermüller) that $S$ is formulated as a total search problem, required to answer “unsatisfiable” for unsatisfiable formulas. Let $L$ be a language whose $\{0,1\}$-valued characteristic function $f_L$ is reducible to $S$, that is, there are poly-time functions $g,h$ such that
$$S(g(x),y)\implies f_L(x)=h(x,y).$$
Then
\begin{align}
x\in L\iff{}&\bigl(g(x)\in\mr{UNSAT}\land h(x,\text{‘unsat’})=1\bigr)\\
&\lor\exists y\,\bigl(y\text{ satisfies }g(x)\land h(x,y)=1\bigr),
\end{align}
and we have a similar expression for $\overline L$ with $0$ in place of $1$, hence
$$L\in\mr{DP}\cap\mr{coDP}.$$
If this were true for all $\mr{DP}$ languages $L$, then the Boolean hierarchy would collapse to $\mr{DP}$, hence the polynomial hierarchy would collapse to something similar one level up. So, assuming no such collapse takes place, there are $\mr{FP}^{\mr{SAT}[2]}$ functions (in fact, characteristic functions of $\mr{DP}$ predicates) not reducible to $S$.

Note that if we instead formulate $S$ so that it is undefined on unsatisfiable inputs, it only becomes easier; it is a (non-total) $\mr{FNP}$ problem. Then it is not hard to see that $f_L$ is reducible to $S$ only if $L\in\mr{NP}\cap\mr{coNP}$. In particular, $S$ is not hard for $\mr{FP}^{\mr{SAT}[1]}$ (or characteristic functions of $\mr{NP}$ languages) unless $\mr{NP}=\mr{coNP}$.


The Eulerian cycle problem with "transition" costs $f$ is NP-hard by reduction from the Traveling Salesman Problem (TSP). Specifically, for any TSP instance given as a complete weighted graph on vertices $V = \{v_1,v_2,...,v_n\}$, encoded via the cost function $d : V \times V \rightarrow \cal{R}$, we can transform this into your problem in polynomial time as follows.

First, create a graph with a single "anchor" vertex $x$. Then, for each vertex $v_i \in V$, create a (self-looping*) edge $e_i = (x,x)$ with cost 0 (you can envision these self-loops as the separate "petals" of a flower-like graph in two-dimensions anchored around $x$). Finally, create a transition function $f$ (as per your definition) such that $f(x, e_i, e_j) = d(v_i, v_j)$. All Eulerian cycles (with transition costs from $f$) in this case are thus in 1:1 correspondence with all Hamiltonian cycles (i.e., solutions) of the original TSP instance and have equivalent cost. So if you can find a minimum-cost Eulerian cycle with such transition costs, then you can solve TSP to optimality, completing the reduction.

*Note that the self-looping edge encoding is not necessary, but it simplifies the description somewhat for the purposes of discussion above just to give the intuition (and your encoding seems to allow this). These self-loops can actually be broken up into separate "triangle" sub-graphs ($K_3$ gadgets), all anchored at the shared node $x$ whose edge transitions to other such gadgets are assigned costs accordingly from $d$ (but in a slightly-more-detailed manner).


Comparison between the maximum clique and maximum biclique problem

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


Compressing information about the halting problem for oracle Turing machines

Let $J^A(e)$ be the output of the $e$th Turing machine equipped with oracle $A$, on input $e$. Here $J$ stands for "jump". (In case of non-halting, $J^A(e)$ is undefined.)

An oracle $A$ is jump-traceable if there is a computable nondecreasing function $h:\mathbb N\to\mathbb N$ such that for all $e$, $J^A(e)\in T_e$ for some computably enumerable family of finite sets $(T_e)_{e\in\mathbb N}$ with $|T_e|\le h(e)$ for all $e$.

Let's consider $f^A(k,n)=$the string of length $n$ indicating which are the first $k$ of the Turing machines numbers $0,\dots,n-1$ to halt.
(If fewer than $k$ halt, $f^A(k,n)$ is undefined.)

Note that $f^A$ is partial computable relative to $A$. Thus there is a computable function $g$ such that $f^A(k,n)=J^A(g(k,n))$.

To compress the first $n$ bits of the halting set for $A$ it suffices to say which one of of the $h(e)$ many elements of $T_e$ is the right one, where $e=g(k,n)$ and $k$ is the correct number of halting TMs.

There is a proper hierarchy of jump-traceable oracles (Nies, Computability and Randomness, Theorem 8.5.2). So by choosing $h$ appropriately small, we get a candidate for an oracle $A$ as you asked for.

It is a reasonably good candidate in the sense that we have one direction (the upper bound on the growth rate) and that provably the method by which we obtained the upper bound does not give any much smaller upper bound than that.


Complexity of digraph homomorphism to an oriented cycle

For the intermediate question (a core with three top-bottom runs), how about this?

Some notation: I will be describing runs by words in $\{l,r\}^*$, with e.g. $llrl$ corresponding to a subgraph $\cdot\leftarrow\cdot\leftarrow\cdot\to\cdot\leftarrow\cdot$. The level increases on $r$ arcs and decreases on $l$ arcs, and I assume that its minimum is $0$. Some straightforward constraints are:

There cannot be a run consisting only of $l$s or only of $r$s, because otherwise there is an obvious homomorphism from $D$ to this run (mapping each node of $D$ to the one with the same level). This also implies that the maximum level must be at least $3$.
If the maximum level were $3$, then all top-bottom (resp bottom-top) runs would be of the form $llr(lr)^ill$ (resp. $rrl(rl)^irr)$; again it is not very hard to find a homomorphism from $D$ to the run which minimizes $i$.

However, for maximum level $4$ there is a solution, of length $36$: consider $D$ given by $(rrrlrrlllrll)^3$. This has the required top-bottom runs and is a core (see below). By the above constraints, it is necessarily minimal, since each run only has a single "backwards" edge.

To convince ourselves that this is a core, let's first name the vertices ($v_1,\ldots,v_{36}$). The bottom (i.e. level $0$) vertices are $v_1,v_{13},v_{25}$. Any homomorphism $\varphi$ from $D$ to a subgraph must preserve levels, and in particular $\varphi(v_1)\in\{v_1,v_{13},v_{25}\}$; modulo the obvious automorphism $v_i\mapsto v_{i+12}$, it is enough to consider the case $\varphi(v_1)=v_1$. Consider the neighbourhood of $v_1$ in $D$ (annotated with levels):

$v_{34}(1)\to v_{35}(2)\leftarrow v_{36}(1)\leftarrow v_1(0)\to v_2(1)\to v_3(2)\to v_4(3)\leftarrow v_5(2)\to v_6(3)\to v_7(4)$

Starting with $\varphi(v_1)=v_1$, we have $\varphi(v_2)\in\{v_{36},v_2\}$. But if $\varphi(v_2)=v_{36}$, then $\varphi(v_3)=v_{35}$, and we have no possible value for $\varphi(v_4)$. We get $\varphi(v_2)=v_2,\varphi(v_3)=v_3,\varphi(v_4)=v_4$. Next $\varphi(v_5)\in\{v_3,v_5\}$, but for $\varphi(v_5)=v_3$ we get $\varphi(v_6)=v_4$, with no possible value for $\varphi(v_7)$. So $\varphi$ must be the identity on the entire run $v_1\to\ldots\to v_7$, and by repeating the same argument for the remaining runs, the same is true on all of $D$. In particular, $\varphi$ does not map $D$ onto a proper subgraph.


Stable comparison sort with $O(1)$ auxiliary memory and $O(n \log n)$ average running time

There is a sort algorithm with $O(1)$ auxiliary words and achieving $O(n\log n)$ worst-case run time, where $n$ is the length of the input array.
http://www.springerlink.com/content/d7348168624070v7/

I don't think that the question seeks an algorithm with $O(1)$ auxiliary bits, because such algorithm must be tricky.  I mean, if we cannot use even $O(\log n)$ bits, then we cannot use a simple for-loop (for(i=0, i < n, i++) {...} ) in the algorithm without introducing variable i (which require additional $O(\log n)$ bits).


Facility location problem with a cost function

The problem you're asking to solve is a variant of the $k$-median problem on a metric space. You haven't mentioned anything about the various sizes involved, but as a formal matter, there are only $n$ choices for the magic number $k$ (the number of centers), and so after "guessing" the right value of $k$, you can run any of the standard approximation algorithms for $k$-median in graphs (your graph is a complete graph). In particular, one such is the method by Jain and Vazirani.

There's an older technique by Lin and Vitter that says that if you're willing to expand the number of centers by a tiny amount, you can get a pretty good approximation to the cost (w.r.t optimal centers).


What is the most intuitive dependent type theory I could learn?

There are a few different ways of approaching this:

Dependent Type Theory.
This is probably not the easiest way of learning about dependent types, but you could look at the Calculus of Constructions papers and their variants, Pure Type Systems, and Martin Hofmann's article on the Syntax and Semantics of Dependent Types, for example.
Theorem proving. Firstly, take a look at my answer to a related question: How would I go about learning the underlying theory of the Coq proof assistant?.
Programming with dependent types. Looking at recent languages with dependent types  such as Epigram or Agda or less recent ones such as Dependent ML and writing some programs will help solidify the ideas. Epigram, for example, is extremely clean in design. Another angle is to see how dependent types are implemented. One practical dependent type theory is $\Pi\Sigma$: Dependent Types without the sugar. Several PhD theses are devoted to programming with dependent type theory: Dan Licata's, Nils Anders Danielsson's, Ulf Norrel's, Susmit Sarkar's, among others. And of course there's Adam Chlipala's book, given in Marc Hamann's answer.

I'd be inclined to start with programming, before moving to using theorem proving, then start exploring the more theoretical issues.


Does there exist a polynomial time algorithm to determine whether an equation is a consequence of (x+y)*(y+z)=(x*y)+(y*z)?

Yes, this problem is decidable in polynomial time.

Let $R$ denote the term-rewriting system given by reductions of the form
$$(r+s)\times(s+u)\longrightarrow(r\times s)+(s\times u).$$
Clearly, $R$ is strongly normalizing: indeed, each reduction step decreases the number of occurrences of $+$ in the term, hence any reduction sequence terminates after at most $n$ steps.

I claim that $R$ is confluent. By Newman's lemma, it sufices to show it is weakly confluent. Thus, consider a pair of single-step reductions $t\to t_0$ and $t\to t_1$; we need to find $t'$ such that $t_0\stackrel{*}{\to}t'$ and $t_1\stackrel*\to t'$. This is easy to do by case analysis of possible redexes. The trivial cases are when the redexes are disjoint (as then we can perform the two reductions in arbitrary order) and when they coincide (as then $t_0=t_1$).

The remaining case is when one redex is strictly contained in the other. Now, this means that one redex is of the form $(r+s)\times(s+u)$, and the other one is a subterm of $r$, $u$, or of one of the two occurrences of $s$. In the first two cases, the two reduction again commute, and we are done. This also works in the third case after we duplicate the second reduction to apply to both occurrences of $s$.

So, each term has a unique $R$-normal form, which can be computed in polynomial time just by applying reductions in arbitrary order until the term becomes reduced. Finally, $t=s$ is a consequence of $C$ if and only if the normal forms of $t$ and $s$ coincide.


How expensive may it be to destroy all long s-t paths in a DAG?

[Self answer; this is a shortened version, the old one can be found
here]

We realized with Georg Schnitger that the answer to my question is strongly negative: there are DAGs
(even of constant degree), where every $k$-cut must have a constant fraction of all edges, not just an about $1/k$ fraction, as in my question. (A slightly weaker result that a $1/\log k$ fraction may be necessary can be obtained by using a much simpler construction mentioned in the footnote above.
A quick write-up is here)

Namely, in the paper
"On depth-reduction and grates", Georg constructed a sequence of directed acyclic
graphs $H_n$ of constant maximum degree $d$ on $n=m2^m$ nodes with the following property:

 For every constant $0\leq \epsilon < 1$ there is a constant $c > 0$ such that, if any subset of at most $cn$ nodes is removed from $H_n$, the remaining graph
contains a  path of length at least $2^{\epsilon m}$.

Take now two new nodes $s$ and $t$, and draw an edge from $s$ to every node of $H_n$, and an edge
from every node of $H_n$ to $t$. The resulting graph $G_n$ still has at most  $2n+dn=O(n)$ edges.

For every constant $0\leq \epsilon < 1$, there is a constant $c ' > 0$ such that, if any subset of at most $c'n$ edges is removed from $G_n$, the remaining graph
contains an $s$-$t$ path with  $2^{\epsilon m}$ or more edges.

Proof:
Call the nodes of $H_n$  inner nodes of $G_n$.
Remove any subset of at most $c'n$ edges from $G_n$, where $c'=c/2$.
After that, remove an inner node if it was incident to a removed edge. Note that
at most $2c'n=cn$ inner nodes are then removed. None of the edges incident to survived nodes
was removed. In particular, each survived inner node is still
connected to both nodes $s$ and $t$. By the above property of $H_n$, there must remain
a path of length $2^{\epsilon m}$ consisting entirely of survived inner nodes.
Since the endpoints of each of these paths survived, each of them
can be extended to an $s$-$t$ path in $G_n$. Q.E.D.

 A consequence is sad:  there does not exist any analogue of Markov's lemma for functions with many short minterms, even though the set of long minterms has some "complicated" structure: no super-linear lower bounds on the network size can be then proved using this "length times width" argument.

P.S. This "length times width" argument (when all $s$-$t$ paths are long enough) was earlier used by Moore and Shannon (1956). The only difference is that they do not allowed rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".


To open the list, here is a survey on SAT in French by Cristina Bazgan:
Optimisation Combinatoire : problèmes paradigmatiques et nouvelles problématiques, Hermes, ed. Vangelis Paschos, pp. 21-50, 2007


Has the semantics of TeX (as a programming language) ever been formalized?

No, to my knowledge there has been no work on formalizing TeX of the kind you are interested in.

(What follows is a subjective and personal commentary). I think it is an intriguing and well-posed idea, and your motivation of using it to perform optimizations sounds reasonable -- another related question is whether you could define a bytecode format for it to speed up interpretation. On the other hand, the idea has two downsides.

First, it is not clear to me that there is a large potential for optimizations (for example, what kind of program-preserving transformations could one perform to speed up computation?), as it may be that the language semantics is intimately related to parsing the character flow, and thus not very accommodating to the design of optimization-friendly intermediate representations.

Second, the need for improvements in TeX interpretation speed is not well-established: the speed of batch speed building has remained reasonable thanks to hardware improvements. Cases where speedups could be welcome are complex graphics package (beamer presentations can take quite some time to build), packages embedding rich computations (but then another language may be more appropriate), and use cases requiring fast rebuild for instant user feedback (but then incrementality, rather than optimization, may be the point; a formal semantics would certainly help reason about incremental implementations as well).

That is to say: this sounds like a fun, instructive topic, but it is not clear to me that the practical justifications for doing the work are strong. If someone was interested in doing it out of curiosity, that sounds like an excellent adventure, but otherwise there may be other ways to employ the same skillset whose impact would be more sought-after by end-users.


Minimizing $L_2$ norm of a vector with two distinct entries

(This is probably a comment but I cannot comment)
This seems to be 1-dimensional $k$-means clustering for $k=2$ and $k=4$. Here is a reference that gives a $O(kn + n \log n)$ algorithm for 1-d $k$-means clustering: Grønlund, Larsen, Mathiasen, Nielsen, Schneider, Song, Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D. It seems similar to the algorithm given in the comments.


Relative consistency of PA and some type theories

The short answer to your question 1 is no, but for perhaps subtle reasons.

First of all, System $F$ and $F_\omega$ cannot express the first-order theory of arithmetic, and even less the consistency of $\mathrm{PA}$.

Secondly, and this is really surprising, $\mathrm{PA}$ can actually prove consistency of both those systems! This is done using the so-called proof-irrelevant model, which interprets types as sets $\in\{\varnothing,\{\bullet\}\}$, where $\bullet$ is some dummy element representing an inhabitant of a non-empty type. Then one can write down simple rules for the operation of $\rightarrow$ and $\forall$ on such types rather easily to get a model for system $F$, in which the type $\forall X.X$ is interpreted by $\varnothing$. One can do a similar thing for $F_\omega$, using a bit more care to interpret higher kinds as finite functions spaces.

There's an apparent paradox here, where $\mathrm{PA}$ can prove consistency of these seemingly powerful systems, but not (as I'll show in a moment) normalization.

The missing ingredient here is realizability. Realizability is a way to make certain programs correspond to certain propositions, typically in arithmetic. I won't go into the details here, but if a program $p$ realizes a proposition $\phi$, written $p\Vdash \phi$, then we have a certain piece of evidence for $\phi$, in particular if $p$ is normalizing, then $p\not\Vdash\bot$. We have:

  Theorem: If $\phi$ is a theorem of 2nd order arithmetic $\mathrm{PA}_2$, then there is some closed term $t$ of system $F$ such that $$ t\Vdash\phi$$

This theorem can be proven in $\mathrm{PA}$, and so we have
$$\mathrm{PA}\vdash F\mbox{ is normalizing}\Rightarrow\mbox{$\mathrm{PA}_2$ is consistent} $$
and Gödel's argument applies (and $\mathrm{PA}$ cannot prove normalization of system $F$). It's useful to note that the reverse implication holds as well, so we have an exact characterization of the proof-theoretic power needed to prove normalization of system $F$.

There is a similar story for system $F_\omega$, which, I believe, corresponds to higher arithmetic $\mathrm{PA}_\omega$.

Finally, we have the tricky case of MLTT with inductive types. Here again a somewhat subtle issue arises. Certainly here we can express the consistency of $\mathrm{PA}$, so that isn't an issue, and there is no proof-irrelevant model, as we can prove that the type $\mathrm{Nat}$ has at least 2 elements (an infinite amount of distinct elements, in fact).

However we run into a surprising fact of higher-order intuitionistic theories: $\mathrm{HA}_\omega$, the higher-order version of Heyting Arithmetic is conservative over $\mathrm{HA}$! In particular, we cannot prove consistency of $\mathrm{PA}$, (which is equivalent to that of $\mathrm{HA}$). An intuitive reason for this is that intuitionistic function spaces do not allow you to quantify over arbitrary subset of $\mathbb{N}$, since all definable functions $\mathbb{N}\rightarrow \mathbb{N}$ must be computable.

In particular, I don't think you can prove consistency of $\mathrm{PA}$ if you add only natural numbers to MLTT without universes. I do believe adding either universes or "stronger" inductive types (like ordinal types) will give you enough power though, but I'm afraid I have no reference for this. With universes, the argument seems quite simple though, since you have enough set theory to build a model of $\mathrm{HA}$.

Finally, references for the proof theory of type systems: there's really a gap in the literature here I think, and I would relish a clean treatment of all these subjects (in fact, I dream of writing it myself some day!). In the meantime:

The proof-irrelevant model is explained here by Miquel and Werner, though they do it for the Calculus of Constructions, which complicates matters somewhat.
The realizability argument is sketched in the classic Proofs and Types of Girard, Taylor and Lafont. I think they also sketch the proof-irrelevant model, and a great deal of useful things besides. It's probably the first reference to read.
The conservativity argument of higher-order Heyting arithmetic can be found in the elusive second volume of Constructivism in Mathematics by Troelstra & van Dalen (see here). Both volumes are extremely informative, but quite difficult to read for a novice, IMHO. It also somewhat avoids "modern" type theory subjects, which is unsurprising given the books' age.

An additional question in the comments was about the exact consistency strength/normalization strength of MLTT+Inductives. I don't have a precise answer here, but certainly the answer depends on the number of universes and the nature of the inductive families allowed. Rathjen explores this question in the excellent paper The Strength of some Martin-Lof Type theories.

Wrt normalization, the basic idea is that if, for 2 theories $\cal{T}$ and $\cal{U}$, we have
$$\mathrm{PA}\vdash\mathrm{Con}(\cal{T})\Rightarrow\mathrm{Con}(\cal{U}) $$

then, generally

$$\mathrm{PA}\vdash \mbox{1-$\mathrm{Con}$}(\cal{T})\Rightarrow\mathrm{Norm}(\cal{U}) $$

where 1-$\mathrm{Con}$ is 1-consistency and $\mathrm{Norm}$ is (weak) normalization.

MLTT + the type of natural numbers (and recursion) is a conservative extension of $\mathrm{HA}_\omega$, which is proven in Besson Recursive Models for Constructive Set Theories.

As far as MLTT with induction-recursion or induction-induction, I don't know what the situation is, and AFAIK, the problem of exact consistency strength is still open.


String distance communication complexity

After the OP's edit (see comments below), this answer is outdated and does not address the question. Leaving it for the said comments.

This seems to be asking the same as in this question of mine (which only has a partial answer, fitting for a partial function). Quoting from the question:

  [Consider, for $x,y\in\{0,1\}^n$] the partial function
  $$
\textsf{GHD}_{n,t,g} = \begin{cases}
0 & \text{ if }\operatorname{d}_H(x,y) \leq t-g\\
1 & \text{ if }\operatorname{d}_H(x,y) \geq t+g.
\end{cases}$$
  Lemma 4.1 to Proposition 4.4 of [CR10] allow to get a lower bound on the communication complexity of $\textsf{GHD}_{n,t,g}$ for (most) of the settings of $t,g$.

As answered there, the general one-sided version is solved in the following paper of Egor Klenin and Alexander Kozachinsky [1], who show that (with your notations) $\tilde{\Theta}\!\left(\frac{t}{(1-\alpha)^2}\right)$ bits are necessary and sufficient.

[1] One-sided error communication complexity of Gap Hamming Distance, Egor Klenin and Alexander Kozachinsky, 2016. ECCC TR16-173.


What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

An extended comment:

Collatz-like sequences can be computed by small Turing machines having few symbols and states.  In "Small Turing machines and generalized busy beaver competition" by P. Michel (2004), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.

There are TMs that compute Collatz-like sequences for which the decidability is still an open problem: $TM(5,2)$, $TM(3,3)$ and $TM(2,4)$ (where $TM(k,l)$ is the set of Turing Machine with $k$ states and $l$ symbols). I don't know if the results have been inproved.

From the comclusion of the paper:

... The present Collatz-like line is already on its lowest possible level, with the possible exception of $TM(4,2)$, but we conjecture that all machines in this set can be proved to be decidable...

See also "The complexity of small universal Turing machines: a survey" by D. Woods and T. Neary (2007).

Another example of Collatz-like problem for which decidability is an open problem is the Post's tag system: $\mu = 2, v=3,0\rightarrow 00, 1 \rightarrow 1101$; for a recent analysis see "On the boundaries of solvability and unsolvability in tag systems. Theoretical and Experimental Results" by L. De Mol (2009).


Can we not output the Kolmogorov complexity?

The question can be rephrased as whether or not $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} = 0$, and as Denis points out in the comments this is false for some encodings.  Here is a weaker statement and an attempted proof of it that doesn't depend on any details of the encoding, but I'll assume a binary language for simplicity:

Let $T:\{0,1\}^* \rightarrow \mathbb{N}$ be a computable function satisfying $0 \le T(x) \le \vert x \vert$ and $\lim \inf_{\vert x \vert \rightarrow \infty}{T(x)} = \infty$.  Then $\lim \inf_{\vert x \vert \rightarrow \infty}{\vert T(x) - K(x) \vert} \lt \infty$.  Informally, if there is a target around each string's Kolmogorov complexity that grows unboundedly wide, no computable function can avoid hitting it.

To see this, let $n$ be a random $b$-bit number, i.e. $0 \le n \lt 2^b$ and $K(n) \ge b$.  For all $b$ such a random $n$ exists.   Also note that there are an infinite number of values of $b$ for which $\vert \{T(x) = b\} \vert \ge 2^b$, this follows from the conditions placed on $T$.  Now let $x$ be the $n^{\text{th}}$ smallest string such that $T(x) = b$.  Clearly there is a constant $c_1$ such that $K(x) \gt b - c_1$, because $K(n) \ge b$ and $n$ can be computed from $x$.  And there is a constant $c_2$ such that $K(x) \lt b + c_2$, because $K(n)$ is also bounded from above by only a constant more than $b$, and $x$ can be computed from $n$.  Then $\vert K(x) - T(x) \vert \lt c_1 + c_2$, and we have an infinite number of choices for $b$ (those with a preimage of cardinality at least $2^b$), yielding an infinite number of values for $x$, so we are done.

An implication is that for some $c \in \mathbb{Z}$, $T(x) = K(x) + c$ infinitely often.  So one might say we can't not output something that's not the Kolmogorov complexity!