Which factors make the problem of inferring the grammar difficult? Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31):

  Following the work of Kearns and Valiant, we now know that many
  natural learning problems — as an example, inferring the rules of a
  regular or context-free language from random examples of grammatical
  and ungrammatical sentences — are computationally intractable.

My question is: Which factors make the problem of inferring the grammar difficult? Is the introducing random examples of ungrammatical sentences? If so, what would happen if the condition of "random examples of grammatical and ungrammatical sentences" is replace with "random examples of grammatical sentences with probability p>0 and random examples of ungrammatical sentences with probability 1-p"?

Regarding the difficulty of learning grammars, let's stick to regular ones for concreteness. These are precisely the grammars/languages recognized by Deterministic Finite-state Automata (DFAs). The source of difficulty is purely computational; the statistical aspects are quite straightforward.

If you were able to find the smallest DFA consistent with your finite sample, simple Occam/cardinality arguments guarantee that this will generalize very well (it's the "optimal" learner in some sense). See Theorems 2 and 3 of Graepel et al.
http://research.microsoft.com/pubs/65635/graepelherbrichtaylor05.pdf
for actual state-of-the-art bounds.

However, finding such a small DFA is VERY hard (see Angluin, Gold, Pitt-Warmuth, etc):
http://www.sciencedirect.com/science/article/pii/S0019995878906836
http://web.mit.edu/6.863/www/spring2010/readings/gold67limit.pdf
http://dl.acm.org/citation.cfm?id=138042
[the latter even gives a hardness-of-approximation result].

But wait, it gets worse! Suppose you didn't care about a DFA and just wanted to learn the grammar in some representation (i.e., a mechanism for predicting the labels of test strings drawn from the same distribution as the training set).
If such an algorithm were to exist, and succeeded against all distributions, then it would also break RSA and related cryptographic primitives:
http://dl.acm.org/citation.cfm?id=697797


A bicartesian closed category of strict complete partial orders (Hask) It seems to be well-known that programming languages can't have sums, products and nontermination together.

Q1. Is this true? Below (or in the above link I gave) is a partial argument.

However, Hinze's Generic programming with Adjunctions ignores the issue, even after discussing somewhat precisely which is the involved category. In particular, he talks (seemingly without reservations) about Haskell being modeled by the category $\mathbf{SCpo}$ of strict continuous partial orders and having sums and products. But we know that Haskell does not have sums (right?).
(Part of the paper uses $\mathbf{Set}$ instead, but that doesn't allow for non-termination).

Q2
So, what am I missing? I see four options:

People often ignore non-termination on purpose when discussing Haskell. Perhaps this paper does it too. But why would one mention CPOs then?
The barrier I discuss can be avoided in clever ways. In particular, the paper models non-strict Haskell functions $f : A \to B$ by strict functions $f : A_{\bot} \to B$, for other reasons.
The paper does mention the limitation and I missed that. I've spent some effort looking for this mention and failed to find any.
This is an actual mistake, and as everybody keeps claiming Haskell indeed lacks categorical sums (as other people agree on), even though the paper claims Either is such a thing. Everything works out nicely instead in total languages with inductive and coinductive types.

Background

It's well known that, in a bicartesian closed category (BCCC), if the initial and final object coincide (that is, if the category has a zero object) the category collapses (with all types being isomorphic) by $A \cong  A \times 1 \cong A \times 0 \cong 0$ for all $A$.

This means, for instance, that the category of pointed sets, with its zero object, can't be bicartesian closed.

But the category SCpo also has a zero object for the same reason: all objects are structured sets (CPOs) with a bottom element $\bot$, and arrows are strict (and ($\omega$-)continuous) functions, so they preserve $\bot$. Indeed, this is attributed to Smyth and Plotkin (1982), who describe this category as $\mathbf{CPO}_{\bot}$ and state it lacks categorical products; other categories they consider lack other features of a BiCCC (e.g., their $\mathbf{CPO}$ lacks sums).

What is not clear to me is whether every way of handling $\bot$ falls into this trap. However, knowledgeable people on Reddit seem to repeat this claim without good sources (Filinski's master thesis was the best reference I got, and it doesn't lay out a generic categorical argument).

Yes, it's impossible to have a nondegenerate CCC with general recursion and categorical coproducts. The standard reference for this is:

  H. Huwig and A. Poigne. A note on inconsistencies caused by fixpoints  in a cartesian closed category. Theoretical Computer Science, 73:101–112, 1990.

However, I and (most of the other people I've met) learned about it from Achim Jung and Samson Abramsky's handbook chapter Domain Theory, which they have kindly made available for free.

Most of the categories of domains that people work with are subcategories of DCPO, the category of predomains and continuous functions on them. Since predomains do not necessarily have a least fixed point, this category is a bi-CCC, but fixed points only exist for functions into domains.

On page 46 of these notes, there is a big table telling you which subcategory of DCPO different constructions exist in.


A random walk that moves to less-visited nodes Consider a random walk on an undirected graph that keeps track of how many times it has visited every node. At each step, it moves to the node among its neighbors which has been visited the least number of times. If there are several such nodes, it chooses one at random. My question is: what is the (worst-case) cover time of this random walk as a function of the number of nodes $n$?

The answer should be at least $\Omega(n^2)$. Consider a star graph where each node has a self-loop. In this graph, the walk starting at the center will visit the leafs in some order, without loss of generality $1,2,3, \ldots, n-1$ (relabel the vertices if necessary). The time spent at leaf $i$ will be at least $i-1$ because the center will have been visited $i-1$ times before leaf $i$.  Thus the total cover time will scale as $\Omega (n^2)$. If we want an example without self-loops, we can consider a star-like graph where each leaf is replaced by a path of length $2$.

Alternatively, what is the largest hitting time between any two vertices for this random walk? This feels like asking a very similar question.

For the usual random walk which jumps to each out-neighbor, the largest hitting time will be $O(n^3)$ but the standard proofs rely on resistances, which are not applicable here due to lack of reversibility.

The assumption here is that the input graph is not a disconnected graph. If it is then it will run forever since some of the nodes will never be reached from set of nodes.

Since the graph is undirected, at any point in time, the decision is made solely based on at what node you are and from that node a neighbor with least visited is going to be picked. So, it is possible that the node that is used to reach the current node may very well be next node to be visited (returning). As you visit the node, it increases the node's visited count and forces alternate node at next choice. Each node would have a visited count any where from 1 to N and no more than N without all nodes being visited.

The constraint that the next node to be visited be a least visited tracks whether node is visited or not and forcing to visit all nodes. Let us say that a global variable tracks the number of visited nodes. Whenever a node's visited counts goes from 0 to 1, increment this counter by 1 for the newly visited node. Until this count reaches the number of nodes in the input graph, we know that there exists some nodes that are not yet visited.

At every node, the unvisited node(s) gets priority over already visited nodes since the unvisited node's visited count is 0. So, initially it tracks like DFS and avoids cycle unless there is no other way. As you visit the node that is already visited, it increments the node's visited count there by making it least preferred till every node in the connected component's node weight to be increased as well. If there is another way to reach other unvisited nodes, then those nodes would be preferred and thereby making to find alternate path. If there is no other way, then we would end up back to articulation point which would have at least one node that is least visited. This least visited component would be now explored until all nodes in that component are visited.

The visited count of each articulation point would be number of nodes in the largest component it is connected to plus number of components it is connected to. Eventually, the largest count possible for a node in the graph is one plus the count of articulation point that has maximum of sum of largest component it is connected to plus the number of components it is connected to.

Therefore, the largest hitting time will be O(n^2).


What is the simplest computational model for which the emptiness problem is undecidable? What is the simplest computational model for which the emptiness problem is undecidable?

Emptiness problem for a computational model (e.g. finite state automaton, alternating pushdown automaton, bounded-error quantum automaton with a counter, deterministic LBA, etc.) is to determined whether, for a given such machine, the language recognized/defined by this machine is empty. Here the description of the machine should be finite!

I know that the word "simplest" is a little vague. There could be more than one answer for some incomparable computational models.

As a special remark, I believe that the question would become more interesting by focusing on unary and binary alphabets separately.

Note that there are many computational models for which the halting problem is decidable but the emptiness problem (and some other problems) is (are) undecidable, e.g. Linear bounded automata (LBAs).

Probably you already got these in your bag :-)

Two way one counter machine over unary alphabet (Minsky61).
Two way weak counter machines (the counter has no effect on the computation but the machine halts if counter reaches zero) [1].
Quantum one counter automata [2].

With binary alphabets, the emptiness remains undecidable for:

One way machines with one unbounded counter and one pushdown store that makes at most one reversal [3].
Two-way machines deterministic finite automata with multiple reversal bounded counters (even over a bounded language) [3].
Stateless (the transitions depend only on the scanned symbol) 2-head 2-way deterministic finite automata even when each head makes only one reversal on the input tape [4].

Edit: on the boundary:

(Open problem) Is the emptiness problem decidable for two-way nondeterministic finite automata with one reversal bounded counter over non-bounded languages? (over bounded languages it is decidable [5])

[1] Tat-hung Chan. On Two-Way Weak Counter Machines. Mathematical Systems Theory 01/1987;
[2] Richard F. Bonner, Rusins Freivalds, and Maksim Kravtsev. 2001. Quantum versus Probabilistic One-Way Finite Automata with Counter. In Proceedings of the 28th Conference on Current Trends in Theory and Practice of Informatics Piestany: Theory and Practice of Informatics (SOFSEM '01), Leszek Pacholski and Peter Ruzicka (Eds.). Springer-Verlag, London, UK, UK, 181-190.
[3] Oscar H. Ibarra. 1978. Reversal-Bounded Multicounter Machines and Their Decision Problems. J. ACM 25, 1 (January 1978), 116-133.
[4] Oscar H. Ibarra, Juhani Karhumäki, Alexander Okhotin, On stateless multihead automata: Hierarchies and the emptiness problem, Theoretical Computer Science, Volume 411, Issue 3, 6 January 2010, Pages 581-593, ISSN 0304-3975.
[5] Zhe Dang, Oscar H. Ibarra, Zhi-wei Sun. On the emptiness problems for two-way nfa with one reversal-bounded counter. In Proc. Thirteenth Int. Symp. on Algorithms and Computation (2002)


Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$ I've never seen an algorithm with a log in the denominator before, and I'm wondering if there are any actually useful algorithms with this form?

I understand lots of things that might cause a log factor to be multiplied in the run time, e.g. sorting or tree based algorithms, but what could cause you to divide by a log factor?

The usual answer to "what could cause you to divide by a log?" is a combination of two things:

a model of computation in which constant time arithmetic operations on word-sized integers are allowed, but in which you want to be conservative about how long the words are, so you assume $O(\log n)$ bits per word (because any fewer than that and you couldn't even address all of memory, and also because algorithms that use table lookups would take too much time to set up the tables if the words were longer), and
an algorithm that compresses the data by packing bits into words and then operates on the words.

I think there are many examples, but the classic example is the Four Russians Algorithm
for longest common subsequences etc. It actually ends up being $O(n^2/\log^2 n)$, because it uses the bit-packing idea but then saves a second log factor using another idea: replacing blocks of $O(\log^2 n)$ bit operations by a single table lookup.


Have any generalizations of maximum weight matching been studied? For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.

accordingly, a maximum weight matching could then be viewed as  maximizing the objective $\sum_v f_v$.

Have any generalizations of maximum weight matching been studied that consider more general objective functions using  weighted, multivariate or nonlinear $f_v$ ?

Have other variants been studied that are generalizations in a different way?

pleas provide references if applicable!

There are several extensions of the problem to more general structures.  For instance:

Matroid matching (lecture notes, Matroid matching and some applications, Matroid Matching: the Power of Local Search)
Path-matching (Path-matching problems, Matching, matroids, and extensions)
Hypergraph matching (Can't find any good references)

Generally, these extensions are NP-hard.


Minimal sum of matrix elements Here's my attempt to explain the problem in mathematical language:

$$
\text{Given square matrix A}
$$
$$
\left(
\begin{array}{cccc}
 a_{1,1} & a_{1,2} & \cdots & a_{1,N} \\
 a_{2,1} & a_{2,2} & \cdots & a_{2,N} \\
 \vdots & \vdots & \ddots & \vdots \\
 a_{N,1} & a_{N,2} & \cdots & a_{N,N}
\end{array}
\right)
$$

Find a minimal sum of $N$ elements such that no two elements are in the same row or column. In other words, find $$\min_{\sigma\in S_N}\left\{\sum_{i=1}^Na_{i,\sigma(i)}\right\},$$ where $S_N$ is the set of permutations on $\{1,\ldots,N\}$.

Is there a standard name for this problem?

This is called the (linear) assignment problem. It can be solved efficiently through linear programming over the Birkhoff polytope.


Bounded-input bijections of infinite sequences Here is a puzzle I haven't managed to solve. I would like to know if this problem is already known, or has an easy solution.

It is possible to define a bijection $ 3^\mathbb{N} \cong 5^\mathbb{N} $ using the properties of bicartesian closed categories. Andrej Bauer posted an explanation of what this means on his blog as "Constructive gem: juggling exponentials".

This bijection has an interesting property: it is "bounded-input" meaning that each component of the output depends only on boundedly many components of the input. However, for $k,l\geq 2$ it seems that this construction can only show that $ k^\mathbb{N} $ and $ l^\mathbb{N} $ are isomorphic if $k$ and $l$ are both odd or both even. This leaves open the question:

Is there a bounded-input bijection from $ 2^\mathbb{N} $ to $ 3^\mathbb{N} $?

Here is a short note describing the problem in more detail:
A conjecture concerning bounded-input bijections of infinite sequences.

Definitions:

A function $f : \prod_{i \in I} X_i \rightarrow \prod_{j\in J} Y_j $ is bounded-input if there exists
an integer $k$
such that each component of the output of $f$ depends only on at most $k$
components of the input.
More formally, $f$ is bounded-input if for each index $j \in J$
there are indices $i_1,\dotsb,i_k \in I$
and a function $f_m : X_{i_1}\times\dotsb\times X_{i_k} \rightarrow Y_j$
such that for all $x \in X$ the component
$f(x)_j$ equals $f_j(x_{i_1},\dotsb,x_{i_k})$.

A bijection $f$ is a bounded-input bijection if
it is a bounded-input function.

A bijection $f$ is a bounded-input isomorphism if
it and its inverse are bounded-input functions. This is also interesting.

I am not a CS theory guy. But in ergodic theory this type of mapping is known as finitary isomorphisms. For example people considered if two Bernoulli sequences of the same entropy is finitarily isomorphic or not. For example (this is one-sided shift because it seems you are concerned with $P^{\mathbb{N}}$ rather than $P^{\mathbb{Z}}$):

A. Del Junco, “Finitary codes between one-sided Bernoulli shifts,” Ergodic
Theory Dynamical Systems, vol. 1, pp. 285–301, 1981.

P.S. I intend to leave this as a comment but I cannot due to lack of reputation. Let me know if it is completely off-topic then I will delete it.


Fast algorithm to find pair of triangles with a common edge in a complete graph Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles that have a common edge, and then draw the energy-energy scatter plot for these pairs.

For example, take this adjacency matrix:
$$ \begin{bmatrix} 0 & 1 & 2 & 3 \\ 1 & 0 & 4 & 5 \\ 2 & 4 & 0 & 6 \\ 3 & 5 & 6 & 0 \\\end{bmatrix}$$
For this graph we have 6 pair of triangles with a common edge:

$1: (1,2,3) \space with \space (1,2,4) $, (with $(1-2)$ as the common edge)

$2: (1,2,3) \space with \space (1,3,4) $, (with $(1-3)$ as the common edge)

$3: (1,2,4) \space with \space (1,3,4) $, (with $(1-4)$ as the common edge)

$4: (1,2,3) \space with \space (2,3,4) $, (with $(2-3)$ as the common edge)

$5: (1,3,4) \space with \space (2,3,4) $, (with $(2-4)$ as the common edge)

$6: (1,2,4) \space with \space (2,4,3) $, (with $(3-4)$ as the common edge)

Now it's quite easy to draw the energy-energy plot for these pairs. For each pair from 1 to 6, on the x axes we take the energy value of the first triangle in the pair, and on the y axes we put the energy value of the second triangle in the pair. So we will have a plot with 6 points, for each point $ (x,y) $,  $x $ is the energy value of the first triangle in the pair, and $y$ is the energy value of the second triangle in the pair.

I'm fine with solving this problem when the number of nodes is quite small. But I need to run this algorithm on a graph with 116 nodes. So I need to find an efficient algorithm. I'm using MatLab and I appreciate any optimize algorithm for this problem.

Thank you so much!

There's a straightforward algorithm.  For each edge $(u,v)$, compute the multiset of products of weights of paths of length 2 from $u$ to $v$:

$$S_{u,v} = \{\text{wt}(u,t) \cdot \text{wt}(t,w) : (u,t) \in E \land (t,w) \in E\}.$$

These multisets can be computed in at most $O(|V| \cdot |E|)$ time.  In practice it suffices to enumerate all edges $(u,v)$, then enumerate all edges $(u,t)$ incident on $u$, then check whether $(t,w)$ is an edge.

Next, for each edge $(u,v)$ and each pair of values $x,x' \in S_{u,v}$, plot the point $(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$ on the scatterplot.  This can be done in at most $O(|V|^2 \cdot |E|)$ time.

It might not be easy to do asymptotically significantly better than this.  For a complete graph, the scatter plot can have $\Theta(|V|^4)$ points, so there is no hope for an algorithm whose running time is faster than $O(|V|^4)$ on complete graphs; and this algorithm takes $O(|V|^4)$ time on complete graphs, so it is asymptotically optimal for such graphs.  For sparse graphs, this algorithm takes $O(|V|^3)$ time, and there might be some hope to get the running time a little faster for sparse graphs.

If it's still too slow, rather than creating the entire scatterplot, you could sample the points on the scatterplot and plot that.  One way to do that is to compute the multisets $S_{u,v}$, then for each edge $(u,v)$ sample a bunch of pairs of values $x,x' \in S_{u,v}$ and plot the points $(\text{wt}(u,v) \cdot x, \text{wt}(u,v) \cdot x')$ on the scatterplot for each such pair.  If there are a lot of points on the scatterplot, plotting a random sample of the points should also be sufficient for visualization purposes and should give you a good sense of the "shape" of the scatterplot.


Problems with Unknown Single Exponential Time Agorithms I'm looking for examples of problems for which it is easy to get algorithms running in time $2^{O(n\log n)}$, or $2^{O(n^c)}$ for some $c>1$ but for which it is not known whether there is an algorithm running in time $2^{O(n)}$.

I'm mostly interested on graph theoretic problems, but other nice examples would also be welcome.

For instance, it is trivial to develop an algorithm running in time
$O(n!) = 2^{O(n\log n)}$ for the Hamiltonian path problem. Just test all permutations. Using dynamic programming however, one can achieve time $2^{O(n)}$. Are there other natural connectivity problems, or variations of the Hamiltonian path problem for which no algorithm running in time $2^{O(n)}$
is known?

In the Graph Homomorphism problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\in E(G)$ we have that $h(u) h(v)\in E(H)$.

The problem can be solved in time $O^*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^*$-notation hides factors polynomial in the input size).

However it is open whether it can be solved in time $O^*(c^{|V(H)|+|V(G)|})$, and this appears as an open question in

Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms. Theory Comput. Syst. 41(2): 381-393 (2007)


What are possible implementations of Haskell's type classes and what are their (dis)advantages? As far as I know, a Haskell function with type classes constraints is internally compiled to a function with additional arguments that receive dictionaries with the necessary implementations of each particular type class.

Are there any other possibilities how compile type classes?
If so, what are their (dis)advantages?
And what compilers use them?

JHC uses a different approach.  The compiler's intermediate language is a dependently typed lambda-calculus where there is no distinction between types and values.  JHC therefore can perform a case analysis on the type parameter of a function and call the correct overloaded function directly.

The JHC website goes into some depth on the implementation, as well as its advantages over the standard dictionary passing implementation.


Diameter Constrained Minimum Spanning Graph The idea of a diameter constrained MST is that you keep all vertices connected and within a certain distance of each other. But all papers I've seen keep the requirement that you produce a tree, when allowing cycles could help reduce the diameter. Does anyone know any papers that explore this? (It's difficult to search for.)

For example, consider a complete graph with vertices arranged in a circle on a plane (edge weight = Euclidean distance). The MST (e.g. via Prim's) will follow the circle, so that the diameter of the graph is roughly the circumference of the circle. By allowing the final edge to be connected we can halve the diameter, without increasing the total weight much.

Minimum Diameter Spanning Subgraph is what you should be looking for. It is NP-Hard to compute even in the case of planar graphs. This paper gives a nice overview.


Is there a natural problem on the naturals that is NP-complete? Any natural number can be regarded as a bit sequence, so inputting a natural number is the same as inputting a 0-1 sequence, so NP-complete problems with natural inputs obviously exist. But are there any natural problems, i.e. ones that do not use some encoding and special interpretation of the digits? For example "Is n a prime?" is such a natural problem, but this one is in P. Or "Who wins the Nim game with heaps of size 3, 5, n, n?" is another problem that I consider natural, but we also know this to be in P. I am also interested in other complexity classes instead of NP.

Update: As pointed out by Emil Jeřábek, given $a,b,c\in \mathbb N,$ to determine whether $ax^2+by-c=0$ has a solution over the naturals is NP-complete. This is exactly what I had in mind as natural, except that here the input is three numbers instead of just one.

Update 2: And after more than four years waiting, Dan Brumleve has given a "better" solution - note that it's still not complete because of the randomized reduction.

Based on the discussion, I’ll repost this as an answer.

As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.

The problem can be equivalently stated as follows: given $b,c\in\mathbb N$, determine whether the quadratic $x^2+by-c=0$ has a solution $x,y\in\mathbb N$.

(The original paper states the problem with $ax^2+by-c$, but it is not hard to see that one can reduce it to the case $a=1$.)


What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes? My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, is $\mathsf{MaxSNP} = \mathsf{APX}$  or $\mathsf{MaxSNP} \subset\mathsf{APX}$?

Thanks a lot in advance. :)

See the following paper by Khanna etal on syntactic vs computational views of approximability. MaxSNP is a syntactic class while APX is a computational class. dl.acm.org/citation.cfm?id=298507

Made comment into answer as per Suresh's request.


Complexity of Finding the Eigendecomposition of a Matrix My question is simple:

  What is the worst-case running time of the best known algorithm for computing an eigendecomposition of an $n \times n$ matrix?

Does eigendecomposition reduce to matrix multiplication or are the best known algorithms $O(n^3)$ (via SVD) in the worst case ?

Please note that I am asking for a worst case analysis (only in terms of $n$), not for bounds with problem-dependent constants like condition number.

EDIT: Given some of the answers below, let me adjust the question: I'd be happy with an $\epsilon$-approximation.  The approximation can be multiplicative, additive, entry-wise, or whatever reasonable definition you'd like.  I am interested if there's a known algorithm that has better dependence on $n$ than something like $O(\mathrm{poly}(1/\epsilon)n^3)$?

EDIT 2: See this related question on symmetric matrices.

Ryan answered a similar question on mathoverflow. Here's the link: mathoverflow-answer

Basically, you can reduce eigenvalue computation to matrix multiplication by computing a symbolic determinant. This gives a running time of O($n^{\omega+1}m$) to get $m$ bits of the eigenvalues; the best currently known runtime is O($n^3+n^2\log^2 n\log b$) for an approximation within $2^{-b}$.

Ryan's reference is ``Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516''.

(I believe there is also a discussion about the relationship between the complexities of  eigenvalues and matrix multiplication in the older Aho, Hopcroft and Ullman book ``The Design and Analysis of Computer Algorithms'', however, I don't have the book in front of me, and I can't give you the exact page number.)


Finding a certificate if E=NE If $\textbf{P}= \textbf{NP}$ then for every language from $\textbf{NP}$ there exists an algorithm of finding a certificate in polynomial time.

Assume that $\textbf{E} = \textbf{NE}$. Is it true that there is an algorithm of finding a certificate in exponential time for every language from $\textbf{NE}$?

R. Impagliazzo ; G. Tardos shown that there exists  an oracle  relative to which
$\textbf{E} = \textbf{NE}$ , yet there is an exponential-type search problem
that requires doubly exponential randomized time.

The similar situation with collapsing of exponential hierarchy.


When we use a proof of unsatisfiability to derive an interpolant, isn't using the interpolant to check satisfiability now redundant? A few papers I've been reading have algorithms on using interpolants for the following clauses (bounded model checking):

$$ \begin{align*}
A &= I \wedge T_1 \\
B &= T_2 \wedge T_3 \wedge \ldots \wedge T_k \wedge (F_1 \vee F_2 \vee \ldots \vee F_k) \\
\end{align*} $$

This interpolant is then used to compute an over approximation of reachable states and then we can check for inconsistency with less computation.

BUT, the interpolant itself is derived from a proof of unsatisfiability. So before you get the interpolant, wouldn't you already know if the final states are reachable?

If the formula is satisfiable you cannot construct an interpolant. If the formula is unsatisfiable, you know that the final states are not reachable in at most $k$ steps. You do not know about reachability of final states in $k+1$ or more steps.

If the formula you suggest is unsatisfiable, you can replace the sub-formula $I$ of $A$ with the interpolant and check for satisfiability. If this new formula is unsatisfiable, you know that the error state is not reachable in $k+1$ steps. Something significant just happened. We were able to determine that the final states are not reachable in $k+1$ steps using only $k$ unwindings.

Interpolant computation can repeat until the formula is unsatisfiable, in which case you are stuck, or until a new interpolant implies the disjunction of the old interpolants. The second case is another advantage of interpolants. We use them to detect fixed points. Detecting a fixed point with just the bounded model checking formula is not easy.

A one-line intuition I once heard was: interpolation is a poor person's quantifier-elimination.


What algorithm is behind akinator or 20q? The title speaks for itself. Here are Akinator and 20Q.

The principle of these games is to ask a user a number of questions relating to some entity chosen by the user. And then find out what is this entity. The core of the algorithm is to find the "most useful question" at each round, while dealing with a user who might not answer all questions correctly.

"most useful question" being defined as the question that give the most information, in the optimal case splitting the audience (or number?) of candidate entities into two equal halves.

I found a paper that described some algorithms (well the word "algorithm" was not used, but the proofs could be turned into algorithms). Unfortunately I cannot find this paper again :( . The paper described the problem with game theory concepts, with some levels of lying allowed to the user (it discussed  3 levels of lying). Please post if you think you know the paper.

I think you are probably looking for "On playing “Twenty Questions” with a liar", Dhagat, Gacs, and Winkler, SODA 1992, http://portal.acm.org/citation.cfm?id=139404.139409

The many other papers that cite this one probably include additional relevant hits.


References for TCS proof techniques Are there any references (online or in book form) that organize and discuss TCS theorems by proof technique?  Garey and Johnson do this for the various kinds of widget constructions needed for NP-completeness proofs (particularly in chapter 3 of their book), but I'm wondering if there's anything that treats proof techniques in TCS more broadly.

So for example, topics might include diagonalization, broken down further by the type of construction used; proofs by computation histories; tableau constructions; incompressibility arguments, etc.  I suppose I could just chop up a standard theory of computation text and rearrange the sections, but it would be great if there is something out there that also provides some additional commentary and shows where there are commonalities between the techniques being used.

Just to be clear, since any text is going to use proofs, what I'm really interested in finding is a reference where the proof techniques themselves are the actual subject matter.

In addition to chapter 3 of Garey and Johnson, here's another partial example that just occurred to me: in Li and Vitanyi, in chapter 6 they discuss the incompressibility method and give examples of how to apply the technique.

The Complexity Theory Companion by Hemaspaandra and Ogihara.  It's not exhaustive in terms of techniques (I imagine no such book is), but I think it qualifies as an answer to your question.  Here are the titles of the chapters:

The Self-Reducibility Technique.
The One-Way Function Technique.
The Tournament Divide and Conquer Technique.
The Isolation Technique.
The Witness Reduction Technique.
The Polynomial Interpolation Technique.
The Nonsolvable Group Technique.
The Random Restriction Technique.
The Polynomial Technique.


Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler? Defunctionalization is a program transformation that converts higher-order programs into first-order programs. The idea is that given a program, there are only finitely many lambda-abstractions, so you can replace each lambda with an id, and each function application with a call to an apply procedure which branches on that id.  This is sometimes used in compilers for functional languages, but its applicability is limited by the fact that defunctionalization is a whole-program transformation (you must statically know all of the functions in the program), and so only whole-program compilers make use of it.

However, Pottier and Gauthier have a given a polymorphic typed defunctionalization algorithm using a more sophisticated typing involving GADTs. Now, given their encoding, it's possible to add a catch-all case to their lambda datatype that isn't a tag, but which contains a higher-order function. This means that it should be possible to use their encoding to defunctionalize on a module-by-module basis.

Has anyone done this, and point me to a compiler using this idea? (Toy compilers are okay, and in fact preferred.)

One approach is described by

Georgios Fourtounis and Nikolaos S. Papaspyrou. 2013. Supporting Separate Compilation in a Defunctionalizing Compiler. SLATE 2013.

As @gasche mentions:

  A different approach at the problem would be to consider that each module can define its own "defunctionalized functions" type and dispatcher/handler.

You can "link" those types and handlers with a specialized linker.
Unlike using open datatypes, you concatenate the list of constructors and the case functions.
But the linker must add cases for partial application: Without whole-program analysis, you cannot predict which partial applications can be used for which function, so you add all cases. An $n$-ary function can be partially applied to $i$ arguments (with $0< i < n$) and produce a function of arity $n-i$, which can be partially applied again.


Longest edge length of the greedy spanner on uniformly distributed pointsets in $[0,1]^d$ Let $P$ be a set of $N$ points in $\mathbb{R}^d$. For any $t \geq 1$, a $t$-spanner is an undirected graph $G=(P, E)$ weighted under the Euclidian measure, such that for any two points $v$, $u$, the shortest distance in $G$, $d(v, u)$, is at most $t$ times the Euclidian distance between $v$ and $u$, $|v u|$ (note that this definition can easily be extended to arbitrary measure spaces).

Consider the following algorithm with $P$ and $t$ as input:

E = empty
for every pair of points (v, u) in ascending order under |vu|
    if the shortest path in (P, E) is more than t times |vu|
        add (v, u) to E
return E

This algorithm computes the so-called greedy spanner (or path-greedy spanner). This graph has been subject to considerable research: it produces extremely good spanners, both in practice and in theory.

I'm interested in the length of the longest edge in the greedy spanner if $P$ is uniformly distributed in $[0,1]^d$ (the case that d=2 is fine as well). I conjecture this maximal length is at most about $1 / \sqrt{N}$, potentially with some log factors and factors $d$. This conjecture is motivated by experimental data.

The reason for my interest is that I have an algorithm that computes the greedy spanner quickly if the length of the longest edge is relatively short. If the above is correct, then it would mean my algorithm is applicable to the above scenario, and therefore potentially useful in practice.

I have found some papers analyzing the number of edges and the degree of other types of spanners on randomly distributed pointsets, but none on the length of the longest edge. The probability theory involved seemed rather complicated, so I was hoping something was known before attempting a proof myself.

In our paper Distribution-Sensitive Construction of the Greedy Spanner (accepted for ESA 2014) we prove the following (combining Theorem 4 and Lemma 6):

  There exists $c_t$ dependent only on $t$ such that for every $c > 0$, if $P$ is a set of points uniformly and independently distributed at random in a $\sqrt{n} \times \sqrt{n}$ square and $n$ is large enough, then with probability at least $1 - n^c$, the greedy $t$-spanner on $P$ does not have edges longer than $c \cdot c_t \log n$.

Our bound on $c_t$ is fairly large, but we have experimental evidence that the 'right' bound is $\frac{1}{\sqrt[4]{t-1}} \cdot \frac{\log n}{\log \log n}$.


Parameterized complexity of Exact Cover Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \subseteq \mathcal{S}$ such that $|\mathcal{S}^*| = K$ and such that each element of $U$ is contained by exactly one subset from $\mathcal{S}^*$.

What is parameterized complexity of the $\mathrm{ExactCover}$ problem for the parameter $K$ (the number of sets used in coverage)? It is known that  $\mathrm{SetCover}$ is $\mathrm{W}[2]$-complete, but is there anything known about $\mathrm{ExactCover}$ for $K$?

Correction:

I have claimed (see below) that "Independent Dominating Set" is a special case of ExactCover. This claim was wrong, as two vertices in the ind-dom set may have overlapping neighborhoods.

In fact, "Exact Cover" is contained in W[1].
It is recognizable by a tail-nondeterministic RAM (as introduced by Flum & Grohe), and therefore lies in W[1]:

In the preprocessing phase, construct and store a 2-dimensional table
that states for every two subsets $S_i$ and $S_j$ in $S^*$ whether they overlap.
Furthermore, construct a second table that stores for every subset $S_i$ in $S^*$ its cardinality. This clearly can be done in polynomial time.
In the guessing phase, guess a system of $k$ (indices of) subsets in $S^*$. This clearly can be done in $O(f(k))$ time on a RAM.
In the verification phase, first check whether any two guessed subsets overlap, by looking up the 2-dimensional table. Then check whether the total size of all guessed subsets equals $|U|$. (The first check guarantees that every element of $U$ is covered at most once, and the second check guarantees that it is covered at least once.) All this can be done in $O(g(k))$ time on a RAM.

Correct answer:

ExactCover is W[1]-complete. The above discussion shows containment in W[1].
Furthermore, ExactCover contains the W[1]-complete PerfectCode problem as a special case. (Given a graph $G$ and an integer $k$. Does $G$ contain a subset $C$ of $k$ vertices, such that every vertex in $G$ is contained in the closed neighborhood of exactly one vertex in $C$?)

R.G. Downey, M.R. Fellows
Fixed-parameter tractability and completeness. II. On completeness for W[1]
Theoretical Computer Science 141 (1995), pp. 109–131

Old (wrong) answer, left for reference:

"Independent Dominating Set" is W[2]-complete, and a special case
of your ExactCover problem:

R.G. Downey and M.R. Fellows.
Fixed-parameter tractability and completeness.
Congressus Numerantium 87:161–178, 1992.


About some possible optimality properties of Ramanujan graphs The Ramanujan graphs are optimal from the Alon-Bopanna point of view but..

Is there any sense in which one can call Ramanujan graphs to be the "optimal" spectral sparsifiers? (Reference : http://arxiv.org/pdf/0808.0163v3.pdf )

(..At least w.r.t $K_n$ can one say that given any $d$ and $n$, any $d-$regular Ramanujan graph on $n$ vertices, say $R_{(d,n)}$, gives the smallest $a$ s.t $x^T L_{K_{n}}x \leq \frac{n}{d} x^TL_{R_{(d,n)}}x \leq a x^TL_{K_{n} }x , \forall x \in \mathbb{R}^n$?..or some such similar inequality?.. )
Does the usual Cheeger's inequality become sharper if restricted to Ramanujan graphs? Or do we otherwise know of graphs which either saturate the Cheeger's inequality and/or maximize any of the combinatorial notions of expansion?

The only kind of connection I know of between the spectral gap of an expander to its combinatorial expansion are statements like Theorem 4 and 6 here in these notes, http://www.math.rutgers.edu/~sk1233/courses/graphtheory-F11/expander1.pdf. But even this is a lower bound and not an upperbound. One can put in $\lambda = 2\sqrt{d-1}$ in these two theorems but that somehow looks too weak and naive.

I wonder if something sharper can be said about the combinatorial expansion properties of a Ramanujan expander : may be some sense in which one can justify calling them optimal from this point of view too?

Lets say we use the definition of Ramanujan graph as those $d-$regular graphs all of whose  adjacency eigenvalues are of magnitude $\leq 2\sqrt{d-1}$ except the largest and the smallest.
For Cheeger's Inequality lets use the form as in these notes, http://www.eecs.berkeley.edu/~luca/books/expanders.pdf, i.e for a $d-$regular graph,

$$ \frac { \lambda_{1+min}(I - \frac{1}{d}A )}{2 } \leq \phi(G) = min _{ S \subset V, \vert S \vert \leq \frac{\vert V \vert}{2} } \frac {\vert \partial S \vert }{d \vert S \vert }  \leq \sqrt {2\lambda_{1+min}(I - \frac{1}{d}A )}$$

At least among regular bi-partite graphs, Ramanujan graphs provide the optimal approximation of the complete bipartite graph. Let's say that a graph $H$ $C$-approximates a graph $G$ if $tL_H \preceq CL_G$ for $t$ the smallest real number such that $L_G \preceq tL_H$. (I.e. $t := \|L_H^{-1/2} L_G L_H^{-1/2}\|$ where the norm is the operator norm and inverses are taken w.r.t. to the space orthogonal to the all-ones vector). The eigenvalues of $L_{K_{n,n}}$ are $\lambda_1 = 0, \lambda_2 = \ldots \lambda_{2n-1} = n, \lambda_{2n} = 2n$. For any $d$-regular bipartite $H$, the eigenvalues $0=\mu_1 \le \ldots \le \mu_{2n} = 2d$  of $L_H$ come in pairs $d \pm x$. By Alon-Boppana, $\mu_2 \le d-2\sqrt{d-1}$, and, therefore, $\mu_{2d-1} \geq d + 2\sqrt{d-1}$ (ignoring lower-order terms). This implies $C \geq \frac{d + 2\sqrt{d-1}}{d - 2\sqrt{d-1}}$, which is achived by a $d$-regular Ramanujan graph.


Number of subgraphs with a given number of nodes Let $G = ( V_G, E_G )$ be a graph. Let $E_H \subseteq E_G$.
The subgraph of $G$ edge-induced by $E_H$ is $H = ( V_H, E_H)$, where
$V_H = \{ v \in V_G : \exists ( u, w ) \in E_H\ v = u \lor v = w \}$
Let $k_1 \leq |E_G|$ and $k_2 \leq |V_G|$ be given in input.
I would like to determine the number $k_3$ of edge-induced subgraphs of $G$ having $k_1$ edges and $k_2$ nodes. Clearly, I don't want to enumerate all the (exponentially many) subgraphs of $G$ having $k_1$ edges.

Questions:

Is it possible to determine $k_3$ in time polynomial in $|E_G|$?
What if $G$ is 3-regular?
What if $G$ is 3-regular planar?
What if $G$ is 3-regular planar bipartite?
Which is the best known algorithm to compute $k_3$? $\longleftarrow$ Added on 30/08/2012

Let $f(G, k_1, k_2)$ be the counting problem that you have defined. Then
$$g(G) = \sum_{k_1 = 0}^{|V_G| / 2} f(G, k_1, 2 k_1)$$
counts the number of matchings in $G$, which only uses a linear number of oracle calls to your problem.

Since counting matchings in 3-regular planar graphs is #P-hard (see ref below), your questions (1), (2), and (3) all give a #P-hard problem. Your last question (4) probably gives a #P-hard problem as well because counting matchings in 3-regular biparitie planar graphs is probably #P-hard, but I don't know if anyone has proved this.  The closest that I know of is that

counting matchings in 2,3-regular biparitie planar graphs is #P-hard and
counting matchings in biparitie planar graphs of max degree 6 is #P-hard.

The reference that I promised above is Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP by Jin-Yi Cai, Pinyan Lu, Mingji Xia. Theorem 6.1 proves that counting matchings in 3-regular planar graphs is #P-hard in the special case that $[y_0, y_1, y_2] = [1,0,1]$ and $[x_0, x_1, x_2, x_3] = [1,1,0,0]$.


Simple model of computation with homoiconicity Is there a simple model of computation with homoiconicity?

It would also be nice if, like beta reduction in lambda calculus, every step in execution yields a new valid program.

Besides the lack of homoiconicity, another annoyance of lambda calculus is the necessity of checking for free variables when performing substitution.

The paper Typed Self-Representation by Tillmann Rendel, Klaus Ostermann and    Christian Hofer seems to satisfy the requirements, and it's typed too. Perhaps it doesn't satisfy the criteria of being a simple model of computation.


Formal notion for energy complexity of computational problems Computational complexity includes the study of time or space complexity of computational problems. From the the perspective of mobile computing, energy is very valuable computational resource. So, Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms. Also, Are there established energy-complexity classes for computational problems?

References are appreciated.

Is there a well studied adaptation of Turing machines that account for the energy consumed during the execution of algorithms?  No!

But maybe you could come up with one. It's possible you could divide the Turing machine steps into reversible and non-reversible (the non-reversible ones are where information is lost). Theoretically, it is only the non-reversible steps that cost energy. A cost of one unit of energy for each bit that is erased would theoretically be the right measure.

There is a theorem of Charles Bennett that the time complexity increases by at most a constant when a computation is made reversible (C.H. Bennett, Logical Reversibility of Computation), but if there are also limits on space, then making the computational reversible might incur a substantial increase in time (Reference here). Landauer's principle says that erasing a bit costs $kT\, \ln 2$ of energy, where $T$ is temperature and $k$ is Boltzmann's constant. In real life, you cannot come anywhere close to achieving this minimum. However, you can build chips which perform reversible steps using substantially less energy than they use for irreversible steps. If you give reversible steps a cost of $\alpha$ and irreversible steps a cost of $\beta$, this seems like it may give a reasonable theoretical model.

I don't know how Turing machines with some reversible steps relate to chips with some reversible circuitry, but I think both models are worth investigating.


"Verifiable information": is this a known concept? The following seems to me like a natural definition and I wonder whether it's been studied somewhere

Consider $\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}$ a set of languages.
Then $K \subset \lbrace 0, 1 \rbrace^\omega$ is called "$\mathsf{X}$-verifiable information" when there is $L \in \mathsf{X}$ s.t.

(i) Given $x \in L$, every prefix of $x$ is in $L$

(ii) Given $f \in K$, every prefix of $f$ is in $L$

(iii) Given $f \notin K$, the length $n$ prefix of $f$ is outside $L$ for $n >> 0$

For example $\lbrace f \rbrace$ is $\mathsf{R}$-verifiable information iff $f$ is computable. This can be seen by constructing an algorithm which runs the verification on all strings of length $n$ and collects the prefixes of length $m$ of those strings which passed the verification. For $n >> m$, the only prefix which remains is the correct one

However if $K$ is $\mathsf{R}$-verifiable information it doesn't mean every $f \in K$ is computable: for example consider $K = \lbrace 0, 1 \rbrace^\omega$

A non-trivial example of $\lbrace f \rbrace$ which is $\mathsf{P}$-verifiable is as follows. Consider $L \in \mathsf{NP} \cap \mathsf{coNP}$ and let $f$ be an encoding of $L$ together with the corresponding $\mathsf{NP}$ and $\mathsf{coNP}$ witnesses (i.e. for each $x \in \lbrace 0, 1 \rbrace^*$, $f$ encodes either an $\mathsf{NP}$-witness proving $x \in L$ or a $\mathsf{coNP}$-witness proving $x \notin L$)

$K\subseteq\{0,1\}^\omega$ is $\mathsf{R}$-verifiable if and only if $K$ is a $\Pi^0_1$ class (in Cantor space), a concept that has been studied extensively in computability-theory. They are also called effectively closed sets.

A set $K$ is a $\Pi^0_1$ class iff it is the set of infinite paths through a recursive (computable) tree, and this is the version of the concept that you defined.

A monograph devoted to them:

Effectively Closed Sets (Douglas Cenzer and Jeffrey B. Remmel), Perspectives in Logic, Cambridge U. Press, 350 pages, to appear.


Heuristics for the minimum-weight $k$-clique problem Hello
Does someone have an idea for heuristics for the problem:

  Given undirected weighted(weights on edges) complete
  graph $G(V,E)[|V|=n,|E| = m]$, find a clique of size $k < n$(k is number of nodes) having
  the minimum weight.

I have searched for minclique problem but it doesn't really answer my question.
Thank you in advance.

Your problem appears to be the minimization variant (flip the edge weight signs?) of the edge-weighted maximal clique problem. Check out this reference:

  @article{park1996extended,
  title={{An extended formulation
  approach to the edge-weighted maximal
  clique problem}},
  author={Park, K.
  and Lee, K. and Park, S.},
  journal={European Journal of
  Operational Research},
  volume={95},
  number={3},
  pages={671--682},
  year={1996},
  publisher={Elsevier} }

where they discuss various LP-based heuristics.


Approximate graph colouring  with a promised upper bound on maximum independent set In my job the following problem arises:

Is there a known algorithm, that approximates the chromatic number of a graph without an independent set of order 65? (So alpha(G)<=64 is known and |V|/64 is a trivial lower, |V| a trivial upper bound. But are there better proven approximations under this special condition?)

What if we relax to the fractional chromatic number? And to "good" running times in average cases?

Compute a maximum matching in the complement of the input graph. Every unmatched node must be in a different color class in any coloring. So: if you get at least cn matched edges, then the matching itself gives you a coloring with an upper bound of (1-c)n, and an approximation ratio of 64(1-c). If you don't get at least cn edges, then you get a lower bound of (1 - 2c)n colors and an approximation ratio of 1/(1-2c). Solving the equation 64(1-c) = 1/(1-2c) leads to an approximation ratio slightly larger than 32; see Sasho Nikolov's comment for the precise value.


Testing empty set intersection Consider the following empty intersection problem:

INPUT: a ground set $[n]:=\{1, \ldots, n\}$; a set family $S_1, \ldots, S_m$ s.t. $S_i\subseteq [n]$ for every $1\leq i\leq m$
TASK: on query $X\subseteq [n]$ decide whether there exists $1\leq i\leq m$ s.t. $S_i\cap X = \emptyset$.
TASKbis: on batch queries $X_1, \ldots, X_k\subseteq [n]$ decide whether $S_i\cap X_j=\emptyset$ for each $i,j$.

I'm in deep search for references about this problem, both TASK as well as the batched version TASKbis: fast algorithms (sequential, parallel, randomized, any other model is appreciated), also complexity lower bounds or other characterizations...

Observe that we can impose special values of $m$, for example consider $m=n^2$, or similar ...

As you might have realized by now, this problem is closely related to Matrix Multiplication.

Particularly: Task B asks to preprocess an m by n matrix S, such that given as a query a n by matrix X, we need to compute the m by m boolean product SX. For particularly structured matrices S, this can be solved by something like FFT. But I suspect that for a non-structured S (say random S) the best you could do is used fast matrix multiplication.

If the matrices S and X are sparse (i.e. the input sets are of cardinality << n) then there are some algorithms for sparse matrix multiplication that can give some good results.

About the first task, it's of course even harder-looking, and I suspect that, unless the input S is of one of those special structures, the best approach is the naive one that takes O(n) time per query.


Compressing information about the halting problem for oracle Turing machines The halting problem is well-known to be uncomputable. However, it is possible to exponentially "compress" information about the halting problem, so that decompressing it is computable.

More precisely, it is possible to compute from a description of $2^{n}-1$ Turing machines and an $n$-bit advice state the answer to the halting problem for all $2^{n}-1$ of the Turing machines, assuming the advice state is trustworthy - we let our advisor choose the bits to describe how many of the Turing machines halt in binary, wait until that many halt, and output that the remainder do not halt.

This argument is a simple variant of the proof that Chaitin's constant can be used to solve the halting problem. What surprised me is that it is sharp.  There is no computable map from a description of $2^n$ Turing machines and an $n$-bit advice states to $2^n$ bits of halting output that gets the right answer, for each tuple of Turing machines, for some tuple of bits. If there were, we could produce a counterexample by diagonalizing, with each of the $2^n$ Turing machines simulating what the program does on one of the $2^n$ possible arrangements of the $n$ bits and then choosing its own halting state to violate the prediction.

It is not possible to compress information about the halting problem for Turing machines with a halting oracle at all (without access to some kind of oracle yourself). The machines can just simulate what you predict on all possible inputs, ignoring the ones where you don't halt, and choosing their halting times to give the lexicographically first answer you didn't predict on any input.

This motivated me to think about what happens for other oracles:

  Is there an example of an oracle where the halting problem for Turing machines with that oracle can be compressed at an intermediate growth rate between linear and exponential?

More formally, given an oracle, let $f(n)$ be the greatest $m$ such that there exists a computable partial function from $m$ oracle Turing machines and $n$ bits to $m$ bits, such that for each $m$-tuple of oracle Turing machines, there is an $n$-tuple of bits, where the value of the function evaluated on that input equals the $m$-tuple of $1$ for each oracle Turing machine that halts and $0$ for each oracle Turing machine that runs forever.

Is there an oracle where $n<f(n)<2^{n}-1$? Is there an oracle where $\omega(n)=f(n)=o(2^n)$?

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.


Min cost set of edges to connect 2 subgraphs s.t dist of nodes between subgraphs <= K I find myself with another graph problem that I can't find the name of. I was wondering if anyone was able to identify if this problem and any efficient algorithms to solve it are known.

The intuition for the problem is I have two islands and a set of possible locations I can build bridges between those islands. I want to determine a minimum cost set of bridges to build such that it takes a short amount of time (no longer than $K$ hours) to travel from any point on the first island to any point on the second island.

To put this into a graph context: We are given two connected components $A$ and $B$ and a set of edges $\{e\}$ with cost $c_e$ required to add them to the graph. I want to find the minimum cost set of edges that connects $A$ and $B$ such that the maximum unweighted distance between any any two nodes between the components is at most $K$.

More precisely:

Let $x_e = 1$ if we choose to add edge $e$ and $0$ otherwise

Let $G' = A \cup B \cup \{e \mid x_e = 1\}$ be the graph augmented with the edges that we added.

Let $dist(G, u, v)$ be the length of the shorted path between $u$ and $v$ in graph $G$.

minimize $\sum_{e} x_e c_e$ such that

$ dist(G', u, v) < K\quad \forall u, v \in A \times B$

When the costs are all equal, you are looking for the fewest number of edges to bring your graph to being of at most diameter $k$. This is the graph diameter augmentation problem. You are looking for the edge-weighted version, which I believe has been studied as well.

There are a number of versions of diameter augmentation out there: some that fix or bound the amount of bridge you can build and the task is the bring the diameter down to as small as possible. Or, your version, you have some $K$ in mind and you want to find the cheapest amount of bridges in order to acheive that $K$.

Naming of these problems is non-standard or inconsistent in the literature, but searching for 'graph diameter augmentation' will get you on your way.


The minimum number of arithmetic operations to compute the determinant Has there been any work on finding the minimum number of elementary arithmetic operations needed to compute the determinant of an $n$ by $n$ matrix for small and fixed $n$?  For example, $n=5$.

It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant.  See for example this table on Wikipedia, as well as its footnotes and references.  Note that the asymptotic complexity of matrix inversion is also the same as matrix multiplication in this same sense.

The equivalence is quite effective.  In particular, you can recursively compute the determinant of a $n\times n$ matrix by working on $(n/2) \times (n/2)$ blocks using the Schur complement:

$$ \text{$D$ invertible}\qquad\implies\qquad\det \begin{pmatrix}A&B\\C&D\end{pmatrix} = \det(D) \det(A-BD^{-1}C). $$

Thus, you can compute an $n\times n$ determinant by computing two $(n/2)\times (n/2)$ determinants, inverting one $(n/2)\times (n/2)$ matrix, multiplying two pairs of $(n/2)\times (n/2)$ matrices, and some simpler operations.  Expanding the determinant calls recursively, the complexity ends up being dominated by the matrix multiplication and inversion.

This works well even for small $n$ and even without using sub-cubic matrix multiplication algorithms.  (Of course, it ends up being more-or-less equivalent to Gaussian elimination.)  For example, for $n=4$, we can compute $\det(D)$ with two multiplications, $D^{-1}$ with four divisions, $BD^{-1}C$ with $2\times 8=16$ multiplications, $\det(A-BD^{-1}C)$ with two multiplications, and the final answer with one multiplication.  The total number is $2+4+16+2+1=25$ multiplications plus divisions, which is less than the $40$ from cofactor expansion.  Using Strassen's algorithm saves two multiplications here, but more asymptotically.

You may notice that this expansion crucially uses division.  If you wish to avoid division, then one can do so in $O(n^4)$ operations by working with Clow sequences and dynamic programming.  It is also known how to achieve $n^{2+\omega/2+o(1)}$ multiplications and no divisions.


Polynomial speedups with algorithms based on semidefinite programming This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time.

I am still puzzling over the actual running time of algorithms that compute the solution of  a semidefinite program (SDP). As Robin pointed out in his comment to the above question, SDPs cannot be solved in polynomial time in general.

It turns out that, if we define our SDP carefully and we impose a condition on how well-bounded the primal feasible region is, we can use the ellipsoid method to give a polynomial bound on the time needed to solve the SDP (see Section 3.2 in L. Lovász, Semidefinite programs and combinatorial optimization).
The bound given there is a generic "polynomial time" and here I am interested in a less coarse bound.

The motivation comes from the comparison of two algorithms used for the quantum separability problem (the actual problem is not relevant here, so don't stop reading classical readers!).
The algorithms are based on a hierarchy of tests that can be cast into SDPs, and each test in the hierarchy is on a larger space, that is, the size of the corresponding SDP is larger.
The two algorithms I want to compare differ in the following tradeoff: in the first one, to find the solution you need to climb more steps of the hierarchy and in the second one the steps of the hierarchy are higher, but you need to climb less of them. It is clear that in the analysis of this tradeoff, a precise running time of the algorithm used to solve the SDP is important. The analysis of these algorithms is done by Navascués et al. in arxiv:0906.2731, where they write:

  ... the time complexity of an SDP with $m$ variables and of matrix size $n$ is $O(m^2 n^2)$ (with a small extra cost coming from an iteration of algorithms).

In another paper, where this approach to the problem was first proposed, the authors give the same bound, but they use the more cautious term "number of arithmetic operations" instead of "time complexity".

My question is two-fold:

Which algorithm/bound are Navascués et al. referring to?
Can I replace the expression "polynomial time" in Lovász with something less coarse (keeping the same assumptions)?

I'm not familiar with details of the ellipsoid method specifically for semi-definite programs, but even for linear programs, analysis of the ellipsoid method is pretty subtle.

First, one needs to bound the number of iterations of the ideal ellipsoid algorithm.  Let $E_i$ be the ellispoid used in the $i$th iteration of the ellipsoid algorithm, and let $c_i$ be its centroid.  In the ideal algorithm, a separation/membership oracle gives you a halfspace $h_i$ that contains the optimum point $x^*$ but not the centroid $c_i$.  The next ellipsoid $E_{i+1}$ is the smallest ellipsoid containing $E_i\cap h_i$.  For each $i$, we have $vol(E_{i+1}) < (1-\frac{1}{n})\cdot vol(E_i)$, where $n$ is the dimension.  Thus, given a reasonable starting ellipsoid, the number of iterations is polynomial in $n$ and $\log(1/\varepsilon)$.  Computing $E_{i+1}$ from $E_i$ and $h_i$ requires (crudely) $O(n^2)$ arithmetic operations.  So the number of arithmetic operations is also polynomial in $n$ and $\log(1/\varepsilon)$.
However, some of those arithmetic operations are square roots!  It follows that the coefficients of the ideal ellipsoid $E_i$ are irrational numbers of degree $2^i$, and so there's no hope of actually computing $E_{i+1}$ exactly in any reasonable time.  So instead, one computes a close outer approximation $\tilde{E}_i \supset E_i$ at each iteration using finite precision arithmetic.  Grötschel, Lovasz, and Schrijver prove that if one uses (say) $10i$ bits of precision in the $i$th iteration, we still have $vol(\tilde E_{i+1}) < O(1-\frac{1}{n})\cdot vol(\tilde E_i)$, so the number of iterations increases by at most a constant factor.  But now each arithmetic operation during the $i$th iteration (including the operations performed by the separation oracle) requires $O(i~\text{polylog}~i)$ time.

Altogether, the total running time of the ellipsoid method is very roughly the square of the number of arithmetic operations.  Since the number of arithmetic operations is polynomial in $n$ and $\log(1/\varepsilon)$, so is the running time.


Embarrassingly Parallel: Formal Definition & Citation I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where:

The full solution can be discretized.
It is efficiently decomposable into subproblems that are similar in structure.
Each subproblem is (more or less) independently soluble (i.e. without a large communication overhead required between the subproblems).
The solutions of each subproblem are independent such that there is an efficient method that can reassemble them into the larger solution.

I realize there's some overlap in the bullets above, hence the question – how is 'embarrassingly parallel' or its synonymous technical term clearly defined? Is there a reference in the literature where this definition was first formalized?

Note: I'm not trained in TCS (as you may have guessed) and am aware that my descriptions above may not be entirely correct or in keeping with established formalisms and terminology.

There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion.  I understand it to basically mean that if you do the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.


Reduction/transformation from MinCostSat to MaxSat I recently ran into MaxSAT competitions website and was looking into the problem formulation. I vaguely remember reading somewhere that MinCostSAT and MaxSAT are related to each other and one can be reduced to another. I read here http://repository.lib.ncsu.edu/ir/handle/1840.16/4594 that the MaxSAT to MinCostSAT reduction is to use a slack variable for each clause in the MaxSAT and giving it the value of 1 and all other boolean variables 0 reduces the problem to MinCostSAT. Can some one please tell me how does this work? How does it make the MaxSAT instance the instance of MinCostSAT?

Also, what is the reduction from MinCostSAT to MaxSAT or may be even weighted MaxSAT, especially considering the fact that I have a problem to which I know the cost of assignments and want to minimize this cost and if I have the off the shelf solvers available like the ones that have won MaxSAT competitions, how do I go about reducing my MinCostSAT problem to MaxSAT?

P.S. I hope this won't be rejected as an implementation level question since my question is really about reduction. I can think about implementing it, if I know the reduction at least.

First thing to realize is that minimization can be rephrased as maximization of the negated literal (and vice a versa). So minimizing $x+y$ is the same as  maximizing $\lnot x + \lnot y$. So to get a partial maxsat problem you just add the unit clauses $\lnot x$, $\lnot y$ as soft clauses and the original clauses as hard. (partial MaxSAT is crucial here, weighted partial MaxSAT is needed if you have  coefficients in the minimization function)


What is the quantum computational model? I have occasionally heard people talk about quantum algorithms and about states and the ability to consider multiple possibilities at once, but I have never managed to get someone to explain the computational model behind this. To be clear, I am not asking about how quantum computers are physically constructed, but rather how to view them from a computational point of view.

I'll echo Martin Schwartz's recommendation of Nielsen & Chaung as the standard reference; there are many others as well.

Research in the field prefers to consider uniform families of quantum circuits, which (ironically) are directed acyclic networks describing how the state of one or more registers transforms with time, in a way similar to classical boolean circuits. If you wish to learn more, I recommend learning in terms of this model.

I would like to give some qualitative answers to complement Martin's response.

Quantum computation does not actually consider "multiple possibilities at once" --- or more precisely, whether or not you consider them to consider multiple possibilities at once is a matter of your choice of interpretation of quantum mechanics, i.e. a philosophical choice which has no bearing on the ability or predictions of the computational model. ("Considering multiple possibilities at once" corresponds to the "many worlds interpretation" of QM.)
At the very least, one can say that a quantum computer considers multiple possibilities at the same time only to the extent that a randomized computation using coin-flips considers multiple possibilities at the same time. This is because:
Quantum states are generalizations of "the usual" probability distributions --- with some simple but important differences. A probability distribution can be represented as a non-negative real vector whose entries sum to 1: that is, a unit vector in the ℓ1 norm. Probabilistic computations must map ℓ1-unit vectors to other such vectors, and so they are described by stochastic maps. One can describe quantum computation in a similar way, except using ℓ2-unit vectors over ℂ (not restricted to be real or non-negative); transformations are by those maps which preserve the ℓ2-norm, i.e. unitary operations. This difference is not trivial, of course, nor does it explain yet what the coefficients of the quantum state vectors mean. But it may help to explain what is going on with Hilbert spaces and tensor products in quantum computation: to wit, exactly the same things as happen in probabilistic computation. The configuration space of a random bit is a vector in ℝ+2 (where ℝ+ are the non-negative reals); but because random bits can be correlated, we combine the configuration spaces of one or more random bits by taking the tensor product. So the configuration space of two random bits is ℝ+2 ⊗ ℝ+2 ≅ ℝ+4 , or the fully-general space of probability distributions over the four distinct two-bit strings. An operation A on the first of these random bits which does not act on the second is represented by the operator A ⊗ I2 . And so on. The same constructions apply to quantum bits; and we can consider quantum registers over sets of distinguishable elements the same way we consider probability distributions over such sets, again using ℓ2-norm vectors over ℂ. This description actually describes the "pure" quantum states --- the ones for which you can in principle transform in an information-preserving way to a delta-distribution over the bit-string 00...0 (or more precisely, to a state arbitrarily close to this in the ℓ2 norm). On top of the quantum-randomness (of which I have not yet mentioned anything explicit), you can consider vanilla-convexity-randomness corresponding to probabilistic mixtures of quantum states: these are represented by density operators, which can be represented by positive definite matrices with trace 1 (again generalizing "classical" probability distributions, which may be represented by the special case of positive diagonal matrices with trace 1). What is important about this is that, while quantum states are often described as being "exponentially large", this is because they are usually described using the same mathematical structures as probability distributions; why probability distributions are not described as "exponentially large" in the same way is unclear (but ultimately unimportant). The difficulty of simulating quantum states come from this fact, together with the fact that the complex coefficients of these ℓ2-distributions (or the complex off-diagonal terms of the density operators, if you prefer) may cancel in a way that probabilities cannot, rendering estimation of them more difficult.
Entanglement is just another form of correlation. For probabilistic computation on e.g. boolean strings, the only "pure" states (which can be mapped by information-preserving transformations to a delta-peaked distribution on 000...0) are the "standard basis" of delta-peaked distributions on the different boolean strings. Thus, this basis of ℝ+2n is distinguished. But there is no such distinguished basis in quantum mechanics, as far as we can tell --- this is clearest for quantum bits (look up spin 1/2 particles, if you want to know why). As a consequence, there are more information-preserving transformations than just the permutations: a continuous group of them, in fact. This allows would-be quantum computers to transform states in ways which are not possible for probabilistic computers, possibly obtaining an asymptotic advantage over them. But what about entanglement, which many people find mysterious, and claim to be the cause of the speed-up of quantum computers over classical? "Entanglement" here is really just a form of correlation: just as two random variables are correlated if their distribution is a convex combination of more than one product distribution (with different marginals on each variable), two "quantum variables" are entangled if their distribution is a linear combination (with unit ℓ2-norm) of two valid product distributions; it is the same concept under a different norm, and plays a similar role in communication tasks. (For example: "quantum teleportation" in quantum communication corresponds to encoding and decoding a message using a one-time pad classically.) This is a form of correlation which is more general than just classically correlated bits; but the only way to show this is that the correlations encoded in the entangled state apply to more than just one privileged basis. In a manner of speaking, entanglement is a consequence of the absence of a privileged basis.  People like to invoke entanglement as the key element of quantum computation, but this simply doesn't seem to hold water: there have been results showing that entanglement is not quantitatively important for Shor's algorithm to factor large integers, and that indeed a quantum system can have too much entanglement to be useful for a computation. In fact, everywhere that I am aware of that entanglement plays an important role in a quantum protocol is essentially one of communication (where correlations would be expected to play an important role for a classical protocol).

At this point, I begin wading into the domain of personal opinion, so I'll stop here. But hopefully, these remarks might de-mystify some of what is obscure about quantum computation and how it is described.


An invariance theorem for algorithmically random data in statistical learning Motivation:
The following invariance theorem for statistical learning in the setting of algorithmically random data occurred to me yesterday. This theorem uses the fact that the property of algorithmic randomness is transformation-invariant. I was motivated to find such a theorem for a couple reasons.
Such a theorem may be used to perform empirical tests using machine learning to determine whether a dataset was sampled from an algorithmically random process as well as to test extraordinary claims that a machine learning model can efficiently simulate algorithmically random processes.
Might this theorem be known by a particular name?
The learning problem:
Let's suppose $F_{\theta}$ is a function space that is useful for statistical learning(ex. Deep Neural Networks) such that $D_N = (X_N,Y_N)$ is a dataset where $X_N=\{X_i\}_{i=1}^{2N}$, the $X_i$ are sampled i.i.d. from a discrete random variable $X$, and $Y_N=\{Y_i\}_{i=1}^{2N} \in \{0,1\}^{2N}$ are the class labels.
If $D_N$ is split into balanced training and test sets $D_N^\text{train}$ and $D_N^\text{test}$ then we have $D_N^\text{train}=(X_N^\text{train},Y_N^\text{train})$ and $D_N^\text{test}=(X_N^\text{test},X_N^\text{test})$ such that $\lvert X_N^\text{train} \rvert = \lvert X_N^\text{test} \rvert = N$ and $X_N^\text{train} \cup X_N^\text{test} = X_N$.
Furthermore, we shall assume that the training and test sets are balanced so we have:
\begin{equation}
\frac{1}{N} \sum_i Y_i^\text{train} = \frac{1}{N} \sum_i Y_i^\text{test} = \frac{1}{2} \tag{1}
\end{equation}
Defining algorithmic randomness:
Now, $X$ is algorithmically random relative to $F_{\theta}$ if $X$ is incompressible relative to $F_{\theta}$ in the sense that for any choice of train-test split we have:
\begin{equation}
\mathbb{E}[K(X |F_{\theta})] = \min_{f \in F_{\theta}} \mathbb{E}[K(X |f)] \sim N \cdot \ln \lvert X \rvert \tag{2}
\end{equation}
where I used the fact that the expected Kolmogorov Complexity equals the Shannon entropy, and applied the Shannon source-coding theorem to i.i.d. data.
The conjecture:
In consequence, (1) implies that for a particular sample $X_N \sim X$ it may be possible to find $f \in F_{\theta}$ such that $\forall i \in [1,2N], f(X_i) = Y_i$ on the condition that the Kolmogorov Complexity:
\begin{equation}
K(f) \sim 2N  \tag{3}
\end{equation}
as this would amount to memorisation and not discovering regularities in $D_N$ since $X$ is algorithmically random relative to $F_{\theta}$. To be precise, if an arbitrary mathematical  transformation $T$(ex. random matrix) is applied to $D_N$ so:
\begin{equation}
X'_N = T \circ X_N \tag{4}
\end{equation}
given that $f(X_i)=Y_i \implies \delta_{f(X_i),Y_i} = 1$, the solution to the empirical risk minimisation problem may be formulated as follows:
\begin{equation}
\hat{f} = \max_{f \in F_{\theta}} \frac{1}{N} \sum_{i=1}^N \delta_{f(X'_i),Y_i} \tag{5}
\end{equation}
and for large $N$, the expected performance on the test set is approximated by:
\begin{equation}
\lim_{N \to \infty} \frac{1}{N} \sum_{i=N+1}^{2N} \delta_{\hat{f}(X'_i),Y_i} = \frac{1}{2} \tag{6}
\end{equation}
Note: I am implicitly interested in natural signals which exhibit algorithmic randomness, and the transformations $T$ are arbitrary to the extent that they don't change the phase-space dimension of the processes responsible for generating natural signals.
References:

Peter Grünwald and Paul Vitányi. Shannon Information and Kolmogorov Complexity. 2010.
Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie. The Elements of Statistical Learning. Springer. 2001.

I think this is a similar approach to Shnor's Martingale characterisation of algorithmic randomness, I have sent you an email with more info, but it is a potential nice non-overfitting test and also alternative characterisation.


Hitting set of pairwise intersecting families A hitting set of a family $\mathcal{S} = \{S_1, \dots, S_n\}$ is a subset $H$ of $\bigcup_{i=1}^{n} S_i$ such that $H \cap S_i \ne \emptyset$ for $1 \le i \le n$.
The problem to find a minimum hitting set of a given family is NP-hard in general,
since it generalizes the vertex cover problem. Now my question is:

  Does the hitting set problem remain NP-hard when the elements of $\mathcal{S}$ pairwise intersect?

I am also interested in the approximation hardness (or tractability) of this problem.

The answer is yes - the problem is still NP-Complete. for every set $S_i$ create a fake elements $e_i', e_i''$ and create a new sets $S_i' = S_i \cup \{ e_i'\}$ and $S_i'' = S_i \cup \{e_i''\}$. It is easy to verify that  any hitting set of the old system is a hitting set of the new system. Furthermore, except for the fake elements, every element now hit at least three sets.

Next, for every pair of sets in the new system (lets call them $T_i$ and $T_j$ to avoid confusion), create a fake element $x_{ij}$ and add it to both $T_i$ and $T_j$. Clearly, in the resulting set system all sets pairwise intersect, but the original optimal hitting set is still the optimal hitting set for this newest system.

Without any further restrictions the problem looks as hard as the original problem.

BTW, proving that indeed the optimal solution would not use any of the fake elements is not trivial. First, we can assume that a given hitting set for the new system does not include any $e_i'$ or $e_i''$, since otherwise we can move the elements to the original elements of the sets, and get a hitting set of similar size. It is slightly more subtle to see why the elements $x_{ij}$ are not in the optimal hitting set. Since it is tedious I would just leave a hint: build a graph connecting two sets $S_i$ and $S_j$ in the original system if $x_{ij}$ connects two sets that are derived from these sets. Argue that this graph in the minimal hitting set must be $3$ regular, and as such the number of edges in it strictly exceeds the number of sets present as vertices. As such, one can find a smaller hitting set for these sets.


Examples of learning via exactly integrable gradient flows If $\ell (\vec{w}, \vec{z})$ is the loss function at weights $\vec{w}$ and for data $\vec{z}$ then corresponding to a distribution ${\cal D}$ we can consider doing gradient flow with step-length $\eta >0$ to solve the corresponding risk minimization question,
$$\frac{d \vec{w}}{dt} = -\eta \cdot \frac{\partial }{\partial \vec{w}} \mathbb{E}_{\vec{z} \sim {\cal D}} [\ell (\vec{w}, \vec{z}) ]$$

Are there non-trivial examples of this for which the above ODE is exactly integrable and the risk gets minimized as $t \rightarrow \infty$ along the solution?

How about the simple squared loss function used in linear regression? That is, let $\ell(w(t), z) = \frac{1}{2n} \sum_{i=1}^n (z_i^\top w(t) - y_i)^2$ for data vectors $z_i \in \mathbb{R}^d$ and $y\in \mathbb{R}^n$?
For the sake of this answer, I'll use the shorthand notation $Z \in \mathbb{R}^{d\times n}$, where each column of $Z$ is the vector $z_i \in \mathbb{R}^d$.
If you use this as the loss function, then the given differential equation is $$\frac{dw(t)}{dt} = -\eta (ZZ^\top) w(t) + Z y.$$ I think this can be solved to get the solution you seek, and I explain below.
Suppose $Z$ is rank-$n$, and let $Z = \sum_{i = 1}^n s_i u_i v_i^\top$ be its singular value decomposition. Pre-multiplying the given ODE with any of the $u_i$ vectors yields the ODE $$ \frac{d}{dt} (u_i^\top w(t)) = - \frac{1}{n} s_i^2 u_i^\top w(t) + \frac{1}{n} s_i v_i^\top y.$$ This is a standard first-order constant coefficient ODE and can be solved  by, for instance, the method of integrating factors. Applying this technique gives $$ u_i^\top w(t) = \frac{1}{s_i} v_i^\top y + c_i (\frac{s_i}{n} v_i^\top y) e^{-\frac{s_i^2 t}{n}}, $$ where $c_i$ is a constant of integration. If you are given an initial condition, you can use it to obtain $c_i$. Suppose you have $w_0 = 0$. Then, this initial condition results in the rule $$u_i^\top w(t) = \frac{1}{s_i} (v_i^\top y) (1 - e^{-s_i^2 t/ n}), $$ for all $i \in [n]$. Therefore, as $t\rightarrow \infty$, we have for all $i \in [n]$ that $u_i^\top w(t) \rightarrow \frac{1}{s_i} v_i^\top y$. This means the loss $\ell(w_t, z) \rightarrow 0$, as you require.


Magic constant to solve NP-complete problem in polynomial time Let's suppose that $P\ne NP$. Is that possible to solve all the instances of size $n$ of an NP-complete problem in polynomial time using some "universal magic constant" $C_n$ that has a polynomial length $P(n)$?
Clearly, if $P\ne NP$ this constant can be only calculated in exponential time and the calculation must be done for each $n$.

Thanks

Probably not. What you are asking is whether NP $\subset$ P/poly. If this were true, then the polynomial hierarchy would collapse (this is the Karp–Lipton theorem), something that is widely believed not to happen.


Constraints on sliding windows Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer.

I would like to know if anything is known on the time and space complexity with respect to $n$ to check for membership in $L$ for a sliding window of size $n$ over an infinite stream. Here I mean the incremental complexity by moving the window along the stream and computing on the fly the membership of the window seen as a word to the language $L$.

Exemple:  It is simple to check with space complexity $\mathcal{O}(\log(n))$ and time complexity $\mathcal{O}(1)$ for the language $\Sigma^* ab \Sigma^*$ with $\Sigma=\{a,b\}$. You simply need to remember the last $ab$ factor seen in a register and to increment it by $1$ at every new symbol, which is constant in the appropriate RAM model.

Case of interest (at least for me) includes:

$L$ is the Parity language over $\{0, 1\}$, the number of $1$ is even, or in regexp: $(0^* + 10^*1)^*$
$L$ is the Majority language over $\{0,1\}$, there are more $1$ than $0$.
$L$ is the language over $\{0,1,e\}$ such that there exists a $0$ before a $1$.
$L$ is an arbitary regular language.

In particular, is it needed to store all the window for those languages?
It seems so but I fail to see a proof. Even if we allow a space $\mathcal{O}(n)$, can we reply in time $\mathcal{O}(1)$?

It seems it would depend on your particular model, in particular what information you have access to.

From what I infer, you are thinking of the following model:

you have a memory $m$, for instance of size $O(\log n)$.
at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$
you then have to say whether the word under you new sliding window shifted by $1$ is in $L$, based solely on $m$.

In particular, you don't have access to the letter leaving the sliding window. If you had this information, the problem would be more symmetrical, and for instance languages Parity and Majority would be computable with constant and logarithmic memory respectively.

Memory constraint

In the setting above without this information, here is for instance a proof that a linear memory is needed for Parity, so  basically you need
 to remember the whole word.
Indeed, if you use sublinear memory, there are two different words $u$ and $v$ of length $n$ that give rise to the same memory state $m$.
Then, let $d$ be the first position where $u$ and $v$ differ, and consider that your stream continues with $0^d$. After having read this suffix, you will have the same memory $m'$, so you must answer the same thing in both cases. But since the bit that got out of the window is not the same for $u$ and $v$, your answer is wrong for one of the two.

Time constraint

It is possible to recognize any regular language $L$ with quasi-constant amortized time. The time complexity is the one from a union-find-delete (UFD) data structure.
For instance this paper shows that operations union, makeset and delete can be done in constant time, and the find operation in reverse Ackermann (so at most $5$ for any input value making sense in the physical word, see wikipedia on union-find).

Let $A$ be a DFA recognizing $L$, with states $Q$, transition function $\delta:Q\times\Sigma\to Q$, and initial state $q_0.$
Let $k=|Q|$, since $L$ is fixed $k$ is a constant.

Let $a_0a_2\dots a_{n-1}\in\Sigma^n$ be the word currently under the window.
The idea is to maintain a memory structure $m$, giving for each word $u_i=a_i\dots a_{n-1}$ the state $q_i$ reached by $A$ after reading $u_i$.
We will also maintain an index $\gamma\in[0,n-1]$, giving the identifier associated with $u_0$. The identifier for $u_j$ is $\gamma+j \mod n$.

The UFD structure will store identifiers of all words $u_0\dots u_{n-1}$, and two words $u_i,u_j$ will be in the same partition if and only if $q_i=q_j$. The common state $q$ labels the partition.

So in order to know whether the current word is in $L$, it suffices to identify the label $q$ of partition of the identifier $\gamma$ (corresponding to the word $u_0$), and check whether $q$ is accepting.

When a new letter $a$ is read, we update the memory as follows:

the identifier $\gamma$ is deleted from the UFD structure
a new identifier $\gamma$ is added, and joins the partition labeled $q_0$. A new partition is created if none exists. For this we can use the help of an auxiliary memory of constant size, storing which states are currently labelling partitions, and giving a witness identifier for each one.
the current index $\gamma$ is updated to $\gamma'=\gamma+1\mod n$.
all labels of partitions are updated to their $a$-successors: $q'=\delta(q,a)$ for each label $q$. Partitions that get the same label are merged.

All these operations are either constant time or in quasi-constant amortized time.


Classes of graphs with easy Hamiltonian cycle but NP-hard TSP The Hamiltonian Cycle Problem (HC) consists in finding a cycle that goes through all vertices in a given undirected graph. The Travelling Salesman Problem (TSP) consists in finding a cycle that goes through all vertices in a given edge-weighted graph and minimizes the total distance measured by the sum of the weights of the edges in the cycle. HC is a special case of TSP, and both are known to be NP-complete [Garey & Johnson]. (See the links above for more details and variants of these problems.)

Are there any studied classes of graphs on which the Hamiltonian Cycle Problem is solvable in polynomial time via a non-trivial algorithm, but the Travelling Salesman Problem is NP-hard?

Non-trivial is to exclude classes such as the class of complete graphs, where a Hamiltonian cycle is guaranteed to exist and can be found easily, or generally classes of graphs where a HC is always guaranteed to exist.

Cographs are not always Hamiltonian, have polynomial time tests for Hamiltonicity, and are NP-hard to solve the traveling salesman problem for.

More generally the Hamiltonian cycle problem can be solved in polynomial time (but is not fixed-parameter tractible) on graphs of bounded clique-width; see, e.g., Fomin et al., "Clique-width: on the price of generality", SODA'09. But again because these graph families include the complete graphs, the TSP is hard on these graphs.


Modal logics axiomatised with nesting depth one which are unlikely to be in PSPACE? I am looking for modal logics, which are axiomatised by a finite set of axioms of modal nesting depth one, and whose satisfiability / derivability problem is unlikely to be in PSPACE. Without the restriction on the modal nesting depth this is not a problem, see for example PDL. But it seems that in proving for example EXPTIME-hardness by reduction to some kind of tiling problem or acceptance problem for Turing machines, one would need some kind of transitivity, which is axiomatised in depth two. There are also undecidable logics with a binary modality (Kurucz et al.: Decidable and undecidable logics with a binary modality, 1995), but these typically require associativity, which is depth two as well. In Conditional Logic, again it seems that we need depth two for EXPTIME-hardness (Friedman, Halpern: On the Complexity of Conditional Logics, 1994).

  Can we get EXPTIME-hardness with
  axioms of nesting depth one?

Background: We are trying to find generic decision procedures of a good complexity for logics axiomatised with nesting depth one.

I just realized that there is a nice solution to your problem, if you are willing to consider linear logic as your ambient logic instead of intuitionistic or classical logic. As is well-known, linear logic with the exponential modality $!A$ is not decidable. Furthermore, the exponential is a comonad featuring the duplication axiom $!A \multimap !!A$, which is evidently an axiom of nesting depth 2.

(I got this far right away, and then I got stuck -- which is why this answer is so late.)

However, I just realized that in implicit complexity, people modify the exponential $!A$ of linear logic to more precisely control the space and time usage of cut-elimination. Critically, all systems for doing so eliminate the duplication axiom! As a result, you can choose a system for which normalization likely goes past PSPACE (e.g., Elementary Affine Logic is as strong as elementary bounded Turing machines), and then the axiomatization of that will be unlikely to be in PSPACE, since that would imply that you could find cut-free proofs quickly.

Link: Ugo dal Lago and Simone Martini, Phase Semantics and Decidability of Elementary Affine Logic


What do dichotomy theorems feed on? It is well known that certain classes of NP-problems have dichotomy theorems, which guarantee that every task in the class is either NP-complete or is in P. The best known such result is
Schaefer's dichotomy
theorem, along with a number of generalizations.

My understanding is that proving these dichotomy theorems is not really easy. I wonder, if there is any relatively short explanation for why certain classes have dichotomy theorems, while others do not? What is the essential problem structure that makes these theorems possible? Or perhaps there is no such clearly understood structure, rather it is a mystery in each case why the class does or does not have a dichotomy theorem?

For the case of Schaefer's dichotomy theorem, informally, the universal expressive power of Boolean CNF formulas built from non-Schaefer logical relations is behind the dichotomy. Every logical relation is definable by such formula using existential quantifier. This is stated formally in Schaefer's expressibility theorem (Theorem 2.5).


Getting an automaton from set of words in and out of a language Possible Duplicate:
  Is finding the minimum regular expression an NP-complete problem?

Let's suppose that I have an unknown language $\mathcal L$, I know only two (particularly large) sets of words $\mathcal I$ and $\mathcal O$ that are and aren't in the langueage, respectively. This means: $\mathcal I\subset\mathcal L$ and $\mathcal O\cap \mathcal L=\emptyset$.

Is there an algorithm that would try to generate the simplest possible automaton such that it accepts words in $\mathcal I$ and denies words in $\mathcal O$?

I know that there's no single automaton for any such case, but I believe my language is quite and the automaton should be simple as well.

My idea in the background is that I don't know the language, I have a program that enumerates it. I suppose the language is regular and I would like to prove it by proving that it's accepted by an automaton.

(NB: If this belongs to CS.SE, feel free to migrate it.)

If I understand your question correctly, it is shown in the following paper that it is an NP-complete problem:

E. Mark Gold: Complexity of Automaton Identification from Given Data Information and Control 37(3): 302-320 (1978)