Searching for the first item satisfying property with penalty for every test

Here is a writeup following up on Tsuyoshi's pointer to use DP.

Given $p(x)$, we can write any (decent, deterministic) algorithm as a binary decision tree with nodes weighted by $p(x)$. The root of the tree is the first node the algorithm selects to test; the left child of each $x$ is the next node to test if $f(x)$ is zero and the right node is the next to test if $f(x) = 1$.

An algorithm's worst-case performance on weights $p(x)$ is its weighted depth: the maximum over any path to a leaf of the sum of the path's weights.

Therefore the optimal deterministic algorithm minimizes this value.

The "minimum maximum length" or "cost" of a path starting at node $x$ is $p(x)$ plus the cost of the tree on the nodes remaining to be searched. The nodes remaining to be searched will always be an interval. This gives the DP relation:

  $cost[x, z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( cost[x, y-1], cost[y, z]) \right)$

with $cost[x,x] = 0$ as a base case (except $cost[b,b] = p(b)$ unless you are promised that a $1$ occurs in the interval).

(Update)

With a probability distribution, say you want to minimize total expected cost. The expected cost for searching an interval is the cost of searching the first node $y$, plus the expected cost for searching the remainder. Using $\Pr[a,b|c,d]$ for the conditional probability of being in interval [a,b] given that we're in interval [c,d], this gives the following:

  $cost[x,z] = \min_{y \in [x,z-1]} \left(p(y) + \Pr[x,y-1|x,z] cost[x,y-1] + \Pr[y,z|x,z] cost[y,z] \right)$ .

Here's what I had before, which does something ... let's say "different" instead of "wrong."

It minimizes maximum expected cost. The idea is, given an algorithm, consider the node $y$ with highest expected cost $\Pr[y] p(y)$. We want the algorithm that minimizes this value. We might view this as risk-averse, I suppose.

  $cost[x,z] = \min_{y \in [x,z-1]} \left( p(y) + \max ( \Pr[x,y-1 | x,z] cost[x,y-1],  \Pr[y,z | x,z] cost[y,z]) \right)$.


Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus P$?

The standard meaning of "derandomized Valiant-Vazirani theorem" is the following.

  There exists a deterministic polynomial time algorithm that, given a 3CNF formula $\phi$, outputs formulas $\psi_1, \ldots, \psi_k$ such that

  If $\phi$ is not satisfiable, then none of the $\psi_i$ are.
  If $\phi$ is satisfiable, at least one of the $\psi_i$ has a unique satisfying assignment.

Indeed, if the above is true, $\mathsf{NP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ (a  comment by Joro suggests that this is what he actually meant). Since $\mathsf{P}^{\oplus \mathsf{P}}$ is closed under complement, it follows that $\mathsf{coNP} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$ holds as well.

If a derandomized Valiant-Vazirani theorem holds relative to $\oplus P$, i.e. with the 3CNF formulas augmented by $\oplus P$ predicates, then, using Fortnow's argument in his simplified proof of Toda's theorem, we would get $\mathsf{PH} \subseteq \mathsf{P}^{\oplus \mathsf{P}}$. The usual randomized Valiant-Vazirani theorem implies a randomized version of this: $\mathsf{PH} \subseteq \mathsf{BPP}^{\oplus \mathsf{P}}$. This is one of the lemmas used by Toda.

Note: My original answer had a bug, thanks to Emil Jeřábek for pointing it out.


Example where equivalence is easy but finding class representative is hard

Ok, how about: numbers $x$ and $y$ are equivalent if either $x=y$, or both $x$ and $y$ have factorizations $x=pq$ and $y=pr$ where $p$, $q$, and $r$ are all prime and $p < \min(q,r)$. That is: products of two primes are equivalent when they share their smallest prime factor; other numbers are only equivalent to themselves.

It's easy to test whether two different numbers are equivalent: compute their gcd, test whether it's nontrivial, test whether the gcd is less than the cofactors, and test whether the gcd and its cofactors are all prime.

But it's not obvious how to compute a representative function $f$ in polynomial time, and if you add the requirement that $f(x)$ must be equivalent to $x$ then any representative function would allow us to factor most products of two primes (every one that isn't its own representative).


It seems to me the pseudo-polynomial time dynamic programming algorithm for Subset Sum problem also works for this problem. For each vertex $v_i$, we compute the set $L_i$ consisting of all possible values of paths ended at $v_i$. Then, we have the recurrence relation:
$L_i=\{g(v_i)\}\cup\{x+g(v_i)\mid x\in \bigcup_{j\in  prec(i)} L_j\}$. Following a topological order, all the $L_i$ can be computed in $O(Km)$ time, where $K$ is the total weight and $m$ is the number of edges.

I think the standard scaling-and-rounding can also be applied to derive a FPTAS.


Is the Set of all Primitive Words a Prime Language?

The answer is yes. Suppose we have a factorization $Q = A\cdot B$.

One easy observation is that $A$ and $B$ must be disjoint (since for $w\in A\cap B$ we get $w^2\in Q$). In particular, only one of $A,B$ can contain $\epsilon$. We can assume wlog (since the other case is completely symmetric) that $\epsilon\in B$. Then since $a$ and $b$ cannot be factored into non-empty factors, we must have $a,b\in A$.

Next we get that $a^mb^n\in A$ (and, completely analogously, $b^ma^n\in A$) for all $m,n>0$ by induction on $m$:

For $m=1$, since $ab^n\in Q$, we must have $ab^n = uv$ with $u\in A, v\in B$. Since $u\neq\epsilon$, $v$ must be $b^k$ for some $k\le n$. But if $k>0$, then since $b\in A$ we get $b^{1+k}\in Q$, contradiction. So $v=\epsilon$, and $ab^n\in A$.

For the inductive step, since $a^{m+1}b^n\in Q$ we have $a^{m+1}b^n = uv$ with $u\in A, v\in B$. Since again $u\neq\epsilon$, we have either $v = a^kb^n$ for some $0<k<m+1$, or $v=b^k$ for some $k<n$. But in the former case, $v$ is already in $A$ by the induction hypothesis, so $v^2\in Q$, contradiction. In the latter case, we must have $k=0$ (i.e. $v=\epsilon$) since from $b\in A$ we get $b^{1+k}\in Q$. So $u=a^{m+1}b^n\in A$.

Now consider the general case of primitive words with $r$ alternations between $a$ and $b$, i.e. $w$ is either $a^{m_1}b^{n_1}\ldots a^{m_s}b^{n_s}$, $b^{m_1}a^{n_1}\ldots b^{m_s}a^{n_s}$ (for $r=2s-1$), $a^{m_1}b^{n_1}\ldots a^{m_{s+1}}$, or $b^{m_1}a^{n_1}\ldots b^{m_{s+1}}$ (for $r=2s$); we can show that they are all in $A$ using induction on $r$. What we did so far covered the base cases $r=0$ and $r=1$.

For $r>1$, we use another induction on $m_1$, which works very much the same way as the one for $r=1$ above:

If $m_1=1$, then $w=uv$ with $u\in A, v\in B$, and since $u\neq\epsilon$, $v$ has fewer than $r$ alternations. So $v$ (or its root in case $v$ itself is not primitive) is in $A$ by the induction hypothesis on $r$ for a contradiction as above unless $v=\epsilon$. So $w=u\in A$.

If $m_1>1$, in any factorization $w=uv$ with $u\neq\epsilon$, $v$ either has fewer alternations (and its root is in $A$ unless $v=\epsilon$ by the induction hypothesis on $r$), or a shorter first block (and its root is in A unless $v=\epsilon$ by the induction hypothesis on $m_1$). In either case we get that we must have $v=\epsilon$, i.e. $w=u\in A$.

The case of $Q' := Q\cup\{\epsilon\}$ is rather more complicated. The obvious things to note are that in any decomposition $Q = A\cdot B$, both $A$ and $B$ must be subsets of $Q'$ with $A\cap B = \{\epsilon\}$. Also, $a,b$ must be contained in $A\cup B$.

With a bit of extra work, one can show that $a$ and $b$ must be in the same subset. Otherwise, assume wlog that $a\in A$ and $b\in B$. Let us say that $w\in Q'$ has a proper factorization if $w=uv$ with $u\in A\setminus\{\epsilon\}$ and $v\in B\setminus\{\epsilon\}$. We have two (symmetric) subcases depending on where $ba$ goes (it must be in $A$ or $B$ since it has no proper factorization).

If $ba\in A$, then $aba$ has no proper factorization since $ba,a\notin B$. Since $aba\in A$ would imply $abab\in A\cdot B$, we get $aba\in B$. As a consequence, $bab$ is neither in $A$ (which would imply $bababa\in A\cdot B$) nor in $B$ (which would imply $abab\in A\cdot B$). Now consider the word $babab$. It has no proper factorization since $bab\notin A\cup B$ and $abab,baba$ are not primitive. If $babab\in A$, then since $aba\in B$ we get $(ba)^4\in A\cdot B$; if $babab\in B$, then since $a\in A$ we get $(ab)^3\in A\cdot B$. So there is no way to have $babab\in A\cdot B$, contradiction.
The case $ba\in B$ is completely symmetric. In a nutshell: $bab$ has no proper factorization and cannot be in $B$, so it must be in $A$; therefore $aba$ cannot be in $A$ or $B$; therefore $ababa$ has no proper factorization but also cannot be in either $A$ or $B$, contradiction.

I am currently not sure how to proceed beyond this point; it would be interesting to see if the above argument can be systematically generalized.


The book by Dubhashi and Panconesi collects together many such bounds, more numerous than can be listed here. If you find that hard to access immediately, there's an online  survey of Chernoff-like bounds by Chung and Lu


Is the current best approximation ratio for Vertex Cover problem also a lower bound?

Cormen, Leiserson, Rivest and Stein say that this algorithm that achieves ratio of 2 is tight. They did not exclude the possibility of another algorithm achieving better.

Vertex Cover is NP-hard to approximate with a factor better than 1.36:
http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf

Also check the following paper which give a 2-epsilon inapproximability result based on unique games hardness:
http://www.sciencedirect.com/science/article/pii/S0022000007000864

For approximation algorithms, see the wiki article for Vertex Cover and in particular the paper of Karakostas 2009: https://eccc.weizmann.ac.il/report/2004/084/


Parallel solution of recurrence equation

For linear recurrences, you may find interesting this recent work:

Adrian Nistor, Wei-Ngan Chin, Tiow-Seng Tan, and Nicolae Tapus. 2009. Optimizing the parallel computation of linear recurrences using compact matrix representations. J. Parallel Distrib. Comput. 69, 4 (April 2009), 373-381. DOI=10.1016/j.jpdc.2009.01.004 http://dx.doi.org/10.1016/j.jpdc.2009.01.004

A discussion of the parallel complexity of solving recurrences is available in

Oscar H. Ibarra and Nicholas Q. Tr\&#226;n. 1994. On the Parallel Complexity of Solving Recurrence Equations. In Proceedings of the 5th International Symposium on Algorithms and Computation (ISAAC '94), Ding-Zhu Du and Xiang-Sun Zhang (Eds.). Springer-Verlag, London, UK, 469-477.

Hope this helps.


Number of different longest common substrings

Let $\ell$ be the length of the longest common substring. The number of longest common substrings $m$ is at most
$$ m \leq \min(k^\ell,n-\ell+1). $$
Let $x = \log_k n$. If $\ell \leq x-1$ then $m \leq n/k$. Otherwise, $m \leq n-\log_k n+2$. One checks that the latter bound is always worse, and so $m \leq n-\log_k n+2$.


Are aspects of the 20 questions game ambitious enough for graduate research?

A PhD thesis should have references to the published literature and should be extending results in that literature.  So it is important to be able to say, these serious researchers did something but we do something they either were not able to do, or at least did not think of doing or did not have time to do, but would want to do.


Cayley subgraph isomorphism and complexity of linear subcode decision

For your first question: yes, it is NP-complete. The complete graph is the Cayley graph of any group, if you take the entire group (say, except the identity, but that would just add a self-loop at every vertex) as the generating set. Then CLIQUE is a particular instance of your problem.

A more interesting question might be to restrict Cayley subgraph isomorphism to Cayley graphs where only a minimal, or say $O(\log|G|)$-sized, generating set is used.

For your second question, the answer is also yes, because not only is Code Equivalence similar to Graph Isomorphism, but GI reduces to Code Equivalence. Essentially the same reduction (due to Petrank and Roth) gives a reduction from Subgraph Isomorphism to Subcode Equivalence.


Also check out the thesis of Ankur Gupta, with emphasis on compressible data.


The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in $\mathsf{FP}^{\mathsf{\# P}}/poly$ [Burgisser].

Valiant already observed that $\mathsf{P/poly} \neq \mathsf{NP/poly}$ implies $\mathsf{VP} \neq \mathsf{VNP}$ over $\mathbb{F}_2$, so separating VP from VNP is necessary on the way to proving that NP is not in P/poly. Not only is it a formally necessary first step, but because of the connection between VNP and counting solutions to NP problems, one could imagine that a better understanding of VNP would yield some insight into NP as well.


Effect of serial repetition on soundness of a PCP, and what is special with 1/2?

Sequential repetition can give you any constant soundness error larger than 0, not just soundness error $\geq 1/2$.
Dinur's approach gives you a constant soundness error which is not only at least half, but, in fact, extremely close to 1, maybe 0.99999.
The note of Andrej Bogdanov that you linked to shows that getting a soundness error smaller than half inherently won't work using Dinur's approach. The reason is specific to this approach, and is explained well in the note.

The soundness amplification results work for imperfect completeness as well. It's pretty straightforward to convince yourself of that in the case of sequential/parallel repetition. Dinur's approach can also be adapted to imperfect completeness.

Remark: Dinur's approach, just like the other two approaches, requires a number of iterations/repetitions that depends on the soundness you start with and the soundness you want to get.
In her case it's $\Theta(\log(\frac{1}{1-s}))$ iterations to get to constant soundness. Irit starts with $s\approx 1-\frac{1}{n}$, and that's why she needs $\Theta(\log n)$ iterations.


Normal forms for intuitionistic formulas?

There are two main ways you could take this.

If you are interested in provability, then what you want is the Gödel-Tarski embedding of intuitionistic logic into classical S4 modal logic.  The  idea is that you can interpret the box modality of modal logic as a "provability" modality, and then stick a box in front of each connective. Then you can put the formula into whatever variant of modal CNF you need.
See Mints' paper The Gödel-Tarski Translations of Intuitionistic Propositional Formulas.

If you are interested in retaining the ability to translate intuitionistic proofs, then one popular idea is to use Tarski's "high school identities" to put intuitionistic formulas into a normal form related to the exponential polynomials. This gives a normal form for types, whose translation preserves the beta-eta equivalence of proofs of that type.
See Danko Ilik's The exp-log normal form of types.

Both of these papers are about the propositional case. I don't know what happens with first-order quantifiers.


How can I formalize key value stores with set theory?

You did not say why you want a formalization, but presumably you want to do things with it, for instance prove properties of dictionaries and operations on them. In fact, your question can be understood in two ways: you want a mathematical description of dictionaries, or you want a computer formalization of dictionaries.

For a computer formalization have a look at the Coq standard library module FMaps, and if someone can find something better, please post it in the comments or just edit this question.

For a mathematical description all you have to note is that a dictionary is the same thing as a mapping with a finite domain. That is, if we have a dictionary (using Python style syntax):

d = { 'a' : 1, 'b' : 3, 'c' : 2 }

that is the same thing as a map $d$ whose domain of definition is the set $\{a, b, c\}$ and is defined as:
$$ d(a) = 1, \quad d(b) = 3, \quad d(c) = 2.$$
So now you can take any mathematical description of a map and use that. In set theory we would say that $d$ is the set of ordered pairs
$$\{(a,1), (b,3), (c,2)\}.$$


Complexity of linearized Ising model at 0

Not a full answer, but hopefully at least helpful. Computing the ground state of such an Ising Hamiltonian is NP-hard, as it contains Max-2-SAT, even if the couplings are restricted to $\pm J$. This is simply because if you take a 2-SAT instance, you can add the term $Jx_ix_j - Jx_ix_0 - J x_jx_0 = \mbox{daig}(-1,-1,-1,3)$ which is minimized iff $x_i \vee x_j$. Thus adding such terms to form a Hamiltonian will result in a spectrum where the ground state corresponds to the assignment of variables which maximizes the clauses satisfied as this corresponds to the maximum number of negative terms in the Hamiltonian. By adding an ancilla system it is then possible to create many such levels (via the tensor product of the two Hilbert spaces) with different energy levels. By tweaking the terms in the ancilla system, you can manipulate the absolute value of the energy levels corresponding to the ground state of the primary system and different excited states of the ancilla system. This would seem to indicate that the general problem is NP-hard. In the specific case of your question, you seem to fix J to be constant and positive which would seem to cause a problem with representing the negation of a variable in any of the clauses, and so this argument may not apply.

You may also be interested in cond-mat/0309240 for some results relating Ising lattices with various complexity classes.

Hope this is useful.


Reordering data (set of strings) to optimize for compression?

This is an addition to the Navin Goyal's answer.

Since a JSON file can be regarded as a tree data structure, you can use the XBW-transform for trees, which is an extension of the Burrows-Wheeler transform for strings.


For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

What you're looking for is an old result of Ginsburg and Spanier actually related to one of the oldest open questions of the field.   See Ginsburg's book The Mathematical Theory of CFLs.

Defs. A linear set is a set of the form $\vec{v} + P^*$ where $\vec{v} \in \mathbb{N}^k$ and $P$ is a finite set of such vectors ($P^*$ denotes all linear combinations of the vectors in $P$).  A linear set is stratified if :

All the vectors in $P$ have at most two nonzero components;
For all $\vec{x}, \vec{y} \in P$, the nonzero positions of $\vec{x}$ and $\vec{y}$ are not interleaved (this is related to the fact that $a^ib^ic^jd^j$ is CFL but not $a^ib^jc^id^j$).

Theorem. Let $w_1, \ldots, w_k$ be some words.  Any CFL $L \subseteq w_1^*\cdots w_k^*$ can be written as $L = \{w_1^{i_1}\cdots w_k^{i_k} \mid (i_1, \ldots, i_k) \in R\}$ where $R$ is an union of stratified sets.  Somewhat conversely, any language of that form with $R$ a union of stratified sets  is a CFL.

Naturally, there are languages that are CFL that can be written in the previous way with $R$ being quite arbitrary—e.g., with $w_1=w_2=a$ and $R = \{(2^i, j)\}.$
 However, if for instance all $w_i$'s are different letters, then $R$ has to be a union of stratified sets for $L$ to be a CFL.

As for the open question I mentioned before, the following problem is not known to be decidable:

Given: A finite union of linear sets
Question: Is this set presentable as a finite union of stratified sets?


Fast extraction of pairs overlapping an interval

This is a standard geometric data structure problem, which can be solved by storing the intervals $(x_1, y_1), \dots, (x_n, y_n)$ in an interval tree.  Then you can extract all the intervals $(x_i,y_i)$ overlapping a given query interval $(X,Y)$ in $O(\log n + k)$ time, where $k$ is the number of output intervals.


Not exactly the most recent (published in 2001), but the text by Arnold L. Rosenberg, Lenwood S. Heath, "Graph Separators, with Applications" may be a good place to look. The Google book link is provided here:
http://books.google.ca/books/about/Graph_Separators_with_Applications.html?id=7DNKE5ZiNZYC&redir_esc=y


What are the equational laws for zero types?

The standard equational rules for the empty type is, as you surmise, $\Gamma \vdash e = e' : 0$. Think of the standard set-theoretic model, where sets are interpreted by types: sum types are disjoint unions, and the empty type is the empty set. So any two functions $e,e' : \Gamma \to 0$ must also be equal, since they have a common graph (namely, the empty graph). .
The empty type has no $\beta$ rules, since there are no introduction forms for it. Its only equational rule is an $\eta$-rule. However, depending on how strictly you wish to interpret what an eta-rule is, you may wish break this down into an $\eta$ plus a commuting conversion. The strict $\eta$-rule is:

$$e = \mathrm{initial}(e)$$

The commuting coversion is:

$$C[\mathrm{initial}(e)] = \mathrm{initial}(e)$$

EDIT:

Here's why distributivity at the zero type implies the equality of all maps $A \to 0$.

To fix notation, let's write $!_A : 0 \to A$ to be the unique map from $0$ to $A$, and let's
write $e : A \to 0$ to be some map from $A$ to $0$.

Now, the distributivity condition says that there's an isomorphism $i : 0 \simeq A \times 0$.
Since initial objects are unique up to isomorphism, this means that $A \times 0$ is itself a
initial object. We can now use this to show that $A$ itself is an initial object.

Since $A \times 0$ is an initial object, we know the maps $\pi_1 : A
\times 0 \to A$ and $!_A \circ \pi_2$ are equal.

Now, to show that $A$ is an initial object, we need to show an
isomorphism between it and $0$.  Let's choose $e : A \to 0$ and $!_A :
0 \to A$ as the components of the isomorphism.  We want to show that
$e \circ !_A = id_0$ and $!_A \circ e = id_A$.

Showing that $e \circ !_A = id_0$ is immediate, since there is only
one map of type $0 \to 0$, and we know that there is always an
identity map.

To show the other direction, note
$$
\begin{array}{lcll}
  id_A & = & \pi_1 \circ (id_A, e) & \mbox{Product equations} \\
       & = & !_A \circ \pi_2 \circ (id_A, e) & \mbox{Since $A\times 0$ is initial} \\
       & = & !_A \circ e & \mbox{Product equations}
\end{array}
$$

Hence we have an isomorphism $A \simeq 0$, and so $A$ is an initial object. Therefore maps $A \to 0$ are unique, and so if you have $e,e' : A \to 0$, then $e = e'$.

EDIT 2: It turns out the situation is prettier than I originally thought. I learned from Ulrich Bucholz that it's obvious (in the mathematical sense of "retrospectively obvious") that every biCCC is distributive. $\newcommand{\Hom}{\mathrm{Hom}}$ Here's a cute little proof:

$$
\begin{array}{lcl}
   \Hom((A + B) \times C, (A + B) \times C)
   & \simeq & \Hom((A + B) \times C, (A + B) \times C) \\
   & \simeq & \Hom((A + B), C \to (A + B) \times C) \\
   & \simeq & \Hom(A , C \to (A + B) \times C) \times \Hom(B, C \to (A + B) \times C) \\
   & \simeq & \Hom(A \times C, (A + B) \times C) \times \Hom(B \times C, (A + B) \times C) \\
   & \simeq & \Hom((A \times C) + (B \times C), (A + B) \times C)
\end{array}
$$


Integer factorization using polynomial whose roots are prime factors

Knowing $F_n(1)$ or $F_n(-1)$ gives good randomized polynomial algorithm for the factorization of $n$.

We have $|F_n(1)|=\phi(n)$ and $|F_n(-1)|=\sigma(n)$ by definition.

$\phi(n)$ is Euler's totient function and $\sigma(n)$ is the sum of divisors function.

The paper you link to proves the case for $\sigma(n)$.

The same paper cites that the case for $\phi(n)$ is known
and is derandomized assuming ERH (p. 1).

I am pretty sure both algorithms will be quite fast in practice.


"Computing on data streams" clarification

The definition says that every edge that exists has to go from some $V_i$ to $V_{i+1}$.  It doesn't say that every possible edge from $V_i$ to $V_{i+1}$ has to be there.  For example, $V_1=\{a,b\}$, $V_2=\{c,d\}$ with edges $ac$ and $bd$ gives a disconnected graph.


On theoretical aproaches for solving $\mathsf{SAT}$ in special cases

Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT.

The first one that you are already familiar with is to restrict the types of the clauses that you are allowed to use. For example, in 2-SAT, you are only allowed to use size two clauses. In Horn-SAT, you only allow Horn clauses etc. The tractable restrictions for SAT have been completely classified by Schaefer in 1978 [1] in his celebrated dichotomy Theorem. The result is a dichotomy in the sense that Schaefer showed that the restriction gives you either a problem in P or an NP-complete problem. It has later been generalized to the problem of counting the satisfying assignments [2] or to the problem of enumerating them [3].

Some of these restrictions indeed lead to better performances of SAT solvers. For example, on a 2-SAT instance, unit propagation will naturally solve the instance in polynomial time and one can observe a similar behavior for Horn clauses. However SAT solvers rarely try to detect if the input is of such a form as it would be too costly to scan all clauses (for hardcore SAT-solver people, linear time is already too slow ;)). So for example, affine formulas will often not be detected (CryptoMiniSat may be an exception here).

The second line of research is to look for tractable instances by trying to uncover some structure in the way the variables interact with the clauses. For example, given a CNF formula, you can look at its incidence graph: it is a bipartite graph whose vertices are the variables and the clauses of the formula and you have an edge between a clause $C$ and a variable $x$ if $x$ or $\neg x$ is in $C$. Now, if this graph is a tree, you can solve SAT in polynomial time by doing some dynamic programming on the tree.

Many results extend this observation and most of them are interested in the parametrized complexity of SAT. For example, a well-known parameter of graphs is the treewidth, an integer that intuitively measures how far a graph is from being a tree. Now, if the incidence graph from above has treewdith $k$, we know algorithms to solve SAT in time $2^{O(k)}\mathsf{size}(F)$, that is, a linear time algorithm if the treewidth is bounded. An early and good survey of these results have been written by Szeider in 2003 [4]. The earliest result of this kind for SAT I am aware of is a paper by Dantsin [5] where he apparently shows the tractability of SAT on bounded branch width graphs (the paper is in Russian and I have never read it but I trust Alekhnovich and  Razborov [6] which improved the result in 2002). Many things have been understood since, for more general parameters and for more general problems (#SAT for example). I am shamelessly citing my thesis here as it contains a whole chapter reviewing most recent improvements on the question since then [8].

The idea of restricting the structure of the input through some associated graph has however been transpiring in computer science in many other domains as early as the 80's. See for example the Yannakakis algorithm for conjunctive queries in databases [7].

Now these tractable instances of SAT do not explain the good performances of SAT-solvers at all. Most of the algorithms used to solve these instances are not directly related to the way SAT-solvers work. But for more complex problem such as #SAT, the links between the theoretical algorithms and the way solvers work in practice is much stronger.

Some work has been done to understand the performances of SAT solvers by analyzing the structure of the formula (by detecting communities for example) but I do not know the literature well enough and let someone more competent than me answer this. All I can say is that it is not really related to the fact that the input belongs to some tractable instance. What you need is good heuristics to quickly converge to one solution. When there is no solution, then proof complexity is also a way of understanding the performances of a SAT-solver as it constructs a refutation of the formula while solving it. Thus, if no small refutation exists, then you can derive a lower bound on the runtime of the solver. But again, this is not completely enough to explain the performances of the SAT solver.

Concerning Question 2, I am not aware of any problem that have been discovered to be in P by reducting to a tractable class of SAT as usually, it is easier to program an algorithm than to encode it into a restricted formula. Moreover one generally prefers direct algorithms because they give more insights on the problem. However, a recent paper by Lampis, Mengel and Mitsou [9] shows the tractability of many parametrized problems by reducing them to SAT with bounded treewidth (which is known to be tractable). In this case, it is indeed usually simpler to writer the reduction instead of redoing complex dynamic programming algorithms again.

References

[1] Schaefer, Thomas J. (1978). "The Complexity of Satisfiability Problems". STOC 1978 https://en.wikipedia.org/wiki/Schaefer%27s_dichotomy_theorem

[2] Creignou, Nadia, and Miki Hermann. "Complexity of generalized satisfiability counting problems." Information and computation 125.1 (1996): 1-12.

[3] Creignou, Nadia, and J-J. Hébrard. "On generating all solutions of generalized satisfiability problems." RAIRO-Theoretical Informatics and Applications 31.6 (1997): 499-511.

[4] Szeider, Stefan. "On fixed-parameter tractable parameterizations of SAT." International Conference on Theory and Applications of Satisfiability Testing. Springer, Berlin, Heidelberg, 2003.

[5] E. Dantsin. Parameters defining the time of tautology recogni-
tion by the splitting method. Semiotics and information science, 12:8–17, 1979.

[6] Alekhnovich, Michael, and Alexander A. Razborov. "Satisfiability, branch-width and Tseitin tautologies." The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings.. IEEE, 2002.

[7] Yannakakis, Mihalis. "Algorithms for acyclic database schemes." VLDB. Vol. 81. 1981.

[8] Capelli, Florent. Structural restriction of CNF-formulas: application to model counting and knowledge compilation, Thèse de Doctorat, Université Paris-Diderot, 2016.

[9] Lampis, Michael, Stefan Mengel, and Valia Mitsou. "QBF as an Alternative to Courcelle’s Theorem." International Conference on Theory and Applications of Satisfiability Testing. Springer, Cham, 2018.


Set theory is doing you some harm here and the sooner you liberate yourself from it the better it will be for your understanding of computer science.

Forget the intersections and unions. People get this idea that $\forall$ and $\exists$ are like $\bigcap$ and $\bigcup$, which is the sort of thing the Polish school was doing a long time ago with Boolean algebras, but it's really not the way to go (definitely not in computer science).

You would like to look at these as sets. Ok, but then we have to ignore issues of size and pretend that there is a set of all sets. (It is possible to fix the issues of size by passing to a different category.) The type $\forall x . T$ is really like the cartesian product
$$\forall X . T \mathrel{{:}{=}} \prod_{S : \mathsf{Set}} T[X \mapsto S].$$
That is, an element of $\forall X . T$ is a function $f$ from sets to sets: for each set $S$ it gives an element $f(S)$ of type $T[x \mapsto S]$. For instance, an element of $\forall X. (X \to X) \to (X \to X)$ is a function $f$ which takes a set $S$ and gives a function of type $(S \to S) \to (S \to S)$. Here are some such functions:
\begin{align*}
f_0(S)(g)(x) &\mathrel{{:}{=}} x \\
f_1(S)(g)(x) &\mathrel{{:}{=}} g(x) \\
f_2(S)(g)(x) &\mathrel{{:}{=}} g(g(x)) \\
f_3(S)(g)(x) &\mathrel{{:}{=}} g(g(g(x)))
\end{align*}
So we get one for every natural number, and it's kind of hard to think of any other examples. (Exercise: google "Church encoding of natural numbers".)

Next, let us look at the existential types. Firstly, the correct encoding of $\exists$ in terms of $\forall$ is
$$\exists X . T \mathrel{{:}{=}} \forall Y . (\forall X . (T \to Y)) \to Y$$
where the variable $Y$ does not appear in $T$! (This should be mentioned in Pierce's TAPL.) Before we look at this encoding, let us do $\exists X . T$ directly in terms of sets. This time it is a coproduct:
$$\exists X . T \mathrel{{:}{=}} \coprod_{S : \mathsf{Set}} T[X \mapsto S].$$
An element of $\exists X . T$ is a pair $(S, a)$ where $S$ is a set and $a$ is an element of $T[X \mapsto S]$. An example would the the type $\exists X . (X \times X \to X)$, whose elements are pairs $(S, m)$ where $S$ is a set and $m : S \times S \to S$ is a binary operation on it. This is also known as a magma. If you get a bit fancier you can express well known structures such as groups and rings (you need to invent identity types first).

Let us see how the encoding of $\exists$ in terms of $\forall$ works. It is wrong to expect that we will get an equality between $\exists X. T$ and $\forall Y . (\forall X . (T \to Y)) \to Y$ (NB: $Y$ is fresh) – only set theory would give people such expectations. We should expect the two to be isomorphic. So the task is to find a bijection between
$$A \mathrel{{:}{=}} \coprod_{S : \mathsf{Set}} T[X \mapsto S]$$
and
$$B \mathrel{{:}{=}} \prod_{R : \mathsf{Set}} \left(\prod_{S : \mathsf{Set}} (T[X \mapsto S] \to R) \right) \to R.$$
This is an exercise in $\lambda$-calculus. In one direction we have the map $f : A \to B$ defined as
$$f(S,a)(R)(h) \mathrel{{:}{=}} h(S)(a)$$
and in the other a map $g : B \to A$ defined by
$$g(\phi) \mathrel{{:}{=}} \phi(A)(\lambda S . \lambda a . (S, a)).$$
(The notation $\lambda S . \lambda a . (S, a)$ means the function $S \mapsto a \mapsto (S, a)$.) Now we can check whether $f$ and $g$ are inverses of each other. One direction is easy:
$$g(f(S,a)) = f(S,a)(A)(\lambda S' . \lambda a' . (S', a'))
  = (\lambda S' . \lambda a' . (S', a')(S)(a) = (S, a).$$
The other direction looks like this:
$$f(g(\phi))(R)(h) = h(\pi_1(g(\phi))(\pi_2(g(\phi))).$$
We could go on a bit more by rewriting $g(\phi)$ to $\phi(A)(\lambda S . \lambda a . (S, a))$, but then we would get stuck!

It turns out that in set theory the encoding of $\exists$ in terms of $\forall$ does not work. But it does work in other setups, where types are not sets. For instance, you can convince yourself that in logic the statements
$$\exists x . \phi(x)$$
is equivalent to
$$\forall{P : \mathsf{Prop}} . (\forall x . (\phi(x) \Rightarrow P)) \Rightarrow P,$$
where $P$ ranges over all propositions (truth values, logical statements). Again, the variable $P$ should not occur in $\phi$.


are there fixed context sensitive grammars which are PSPACE complete?

$\mathrm{CSL}=\mathrm{NSPACE}(O(n))$. Thus, take your favourite PSPACE-complete problem. If it is decidable in $\mathrm{NSPACE}(O(n))$ (for example, QBF is), you are done. Otherwise, introduce a polynomial amount of padding to make it so.


Why is it impossible to work with polylog length encoding schemes for quantum circuits?

Clearly you can work with abstract compressed representations of circuits. You can reason about them and manipulate them and turn them into concrete lists of gates. We do it all the time.

But in context the author is in the middle of explaining the complexity class BQP (bounded-probability quantum polynomial-time). I think they're just making sure that you don't sneak non-polynomial amounts of work into the encoding. You don't want "repeat the diffusion operator $\sqrt{2}^n$ times" to count as being in BQP with respect to $n$.


Cases of nearly linear time solvable linear systems

Linear systems with circulant matrices can be solved in $O(n \log n)$ using the fast Fourier transform. A circulant matrix has entries $a_{i,j} = a_{1,i+j-1 \bmod n}$ so it is completely specified by the first column. Circulant matrices are diagonalized by the fast Fourier transform (log-linear time) and linear systems with diagonal matrices can be solved in linear time. See for instance the Wikipedia article http://en.wikipedia.org/wiki/Circulant_matrix for more details.

Apologies if this is too trivial to be mentioned here.


This is not a complete answer, but some basic observations about applying this to MAX-SAT.

At a high level, it looks like this heuristic approach (when applied to MAX-SAT) would be similar to a branching algorithm based on the method of "conditional expectation", a standard method in derandomization. For example, to get a deterministic $7/8$-approximation for MAX 3-SAT (with 3 variables per clause), one sets a variable $x=0$, estimates the expected fraction of clauses that will be satisfied by a random assignment in the remaining formula, then sets $x=1$ and does the same calculation. (This looks extremely similar to "playing a game to completion randomly".) The variable setting with the higher expected fraction of clauses ($x=0$ or $x=1$) will be chosen. This polynomial time algorithm gives a $7/8$-approximation and is known to be tight (you can fool it into satisfying only $7/8$ of the clauses). This connection should make it possible to prove lower bounds on the ability of this heuristic.

It is known that approximating MAX 3-SAT better than $7/8$ is $NP$-hard, so we don't expect an efficient heuristic to do better than this. It would be interesting to show (and I conjecture it is true) that a branching algorithm based on the above variable choice heuristic requires exponentially many steps to find a better-than-$7/8$ approximation. There are already lower bounds on backtracking which say that no matter what heuristic you use, even if you guess perfectly, there are still unsatisfiable formulas for which backtracking will only conclude they're unsatisfiable after exponentially many steps. Lower bounds on the lengths of resolution proofs yield these results. One reference is:

  Pavel Pudlák, Russell Impagliazzo: A lower bound for DLL algorithms for k-SAT (preliminary version). SODA 2000: 128-136


Is the D-Wave architecture a close implementation of quantum interactive proof?

This question seems a little confused. The class of decision problems solvable efficiently on a quantum computer is BQP, while on a classical computer it is either P or BPP depending on exactly how you define things. An interactive proof is something entirely different. It is a protocol which allows a prover to prove, beyond reasonable doubt, the outcome of some decision problem, and allows the prover and verifier to interact. QIP is the class of interactive proofs where the verifier, not the prover, has access to a quantum computer. It turns out that this doesn't help very much since you can prove exactly the same things to a fully classical verifier. I think what you have in mind is something different: an interactive proof where the prover is limited to quantum computation. This is something that has been studied in recent years (see for example arXiv:0807.4154, arXiv:0810.5375 and arXiv:1209.0449). The extent of our current knowledge is that you can basically prove anything in BQP if you have either some limited quantum power for the verifier (the ability to prepare single qubit states, for example) or if you have several provers who do not communicate, but share entanglement.

The DWave machine does not implement anything like these schemes, and does not constitute any form of interactive proof. Actually, the problem of implementing such a scheme on DWave hardware has been something that has interested me for a while. There are a few hurdles to doing this. All of the known schemes are based in the circuit model or the closely related measurement based model, while the DWave machines use a very different model of computation. This introduces a few problems, as their system is not a general purpose quantum computer, and so cannot implement any of the known schemes directly. Further, it cannot really accept any kind of quantum input, which rules out many of the tricks used to construct the known schemes.

However, I don't mean this to be a criticism of DWaves device: virtually no other quantum device has been used to implement such a proof. The closest you get are things like violations of Bell's inequalities and the recent experimental demonstration of blind quantum computing in linear optic (arXiv:1110.1381). At this point, no one has yet published an experimental demonstration of a quantum prover interactive proof, so DWave isn't any better or worse in this respect than anyone else.

By the way, I apologise for linking to two of my own papers in the above, but this is a question I have been very interested in in recent years, and I think those papers are relevant to the question at hand. It's not intended as self-publicity.


Proof that the graph optimization problem is NP-hard

This problem is in P, it can be reduced to the Minimum cut problem.

The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$.

The cost of the cut from source to sink in this graph with set of vertices $S$ along with source in one side of the cut exactly corresponds to your function $C$


Characterization of problems for which sublinear time algorithms exist

For the constant-time task of testing graph properties, an interesting characterization is known. A graph property is a function from all graphs to $\{0,1\}$, and a graph property $P$ is testable if there is a randomized algorithm $A$ such that for all $\varepsilon > 0$ and all graphs $G$:

$A(G)$ reads only $g(\varepsilon)$ edges of $G$ for some function $g$
If $P(G)=1$ then $A(G)$ outputs ``yes'' with high probability (say, at least $2/3$)
If at least $\varepsilon n^2$ edges of $G$ have to be added or removed in order to get a $G'$ such that $P(G')=1$ (that is, $G$ is $\varepsilon$-far from the property) then $A(G)$ outputs ``no'' with probability at least $2/3$

That is, $A$ can distinguish between graphs which have $P$ and graphs which have high edit distance from graphs having $P$. Alon, Fischer, Newman, and Shapira proved that a property $P$ is testable in this way if and only if the property can be "reduced" to the property of checking whether a graph has an $\varepsilon$-regular partition (in the sense of Szemeredi). This shows that testing regularity is "complete" for testing, in some sense. (There is also a one-sided error version of testability, see the reference.)


Proving not NP-complete by non-existence of gadget

First, I agree w/ Ludwik & other comments that I think (i) is unlikely. Polynomial-time reductions are just polynomial-time algorithms satisfying a certain (fairly flexible! compared to say p-time algorithms computing a fixed function $f$) input-output relationship, and polynomial-time algorithms are just too varied to say that they must take a certain form. You can always compose a gadget-based reduction with a p-automorphism to get something that does not recognizably have gadgets anywhere. (So at the very least you probably want to say "up to p-isomorphism, every reduction must have a gadget of this form", but "up to p-isomorphism" is a pretty hairy equivalence relation to work with at this level.)
But for (ii), I know of one result like this:

Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, Thomas Thierauf, Planarizing Gadgets for Perfect Matching Do Not Exist, MFCS '12.

I don't think I can do much better than quoting the abstract:

To reduce a graph problem to its planar version, a standard technique is to replace crossings in a drawing of the input graph by planarizing gadgets. We show unconditionally that such a reduction is not possible for the perfect matching problem and also extend this to some other problems related to perfect matching. We further show that there is no planarizing gadget for the Hamiltonian cycle problem.


Here is a hint for your question in the comment to the question.  The independence number of a graph can be computed by a polynomial-time oracle Turing machine which calls the #P oracle just once.  That is, the independence number is in class FP#P[1].

For a graph G on n vertices, let gk(G) be the number of independent sets of size k in G.  Note that 0≤gk(G)<2n.  Let

$$f(G)=\sum_{k=0}^n 2^{nk}g_k(G).$$

I leave the rest of the proof as exercise.

Show that function f is in #P.
Show that the independence number of G can be computed from two integers n and f(G) in time polynomial in n, and conclude that the independence number can be computed in FP#P[1].
(If this is not clear from item 2,) conclude that the independence number can be computed by a polynomial-time oracle Turing machine which calls the oracle for the permanent just once.

The same idea works also for the chromatic number.


How to estimate the probability of distribution of a variable in a Constraint Satisfication Problem

If the SAT instance has a unique solution then you are asking for the actual solution. Given the Valiant–Vazirani randomized reduction from SAT to unique SAT, if there was a way of efficiently estimating the probability distribution of variables then you could use it to solve SAT.


I guess Single-source Single-sink Planar DAG (SSPD) reachability has logspace algorithm with a modest running time ($O(n^2)$?). I am not so sure about
Single-source Multiple-sink Planar DAG Reachability (SMPD) algorithm.

Ref: Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009)

Also, a new logspace algorithm for planarity testing and embedding runs in modestly polynomial time (modulo undirected reachability, of course)

Ref: Samir Datta, Gautam Prakriya: Planarity Testing Revisited CoRR abs/1101.2637: (2011)

Finally, here is a simple toy problem which has a logspace algo with a modest
running time (modulo undirected reachability) viz. Outerplanar Isomorphism.


Looking around on google, I couldn't find much on this topic at all. However, I did find this thesis on arxiv, which I believe addresses this problem, albeit in a semi-roundabout way. As the author states in the conclusion

  The goal of this work was to discover namespaces in mathematical notation
  given a collection of documents with mathematical formulae. This
  problem could not be performed manually: this task it too time consuming
  and requires a lot of effort.
  To achieve the goal we proposed an automatic method based on cluster
  analysis. We noted that document representation in terms of identifiers is
  similar to the classic Vector Space Model. This allowed us to apply traditional document clustering techniques to the namespace discovery problem.

So cluster analysis seems to be something to look into here.

Hope this helps; I'll keep looking around for other resources.


Reducing the Height of Context-Free Grammars

The partial case is presented here: Balancing Straight-Line Programs for Strings and Trees. I'm not sure, that the problem can be solved in the general case.


Complexity of generating a pseudo-Boolean function

There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,

$$f_z(x_1,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$

Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at only the points $z[1],\dots,z[k]$ and strictly positive elsewhere: namely,

$$g(x) = f_{z[1]}(x) \cdot f_{z[2]}(x) \cdots f_{z[n]}(x).$$

It follows immediately that the pseudo-Boolean function $g$ has global minima at exactly the points $z[1],\dots,z[k]$ and no others, so it meets all your criteria.  This "algorithm" is simple and efficient.


Ambiguity in regular and context-free languages

About Q1:
Both the ambiguity problem (given a CFG, whether it is ambiguous) and the inherent ambiguity problem (given a CFG, whether its language is inherently ambiguous, i.e. whether any equivalent CFG is ambiguous) are undecidable.  Here are the original references:

The undecidability of ambiguity was proved by Cantor (1962), Floyd (1962), and Chomsky and Schützenberger (1963).  The proofs in textbooks typically reduce from the Post Correspondence Problem.
The undecidability of inherent ambiguity was proved by Ginsburg and Ullian (1966).

About Q2:  A regular grammar is a "one-sided linear" context-free grammar, where at most one nonterminal appears in any rule right-part, and where that nonterminal is at the last (in right linear grammars) or first (in left linear grammars) position.  Such grammars are easily translated into equivalent finite-state automata (roughly by considering each nonterminal as a state), which are unambiguous iff the regular grammar is unambiguous.  The class of unambiguous regular grammars and unambiguous automata has been studied in particular by Stearns and Hunt (1985), who show that they enjoy tractable algorithms for the inclusion problem.

About the relationship between derivations (i.e. sequences of rules applications $\beta A\gamma\Rightarrow \beta\alpha\gamma$ where $A\to\alpha$ is a rule of the grammar) and derivation trees (i.e. where a node labeled $A$ is the parent of a sequence of nodes $X_1,\dots,X_m$, where $A\to X_1\cdots X_m$ is a rule): in a general CFG, there can be different derivations, which visit the same derivation tree in different ways.

These different derivations occur because one has a choice between applying a grammar rule in two different places in a sentential form: in a sentential form $\gamma A\eta B\theta$ with at least two nonterminals $A$ and $B$, one can apply $A\to\alpha$ first and obtain $\gamma\alpha\eta B\theta$, or $B\to\beta$ first and obtain $\gamma A\eta\beta\theta$, but applying the other rule will lead to the same $\gamma\alpha\eta\beta\theta$.  Imposing leftmost (always deriving the leftmost nonterminal in any sentential form) or rightmost derivations imposes a fixed order for visiting derivation trees, and there is then a single derivation for a given derivation tree.

In a linear context-free grammar, there is no such choice, since there is at most one nonterminal in any sentential form, and there is a single derivation for a given derivation tree, which is both leftmost and rightmost.
Having two different parse trees with the same yield $w$ (sequence of leaves) is the definition of $w$ being ambiguous, it does not change when considering regular grammars.  Alternatively, one can also ask for two different leftmost derivations.  Note that a derivation in a one-sided grammar corresponds to an accepting run in its associated finite-state automaton, which is called ambiguous exactly in the same way: when there exist two different accepting runs for a given input $w$.
and 4.$~$  If you take the finite-state automata view, it suffices to determinize your ambiguous automaton in order to obtain an unambiguous automaton for the same language: there will be a single run for any given word.  This deterministic automaton is equivalent to an unambiguous regular grammar.

To answer your comment: there exist ambiguous regular grammars, for instance $S\to A\mid B,\,A\to a,\,B\to a$ has two leftmost derivations for $a$: $S\Rightarrow A\Rightarrow a$ and $S\Rightarrow B\Rightarrow a$.  An equivalent unambiguous grammar is $S\to a$.

About the relation with Q1: it is decidable whether a regular grammar is ambiguous (the inherent ambiguity problem is not very challenging on regular grammars, since the answer is invariably "no" without even looking at the input grammar).  This can be checked in $O(|G|^2)$ using a squaring construction on its associated automaton: construct the product of the automaton with itself, and see whether some state $(q,q')$ with $q\neq q'$ is accessible and co-accessible.  The oldest reference I know for this idea is a paper by Even (1965).


Are there known "completion" operations over languages ?

Some observations:

1) For any NPI set $L$, there is an isomorphic set $L'$ and a set $S$ such that $L' \cup S$ is NP-complete.  Let $L' = \{0x : x \in L\}$ and let $S = \{ 1x : x \in SAT \}$.  This observation applies in a more direct manner to some of the natural suspected NPI sets (such as $GA$ -- see my comments on turkistany's answer).  It will also apply to the padded version of any set in $NEXP \backslash EXP$ (assuming $NEXP \neq EXP$, such a set is in NPI), for most reasonable ways of padding sets.

This rasises a potentially interesting question:

  Is it the case that for any $L \in NPI$, there is an isomorphic language $L'$ and a set $S$ that is not NP-complete such that $L' \cup S$ is NP-complete?

2) R. Downey and L. Fortnow. Uniformly hard languages. Theoretical Computer Science, 298(2):303-315, 2003 (available from Lance's web page).  They show that the current proofs of Ladner's Theorem cannot easily be modified to produce uniformly hard languages (their definition of uniform hardness is natural, but is also in a sense aimed at Ladner-type constructions; it is not simply almost-everywhere hardness).  In particular, they show that if $P = PSPACE$ there is a minimal uniformly hard language under honest reductions; in particular, there is no relativizing proof of Ladner's Theorem for honest p-degrees that produces uniformly hard languages.

In particular, that means that any relativizing proof of Ladner's Theorem that works for honest p-degrees (all known proofs fall in this category) produces sets with arbitrary polynomially-long stretches where they look like a set in $P$.  Now, that's not quite enough to be able to say that if $L$ is a language produced by such a construction then there is a set $S$ such that $L \cup S$ is NP-complete, but it's pretty close.


Here is a fairly recent paper by Balcan et. al. from SODA'19 that gives a sample-optimal algorithm to test matrix rank. Note, in the query complexity setting, you need to have an appropriate notion of gap, which is exactly what they consider here. The paper should also list most of the relevant references.


What is the complexity of model checking Process Logic (LTL fragment)?

More along the "related formalisms" direction.

PDL with intersection and converse: satisfiability and infinite-state model checking, Stefan Göller, Markus Lohrey, and Carsten Lutz, 2009
The Effects of Bounding Syntactic Resources on Presburger LTL, Stéphane Demri and Régis Gascon

The introduction section of the first paper has an extensive discussion of complexity results for PDL fragments and extensions. I include the second mainly because you may be be able to encode some parts of your problem as a Presburger extension and transfer some results.


My thanks to Aryeh for bringing this question to my attention.

As others have mentioned, the answer to (1) is Yes, and the
simple method of Empirical Risk Minimization in $\mathcal{C}$ achieves
the $O((d/\varepsilon)\log(1/\varepsilon))$ sample complexity (see Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989).

As for (2), it is in fact known that there exist spaces $\mathcal{C}$
where no proper learning algorithm achieves better than $\Omega((d/\varepsilon)\log(1/\varepsilon))$ sample complexity, and hence proper learning cannot achieve the optimal $O(d/\varepsilon)$ sample complexity. To my knowledge, this fact has never actually been published, but is rooted in a related argument of Daniely and Shalev-Shwartz (COLT 2014) (originally formulated for a different, but related, question in multiclass learning).

Consider the simple case $d=1$, and put the space $\mathcal{X}$ as $\{1,2,...,1/\varepsilon\}$, and $\mathcal{C}$ is singletons $f_z(x) := \mathbb{I}[x = z], z \in \mathcal{X}$: that is, each classifier in $\mathcal{C}$ classifies exactly one point from $\mathcal{X}$ as $1$ and the others as $0$. For the lower bound, take the target function as a random singleton $f_{x^*}$, where $x^{*} \sim {\rm Uniform}(\mathcal{X})$, and $P$, the marginal distribution of $X$, is uniform on $\mathcal{X}\setminus\{x^*\}$.  Now the learner never sees any examples labeled $1$,
but it must choose a point $z$ to guess is labeled $1$ (importantly, the
``all zero'' function is not in $\mathcal{C}$, so any proper learner must guess some $z$), and until it has seen every point in $\mathcal{X}\setminus\{x^*\}$ it has at least $1/2$ chance of guessing wrong (i.e., the posterior probability of its $f_z$ having $z \neq x^*$ is at least $1/2$).  The coupon collector argument implies it would require $\Omega((1/\varepsilon)\log(1/\varepsilon))$ samples to see every point in $\mathcal{X} \setminus \{x^*\}$. So this proves a lower bound of $\Omega((1/\varepsilon)\log(1/\varepsilon))$ for all proper learners.

For general $d>1$, we take $\mathcal{X}$ as $\{1,2,...,d/(4\varepsilon)\}$, take $\mathcal{C}$ as classifiers $\mathbb{I}_{A}$ for sets $A \subset \mathcal{X}$ of size exactly $d$, choose the target function at random from $\mathcal{C}$, and take $P$ again as uniform on just the points the target function classifies $0$ (so the learner never sees a point labeled $1$). Then a generalization of the coupon-collector argument implies we need $\Omega((d/\varepsilon)\log(1/\varepsilon))$ samples to see at least $|\mathcal{X}| - 2d$ distinct points from $\mathcal{X}$, and without seeing this many distinct points any proper learner has at least $1/3$ chance of getting greater than $d/4$ of its guess $A$ of $d$ points wrong in its chosen hypothesis $h_{A}$, meaning its error rate is greater than $\varepsilon$.  So in this case, there is no proper learner with sample complexity smaller than $\Omega((d/\varepsilon)\log(1/\varepsilon))$, which means no proper learner achieves the optimal sample complexity $O(d/\varepsilon)$.

Note that the result is quite specific to the space $\mathcal{C}$ constructed. There do exist spaces $\mathcal{C}$ where proper learners can achieve the $O(d/\varepsilon)$ optimal sample complexity, and indeed even the exact full expression $O((d/\varepsilon)+(1/\varepsilon)\log(1/\delta))$ from (Hanneke, 2016a). Some upper and lower bounds for general ERM learners have been developed in (Hanneke, 2016b), quantified in terms of properties of the space $\mathcal{C}$, as well as discussing some more specialized cases where specific proper learners can sometimes achieve the optimal sample complexity.

References:

Vapnik and Chervonenkis (1974). Theory of Pattern Recognition. Nauka, Moscow, 1974.

Blumer, Ehrenfeucht, Haussler, and Warmuth (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):
929–965.

Daniely and Shalev-Shwartz (2014). Optimal Learners for Multiclass Problems. In Proceedings of the 27th Conference on Learning Theory.

Hanneke (2016a). The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research, Vol. 17 (38), pp. 1-15.

Hanneke (2016b). Refined Error Bounds for Several Learning Algorithms. Journal of Machine Learning Research, Vol. 17 (135), pp. 1-55.


Recovery of preimage of hash function given part of it

You don't specify how long $m_1$ and $m_2$ are. If $|m_1| = |m_2| > s$, then there is no way to recover $m$ given $s=h(m)$ (or $m_1$ given $m_2$ and $s=h(m_1\|m_2$) simply because there are exponentially many solutions to the equation $h(X)=s$ (resp., $h(X \| m_2) = s$).

Or are you asking to find any solution, not necessarily the original one? Even in this case, the above property (namely, existence of multiple solutions) can be used to show that solving either of the stated problems is hard if $h$ is collision resistant. In fact, this remains true even if $|m_1|=|m_2|=s$.


Simple proof of Ω(n lg n) worst-case bound for uniqueness/distinctness?

I am not sure if I understand the question correctly, but the proof by Dobkin and Lipton [DL79] that the uniqueness problem on n numbers requires Ω(n log n) comparisons in the linear decision tree model is much easier than the stronger result in the algebraic computation tree model by Ben-Or [Ben83] (not surprisingly).

References

[Ben83]  Michael Ben-Or.  Lower bounds for algebraic computation trees.  In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), pp. 80–86, April 1983.  http://doi.acm.org/10.1145/800061.808735

[DL79] David P. Dobkin and Richard J. Lipton.  On the complexity of computations under varying sets of primitives.  Journal of Computer and System Sciences, 18(1):86–91, Feb. 1979.  http://dx.doi.org/10.1016/0022-0000(79)90054-0


Complexity of deciding whether a family is a Sperner familiy

Can't you solve this by matrix multiplication? Let the sets be $S_1$, $S_2$, $\ldots$, $S_m$. Take matrix $A$ to be the $m \times n$ matrix where $A_{ij}=1$ if $j \in S_i$ and 0 otherwise, and $B$ to be the $m \times n$ matrix where $B_{ij}=1$ if $j \notin S_i$ and 0 otherwise. Now, $AB^T$ has a $0$ entry if and only if there is one set of $\mathcal{F}$ contained in another.

So if you prove a lower bound of $\Omega(n^{2+\epsilon})$ for the case where $m = \theta(n)$, you have proven the same lower bound for matrix multiplication. This is a famous open problem.

I haven't thought much about it, but I don't see any way you could prove that this particular case of matrix multiplication is essentially as hard as the general case; if you really need a lower bound, this would seem to be the only hope you have of proving one without solving the matrix multiplication problem.

On the plus side, this gives algorithms for this problem that are better than the naive algorithm that takes $\theta(m^2n)$.


(How) Could we discover/analyze NP problems in the absence of the Turing model of computation?

You may wish to look at cost semantics for functional languages. These are various computational complexity measures for functional languages that do not pass through any kind of Turing machine, RAM machine, etc. A good place to start looking is this Lambda the Ultimate post, which has some good further references.

Section 7.4 of Bob Harper's Practical Foundations for Programming Languages explains the costs semantics.

The paper On the relative usefulness of fireballs by Accattoli and Coen shows that $\lambda$-calculus has at most linear blowup with respect to RAM machine model.

In summary, on this other planet things would be pretty much the same with regards to NP, but there would be fewer buffer overflows, and there wouldn't be as much garbage lying around.


Are optimal evaluators actually optimal?

Efficiency of optlam

I have not studied the details of BADTERM nor of the implementation of optlam evaluator, but I find quite strange that optlam performs a number of ß-interactions drastically different than another optimal evaluator like BOHM. Such a number must be, by definition, basically the same on a given term. Are you sure of the correctness of optlam's core?

Efficiency of optimal evaluators

Recall that the notion of optimality of these evaluators is more properly known as Lévy-optimality, and it is not the naive one, since a strategy of reduction performing the minimum number of ß-steps is not computable. What is minimised, then, is the number of parallel ß-reduction steps performed on a whole family of redex, that is roughly the set obtained by the symmetric and transitive closure of the relation which binds two redexes when one is copied from the other. It should in general not surprise to see discrepancies between the number of ß-steps and the rest of duplication-steps, since we know that most of the normalisation load could be transferred from the former to the latter, as shown by Asperti, Coppola and Martini [1].

It should not surprise us either to see that total number of interactions needed to normalise an term with an optimal evaluator is that lower than with an ordinary one, since previous empirical observation already showed notable performance improvements. In spite of this, such a huge complexity jump, from exponential to linear time, is perhaps the very first of its kind being being discovered, though. (I will check this.)

On the other hand, the theoretical results about the efficiency of optimal reduction (which is your big question), are still few and not yet general, since they are limited to EAL-typed proof-nets (which is basically the same restriction of optmal evaluator, if I correctly understand), but all are mildly positive, since in the worst case the complexity of sharing reduction is bounded by the ordinary one by a constant factor [2,3].

References

A. Asperti, P. Coppola, and S. Martini, (Optimal) Duplication is not elementary recursive, Information and Computation, vol. 193, 2004.
P. Baillot, P. Coppola, and U. Dal Lago, Light logics and optimal reduction: Completeness and complexity, Information and Computation, vol. 209, no. 2, pp. 118–142, 2011.
S. Guerrini, T. Leventis, and M. Solieri, Deep into optimality – complexity and correctness of sharing implementation of bounded logics, DICE 2012, Tallin, Estonia, 2012.


The relation $\overset{*}{\leftrightarrow}$ is defined as $(\leftrightarrow)^*$, the reflexive-transitive closure of $\leftrightarrow$, and $\leftrightarrow$ is defined as $\leftarrow \cup \rightarrow$, the symmetric closure of $\rightarrow$.  This means that $\overset{*}{\leftrightarrow}$ is: a sequence of rewrites going in either direction.

Now the inference is immediate: a sequence of reverse rewrites followed by a sequence of direct rewrites is indeed a sequence of (either direction) rewrites.

Another way to view it, is that $a \rightarrow b$ stands for $a = b$ in some semantical sense, but $b$ is somewhat simpler than $a$. The relation $\overset{*}{\leftrightarrow}$ is then simply the underlying, semantical, equality.


Here are two solutions which (as suggested in the question and comments) assume that all the given sets are disjoint and performs destructive set unions (when we find the union of sets A and B, we remove A and B themselves from the family of sets).

Amortized constant time

We maintain objects for the sets and objects for the elements. The sets know what elements they have, as a concatenable list, so that we can list those elements quickly, but we don't keep pointers from the objects to the sets that contain them (because it would be too slow to update them).

There is at most one special set Z, the one containing zero. Every object knows whether it is part of Z or not (a binary flag). The set Z maintains the value of its mex. For every other set, the mex is zero. So you can compute the mex of a set in constant time, given either the set itself or one of its elements.

To form the union of two sets, if neither one is Z, just concatenate their lists. If one of the two sets is Z, run through its elements setting the flag that says the element is now in Z. Then, while the mex is an element of Z, increment it.

Each element accounts for one increment operation to the mex of Z, so the amortized time per element, merge, or mex request is constant.

Worst-case logarithmic time

For a worst-case rather than amortized (but slower) solution, that also allows for creation of new singleton sets and does not assume that the union of all the sets is a contiguous interval, we use the following data structures:

union-find rather than flags to determine the set that contains any element (even if we just do union-by-rank without path compression, this is worst-case logarithmic per find operation)
a binary search tree of the elements in the union of all the sets
for each element, the smallest non-element between it and its predecessor in the binary search tree (or zero if it has no predecessor)
for each binary search tree node, the smallest non-element listed in its subtree (updated in constant time per tree rotation)
the smallest element of each set
a priority queue of the smallest elements of sets that are not Z.

Then at all times mex(Z) is the minimum of the priority queue value and the smallest non-element. And as before, for sets that are not Z, the mex is zero. Adding a new singleton set, merging two sets, or finding a mex all take logarithmic time with more-or-less obvious updates.


Why is it important to prove that a problem is NP-complete?

Ali, good question.

Suppose you want to show that some problem P is computationally hard.  Now, you could conjecture that P is hard just based on the fact that we don't have any efficient algorithms for it yet.  But this is rather flimsy evidence, no?  It could be that we have missed some nice way to look at P which would make it very easy to solve.  So, in order to conjecture that P is hard, we would want to accumulate more evidence.  Reductions provide a tool to do exactly that!  If we can reduce some other natural problem Q to P, then we have shown P is at least as hard as Q.  But Q could be a problem from some completely different area of mathematics, and people may have struggled for decades to solve Q also.  Thus, we can view our failure to find an efficient algorithm for Q to be evidence that P is hard.  If we have lots of such Q's from many different problem domains, then we have a huge body of evidence that P is hard.

This is exactly what the theory of NP-completeness provides.  If you prove your problem to be NP-complete, then you have tied its hardness to the hardness of hundreds of other problems, each of significant interest to various communities.  Thus, morally speaking, you can be assured that your problem is indeed hard.


Upper bound on Chaitin's constant for lambda calculus and SKI combinatory logic

You probably want to look at David et al's paper, Asymptotically Almost All λ-terms are Strongly Normalizing:

We present a quantitative analysis of various (syntactic and behavioral) properties of random λ-terms. Our main results show that asymptotically, almost all terms are strongly normalizing and that any fixed closed term almost never appears in a random term.
Surprisingly, in combinatory logic (the translation of the λ-calculus into combinators), the result is exactly opposite. We show that almost all terms are not strongly normalizing. This is due to the fact that any fixed combinator almost always appears in a random combinator.

You should be able to cook up a bound from looking at the details of their proof.


The answer is “yes”. The proof is by contradiction.

For notational convenience, let us denote the first $n/2$ variables by $x$ and the second $n/2$ variables by $y$. Suppose that $f(x,y)$ is $\delta$-close to a function $f_1(x,y)$ which depends only on $k$ coordinates of $x$. Denote its influential coordinates by $T_1$. Similarly, suppose that $f(x,y)$ is $\delta$-close to a function $f_2(x,y)$ which depends only on $k$ coordinates of $y$. Denote its influential coordinates by $T_2$. We need to prove that $f$ is $4\delta$- close to a $2k$-junta $\tilde f(x,y)$.

Let us say that $(x_1,y_1) \sim (x_2,y_2)$ if $x_1$ and $x_2$ agree on all coordinates in $T_1$ and $y_1$ and $y_2$ agree on all coordinates in $T_2$. We choose uniformly at random a representative from each equivalence class. Let $(\bar x, \bar y)$ be the representative for the class of $(x,y)$. Define $\tilde f$ as follows:
$$\tilde f(x,y) = f(\bar x, \bar y).$$

It is obvious that $\tilde f$ is a $2k$-junta (it depends only on variables in $T_1 \cup T_2)$. We shall prove that it is at distance $4\delta$ from $f$ in expectation.

We want to prove that
$$\Pr_{\tilde f}(\Pr_{x,y}(\tilde f(x,y) \neq f(x,y))) = \Pr(f(\bar x, \bar y) \neq f(x,y)) \leq 4\delta,$$
where $x$ and $y$ are chosen uniformly at random.
Consider a random vector $\tilde x$ obtained from $x$ by keeping all bits in $T_1$ and randomly flipping all bits not in $T_1$, and a vector $\tilde y$ defined similarly. Note that
$$\Pr(\tilde f(x,y) \neq f(x,y)) = \Pr(f(\bar x, \bar y) \neq f(x,y))= \Pr(f(\tilde x, \tilde y) \neq f(x,y)).$$

We have,
$$\Pr(f(x,y) \neq f(\tilde x, y)) \leq  \Pr(f(x,y) \neq f_1(x, y)) + \Pr(f_1(x,y) \neq f_1(\tilde x, y)) + \Pr(f_1(\tilde x,y) \neq f(\tilde x, y)) \leq \delta + 0 + \delta = 2\delta.$$

Similarly, $\Pr(f(\tilde x,y) \neq f(\tilde x, \tilde y)) \leq 2\delta$. We have
$$\Pr(f(\bar x, \bar y) \neq f(x,y))  \leq 4\delta.$$
QED

It easy to “derandomize” this proof. For every $(x,y)$, let $\tilde f(x,y) = 1$ if $f(x,y) = 1$ for most $(x',y')$ in the equivalence class of $(x,y)$, and $\tilde f(x,y) = 0$, otherwise.


See the paper "A parallel approximation algorithm for positive linear programming." by Luby and Nisan. (Some kinds of) linear programs can be approximated in log^(O(1)) n time.


Is there a gadget that reduces generalized geography to undirected graphs?

Undirected (Vertex) Geography is in P. In particular, the game on graph $G$ with starting vertex $v$ is a win for player 1 if and only if every maximum matching of $G$ uses the vertex $v$. This can be checked in polynomial time.

The above is Theorem 1.1 from the paper "Undirected Edge Geography", by Fraenkel, Scheinerman and Ullman, Theoretical Computer Science 1993.


You might want to take a look at the compiler literature for some ideas.  What you're describing is akin to a well-known compiler optimization (virtually any modern compiler worth its salt will do it) called constant folding.  Of course, constant folding goes further in not just identifying constant expressions, but replacing them by their value.

In particular, compilers use a dataflow analysis to identify such constant expressions.  Any good compiler textbook will discuss this.


Richard Beigel gives an oracle $A$ where $P^{NP^A}\not\subseteq PP^A$ which immediately gives $PP^{PP^A}\neq PP^A$.


Here's a paper that considers a more general variant of the problem (multiple machines, job dependent demands etc.):

Rohit Khandekar, Baruch Schieber, Hadas Shachnai, Tami Tamir.
Real-time scheduling to minimize machine busy times.
Journal of Scheduling 18(6), 561-573, 2015.
doi:10.1007/s10951-014-0411-z

In particular, their results give a polynomial time algorithm for the case described in my question.


Communicating a string of zeros and ones quantumly

This paper proves the results you have described:

  Ashwin Nayak and Julia Salzman. Limits on the Ability of Quantum
  States to Convey Classical Messages. Journal of the ACM, 53(1):
  184-206, 2006.


Facility Location problem, multiple facilities with no specific locations

What you're talking about is, I believe, called the Capacitated Facility Location Problem.  Searching for that should give you plenty of papers to read.  It appears the problem is NP-hard, but in Euclidean space a simple search procedure gives you a 6-approximation [PDF].


Recent fundamental results in algorithms?

Cache-oblivious algorithms were first conceived of (according to Wikipedia) in 1996.

An algorithm is cache-oblivious if it uses caches in an optimal way, without knowing the size of the cache (which also means that if there is more than one level of cache, as in a modern PC, it is also used optimally).


Is there any gradient descent based technique for searching absolute minimum (maximum) of a function in multidimensional space?

I presume you are talking about unconstrained minimization. Your question should specify if you are considering a specific problem structure. Otherwise, the answer is no.

First I should dispel a myth. The classical gradient descent method (also called steepest descent method) is not even guaranteed to find a local minimizer. It stops when it has found a first-order critical point, i.e., one where the gradient vanishes. Depending on the particular function being minimized and the starting point, you may very well end up at a saddle point or even at a global maximizer!

Consider for instance $f(x,y) = x^2 - y^2$ and the initial point $(x_0,y_0) := (1,0)$. The steepest descent direction is $-\nabla f(1,0) = (-2,0)$. One step of the method with exact line search leaves you at $(0,0)$ where the gradient vanishes. Alas, it's a saddle point. You would realize by examining the second-order optimality conditions. But now imagine the function is $f(x,y) = x^2 - 10^{-16} y^2$. Here, $(0,0)$ is still a saddle point, but numerically, the second-order conditions may not tell you. In general, say you determine that the Hessian $\nabla^2 f(x^*,y^*)$ has an eigenvalue equal to $-10^{-16}$. How do you read it? Is it negative curvature or numerical error? How about $+10^{-16}$?

Consider now a function such as
$$
f(x) =
\begin{cases}
 1 & \text{if } x \leq 0 \\
\cos(x) & \text{if } 0 < x < \pi \\
-1 & \text{if } x \geq \pi.
\end{cases}
$$

This function is perfectly smooth, but if your initial point is $x_0 = -2$, the algorithm stops at a global maximizer. And by checking the second-order optimality conditions, you wouldn't know! The problem here is that some local minimizers are global maximizers!

Now virtually all gradient-based optimization methods suffer from this by design. Your question is really about global optimization. Again, the answer is no, there are no general recipes to modify a method so as to guarantee that a global minimizer is identified. Just ask yourself: if the algorithm returns a value and says it is a global minimizer, how would you check that it's true?

There are classes of methods in global optimization. Some introduce randomization. Some use multi-start strategies. Some exploit the structure of the problem, but those are for special cases. Pick up a book on global optimization. You will enjoy it.


In Agda this is done by tagging types as "irrelevant". It's a kind of quotenting. A function from an irrelevant to a (relevant) type must be constant (and Agda enforces this). You can read more about it on the Agda wiki Irrelevance page.


Finding triangles in a graph: other approaches besides property testing?

For several references for the problem of testing for the existence of a triangle (exactly, not in the property testing framework), see Triangle-free graph on Wikipedia. In particular Alon, Yuster, and Zwick (ESA'94) give an O(m^{1.41}) algorithm, and it can also be done in fast matrix multiplication time which is better for dense graphs.

If you're ok with something in the dynamic graph algorithms setting, I also have one for counting the triangles:

The h-index of a graph and its application to dynamic subgraph statistics, D. Eppstein and E. S. Spiro, arXiv:0904.3741 and WADS 2009.

In our paper we cite Chiba and Nishizeki (SICOMP 1985) and Itai and Rodeh (SICOMP 1978) for the basic static-algorithm facts that a graph with m edges can have at most O(m^{3/2}) triangles in the worst case and that they can be listed in that amount of time.


No, the string need not be normal.  Take any uncomputable sequence and add two 0s between each term; now there are too many 0s for the sequence to be normal but it's still uncomputable.


How to implement a functional programming language efficiently?

It's not entirely clear what do you mean by a functional programming language without closures. Can you give an example?

Functional programming languages are usually based on lambda calculus, whose essential part is that you can have open lambda terms. For example the term for the constant function (the K-combinator) $\lambda x . \lambda y . x$ can be viewed as a function that given $x$ returns a constant function that returns $x$ on any argument - a closure of the open term $\lambda y . x$.

However you can use another basis, a combinatory calculus such that it's power is equivalent to the lambda calculus. Then you can take a lambda term and convert it into an equivalent combinator that doesn't use any variables at all, so there are even no closures to talk about - see Completeness of the S-K basis. Which I believe answers yes to your question.

This is actually what Haskell compilers do under the hood. Evaluating lambda terms with variables is very inefficient and cumbersome, so they convert the program to a representation without variables and use techniques such as combinator graph reduction.

I can recommend two books on the subject which are both available online, the first one more theoretical, the second one focused more on the actual implementation techniques:

The Implementation of Functional Programming Languages, Simon Peyton Jones, published by Prentice Hall, 1987.
Implementing functional languages: a tutorial


Larry Wall proposed that we use "regular expression" for the formalism Kleene proposed, and "regex" for expressions for the widely used extensions.  It's a fairly widely followed convention.  If you want to make it clear that you are talking about regular expressions in the formal languages sense, it is usually not difficult to translate into talk of regular languages.

The power of regexes comes from backtracking, and there has been work done on automata for regular languages with backtracking.  See, in particular, Becchi & Crowley, 2008, Extending Finite Automata to Efficiently Match Perl-Compatible Regular Expressions.


Polynomial algorithms for UPB (Unextendable Product Bases)

I'm a little baffled by question (1). An unextendable product basis exists in $H_1 \otimes H_2 \otimes \ldots \otimes H_n$ if $n\geq 3$ or if $n=2$ and $\dim H_1, \dim H_2 \geq 3$. In all of these cases, it is straightforward to find one.

For question (2), the question is equivalent to checking whether there is a tensor product state in the subspace which is the complement of the space spanned by the basis. Leonid Gurvits has shown that checking whether a general subspace contains a tensor product state is NP-hard, so I suspect that it is hard in this case as well.


For the non-metric $k$-median problem, we can show a stronger inapproximability result than $O(\log n)$. The following is a stronger claim:
Main Claim: The non-metric $k$-median problem can not be approximated to any factor better than $n^{c}$, for any constant $c>0$.
Proof:
The proof follows from the reduction from the hardness of the max $k$ coverage problem. Given a universe set $U = \{1,\dotsc,n\}$ and subsets $S_{1}, \dotsc,S_{m}$ of $U$. It is NP-hard to distinguish between the following instances:

Yes Instances: There are some $k$ sets $S_{t_{1}},\dotsc,S_{t_{k}}$ that covers all elements in $U$.

No Instances: There does not exists any $k$ sets in $S_{1}, \dotsc,S_{m}$ that can cover more than $(1-\frac{1}{e}) \cdot |U|$ elements of $U$.

Reduction: Using an instance of the max $k$ coverage, we construct a $k$-median instance $(L,C)$ as follows. A location in $L$ corresponds to a subset $S_{i}$. And, a client in
$C$ corresponds to an element $e_{j}$. Let $f_{i} \in L$ denote a
location corresponding to $S_{i}$, and $x_{j} \in C$ denote a client
corresponding to an element $e_{j} \in U$. The distance between
$f_{i}$ and $x_{j}$ is $1$ if $e_{j} \in S_{i}$ and $\Delta$
otherwise. Here $\Delta$ is some value $\gg 1$.

Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a Yes Instance.
Completeness: We open facilities at the locations that corresponds to $S_{t_{1}}, \dotsc,S_{t_{k}}$. The cost of every client to the closest facility would be exactly $1$ since every element belongs to some $S_{t_{i}}$. Therefore, the $k$-median cost is at most $|U|$.
Now, let us compute the $k$-median cost of $(L,C)$ corresponding to a No Instance.
Soundness: No matter where we open $k$ facilities, there always exist at least $\frac{1}{e} \cdot |U|$ elements that are left uncovered. In other words, there are at least $\frac{1}{e} \cdot |U|$ clients at a distance of $\Delta$ from any open facility. Therefore, the $k$-median cost is at least $\Delta \cdot \frac{1}{e} \cdot |U|$
The completeness and soundness analysis imply that the non-metric $k$-median problem can not be approximated to any factor better than $\Delta \cdot \frac{1}{e}$. Here, we can set $\Delta$ to any arbitrary large value $\gg n^{c}$ for any constant $c>0$. This completes the proof of the main claim.

Note that I could not find the above result in any literature. However, the above reduction is similar to the one used by Guha and Khuller where they take a distance of $1$ if $e_{j} \in S_{i}$ and $3$ otherwise. Using it they show the hardness of approximation for the metric facility location problem and other related problems.


Are Reversal-bounded Multicounter Machines closed under reversal?

DCM is not closed under reversal.  I don't know of a reference, but it is easy to show it using the expressveness lemmata of Chiniforooshan, E., Daley, M., Ibarra, O.H., Kari, L., Seki, S.: One-reversal counter machines and multihead automata: revisited.

In particular, they state that for any DCM language $L$, there is a word $w$ such that $L \cap w\Sigma^*$ is a nontrivial regular language.  Now let $D$ be the following hinted version of the complement of the prefixes of the Dyck language:
$$D = \{a^nw_1w_2\cdots w_k \mid w_i \in \{[, ]\} \land |w_1w_2\cdots w_n|_] > |w_1w_2\cdots w_n|_[\}.$$
In other words, $D$ is the complement of the Dyck where the number of $a$'s in the prefix gives a position witnessing the unbalancing of the parentheses.  Also, $(\{a\}^*)^{-1}D$ is the complement of the prefixes of the Dyck.  Note that $D$ is in DCM.  Now consider $D^R$ and a word $w \in \Sigma^* = \{a, [,]\}^*$.  Then either $D^R \cap w\Sigma^*$ is finite, or it is nonregular, hence $D^R \notin$ DCM.

I don't know of any interesting subclass of DCM closed under reversal.  (Ad placement!) However, we studied a model called Unambiguous constrained automata which is close but not comparable to DCM, and which enjoys closure under reversal --- constrained automata, or Parikh automata, themselves are equivalent to NCM in the nondeterministic case, and a strict subset of DCM in the deterministic case.


How to mechanically derive the recursor of a type from its constructors?

Section 5.6 of the HoTT book discusses the general schema for inductive types, including how to get the corresponding induction principle.

In short, yes there is a general way to derive the elimination principle from the signature (the description of the construcotrs), and it is of course algorithmic. Coq does it, for instance, when you define an Inductive foo and it generates the eliminator foo_rect.


If you do not insist on a database, the Encyclopedia of algorithms By Ming-Yang Kao is very valuable reference. The above link is the entry for the minimum Bandwidth problem.

  This is an encyclopedia of algorithms that sets out the solutions to important algorithmic problems. It aims to be a comprehensive collection and is designed to provide quick and easy access for both students and researchers.” (Kybernetes, Vol. 38 (1/2), 2009)


Complexity of algorithm to test if a graph is asymmetric

The complement of your problem is known as graph automorphism problem (GA). It is a candidate for $NP$-intermediate problems. The problem is not known to be solvable in polynomial time. Also, It is not known to be $NP$-complete. It polynomialy reduces to the graph isomorphism problem (GI) but no known polynomial reduction from GI to GA. Unique-GI is equivalent to GA.


Vertex Cover applications in the real world

Some problems in the area of computational biology seem suitable for practical applications that are not artificial - or at least not as artificial as the problems mentioned by Jukka Suomela.

For instance, people often mention the work by F. Abu-Khzam, R. Collins, M. Fellows, M. Langston, W. Suters C. Symons, Kernelization Algorithms for the Vertex Cover Problem: Theory and Experiments, Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX), ACM/SIAM, Proc. Applied Mathematics 115, 2004.

As the authors state, "One of the applications to which we have applied our methods involves finding phylogenetic trees based on protein domain information, ..." (section 8 of above paper).

A subset of the authors have similar papers on this topic, see, e.g., Faisal N. Abu-Khzam, Michael A. Langston, Pushkar Shanbhag and Christopher T. Symons, Scalable Parallel Algorithms for FPT Problems, Algorithmica, Volume 45, Number 3, 269-284.

I'm not sure whether the instances used in the experiments were real-world instances or artificial, but I hope the two references give you a good starting point.


Several papers appear to imply P=NP via chordal graphs, what is wrong?

The problem is that you confused the definiton in the paper of Aharoni & Szabo and the normally used definition for the term "independence domination number". The former one refers to the largest size over all minimum set dominating an independent set, and the latter one is the smallest size of a dominating set which is also an independent set.

These two definitions are quite different, and as you noticed they have different symbols: $\gamma^i(G)$ and $i(G)$. The Theorem 1.1 you mentioned actually claims $\gamma(G)=\gamma^i(G)$ for chordal graphs $G$, and generally they are not equal to $i(G)$ even when $G$ is chordal. The following graph is a counterexample:

where $\gamma(G)=2$ and $i(G)=3$.

As a comment, Allan & Laskar showed that $\gamma(G)=i(G)$ when $G$ is claw-free, but there are no such conclusions for chordal graphs.


Aren't Monads F-Algebra's? And then if that could be said are Comonad's F-Coalgebra's?

The paper with a rather suggestive title "Algebras, Coalgebras, Monads and Comonads" (2001)
by Neil Ghani, Christoph Lüth, Federico De Marchi, John Power addresses this topic.


I found myself having to find a Hamilton path in a graph of 200 vertices (what you called "nodes"). My first idea was to use the Hamilton path solver in Maxima ( http://maxima.sourceforge.net/docs/manual/de/maxima_50.html#IDX2257 ), but it wasn't able to solve it. Luckily, a few years ago, I used to use SAT solvers to solve difficult logic grid puzzles (because I had a friend who kept on sending them to me!), so wrote a program to write a SAT model for the graph. To my delight, when I fed the model to an open source SAT solver (MiniSat), it was able to resolve it in less than 10 minutes (I didn't time it I'm afraid - I started it, and it had finished when I came back).

Disclaimer: I am not a "theoretical computer scientist", nor even somebody who has ever done a Hamilton cycle before - I landed here after a Google search and thought I'd share what I did over the weekend. However, for a beginner, beating the mathematicians who wrote the Graphs package in Maxima isn't bad - and suggests that if you need to find a Hamilton path (or cycle) in a large graph, building a SAT model is an approach worth considering.


Are there families of formal languages known to be truly PAC learnable?

There is a recent result on the polynomial pac-learnability of semilinear sets at LICS 2010: Parikh Images of Regular Languages: Complexity and Applications. I guess this is not what you are looking for.

You should also have a look to the paper of Clark and Thollard: PAC-learnability of Probabilistic Deterministic Finite State Automata


I don't know about constructions from general assumptions, but you can get a plausible candidate for a "one-way permutation without a trapdoor" by using discrete log modulo a prime $p$.  That is, let $g$ be a primitive root modulo $p$, and define $\pi(x) = g^x\!\mod p$.  Then $\pi$ is a permutation on the integers between $1$ and $p-1$, and it is generally assumed to be one-way.  For the "no trapdoor" part, I suppose you need to define exactly what that means, but as far as I know, we don't have any way to set things up to enable inversion.  (If we did, then it'd have all sorts of cool (positive) applications in cryptography!)


Main idea of the answer: if we reduce an instance of parameterized Independent Set to parameterized Vertex Cover, then the parameter than we end up with depends on the size of the graph, and does not only depend on the input parameter. Now for some more detail.

As you know, a parameterized problem $Q$ is in (uniform) FPT if there is an algorithm that decides whether an input $(x,k)$ is contained in $Q$ in time $f(k) |x|^{O(1)}$ for some function $f$.

Since you can decide whether a graph $G$ has a vertex cover of size $k$ by picking an edge, and branching on which of its two endpoints to put in the vertex cover, this branching only goes $k$ deep (else you've put more than $k$ vertices in the cover), and easily runs in time $O(2^k n^2)$; therefore $k$-Vertex Cover is in FPT.

Now suppose we want to try use this algorithm to show that parameterized Independent Set is in FPT; assume we are given a graph $G$ on $n$ vertices and want to decide whether it has an independent set of size $\ell$. This is equivalent to asking whether $G$ has a vertex cover of size $n - \ell$. So we use our above algorithm to compute the answer in $O(2^{n - \ell} n^2)$ time. For our FPT algorithm, the exponential function in the running time may depend on the parameter, which is $\ell$, but it may NOT depend on the size of the input, which is $n$; but the approach we sketched uses time exponential in $n - \ell$ and is therefore not an FPT parameter with respect to the parameter $\ell$. This is why the fact that Vertex Cover is in FPT does not imply that Independent Set is in FPT.


How can one construct a densest graph with no k-clique?

Turan's theorem exactly characterizes the densest graphs on n vertices with no k clique. The Turan graphs are the maximal graphs, and they're very easy to construct. Is this what you want?


If machine learning techniques keep improving, what's the role of algorithmics in the future?

This is a question that has been haunting me recently, so I am glad you asked it.
However, I am less interested in classifying the application areas for which machine learning will dominate the computational approach than I am in the impact on advancement in the field of (traditional) algorithms.  What kind of "human-crafted algorithms" research will we still be interested in, in 30 years?  Admittedly, this is the harder question to answer in general, because it is the application that determines what quality of result is required.

I think that enumeration algorithms will number among the survivors.  There will continue to be a need to test all inputs to a chip, or conduct an exhaustive search.  The object-specific attention, the finely-tuned design required to generate each object instance exactly (or at least) once; and the running-time amplification of any wasted effort (there may be an exponential number of instances, as a function of the description of the object) -- these factors make me skeptical that a general-purpose automated learning process can match a clever, purpose-designed solution in this area.


Canonical forms for relational algebra expressions

There are canonical forms, but there are not unique canonical forms. Roughly, the idea is to use observe that sets form a monad and use the equational theory of Moggi's monadic metalanguage as a well-behaved IR for  optimizing queries. See Torsten Grust's PhD thesis, Comprehending Queries.

More recently, the Ferry Project has been investigating integrating programming languages with query languages.


How can we derive this lower bound of a special cut in a graph?

Consider a cut $C$ in $G^\prime$. Let $c_k(C)$ be its uniform cut capacity in $G$. Then $c_k(C) \geq c_k(s,t)$. By definition of $c_k(C)$, exactly $k$ packets, each of size $c_k(C)/k$ can be packed into the cut $C$. So sum of $\lfloor ku_e /c_k(C) \rfloor$ over the cut is at least $k$. As $c_k(C) \geq c_k(s,t)$, $ku_e /c_k(C) \leq ku_e /c_k(s,t)$. So

$$
\sum_C u_e^\prime = \sum_C \lfloor ku_e /c_k(s,t)\rfloor \geq \sum_C \lfloor ku_e /c_k(C)\rfloor \geq k
$$


Call-by-push-value's denotational semantics of "thunk diverge"

Yes, your reading is correct.

$U$ forgets that something is a domain, but does not change the underlying carrier set or the poset structure. The least element is still there.

It is also the case that $U \circ F$ can be equipped with the structure of a monad, as you say.

And yes, predomains need not have a least element.


Combinatorial Independent set Algorithms for sub-classes of perfect graphs

One springs to mind and is listed as a maximal subclass in ISGCI, which surprised me: perfect claw-free graphs (a.k.a. perfect quasi-line graphs).  This was done by Minty for all claw-free graphs around 1980.  But a couple of other algorithms for claw-free graphs, one recently in SODA 2011 that is $O(n^3)$ by Faenza, Oriolo, and Stauffer, use the Chudnovsky-Seymour structural characterization of these graphs to reduce the problem to line graphs (and therefore maximum matching) in a fairly straightforward way.  If you're only looking at perfect claw-free graphs, then the earlier characterization by Maffray and Reed is sufficient (and the reduction to line graphs is more obvious).


Lower bound on the size of maximum interval induced subgraphs of an $n$-vertex graph $G$

We can do $2\sqrt{n}-1$; consider the complete $\sqrt{n}$-partite graph, as long as there are two parties both with more than one node inside there is an induced $C_4$, so it cannot be inteval.  Therefore we have to remove at least $(\sqrt{n}-1)^2 = n - 2\sqrt{n} + 1$ nodes to destroy all the induced $C_4$.


Finding the shortest distance in a dynamic graph

The search keywords are "dynamic all pairs shortest paths".

Demetrescu and Italiano have a good survey,
http://dl.acm.org/citation.cfm?id=1198519

Looks like $O(n^2 log^3 n)$ cost per update if you want to maintain fast lookups.


Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Gil, would something like this be a counterexample?

Let $m$ be such that $n=m+\log m$, and think of an $n$-bit input as being a pair $(x,i)$ where $x$ is an m-bit string $(x_1,\ldots ,x_m)$ and $i$ is an integer in the range $1,\ldots,m$ written in binary.

Then we define $f(x,i):= x_1 \oplus \cdots \oplus x_i$

Now for each $i=1,\ldots,m$ the function f() has $1/m$ correlation with the Fourier character $x_1 \oplus \cdots \oplus x_i$, and so the "level i" has at least a $1/m^2$ fraction of the mass. (In fact more, but this should suffice)

f() can be realized in depth-3: put all the XORs in a layer, and then do the "selection" in two layers of ANDs, ORs and NOTs (not counting the NOTs as adding to the depth, as usual).


No. Consider the 4-by-4 matrix below.

 0     1     1     1
 1     0     1     1
 0     0     0     1
 1     1     0     1