"Impredicative" in type theory I am confused. I think I've read two usages of the word "impredicative" in type theory:

When people talk about the "impredicative" version of Martin-Löf's type theory, which they say it is inconsistent. Apparently they call it impredicative because of Type : Type.
When people talk about the "impredicative" Prop in CoC. Apparently they call it impredicative because you can quantify over Prop and get Prop stuff.

Is it the case? One notion of impredicativity implies the other? Is there no problem (i.e. inconsistency) by assuming "Prop impredicative"?

The definition of an object $X$ is impredicative, if the definition uses a collection $C$ in the construction of $X$, such that $X$ is a member of $C$.  So impredicativity is a form of circularity.

We are wary of circular definitions because they are often paradoxical. Fortunately it turns out that not all forms of
circularity are (or appear to be) problematic.  The most famous example of an impredicative definition that is circular, but (as far as we know) not contradictory is the definition of natural numbers in set theory:

$$
\mathbb{N}\ \stackrel{\text{def}}{=}\ \bigcap \{X\ |\ X\ \text{is an inductive set}\}
$$

where a set is inductive if it contains $\emptyset$ and
  is closed under the set-theoretic successor operation.  Clearly, $\mathbb{N}$ is itself inductive, hence what you define on the left already occurs in some sense on the right.

By the "impredicative version of Martin-Löf's type theory" I guess you mean the type theory in his 1971 manuscript "An intuitionistic theory of types". This system has an  impredicative axiom  that stipulates a type of all types.  For this reason the system is often simply called "type:type". This axiom is too strong as J.-Y. Girard showed, as it makes the type-theory inconsistent.

In contrast, the impredicativity in the CoC is not (known to be) inconsistent.

In some sense there are two forms of impredicativity: those that are known to be paradoxical, and those that are not.


Is there any special property the resulting graph G' has? Undirected graph $G$ can be partitioned into several vertex blocks, each vertex pair $(u,v)$ has an edge if "$u$" and "$v$" are in the different blocks; no edge, otherwise. Question is: Suppose we have several such graphs $G_1,\ldots,G_n$, where a vertex $v_i$ may be in more than one $G_j$.  If we combine graphs $G_1,\ldots,G_n$ by taking the union of their edge sets to get a graph $G'$, as shown in the example below, what is the name of the resulting graph?

The formal statement of the graph you are describing is the sum of $n$ complete $k_i$-partite graphs (where $k_i$ is the number of groups in $G_i$).

Here is an interesting property: $G'$ is $\prod k_i$-colorable.

A $k$-partite graph (assuming non-empty parts) is $k$-colorable (color all of the vertices in one part with the same color). A complete $k$-partite graph has chromatic number $k$ (clearly two vertices in two different parts require different colors). In fact, it has a maximal set of edges such that the graph has chromatic number $k$ (adding an edge within a part will force another color). If the graphs $G_1$ and $G_2$ are $k_1$ and $k_2$ colorable respectively, the sum $G = G_1 + G_2$ is $k_1k_2$ colorable by the product coloring. It follows that each $G_i$ is $k_i$ colorable, and that the sum, $G'$ is $\prod k_i$-colorable.

This property is tight if we know nothing more about the graphs. For arbitrary $n$ let $p_1p_2\cdots p_k$ be the prime factorization of $n$ (where repeated primes are listed repeatedly). If $G'$ is the sum of $k$ correctly-chosen complete $p_i$ partite graphs, $G' = K_n$. To choose $G_1$, let the parts be the residues modulo $p_1$. For $G_2$, let $i$ be in a part according to the residue of $\lfloor \frac{i}{p_1}\rfloor$ modulo $p_2$. Continuing this for each $k$ makes the right subgraphs. The best way to imagine this is to express $i$ has a number where the 1s place goes up to $p_1$, the $p_1$s place (the next digit over) goes up to $p_2$, etc. Then $G'$ is complete because if $i \neq j$ then The representations of $i$ and $j$ are different.


Probability of two vertices being connected by some path in a random directed graph Define $G(n, p)$ as a random directed graph ($n$ vertices; we put edge between two vertices with probability $p$).

What are the known results for the following problem:

Fix two vertices $v$ and $u$. What is the probability that there is at least a path (of length at most $k$) between $u$ and $v$?  (clearly the result should be a function of $n$, $p$ and $k$). Upper-bound would work too, if there is no known exact answer.

Consider a BFS exploration process, which proceeds in $k$ stages. Put $V_0 = \{u\}$. Given $V_0,\ldots,V_i$, explore all edges from $V_i$ to $V \setminus \bigcup_{j=0}^i V_j$ (where $V$ is the set of all vertices), and set $V_{i+1}$ to consist of all vertices reached in this fashion; their number has a binomial distribution which can easily be calculated. After $k$ steps, check whether the vertex $v$ belongs to $\bigcup_{j=0}^k V_j$.

Note that this process is exactly the same in both the undirected and the directed case. Hence the answer, whatever it is, is identical for both models. Presumably in the undirected case the answer is known and can be looked up. Otherwise you can try to estimate it by estimating the sizes $|V_i|$ and so the probability $\frac{1}{n-1} \sum_{i=1}^k |V_i|$ that $v$ belongs to $\bigcup_{i=1}^k V_i$.


Formal representation of algorithm using recursive algebraic data types I have an algorithm written in Haskell which I am describing in my thesis. In the code for the algorithm I have a recursive data type similar to this:

  data Data = A Int | B Data | C Data

Now I am thinking about how to explain this in a formal way, in a way that feels natural and clear. Note that B and C contain the same data.

The only reasonable alternative I have come up with is to use some kind of tagged union, like this:

Let $Data$ be a recursively defined set given by:

Let $i$ be an integer. Then $\langle \mathcal{A}, i \rangle \in Data$.
Let $d \in Data$. Then $\langle \mathcal{B}, d \rangle \in Data$.
Let $d \in Data$. Then $\langle \mathcal{C}, d \rangle \in Data$.

With this definition I write functions over $Data$ like this:

$$
func(\langle \mathcal{A}, i \rangle) = \cdots \\
func(\langle \mathcal{B}, d \rangle) = \cdots \\
func(\langle \mathcal{C}, d \rangle) = \cdots \\
$$

And predicated about is like this:
$$
Pred(\langle \mathcal{A}, i \rangle) \text{ holds if ... } \\
Pred(\langle \mathcal{B}, d \rangle) \text{ holds if ... } \\
Pred(\langle \mathcal{C}, d \rangle) \text{ holds if ... } \\
$$

This representation is very close to the Haskell source code, which is good, but it feels rather unnatural to mathematicians.

Is there a more elegant and natural way to do this?

EDIT:
Thanks for the replays, sorry if I am being unclear.

I am writing a master's thesis in CS about alias analysis. The text should be comprehensible for students on master level in CS with a background in algorithms (does master level mean the same in the USA? In EU you get this degree after 5 years of study including an 1 term thesis project).

I have used this paper as a starting point, implemented that algorithm in Haskell and made some extensions. Now I want to describe my extension in a way that is similar to the paper in formulation and level of formalism. However I use a recursive algebraic data type in my extension and I'm not sure about the most natural and clear way to represent it.

EDIT: The example $Data$ above is intended to have finite values only.

EDIT:
I see that my question is very similar to this: Formal Representation of Haskell Data-Types

Except that I'm also interested in how to represent recursive data types.

EDIT: Summary of the alternative suggestions I have received

Tagged tuples (my example above and  Andrej Bauer's alternative)
Function applications (Shahab's first alternative)
$$
  data(a(d)) = \dots
$$
Objects with special notation / operators (Shahab's second alternative)
$$
  \langle d \rangle = \dots
$$
Un-data-type-ization (yatima2975's alternative)

Transform into non-recursive form. Works only for data types with one recursive element.
"the Cartesian product of finite strings over {B,C} and the integers"

I think all of the have advantages and disadvantages.

You should get acquainted with inductive definitions.

Instead of saying that $Data$ is recursively defined, say that it is a set constructed inductively by:

$(0,i) \in Data$ for every $i \in \mathbb{Z}$,
$(1,d) \in Data$ for every $d \in Data$,
$(2,d) \in Data$ for every $d \in Data$.

Another way to say the same thing is that $Data$ is the smallest set such that
$$Data = \lbrace (0,i) \mid i \in \mathbb{Z} \rbrace \cup
\lbrace (1,d) \mid d \in Data \rbrace \cup
\lbrace (2,d) \mid d \in Data \rbrace.$$
Then remark that you use abbreviations $\mathcal{A} = 0$, $\mathcal{B} = 1$, $\mathcal{C} = 2$. Mathematicians are not used to introduction of basic symbols or tags, unless they are considering polynomials in a "variable" $X$ (which they really should call "symbol").

But it may be better not to cater to old-fashioned traditions of mathematicians. We should push them into the 21st century and teach them some math which they think of as "computer science". What is wrong with assuming your reader knows what an inductive data type is?

One word of warning: Haskell does not have inductive datatypes, but rather coindcutive data types. If you define the type in Haskell you will also get infinite elements of the form B (B (C (B ....))). There is just no way to get this right in Haskell. ML has proper datatypes.


Characterisation of computability of partial functions from infinite words into finite words by functions with prefix-free domain The following is taken from K. Weihrauch, Computable Analysis, page 21. The notation $f : \subseteq A \to B$ means a partial function. By $\Sigma^{\omega}$ and $\Sigma^{\ast}$ we denote the set of infinite words, and finite words over $\Sigma$. The book is concerned with Type-2 computability, which defines computability over infinite words. Then a function $f : \subseteq \Sigma^{\omega} \to \Sigma^{\ast}$ is called computable iff there exists a Turing machine reading its input on a read-only tape from left to right (without going back), and outputting symbols on its output tape without the ability to go back, i.e. what is written once could not be erased. This is called Type-2 computability (or a Type-2 machine).

  Statement: A function $f :\subseteq \Sigma^{\omega} \to \Sigma^{\ast}$ is computable, iff $f = h_{\ast}$ for some computable function $h :\subseteq \Sigma^{\ast} \to \Sigma^{\ast}$ with prefix-free domain.

  Proof: Let $M$ be a Type-2 machine computing $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$. Define $h :\subseteq \Sigma^{\ast} \to \Sigma^{\ast}$ by
  $$
 h(w) := \left\{\begin{array}{ll} f(w0^{\omega}) & \mbox{if on input $w0^{\omega}$ the machine $M$ halts after exactly $|w|$ steps} \\
     \mbox{div} & \mbox{otherwise.} \\
 \end{array}\right.
$$
  Then $h$ is computable, has prefix-free domain and satisfies $f = h_{\ast}$. [...]

I am unsure about $f = h_{\ast}$. Surely if $h_{\ast}(p) = u$, then $h(w) = u$ for some $w \in \mbox{dom}(h)$ with $w \sqsubseteq p$. By the defintion of $\mbox{dom}(h)$ this mean the machine halts on $w0^{\omega}$ in exactly $|w|$ steps, hence has read at most $|w|$ symbols, and thereby exhibiting the same behavior on $p$, i.e. we have $f(p) = u$.

But now I want to show that if $h_{\ast}(p)$ diverges, then $f$ diverges too, or, giving the same, that if $f(p) = u$ then $h_{\ast}(p) = u$. But for example suppose $f(p) = u$, and let $k$ be the steps taken by the machine reading $p$ to halt and produce $u$, then surely the prefix $v$ of $p$ read in this process has at most length $k$. But as $|v| < k$ is possible, we could not conclude that $v \in \mbox{dom}(h)$, but by padding $v$ with zeros we know $v0^{k - |v|} \in \mbox{dom}(h)$ by definition, and hence $h_{\ast}(v0^{\omega}) = h(v0^{k - |v|})$ so that $f(p) = h_{\ast}(v0^{\omega})$. But this is all I get, I do not see how to conclude $h_{\ast}(p) = f(p)$, as this would mean we have some prefix $x$ from $p$ such that the machine takes exactly $|x|$ steps in producing $u$, but in general we cannot conclude that $v0^{k - |v|}$ is a prefix of $p$ if $k - |v| > 0$.

So why does this result holds? And why $h_{\ast} = f$?

I guess I have an alternative solution. Let $f :\subseteq \Sigma^{\omega} \to \Sigma^{\omega}$ be computable. Define
$$
 h(u) = v \mbox{ iff }
  f(u\Sigma^{\omega}) = \{v\} \mbox{ with $u$ minimal}
$$
and let $h(u)$ diverge otherwise. Then $\mbox{dom}(h)$ is prefix-free for if $h(u) = v$ then $f(u\Sigma^{\omega}) = \{v\}$ as the machine behaves the same when reading the prefix $u$, producing $v$. Also $h$ is computable, for if $M$ is a machine for $f$ and $u \in \Sigma^{\ast}$, just simulate $M$ on $u0^{\omega}$ and if it produces some output and stops check if the prefix read by $M$ equals $u$; and if not just enter an infinite loop.

Furthermore we have $f = h_{\ast}$. For if $f(p) = u$ then there exists some minimal prefix $w \sqsubseteq p$ with $f(w\Sigma^{\omega}) = \{u\}$, hence $h_{\ast}(p) = h(w) = u$. For the other direction suppose $h_{\ast}(p) = u$, then $w \sqsubseteq p$ with $h(w) = u$, i.e. $f(w\Sigma^{\omega}) = \{u\}$, in particular $f(p) = u$.


Examples where the uniqueness of the solution makes it easier to find The complexity class $\mathsf{UP}$ consists of those $\mathsf{NP}$-problems that can be decided by a polynomial time nondeterministic Turing machine which has at most one accepting computational path. That is, the solution, if any, is unique in this sense.
It is thought highly unlikely that all $\mathsf{UP}$-problems are in $\mathsf{P}$, because by the Valiant-Vazirani Theorem this would imply the collapse $\mathsf{NP}=\mathsf{RP}$.

On the other hand, no $\mathsf{UP}$-problem is known to be $\mathsf{NP}$-complete, which suggests that the unique solution requirement still somehow makes them easier.

  I am looking for examples, where  the uniqueness assumption leads to a faster algorithm.

For example, looking at graph problems, can a maximum clique in a graph be found faster (though possibly still in exponential time), if we know that the graph has a unique maximum clique? How about unique $k$-colorability, unique Hamiltonian path, unique minimum dominating set etc.?

In general, we can define a      unique-solution version of any $\mathsf{NP}$-complete problem, scaling them down to $\mathsf{UP}$. Is it known for any of them that adding the uniqueness assumption leads to a faster algorithm? (Allowing that it still remains exponential.)

3-SAT may be one such problem.  Currently the best upper bound for Unique 3-SAT is exponentially faster than for general 3-SAT.  (The speedup is exponential, although the reduction in the exponent is tiny.)  The record-holder for the unique case is this paper by Timon Hertli.

Hertli's algorithm builds upon the important PPSZ algorithm of Paturi, Pudlák, Saks, and Zane for $k$-SAT, which I believe is still the fastest for $k \geq 5$ (see also this encyclopedia article).  The original analysis showed better bounds for Unique $k$-SAT than for general $k$-SAT when $k = 3, 4$; subsequently, however, Hertli showed in a different paper that you could get the same bounds for (a slightly tweaked) PPSZ algorithm, without assuming uniqueness.  So, maybe uniqueness helps, and it can definitely simplify the analysis of some algorithms, but our understanding of the role of uniqueness for $k$-SAT is still growing.

There is evidence that Unique $k$-SAT is not too much easier than general $k$-SAT. The Strong Exponential Time Hypothesis (SETH) asserts there is no $\delta < 1$ such that $n$-variable $k$-SAT is solvable in $O^*(2^{\delta n})$ time for each constant $k \geq 3$. It was shown in a paper of Calabro, Impagliazzo, Kabanets, and Paturi that, if SETH holds, then the same statement is true for Unique $k$-SAT.  Also, if general $k$-SAT  requires exponential time, i.e. there is some $k \geq 3, \epsilon > 0$ such that general $k$-SAT cannot be solved in time $O^*(2^{\epsilon n})$, then the same must be true for Unique 3-SAT.  See the paper for the most general statement.

(Note: the $O^*$ notation suppresses polynomial factors in the input length.)


Has there been any research on $k$-SAT above the satisfiability threshold? A well known characteristic of $k$-SAT instances is the ratio of the number of clauses $m$ over the number of variables $n$, i.e., the quotient $\rho = m/n$.  For every $k$, there is a threshold value $\alpha$ s.t.\ for $\rho \ll \alpha$, most instances are satisfiable, and for $\rho \gg \alpha$ most instances are unsatisfiable. There has been a lot of research done for problems where $\rho \ll \alpha$, and for problems with sufficiently small $\rho$, $k$-SAT becomes solvable in polynomial time.  See, for instance, Dimitris Achlioptas's survey article from the Handbook of Satisfiability (PDF).

I am wondering if any work has been done in the other direction (where $\rho \gg \alpha$), e.g., if we can somehow transform the problem from CNF to DNF in this case to solve it quickly.

So, essentially, What is known regarding SAT where $\rho = m/n \gg \alpha$?

Yes, there has been. Moshe Vardi recently gave a survey talk at BIRS Theoretical Foundations of Applied SAT Solving workshop:

Moshe Vardi, Phase transitions and computational complexity, 2014.

(Moshe presents the graph of their experiment a bit after minute 14:30 in his talk linked above.)

Let $\rho$ denote the clause ratio.
As the value of $\rho$ increases beyond the threshold
the problem becomes easier for existing SAT solvers,
but not as easy as it was before reaching the threshold.
There is a very steep increase in difficulty as we approach the threshold from below.
After the threshold the problem becomes easier compared to the threshold but
the decrease in difficulty is much less steep.

Let $T_\rho(n)$ denote the difficulty of the problem w.r.t. to $n$
(in their experiment $T_\rho(n)$ is the median running-time of GRASP on random 3SAT instances with the clause ratio $\rho$).
Moshe suggests that $T_\rho(n)$ changes as follows:

$\rho \ll$ the threshold: $T_\rho(n)$ is polynomial in $n$,
$\rho$ is near the threshold: $T_\rho(n)$ is exponential in $n$,
$\rho \gg$ the threshold: $T_\rho(n)$ remains exponential in $n$ but
the exponent decreases as $\rho$ increases.


Fingerprinting for dynamic sets Does there exist a w-bit word-RAM data structure with O(1) time per operation for the following problem?:  Maintain a set of w-bit non-negative integers that supports the operations

add(x) : add x to the set
remove(x) : remove x from the set
fingerprint() : return a fingerprint of the set.  This w-bit fingerprint has  the property that two sets that are identical have the same fingerprint while two sets that are different probably have different fingerprints

All operations should run in constant time.

The Rabin-Karp fingerprinting scheme, where $$f(S) = \left(\sum_{x\in S} 2^x\right) \bmod p$$ where p is a random w-bit prime almost works.  The problem is with the update time, since computing $$2^x \bmod p$$ takes more than constant time.  Using repeated squaring, this can be done in O(log w) time. The fastest modular exponentiation algorithm I could find does something like (log w)/(loglog w) arithmetic operations.

This answer is a bit hand-wavey.

Select a function $h$ uniformly at random from the set of all functions from w-bit words to w-bit words. For each set, maintain a w-bit fingerprint as follows:

The empty set has the fingerprint 0.
add(x) and remove(x) update a fingerprint $f$ to $f \oplus h(x)$, where $\oplus$ is xor.

Let $S \neq T$ be two sets of w-bit integers. If their fingerprints are the same, then the fingerprint of $S \triangle T$, the symmetric difference of $S$ and $T$, is 0, which happens with probability $2^{-w}$.


NFA to 2DFA: what are the upper and lower bounds? Suppose that one has an NFA (from, say, a regular expression).  What is the state complexity of turning it into a 2DFA?

The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction:

  The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs
  are still unknown. The problem of stating them was raised in 1978 by
  Sakoda and Sipser [32], with the conjecture that they are not
  polynomial. In spite of all attempts to solve it, this problem is
  still open.

As explained in section 6 of that survey, the question relates to the L vs. NL problem, so it may be not surprising that the problem remains unresolved.
Concerning lower bounds, section 5 states the following:

  The question 1NFAs versus 2DFAs has been solved in the unary case
  in [4] by showing that the tight cost is polynomial, more precisely
  Θ(n²). This gives also the best known lower bound for the general
  case.

EDIT (2017/09/18): Concerning upper bounds, the PhD thesis of Christos Kapoutsis provides a valuable source (thanks goes to András Salamon for his valuable comment below). Section 2 of the PhD thesis mentions the following:

  Second, it is even conjectured that this alleged exponential difference in size between 1NFAs and 2DFAs covers the entire gap from n to $2^n - 1$ which  is known to exist between 1NFAs and 1DFAs [35]² In other words, according to this conjecture, a 2DFA trying to simulate a 1NFA may as well drop its bidirectionality, since it is going to be totally useless: its optimal strategy is going to be the well-known brute-force
  one-way deterministic simulation [47]. So, once more we have an instance of the claim that the obvious, highly inefficient solution is also the optimal one.
  [...]

  ² As with 2DFAS (cf. Footnote 1 on page 8), a 1DFA is allowed to reject by just hanging anywhere along its input. Without this freedom, the gap would actually be from $n$ to $2^n$.

References:

Pighizzini, Giovanni: Two-Way Finite Automata: Old and Recent Results. In: E. Formenti (Ed.), Proceedings 18th international workshop on Cellular Automata and Discrete Complex Systems and 3rd international symposium Journées Automates Cellulaires, AUTOMATA & JAC 2012, pp.3-20.

Kapoutsis, Christos: Algorithms and lower bounds in finite automata size complexity. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA 2006.


Completeness under injective Karp reductions Karp reduction is polynomial time computable many-one reduction between two computational problems. Many Karp reductions are actually one-one functions. This raises the question whether every Karp reduction is injective (one-one function).

  Is there a natural $NP$-complete problem that is known to be complete only under many-one Karp reduction and not known to be complete under injective Karp reduction? What do we gain (and lose) if we define $NP$-completeness using injective Karp reduction?

One obvious gain is that sparse sets can not be complete under injective Karp reductions.

Here is an answer to a special case, when we restrict ourselves to the case when the Karp reduction can also be made length-increasing, along with making it injective.  (Length-increasing means that $|f(x)|>|x|$, where $f$ is the function that represents the reduction.)

Claim: If every Karp reduction in $NP$ can be transformed into one that is injective and  length-increasing, then $P\neq NP$ holds.

Proof.
Let us assume that every  Karp reduction in $NP$ can be transformed into one that is injective and length-increasing. Then there are two possibilities:

All these reductions are not just computable in polynomial time, but the inverse of each function, which exists after making the function injective, is also computable in polynomial time. It is known that if two languages are both reducible to each other  by reductions that are polytime computable, polytime invertible and length-increasing, then they are polytime isomorphic (see Theorem 7.4 in the book "Theory of Computational Complexity" by Ding-Zhu Du and Ker-I Ko). This would mean that all $NP$ complete languages are $p$-isomorphic, that is, the Isomorphism Conjecture holds, which is known to imply $P\neq NP$.
There is at least one among these functions, for which the inverse is not computable in polynomial time. This function would provide an example of a worst-case one-way function. It is known, however, that the existence of worst-case one-way functions also implies $P\neq NP$. (See Theorem 2.5 in the book "The Complexity Theory Companion" by Hemaspaandra and Ogihara.)

Therefore, the assumption that every  Karp reduction can be made injective and lenght-increasing implies $P\neq NP$, so it is likely very hard to prove. On the other hand, it might be easier to disprove because that does not seem to have such a dramatic consequence. It is also unclear, what happens if we drop the length-increasing assumption.


Boundedness of expected reward Markov chain This is a repost of a question I asked on math.SE.

The problem:

I have an infinite Markov chain $M$ over the natural numbers, with transition probabilities $$P(n,m)=\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q).$$

For any natural numbers $n$ and $s$, I define the random variable $O^n_s:\mathbb{N}^*\rightarrow \mathbb{N}$ to be sum of all states visited if we start in state $s$ and end when we first reach a state less than or equal to $n$. Formally, let $w = (s, w_1, w_2, \dots)$ denote the random sequence of states visited by the Markov chain, and let $$O^n_s(w)=\left\{\begin{array}{ll} \sum_{i=1}^{l}w_i& \text{where $l$ is the smallest index such that $w_l\le n$}\\\bot& \text{if $w_i > n$ for all $i$}\end{array}\right.$$

Let $\mathcal{E}^n_s$ denote the conditional expectation $E_w[O^n_s(w)\mid O^n_s(w)\neq\bot]$.

The question is:

Is there a real number $B$ such that $\mathcal{E}^n_s\leq B$ for all natural numbers $n$ and $s$?

what I think:

This process reminds me of a discrete time $M/M/\infty$ queue where at each step $n$ arrives with probability $q^n(1-q)$ and at each step each service terminates with probability $p$.

What I'm looking for:

But I couldn't find any references or hint about a model like that. If you have any idea or references (or, even better, a proof) please tell me.

Any ideas, (even if it doesn't apply directly there) would be accepted. I'm a bit out of idea on how to solve this.

[note: why P is a transition matrix]

For all $n\in \mathbb{N}$, $$\begin{array}{rcl}
\sum_{m\in\mathbb{N}}P(n,m)&=&\sum_{m\in\mathbb{N}}\sum_{i=0}^{min(m,n)} {n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\
&=&\sum_{i=0}^{n}\sum_{m\geq i}{n\choose i}(1-p)^ip^{n-i}q^{m-i}(1-q)\\
&=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq i}q^{m-i}(1-q)\\
&=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\sum_{m\geq 0}q^{m}(1-q)\\
&=&\sum_{i=0}^{n}{n\choose i}(1-p)^ip^{n-i}\\
&=&1
\end{array}$$

It is not bounded sorry for the inconvenience. Here is the proof a friend gave me (thanks a lot to him):

Let consider the set $W_1 = \{w = (s,w_1,\dots)| w_1 \leq n\}$. Then $\mathcal{E}^n_n$ is bigger than $\displaystyle\sum_{w\in W_1}O^n_n(w)*P(w)$.

\begin{align}
\sum_{w\in W_1}O^n_n(w)*P(w) &= \sum_{k=0}^n \sum_{i=0}^k {n\choose i}(1-p)^i p^{n-i}q^{k-i}(1-q) * k \\
&= (1-q) \sum_{i=0}^n \sum_{k=i}^n {n\choose i}(1-p)^i p^{n-i}q^{k-i}*k\\
&= (1-q) \sum_{i=0}^n  {n\choose i}(1-p)^i p^{n-i}\sum_{k=i}^n q^{k-i}*k\\
&\geq (1-q) \sum_{i=1}^n  {n\choose i}(1-p)^i p^{n-i}i \\
&\geq (1-q) \sum_{i=0}^{n-1} {n\choose i+1}(1-p)^{i+1} p^{n-1-i}(i+1) \\
&\geq (1-q) n (1-p) \sum_{i=0}^{n-1} {n-1 \choose i}(1-p)^i p^{n-1-i} \\
&\geq (1-q) n (1-p)
\end{align}


Complexity lower bound: the gap between decision trees and RAMs I recently discovered a quadratic lower bound on the complexity of a problem in the decision tree model, and I wonder whether this result could be partially generalized to the random access machine model. By partially, I mean a generalization to RAM programs with a certain time/space tradeoff. For instance, I'd like to show that my problem cannot be solved by a linear-time and -space RAM program.

A.M. Ben-Amram and Z. Galil proved in this paper that a RAM program running in time $t$ and space $s$ can be simulated in $O(t \, \log s)$ time on a pointer machine. Do we know similar results which could be applied to decision trees?

Alternatively, is it possible to simulate a RAM program running in space $s$ with a decision tree of degree $s$? (intuitively, indirect addressing could be simulated using nodes of degree $\leq s$)

The natural model related to decision trees that can simulates RAMs is the branching program.  Basically, it is a decision tree with common subtrees coalesced yielding a DAG.   Time T and space S on a RAM can be simulated in height T and size 2^S on a branching program.  (You might need to use multi-way branching.)

For decision problems, it is clear that any decision tree only needs height = # inputs and space=total # of bits in the input.  Note that with multi-way branching one might have the # bits in the input larger than the usual measure of the # of inputs (e.g. n pointers each taking log n bits.)    For such problems with nlog n total input bits one can prove that certain problems cannot be solved in time O(n) and space=O(n) bits.  Is that the form of you problem?

You seem to suggest that you are using the # of outputs to try to get a larger lower bound.  It is usual for multi-output problems to allow many outputs along a single edge rather than at leaf nodes (see, for example, Borodin-Cook's 1982 paper on sorting lower bounds).  However, even without this assumption, one also can compute any function with height = # inputs and space = # input bits.  (Read and remember the input, and output all the values at each leaf node.)


Is there a list of known problems? Is there a database of known problems with information about their complexity and algorithms, related problems, references etc that is available to us?  [If not, can we make one? I know this is off topic, but it would be SO useful]

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)


Introduction to probabilistic automata Where can I find an introduction to probabilistic automata and what they recognize (certain functions from words to $[0,1]$)? Is there a standard term for such functions which are recognized by probabilistic automata, analogous to "regular languages" for what deterministic finite automata (DFAs) recognize?

I'm looking for something which approaches it analogously to studying basic questions on DFAs and regular languages, such as expressiveness, closure, and decidability properties.

This and this don't quite seem to be what I'm looking for.

The first paper by Rabin (1963) gives the basics what you are looking for. The class of languages recognized by probabilistic automata (with cutpoint) is called stochastic languages.

Let $P$ be a probabilistic automaton defined on the alphabet $ \Sigma $ and $ f_P(w) $ be the accepting probability of $ P $ on the input $ w \in \Sigma^* $. Then, $P$ with cutpoint $\lambda \in [0,1)$ defines the following language:

  $ L(P,\lambda) = \{ w \in \Sigma^* \mid f_P(w) > \lambda \}  $.

Remark that the recognition with cutpoint can be seen as recognition with unbounded error. In case of bounded-error (or isolated cutpoint) probabilistic automata can recognize all and only regular languages.

The book by Paz (1971) and the survey by Bukharaev (1980) are good references.

You can also check a recent survey on quantum automata where you can trace some references on probabilistic automata.


Why is Bayesian filtering better than Neural Networks when classifying spam? According to several people on StackOverflow Bayesian filtering is better than Neural Networks for detecting spam.

According to the literature I've read that shouldn't be the case. Please explain!

It would be interesting to know what litterature you have read.

As far as I know, Bayesian filters were working very well. That's because the learning is based on the words used, and a Bayesian filter is quick to understand that an email containt "Viagra" is likely spam.

But spammers are not so stupid, and they quickly introduced mispelled word. "VI4GRA" has never been seen in any spam before. In a word: it's easy to work around a Bayesian filter.

Neural Networks can be good at classifying. But there are two difficulties: the choice of measures ; the training data.


Quality of a conference I am a physicist working in TCS in a new group. I would like to know, given a conference (imagine your favorite ones),  how can I know the quality of this conference and also the quality of the journal where the proceedings will be pusblished (in case they are). I heard something about CORE classification but found no link or more information about. Thanks

P.S.: I find TCS stack exchange very interesting for TCS discussions (obviously). I just wonder if there is any similar stack exchange academic site for physics/chemistry. I found physics.stackexchange, but some questions related with journals were instantly classified as offtopic

Usually, you should be able to figure out who are the leading researchers or research groups in your research area.

Everything else is then usually fairly straightforward: just find out in which conferences the leading researchers publish their work, and in which conferences they serve in programme committees, etc. Most likely those would be the most relevant conferences for your work as well.

The same applies to journals as well.

(Note that the most relevant conference is not necessarily the same as the most prestigious conference, but it might be a good idea to start with relevant conferences... Your work might have much more impact that way, even if it does not look that impressive in your CV.)


Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices Consider the standard minimum-cost flow problem presented here. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and the target $t$) as follows:
$$\sum\limits_{w \in V } {f({v_i},w) = \sum\limits_{w \in V} {f(w,{v_i}) = } {r_i}} ,\forall {v_i} \in V - \{ s,t\},$$
where $r_i$ is called vertex $v_i$ flow requirement (is there a standard term for it?). Please note that this problem is single-commodity and it is different from the multi-commodity flow problem.

Moreover, consider that all the capacities, costs, flows, and requirements are non-negative integers. Is there a well-known algorithm to solve this problem in polynomial time? If this is an NP-Complete problem, what's the fastest known algorithm and the approximation method to solve it?

This is a standard variant (if not the standard variant) of the minimum-cost flow problem.  The "flow requirements" are sometimes called balance conditions and sometimes called vertex supplies/demands.  It can be solved in polynomial time using any number of algorithms.

In particular, you can reduce to the single-source single-target variant in polynomial time as follows:

Compute a conservative upper bound $M$ on the cost of any flow in your network; for example, let $M = \sum_e cap(e)\cdot |cost(e)|$.  Alternatively, treat $M$ as a symbolic infinite value.
Add new nodes $s^*$ and $t^*$.
Add arcs $s^*\to s$ and $t\to t^*$ with infinite capacity and zero cost.
For every node $v_i$ with $r_i>0$, add an arc $s^*\to v_i$ with capacity $r_i$ and cost $-M$.
For every node $v_i$ with $r_i<0$, add an arc $v_i\to t^*$ with capacity $-r_i$ and cost $-M$.
Set all vertex requirements to zero.

The minimum-cost feasible flow from $s^*$ to $t^*$ in this modified network saturates every arc $s^*\to v_i$ and $v_i\to t^*$, and the remaining arcs carry the minimum-cost flow from from $s$ to $t$ in the original network that meets all the flow requirements.


Reachability on DAG (best-known algorithm) Task: To answer several reachability queries on large DAGs (millions or billions of vertices and edges) using a data structure that takes up as little space as possible, is not expensive to construct, and subsequently allows for "near-constant time" responses to reachability queries.

Question: Is there a state-of-the-art data structure that has the following features:
(1). Pre-processing time or time to build data structure is linear in number of edges or vertices. This can also be quadratic, as its a once-off process.
(2). Has linear space complexity
(3). Can answer reachability queries in O(1) time (or even logarithmic time)?

The paper I found which mentioned some structures --> http://www.vldb.org/pvldb/vol7/p1191-wei.pdf

The trade-off between properties (1)-(3), would be that we want to optimize (3), then (2) to the best possible, while (1) is still important but can be rated lowest. So, optimize (3) > (2) > (1).

The worst case would be to do a BFS/DFS for every single query. The other extreme is to pre-compute reachability for every pair of vertices, but then storage would be O(n^2) in a matrix.

[Rooted trees with edges directed away from the root] are DAGs,

and from reachability on such a DAG, one can recover

the root as the unique vertex from which every other vertex is reachable
and
the tree by observing that x is adjacent to y if and only if [x≠y and [one of {x,y} is

reachable from the other of {x,y}] and [there is no vertex z such that [[z is not in {x,y}] and

[[x is reachable from z is reachable from y] or [y is reachable from z is reachable from x]]]]]

.

Thus, by this formula, there are  $n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(\hspace{-0.02 in}n^{n-2}\right)$  distinct reachability oracles

for [rooted trees with edges directed away from the root].

$\log_2\hspace{-0.06 in}\left(n\hspace{-0.04 in}\cdot \hspace{-0.05 in}\left(n^{n-2}\right)\hspace{-0.03 in}\right) \;\; = \;\; \log_2\hspace{-0.06 in}\left(\hspace{-0.02 in}n^{n-1}\right) \;\; = \;\; (n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n) \;\;$,

so any encoding of [reachability oracles for rooted trees with edges directed away from the root]

will need to use more than $\;\;\; \left((n\hspace{-0.04 in}-\hspace{-0.05 in}1)\cdot \log_2(n)\right)-3 \;\;\;$ bits for more than 3/4 of such DAGs.

By this paper,

"has n1+o(1) space complexity"  and  "Can answer reachability queries in O(1) time"

are incompatible:

As described at the bottom of page 5 and the top of page 6,

"butterfly graph"s are directed acyclic.

Accordingly, all of their subgraphs are also DAGs.

By Theorem 1.2 and the two sentences after that,

for constant time,    "the space needs to be  $n^{1+\Omega \hspace{.02 in}(1)}$ ."

(I'm not aware of any positive results.)


What are values relative to Hask? According to ncatlab's page on category theory and haskell,
"we can identify a subset of Haskell called Hask that is often used to identify concepts used in basic category theory. One considers Haskell types as objects of a category whose morphisms are extensionally identified Haskell functions."

So types are objects, and functions are morphisms.  How, then, does a value, such as the list [1,2,3] or the boolean "true", fit into a category-theoretic definition of Haskell?  (I realize that lists, as monads, are presumably different in any category theoretical representation than booleans, which could be described as a coproduct, but I don't understand how the actual values in either case are related to the definition of Hask).

At the level of precision used in the nlab page, values are global elements -- i.e., a value of type $A$ corresponds to a morphism $1 \to A$.

If you want to be serious about this, there are some technicalities to account for:

First, actual Haskell does not actually form a category in the sense that we would hope -- the seq operator breaks a lot of the program equivalences we need. However, if it were removed, then the pure fragment of Haskell would form a category (basically corresponding to the category of domains and continuous functions).
However, global elements in "Hask" (how I hate this terminology!) are not precisely values, since the nonterminating computation is an inhabitant of every type, and so for every type $A$ there is a map $\mathsf{loop}_A : 1 \to A$ which just runs forever.

If you want to distinguish between values and nonterminating computations, then you need a somewhat more complicated setup, corresponding to the models of Paul Blain Levy's call-by-push-value.

There, you work with two categories -- one, a category of values, and the other, a category of computations, with an adjunction which gives you two functors, one embedding values into computations and the other embedding computations into values.


Is This Scheduling Problem NP-Hard? The scheduling problem (arising from distributed computing) is defined as a decision problem as follows:

Instance:

  A trace is comprised of $n$ processes histories (denoted $p_0, p_1, \ldots, p_{n-1}$), each of which consisting of a finite sequence of Read and Write operations on multiple shared variables in program order.

  An important restriction here is that all the Read operations are on the process $p_0$.

Example:

   The above figure gives a trace example. Here, $W$ is for Write operation, and $R$ is for Read operation. $Wx1$ means updating the shared variable $x$ to 1. $Ry3$ means reading the shared variable $y$ and returning 3.

Problem:

  Is there some schedule (i.e., a sequence) of all the operations such that:

  the program order between operations is maintained;
  in the schedule, each Read should read the value from the latest preceding Write on the same variable.

Example (Cont.):

  For example, the trace in the above figure can be scheduled as follows:
  $$Wx1(p_1), Wx1(p_0), Rx1, Wx2(p_1), Wy3, Ry3, Wx2(p_0), Wx1(p_3), Rx1.$$

Now, I want to study the complexity issue of this decision problem. Specifically, is this decision problem NP-hard?

This is a possible reduction from 3-partition which is strongly NP-complete.

Given a set $A = \{a_1,a_2,...,a_{3m}\}$ of $3m$ positibe integers, and a target sum $B$.

The basic idea is simple: if we found a read sequence like $Rx1\; Rx2\; Rx1$, even if the last write of $x$ before the sequence was a $Wx2$, the first $Rx1$ forces to "use" another $Wx2$ to satisfy the $Rx2$ in the middle.

We represent each $a_i$ with a unary chain $P_{a_i}$ made of $a_i+2$ write operations: the first operation is a $Wx2$ (green boxes in the figure), followed by $a_i$ write operations $Wy2$ (gray boxes), followed by a single $Wz2$ (blue boxes) write operation.

We add three auxiliary chains $P_{c_1}, P_{c_2}, P_{c_3}$. $P_{c_1}$ made with $4m$ write operations $Wx1$, $P_{c_2}$ made with $B \cdot m = \sum_{i=1}^{3m} a_i$ write operations $Wy1$,  $P_{c_3}$ made with $4m$ write operations $Wz1$.

Now we build the chain $P_0$ made only with read operations in the following way:
concatenate $m$ slot subsequences; each slot subsequence is made with:

a leading open sequence $Rx1\; Rx2\;  Rx1\;  Rx2\;  Rx1\;  Rx2\;  Rx1$, that forces to pop three operations $Wx2$ from three distinct $P_{a_i}$ and open those chains;
followed by a sum sequence $Ry1\; Ry2$ repeated $B$ times, that forces to pop $B$ operations $Ry2$ from the chains that are currently open;
followed by a trailing close sequence $Rz1\; Rz2\;  Rz1\;  Rz2\;  Rz1\;  Rz2\;  Rz1$, that forces to pop three operations $Wz2$ from the end of the chains that are currently opened.

Note that if a chain is opened and some $Wy2$ are still there and in order to complete the current close sequence  we pop them  (without a corresponding $Ry2$) to reach the final $Wz2$, in one of the next slot subsequences there will be not enough $Wy2$ to reach the close sequence. And if we are in the middle of a sum sequence and we need a $Wy2$ but we've already reached the end of all the currently opened $a_i$ chains, we cannot open another chain to recover a $Wy2$ to complete the sum sequence, otherwise in one of the next slot subsequences there will be not enough $Wx2$ to complete an open sequence.

The figure represents the instance: $A = \{ 3,3,2,2,2,2 \}$, $m=2$, $B=7$ (note that every $a_i$ should be between $B/4$ and $B/2$ to force exactly three elements in each slot sequence)

NOTE: as noted in the comments, the trailing $Rx1$ (resp. $Rz1$) of the open (resp. close) sequences are unuseful and they can be removed (and $P_{c1}, P_{c3}$ shortened to $3m$ elements).


Regular languages from category-theoretical point of view I noticed that regular languages over the alphabet $\Sigma$ can be naturally thought of as a poset, and indeed a lattice. Moreover, concatenation together with the empty language $\epsilon$ defines a strict monoidal structure on this category that is distributive over joins (I'm not sure about meets). Is this a useful construct in theory or practice of regular languages? Are there some nice adjunctions to be found, e.g. can we define the Kleene star as one?

This is a copy of a question asked at the Compilers course at Coursera:
https://class.coursera.org/compilers/forum/thread?thread_id=311

There has been a lot done applying category theory to regular languages and automata. One starting point is the recent papers:

Bialgebraic Review of Deterministic Automata, Regular Expressions and Languages
by Bart Jacobs
A Bialgebraic Approach to Automata and Formal Language Theory by James Worthington.

In the first of these papers, the structure of regular expressions is treated algebraically and the languages generated are dealt with coalgebraically. These two views are integrated in a bialgebraic setting.  A bialgebra is an algebra-coalgebra pair with a suitable distributive law capturing the interplay between the syntactic terms (the regular expressions) and the computational behaviour (languages generated). The basis of this paper is algebra and coalgebra, as treated in computer science under the umbrellas of universal algebra and coalgebra, rather than what one sees in mathematics (groups etc).

The second paper uses techniques that come from the more traditional mathematical treatment of algebra (modules etc) and coalgebra, but I'm afraid that I don't know the details.

Neither treats Kleene star as an adjunction, as far as I can tell.

More generally, there is a lot of work applying category theory to automata instead of regular expressions. A sample of this work includes:

Bloom S.L.; Sabadini N.; Walters R.F.C. Matrices, Machines and Behaviors. Applied Categorical Structures, Volume 4, Number 4, December 1996 , pp. 343-360(18)
Michael A. Arbib, Ernest G. Manes: A categorist's view of automata and systems. Category Theory Applied to Computation and Control 1974: 51-64
M.A. Arbib and E.G. Manes. Adjoint machines, state-behaviour machines, and
duality. Journal of Pure and Applied Algebra, 6:313-344, 1975.
M.A. Arbib and E.G. Manes. Machines in a category. Journal of Pure and Applied
Algebra, 19:9-20, 1980.
Jirí Adámek and Vera Trnková's book  Automata and Algebras in Categories, as pointed out in a comment.

Finally, there's the work on iteration theories, Iteration theories: the equational logic of iterative processes by Stephen L. Bloom and Zoltán Ésik, which focusses on iteration (e.g., Kleene star), but from a more general perspective, where regular languages are just one thing that falls under the theory.


Weak incidence colouring Let $G(V,E)$ be a simple undirected graph, let $k\in \mathbb{N}$, and let $I(G)=\{(v,e)\ :\ e\in E, v\in e \}$ (here, $v\in e$ means $v$ is incident on $e$). A $k$-incidence colouring of $G$ is a function $c:I(G)\to \{1,2,\dots,k\}$ such that the following hold for all $u,v\in V$ and $e,f\in E$ :
(i) $c(\,(v,e)\,)\neq c(\,(v,f)\,)$,
(ii) $c(\,(u,e)\,)\neq c(\,(v,e)\,)$, and
(iii) if $e=\{u,v\}$, then $c(\,(u,e)\,)\neq c(\,(v,f)\,)$.
I am interested in the weak variant where we drop condition (iii). Let us call it weak incidence colouring. That is, a $k$-weak incidence colouring of $G$ is a function $c:I(G)\to \{1,2,\dots,k\}$ such that $c(\,(v,e)\,)\neq c(\,(v,f)\,)$,  and $c(\,(u,e)\,)\neq c(\,(v,e)\,)$ for all $u,v\in V$ and $e,f\in E$. This seems to be a very natural relaxation to me.
I couldn't find any paper that study weak incidence colouring.
Is this because this is equivalent to some known notion?
We know that incidence colouring has several equivalent characterizations, for instance, in terms of strong edge colouring (or directed star arboricity). See "Links with other notions" in The Incidence Coloring Page maintained by Éric Sopena.
If it matters, I am particularly interested in the complexity of $k$-weak incidence colouring of $k$-regular graphs. Thank you, in advance.

I don't know if this problem has another name, but it seems like it's easy to solve.
We first see that a weak incidence coloring of a graph $G$ corresponds to an edge coloring of the graph $G'$ obtained by subdividing each edge of $G$ once. This, in turn, corresponds to a vertex coloring of $L(G')$, the line graph of $G'$. This line graph consists of a collection of cliques, one for each vertex in the original graph $G$. Each vertex in each clique is adjacent to one and only one vertex in another clique.
Now, it is not hard to prove that $L(G')$ is a perfect graph by the strong perfect graph theorem (neither $L(G')$ or $\overline{L(G')}$ have any long odd cycles). This implies that the chromatic number of $L(G')$ is equal to the size of the largest clique in $L(G')$, which in turn implies that the weak incidence coloring number of $G$ is equal to $\Delta(G)$.


Space complexity of Coppersmith–Winograd algorithm Coppersmith–Winograd algorithm is the asymptotically fastest known algorithm for multiplying two $n \times n$ square matrices. The running time of their algorithm is $O(n^{2.376})$  which is the best known so far. What is the space complexity of this algorithm ? Is it in $\Theta(n^2)$ ?

Yes, all algorithms which stem from Strassen's original algorithm (this includes most known $n^{3-\varepsilon}$ algorithms for matrix multiplication, but not all -- see the comments) have space complexity $\Theta(n^2)$. If you could find a $n^{3-\varepsilon}$ time algorithm with $poly(\log n)$ space complexity, this would be a great advance. One application would be a $2^{(1-\varepsilon)n}$ time, $poly(n)$ space algorithm for the Subset-Sum problem.

However there are some obstacles to such a result. For some computational models, there are fairly strong lower bounds for the time-space product of matrix multiplication. References like Yesha and Abrahamson will give you more information.


Comparing Two Algorithms for 3SUM problem over Integers The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the

3SUM problem: given a list $L$ of $n$ integers if there are $x,y,z \in L$ such that $x+y=z.$

They state, "On a standard word RAM with $w-$bit words, we obtain a running time of
$O(n^2/ \max\{w \log w, \log n (\log \log n)^2 \})$. In the circuit RAM with one nonstandard $AC0$ operation, we obtain $O(n^2/ w^2 \log w)$. In external memory, we achieve $O(n^2/(MB))$, even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of $O(n^2/ MB \log M )$. In all cases, our speedup is almost quadratic in the “parallelism” the model can aﬀord, which may be the best possible. See the Baran, Demaine, Patrascu paper here.

Recently, a paper "Threesomes, Degenerates, and Love Triangles" by Grondlund and Pettie has proved that "the decision tree complexity of 3SUM is $O(n^{3/2}\sqrt{\log n})$,  and that there is a randomized 3SUM algorithm running in $O(n^2(\log \log n)^2/\log n)$ time, and a deterministic algorithm running in $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ time.

These results refute the strongest version of the 3SUM conjecture, namely that its decision tree (and algorithmic) complexity is $Ω(n^2)$."

See this second paper here.

Clearly, both are important papers. Not being an expert to this area, my question is about how to compare the impact and significance of either, given the different complexity models. Any other insightful comments about this problem is also welcome. For example had the first paper already ruled out the $\Omega(n^2)$ bound?

The first paper essentially gives a subquadratic algorithm if we know that every input number has $w$ bits and we can add two $w$ bit numbers in one step. This was not a very surprising result and it did not rule out an $\Omega(n^2)$ bound.

The second paper does not use any such assumptions and improves the exponent of $n$ for decision trees, which is a surprise, although not as big as it would be for all algorithms, for which they have only improved slightly (thus disproving the strongest conjecture). I would guess that more results will follow shortly.


Algorithms for online clique detection Are there any algorithms which let you detect cliques when adding/deleting edges based on previously detected cliques? What would be the time/memory complexity of this approach?

First of all I think you mean a maximum clique, not all cliques (and even not maximal cliques). As otherwise e.g in $K_n$ there are $2^n−1$ cliques.

If the question is the one that I said, then there is no polynomial time online algorithm for update (unless P=NP). If there is such an algorithm $A$, given a graph $G$, we can find a maximum clique of $G$ in polynomial time. Just start from a graph on $n$ vertex without any edge and add edges of $G$ one by one and update information in each step by $A$. After adding all edges we have a maximum clique. Note that if we use exponential memory at some steps we can do this, but to write on exponential memory we need exponential time as well.

Maybe there are some heuristics.


Reducing space usage of st-connectivity with multiple passes? Suppose a graph $G$ with $n$ vertices is presented as a stream of $m$ edges, but multiple passes are allowed over the stream.

Monika Rauch Henzinger, Prabhakar Raghavan, and Sridar
Rajagopalan observed that $\Omega(n/k)$ space is necessary to determine whether there is a path between two given vertices in $G$, if $k$ passes are allowed over the data.  (See also the technical report version.)  However, they do not provide an algorithm to actually achieve this bound.  I assume that an optimal algorithm would actually take $O((n\, \log\, n)/k)$ space in a realistic computing model, since one has to distinguish the $n$ different vertices if one cannot index memory using constant size pointers.

  How can one decide graph connectivity with $k$ passes using $O((n\, \log\, n)/k)$ space?

If only one pass is allowed, the input data can be stored as a partition of the set of vertices, merging sets if an edge is seen between vertices in two different sets.  This clearly requires at most $O(n\, \log\, n)$ space.  My question is about $k > 1$: how can one use more passes to reduce the required space?

(For avoidance of triviality, $k$ is a parameter that cannot be bounded a priori by a constant, and the space bounds are expressions involving functions of both $n$ and $k$.)

Update: even for $k=2$ it would be really useful to have a way to store only $n/2$ vertices.  Or is there actually a stronger lower bound $cn$ for some constant $c$, regardless of $k$?

It is a long standing open problem to find an algorithm for st-connectivity that runs in simultaneously sub-linear space and polynomial time, an easier task that what you are aiming at.  Such algorithms are known for the un-directed version, but even these require a large polynomial time (rather than O(km) time which would be implied by a k-pass algorithm).  See especially the reference to Tompa's paper on why the directed case seems hard.


Representing non-planar graphs with overlapping circles We know that we can represent any planar graph by a set of circles in the plane, known as a coin graph. Each circle represents a vertex and there is an edge between two vertices if and only if the circles "kiss" at their boundary.

Suppose that instead we allow the circles to overlap, and represent an edge by a pair of circles that intersect in their interior? What class of graphs can we represent in this model? Clearly we can represent complete graphs (every circle intersects every other circle). Can we represent all graphs like this?

The definitive article is a paper by Hlineny and Kratochvil from 2001. In it they show that the problem of recognizing a disk intersection graph (your question) is NP-hard, which suggests that it will be difficult to come up with a clean characterization. They also point out that $K_{3,3}$ cannot be represented as the intersection of disks, answering the other part of your question.


An obstruction like ETH We know under $ETH$ we cannot solve $K$-SUM in $f(K)poly(nK)$ time under any function $f(K)$ (usually $2^{O(K)}$).

Is there any conjecture that prevents a $(\log n)^{O(K)}$ complexity (this is entirely consistent with possibility as $K=\Omega(n)$ we need exponential time for subset sum) or is such possibility allowed?

ETH itself precludes this possibility.

In https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf
 we show that any $n^{O(1)} n^{k/\alpha(k)}$ time algorithm for k-SUM, for any monotone nondecreasing unbounded function $\alpha$, would imply ETH is false.


Is meta-undecidability possible? There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc.

In this case I wonder whether a problem can be meta-undecidable. This means (at least in my head) we cannot tell whether it is decidable or not.

Maybe it's known decidability is undecidable (everything is meta-undecidable) and no algorithm exists to prove decidability for anything, so decidability has to be proven by hand on a case by case basis.

Maybe my question doesn't make sense. Maybe I'm assuming we are carbon machines running very complex algorithms and that's why the question makes sense only in my head.

Please let me know if the question needs further clarification. I may need that myself at this moment.

Thank you.

Here's a quick sketch to show that there is no Turing machine to decide whether an arbitrary class of problems is decidable.

I should clarify what I mean by class of problems: a class of problems $T$ is a Turing machine which enumerates the elements (natural numbers, say) of a recursively enumerable set one after the other, such that each element in the set is eventually printed. The problem intuitively captured by $T(n)$ is: "is the number $n$ in this set?". This captures the usual problems in the field of computability, such as "is i the index of a Turing machine that halts on empty input?".

Suppose there was machine $M$ which, given as input a class of problems $T$ answered $\mathit{true}$ if that class is decidable and $\mathit{false}$ otherwise.

Now take an arbitrary Turing machine $T$. We build the following class of problems $T'$ in the following manner:

Simulate $T$.
If $T$ halts, enumerate the indices of the Turing machines that halt on empty input.

Now it is clear that if $T$ halts, then $M(T')$ returns $\mathit{false}$, as the set of indices halting Turing machines is not a decidable (recursive) set.

If $T$ does not halt, then $T'$ does not enumerate any numbers, which makes it exactly the class of problems containing no indices! Therefore $M(T')$ answers $\mathit{true}$, since that class is decidable (by the machine that always rejects).

Therefore, $M(T')$ returns $\mathit{true}$ iff $T$ does not halt, and $\mathit{false}$ otherwise. Thus the existence of $M$ allows us to solve the halting problem for an arbitrary machine $T$, which is a contradiction.


Find the maximum subset contained by a ball of radius R I am searching for the name of / literature to the algorithmic problem as follows:

  Given a metric space $(M,d)$, a finite Subset $X = \{ x_1, \dots, x_n \} \subset M$ and a fixed Radius $R > 0$, find the maximum amount of points being enclosed by a ball of radius $R$. Alternatively, find $N$, such that
  $ N = \max_{x \in M} |X \cap B_R(x)| $

I only know of the 1-center problem so far. But this tries to solve the problem for minimizing the radius of a ball containing all points within a set. I also found one paper discussing a $\mathcal{O}(|X|^2)$ solution for the euclidean plane. There it has been called Maximum-Enclosing-Disk-Problem. Any information regarding generalizations for $\mathbb{R}^D, D > 2$ or different metrics, would be helpful.

I am not very experienced with computational geometry and the theory of algorithms, but I need to find current literature on this problem. Having a name, or a similar problem, on which this problem can be reduced, would be help me a lot. Also, if you know literature or keywords regarding approximation attempts.

Thank you for your answers.

Edit: As discussed in the comments, an arbitrary metric space might not even computable. However, as I didn't want to restrict the solution on real euclidean spaces (e.g. the space of strings provided with the edit-distance should be an option), I decided for the very general formulation of the problem.

Here is a slightly-better-than-raw-brute-force algorithm for $D$-dimensional Euclidean space. It's about as trivial as you can get with this kind of problem short of "check all subsets of points for being in a disk of radius at most $R$", but I figure it's nontrivial enough to serve as a baseline for future answers.

Suppose you have a disk that contains a collection of points, say the optimal disk that you're looking for. Unless there are points on its boundary, you can wiggle this disk around/shrink its radius to contain the exact same collection of points. Hence there can be many optimal choices of the disk. The main idea here is to focus only on disks that are easy to describe, namely those which are determined by some points on the boundary. With this restriction, we'll only need to consider a finite number of disks, and the rest of the algorithm will just be to enumerate all of these disks and count how many points each contains.

So now focus on a particular disk containing a fixed set of points. With translations, you can get one point on the boundary. We now consider some cases, which I'll outline for $D = 3$, though they generalize.

If we have exactly one point on the boundary, imagine moving the center of the disk toward that boundary point and shrinking the radius so that the boundary point stays on the boundary. As we do this, one of two things happens: either the radius gets to zero without any other points crossing the boundary (in which case the disk contained only a single point in the first place), or else some other point enters the boundary.
If we have exactly two points on the boundary, this forces the center to lie in the plane of points equidistant to the two points on the boundary. Now imagine moving the center toward the midpoint of the two boundary points, and adjusting the radius accordingly. One of two things happens: the center reaches the midpoint of the two boundary points without any additional points crossing the boundary, or else some point enters the boundary. In the first case, we have two antipodal points on the sphere (which determines the disk); in the second case, we now have a collection of three (non-colinear) points on the boundary.
There are three non-colinear points on the boundary, but every collection of four or more is coplanar. Consider the plane defined by the boundary points, and draw the circle defined by them within this plane. This circle is included in the boundary of the disk, and moreover the center of the disk must lie on the line perpendicular to the plane running through the center of the circle. Consider moving the center of the sphere along this line, toward the center of the circle, and adjusting the radius accordingly. One of two things happens: either the center of the disk reaches the center of the circle without any points crossing the boundary, or else a new point (not on the plane defined by the initial boundary points) enters the boundary. In the first case, we have some three non-colinear points on a greater circle on the disk (which determines the disk); in the second case, we have at least four non-coplanar points on the boundary.
Finally, the case where we have at least four non-coplanar points on the boundary. Here (in $D = 3$), this completely determines the disk.

It follows that you can enumerate every collection of $1, 2, \ldots, D+1$ points, compute the appropriate disk, check that its radius is at most $R$, and then count the number of points in it. You can compute the disk in time $O(D)$ in each case, and you can naively count the points inside the sphere in $O(n\cdot D)$ time. This gives an overall time of $O(D\cdot n^{D+2})$.

If you know some more information about what your input looks like, there are very likely to be some heuristic optimizations you can put on top of this algorithm. A simple example is ignoring any collection containing two points with distance greater than $2\cdot R$.


(eps,delta)-approx with VC-Dimension 1? I have a domain $X$ and a set system $R$ on $X$, such that the sets in $R$ are one included in the other, that is, for any $A,B\in R$, either $A\subseteq B$ or $B\subseteq A$. The sets are not all equal: there is at least a pair of sets $A,B\in R$ such that $A\subsetneq B$ The VC-dimension for this set is therefore 1.

I seem to recall that the usual random sampling theorem to obtain an $(\varepsilon,\delta)$ approximation of the sizes of all the sets in $R$ can be used only if the range space has VC-dimension at least 2, but now I cannot find this explicitly stated anywhere. Could anyone please tell me whether I am just remembering it wrong and the theorem can be used for range spaces of any VC-dimension?

If not, are there other techniques I can use or do I have to resort to Chernoff+union bounds?

So the answer is yes, as pointed out by in one comment with reference to the original paper.


Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps? Can regular maps, no matter their complexity, be topologically transformed into circular maps or rectangular maps?

For rectangular maps, for example, I intend maps that are made from overlapping rectangular faces as shown here: Rectangular and circular maps.
And here is the proof.

I don't know if this is a new result or not (I did not find it on internet) and I don't even know if this may be useful to help finding a "pencil and paper", elegant and human checkable proof for the four color problem.

What is known about this? Has it been studied before?

Your "proof" is too vague to convince me, but here's a description of how these maps can be formed. Given a 3-regular 3-connected planar graph, its dual is a maximal planar graph. Every maximal planar graph has a canonical ordering (see references in my earlier comment): an ordering on the vertices of the graph such that the following properties hold:

The first three vertices in the ordering are adjacent
Each prefix of three or more vertices in the ordering defines a subset of the vertices whose boundary is a simple cycle
Each vertex after the first three has as its neighbors a contiguous path of the boundary cycle of the previous vertices

This should allow you to define your rectangular drawing top down. Find a canonical ordering of the dual graph, and make side-by-side rectangles for the first two dual vertices in the canonical ordering (corresponding to two adjacent faces in your graph). Then, add rectangles one by one in the given ordering, below these first two rectangles. For each successive rectangle r, corresponding to a dual vertex v, choose the top vertices on the left and right sides of r to be points on the rectangles corresponding to the endpoints of the contiguous path of neighbors of v from the canonical ordering.

The invariant that makes this work, at each step, is that the boundary cycle of the canonical ordering is exactly the same as the sequence of rectangles that you would see if you stood underneath your drawing and looked upwards.

The circular map should be exactly the same, just starting at the outside and working inwards.

As for the other questions at the end of your post: is this interesting? I don't know. There's some related work in the graph drawing community on representing maps by regions with rectilinear boundaries; the phrase to search for is "rectilinear cartogram". You'd have to show some concrete advantage of your method over previous rectilinear cartogram construction methods such as the one in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.6582&rep=rep1&type=pdf — but suggesting ways to achieve this is probably beyond the scope of this exchange.


Counting length-k increasing subsequences in a permutation (Originally posted on Math.SE.)

Let $f$ be a permutation on $n$ letters. I want to count the number of $k$-long increasing subsequences quickly.

One approach is to first use divide and conquer to split the problem into finding increasing subsequences in pairs of numbers. The resulting 'tree' then has height $\log n$. I'm wondering how the subproblems could be combined in an efficient way. I thought about prefix sums and using mergesort, but I can't see how to effectively implement them.

One idea to save time when combining two subproblems is to compare elements at the end of the increasing subsequences in the first subproblem with values in the second subproblem.

My goal is to get to $O(k n \log n)$ time but this doesn't do it.

According to Kim, finding one such sequence is equivalent to finding a maximum independent set in a permutation graph and can be done in $O(n\log n)$ time. The running time you're looking for suggests you already knew about that, but if not, looking at citing papers might help.

Update: actually, the complement of a permutation graph is also a permutation graph, and the complement of an independent set is a clique, so unless I'm missing something, maximising the number of increasing sequences of length $k$ in your permutation should be equivalent to partitioning a permutation graph into as many $K_k$'s as possible. Surely this has been studied, at least for triangles...


A counting subset sum problem with fixed subset size and bounded weights I am interested in the following variant of the subset sum problem:

Given a set of positive integer weights $w_1,..., w_n$, such that each $w_i$ is polynomial in $n$, and given integers $s$ and $k$, count the number of subsets of weights of cardinality exactly $s$ such that the sum of the weights in each subset is at most $k$.

I expect that there is a polynomial-time dynamic programming algorithm for this problem but don't have a reference. Can anyone please point me to the relevant reference?

Even if $s$ is not constant, a dynamic programming algorithm similar to that for the knapsack problem would work.  For this to be polynomial time, we need each $w_i$ to be polynomial in $n$ (implying that $k \leq \sum w_i$ is polynomial in n).

The idea is that $T(j,i)$ is the number of subsets of weight $j$ and cardinality $i$.  Start with all $T(j,i) = 0$ except $T(0,0) = 1$

Then:

For i = 1 to $n$
For j = 0 to $k$
For h = 1 to $s$
T(w_i + j,h+1) += T(j,h)

Then your answer is $\sum_{j \leq k} T(j,s)$

$s$, $n$, and $w_i$ (and therefore $k$) are all polynomial so all of this is polynomial.  Specifically this is at worst $O(n^2k)$ time.


Consequences of BPP=BQP If BPP=BQP then there is a polynomial time randomized factoring algorithm.  A lot of other quantum algorithms that appeared to have an exponential speedup have recently been dequantized. For examples, see https://arxiv.org/abs/1910.06151 and references therein.

What other significant practical consequences would BPP = BQP be likely to lead to?

Assuming a practical algorithm is found, the applications will overwhelmingly be in quantum simulation. Basically any research in large quantum systems - chemistry, biochemistry, condensed matter, nuclear systems will be affected. We'd likely see major advances in basic biology, medicine and pharmaceuticals. Moore's law would be restored for a few years and we would finally have working fusion reactors. Physical simulation using the new algorithm might also lead to new physics.


The asymptotic behavior of a recurrence related to stable matchings I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows:

$$a_1 = 1, a_2 = 2$$
$$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$

Apparently, Knuth was able to prove that the sequence grows at least like $2.28^n$. Unfortunately, any hint of the proof seems to be lost or never published, as all reference cite "personal communication". I'd like to know the rationale.

While I don't need to know the sequence exactly, lower order terms have some importance. For example, the difference between a growth rate of  $n^{\Omega(1)} c^n$ verses $c^n / n^{\Omega(1)}$ would be significant (although I think I have a proof sketch that the first case is impossible, it would be nice to check).
I'm also interested in the initial conditions $a_1=2, a_2=7$.

So far, I've mostly just tried playing around the with generating function of the sequence, but I haven't gotten anywhere. A reference for applying generating function techniques to recurrence problems involving squares etc. of previous terms would be appreciated! I'm not sure what other techniques would be useful.

Background: [1] introduced a family of stable marriage instances which provide the best known lower bounds for the maximum number of stable matchings possible for some problem instance. [2] is the first source I could find to mention the number $2.28$. [3] generalizes the family created in [1] somewhat but doesn't do better than $2.28^n$.

[1] Irving, Robert W., and Paul Leather. "The complexity of counting stable marriages." SIAM Journal on Computing 15.3 (1986): 655-667.

[2] Pittel, Boris. “On Likely Solutions of a Stable Marriage Problem.” The Annals of Applied Probability, vol. 2, no. 2, 1992, pp. 358–401. JSTOR, www.jstor.org/stable/2959755.

[3] Edward G Thurber. Concerning the maximum number of stable matchings in the stable marriage problem.Discrete Mathematics, 248(1-3):195–219, 2002.

Solution

I wrote up Professor Shor's solution here!

Here is a proof. Parts of the proof involve some real analysis; I've sketched the details in an appendix, and if you know real analysis, you should be able to fill in the details fairly easily.

First, let's notice that for $b_n=a_{2^n}$, we have the recurrence

$$b_n = 3b_{n-1}^2 - 2b_{n-2}^4.$$

Now, let's assume that $b_n = r s^{2^n}$. The equation becomes

$$r s^{2^n} = 3 r^2 s^{2^n} - 2 r^4 s^{2^n},$$

and $s^{2^n}$ factors out. Solving the equation $r = 3r^2 - 2r^4$, we find two positive roots,  $r = 0.366 = \frac{1}{2}(\sqrt{3}-1)$ and $r= 1$. Let $r_0$ be the smaller of these roots.

Suppose we could show that $\frac{b_{n-1}^2}{b_n} = r_0$. Then we can show by induction that $b_n=r_0 s^{2^n}$ for some value of $s$. Suppose this is true for some value $n$. Then
\begin{align}
b_{n+1} &= \frac{b_{n}^2}{r_0} = \frac{\left(r_0 s^{2^n}\right)^2}{r_0} = r_0 s^{2^{n+1}}.
\end{align}

In fact, we won't quite show this; what we will show is that $\frac{b_{n-1}^2}{b_n}$ goes to $r_0$ as $n$ goes to $\infty$. With some analysis (given in an appendix), we can complete the proof that $b \approx r_0 s^{2^n}$ for some value of $s$. The actual value of $s$ depends on the initial conditions, and the only way I know to get it is computationally. Maple seems to say that $s$ is around 2.280142. If you start with $a_1=2$, $a_2=7$, Maple gives $s \approx $ 4.189425.

Why does $\frac{b_{n-1}^2}{b_n}$ go to $r_0$? Take the recurrence, and divide $b_{n-1}^2$ by both sides. This gives

$$ \frac{b_{n-1}^2}{b_n} = \frac{1}{3-2\left(\frac{b_{n-2}^2}{b_{n-1}}\right)^2},$$
or, letting $t_n = b_{n-1}^2/b_n$,
$$t_n=\frac{1}{3-2 t_{n-1}^2}.$$
This has three fixed points, but the only attractive point is $r_0$, and $t_n$ approaches this point from any initial value except the two other fixed points.

Appendix:

Here is a sketch of the argument that if $\lim_{n\rightarrow \infty} t_n = r_0$, then $s$ exists. We'll consider an approximation to $s$ based on $b_n$. Let
$$s_n = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}.$$
Then
$$\frac{s_n}{s_{n-1}} = \left(\frac{b_n}{r_0}\right)^{\frac{1}{2^n}}\left(\frac{r_0}{b_{n-1}}\right)^{\frac{2}{2^{n}}}
= \left( \frac{b_nr_0}{b_{n-1}^2}\right)^{\frac{1}{2^n}}
= \left( \frac{r_0}{t_n}\right)^{\frac{1}{2^{n}}} .
$$
If $\lim_{n \rightarrow \infty} t_n = r_0$, this equation implies that $$ \prod_{m=n}^\infty \frac{s_{m+1}}{s_m} \rightarrow 1 \quad \mathrm{as} \quad n \rightarrow \infty,$$ and thus that $s =\lim_{n\rightarrow \infty} s_n $ exists.

But in order to show that $b_n$ grows like $r_0 s^{2^n}$ as $n \rightarrow \infty$, you need not just that $s_n$ converges, but that it converges quickly. The exponent on $\frac{r_0}{t_n}$ above takes care of that. What we would like to show is that
$$\lim_{n\rightarrow\infty} \frac{s^{2^n}}{s_n^{2^n}} = 1.$$

But
$$
 \frac{s^{2^n}}{s_n^{2^n}}
= \prod_{m=n}^{\infty} \left(\frac{s_{m+1}}{s_m}\right)^{2^{n}}
= \prod_{m=n}^{\infty} \left(\frac{r_0}{t_{m+1}}\right)^{\frac{1}{2^{m+1}}2^{n}} \approx \left(\frac{r_0}{t_{n}}\right)^{2^n\left(\sum\limits_{m=n}^\infty \frac{1}{2^{m+1}}\right)}= \frac{r_0}{t_n},$$
which goes to $1$ as $n \rightarrow \infty$.


Complexity of Topological Properties. I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description of a space (by simplices) for topological properties; those preserved up to homeomorphism.

It is known, for example, that determining the genus of a knot is in PSPACE and is NP-Hard. (Agol 2006; Hass, Lagarias, Pippenger 1999)

Other results have more a more general feel: A. A. Markov (the son of the Markov) showed in 1958 that testing two spaces for a homeomorphism in dimensions $5$ or higher is undecidable (by showing the undecidability for 4-manifolds). Unfortunately, this last example is not a perfect exemplar of my question, as it deals with the homeomorphy problem itself rather than properties preserved under homeomorphism.

There seems to be a large amount of work in "low dimensional topology": knot and graph theory. I am definitely interested in results from low dimensional topology, but am more interested in generalized results (these seem to be rare).

I am most interested in problems which are NP-Hard on average, but feel encouraged to list problems not known to be so.

  What results are known about the computational complexity of topological properties?

Computational topology encompasses an enormous body of research.  A complete summary of every complexity result would be impossible.  But to give you a small taste, let me expand on your example.

In 1911, Max Dehn posed the word problem for finitely presented groups: Given a string over the generator alphabet, does it represent the identity element?  One year later, Dehn described an algorithm for the word problem in fundamental groups of orientable surfaces; equivalently, Dehn described how to decide whether a given cycle on a given orientable surface is contractible.  Properly implemented, Dehn's algorithm runs in $O(n)$ time.  In the same 1912 paper, Dehn opined that “Solving the word problem for all groups may be as impossible as solving all mathematical problems.”

In 1950, Turing proved that the word problem in finitely presented semigroups is undecidable, by reduction from the halting problem (surprise, surprise).

Building on Turing's result, Markov proved in 1951 that every nontrivial property of finitely-presented semigroups is undecidable.  A property of groups is nontrivial if some group has the property and some other group does not.  Theoretical computer scientists know the similar result about partial functions as "Rice's Theorem".

In 1952, Novikov proved that the word problem in finitely presented groups is undecidable, thereby proving that Dehn's intuition was correct.  The same result was independently proved by Boone in 1954 and Britton in 1958.

In 1955, Adyan proved that every nontrivial property of finitely-presented groups is undecidable.  The same result was proved independently by Rabin in 1956.  (Yes, that Rabin.)

Finally, in 1958, Markov described algorithms to construct 2-dimensional cell complexes and 4-dimensional manifolds with any desired fundamental group, given the group presentation as input.  This result immediately implied that a huge number of topological problems are undecidable, including the following:

Is a given cycle in a given 2-dimensional complex contractible? (This is the word problem.)
Is a given 2-complex simply connected?  ("Is this group trivial?")
Is a given cycle in a given 4-manifold contractible?
Is a given 4-manifold contractible?
Is a given 4-manifold homeomorphic to a particular 4-manifold (constructed by Markov)?
Is a given 5-manifold homeomorphic to the 5-sphere (or any other fixed 5-manifold you choose)?
Is a given 6-complex a manifold?

My favorite corollary of these results is more recent and more subtle: It is undecidable whether a given finitely-presented group is the fundamental group of a 3-manifold.  Perelman's recent proof of Thurston's geometrization conjecture implies the existence of an algorithm to determine whether a given 3-manifold has a trivial fundamental group.  (As @SamNead points out, results of Rubenstein and Casson imply an algorithm that runs in exponential time.)  If a given group $G$ is not a 3-manifold group, then $G$ cannot be trivial, because $\pi_1(S^3)$ is trivial.  Thus, if you could decide whether $G$ is a 3-manifold group, you could decide whether $G$ is trivial, which is impossible.


Bipartite graph projections, with threshold Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked together if they have a common neighbor in $G$.
Weighted projections are defined by adding the following weight function: $\omega(u,v)$ is the number of common neighbors of $u$ and $v$ in $G$.
For any $k$, the $k$-projections $G^k_\bot = (\bot,E^k_\bot)$ and $G^k_\top = (\top,E^k_\top)$ are defined as follows: two vertices are linked together if they have at least $k$ common neighbors in $G$.
Assume that both $G$, $G_{\bot}$, and $G_{\top}$ are sparse.
Questions:

What is the (time and space) complexity of building $G_\bot$ and $G_\top$?
Is it possible to build their weighted version with same complexity?
Is there a significantly better way to build $G^k_\bot$ and $G^k_\top$ than first building weighted $G_\bot$ and $G_\top$ and then removing the edges of weight lower than $k$?

These questions are important in social network analysis and related fields. For instance, many studies consider co-authorship networks: $G$ is graph where authors are linked to papers, and $G^k_{\bot}$ is the graph of authors who co-signed at least $k$ papers.

My two cents:

The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$.
Maybe you are not looking for a worst case complexity? Then, $O(\sum_{u\in\bot}(d_u)^2)$ time to build $G_\top$ by listing all edges $u,v$ such that $u$ and $v$ are neighbors of the same node in $\bot$.
You can use some pruning in the case $k$ is large with the following algorithm. For each node $u\in \top$ such that its degree is $k$ or more: For each neighbor $v$ of $u$: For each neighbor $w$ of $v$ such that $w>u$: List the edge $u,w$. Then postprocess the listed edges to find the ones that appear $k$ times or more. Here is a code that does something like that efficiently.
Some related code here for simple graphs (not bipartite, but can be adapted) where we look for pairs of nodes with Jaccard similarity higher than a threshold. It seems that Jaccard allows to leverage a more aggressive pruning: only a pair of nodes $u,v$ such that $\frac{\min(d_u,d_v)}{\max(d_u,d_v)}>\alpha$ can have a Jaccard similarity higher than $\alpha$.


Analogue of $k$-wise independence for other distributions than uniform I am looking for the name of the following notion (in order to look it up for myself), and possibly pointers to the corresponding literature.

Let $D$ be a fixed distribution over $\{0,1\}^n$, and $1\leq k\leq n$ a fixed integer. A random variable $X$ over $\{0,1\}^n$ is said to be $(k,D)$-something if all size-$\ell$ marginals of $X$, for $\ell\leq k$, match those of $D$.

In particular, for $D$ product distribution (and, in most derandomization literature I have seen, actually for $D$ uniform), this is $k$-wise independence. I am looking for $D$ non-uniform, however -- for instance, $D$ being the distribution of the $n$ bits indicators obtained when choosing a subset of $[n]$ of size exactly $n/2$.

  Does something have a name?

I met once a similar notion to what you want in one paper by Mark Zhandry's paper under the name $k$-wise equivalent. I cannot find further references or pointers from that paper, but I think this name nicely describes your something.
Concretely, the original definition in the paper is about the distributions over the functions $f: X\rightarrow Y$, and define the size-$k$ marginal by its marginal distribution for any size-$k$ subset $W$ of $X$. The notion $k$-wise equivalence is defined accordingly, that is, two distributions are identical on any $k$-marginal.
It is not directly addressing your main question, but we can say that your desired distribution is $k$-wise equivalent to the uniform random permutation. It also, unfortunately, does not give any efficient construction for equivalent distribution as well.


Do all complexity classes have a leaf language characterization? Leaf languages are a beautiful way to uniformly define many complexity classes. Most complexity classes are usually specified by a model of computation (e.g., deterministic/randomized TM), and a resource bound (log time, poly space, etc.). However in the leaf language formulation, there is only one model of computation, and the class is specified by giving its leaf language.

The details are too long to explain, so I'll direct interested readers to either of these two surveys:

Uniform characterizations of complexity classes by H Vollmer
Leaf Language Classes by KW Wagner

Both surveys do a great job of explaining the formulation within the first few pages.

In Wagner's survey, he says "it turns out that practically every complexity class considered so far can be described by leaf languages."

My question relates to this statement. I know there are some classes for which we do not know a leaf language characterization, so this means either the classes don't necessarily have such a characterization, or we haven't found it.

Do we expect every complexity class (say between P and PSPACE) to have a leaf language characterization? (Let's restrict ourselves to "natural" complexity classes.) Is there any result of this sort in the literature?

(A related question that I'd be happy to know the answer to: Is there a (heuristic) method to come up with a leaf language for a given class?)

EDIT: Suresh points out that there is a short definition of leaf languages in the Wikipedia article. I'm copying it below.

Several complexity classes are typically defined in terms of a polynomial-time nondeterministic Turing machine, where each branch can either accept or reject, and the entire machine accepts or rejects as some function of the branches' conditions. For example, a non-deterministic Turing machine accepts if at least one branch accepts, and rejects only if all branches reject. A co-non-deterministic Turing machine, on the other hand, accepts only if all branches accept, and rejects if any branch rejects. Many classes can be defined in this fashion.

Have a look at

  Bernd Borchert, Riccardo Silvestri: A Characterization of the Leaf Language Classes. Inf. Process. Lett. 63(3): 153-158 (1997) (doi link here)

The authors characterize the leaf language classes as those which are (a) "countable", (b) are "downward" closed wrt polytime many-one reducibility, and (c) "join-closed" (i.e., disjoint union) wrt polytime many-one reducibility.

More formally, all the languages $L$ in a leaf language class have a bijection with the natural numbers, and the property that for every $C,D \in L$, if $E \leq^P_m C \sqcup D$ then $E \in L$ as well (the $\sqcup$ denotes disjoint union). Also, every "non-leaf language class" contains a language which fails to have one of these properties.

From these three conditions we can get many examples of classes which aren't leaf language classes. For example, the "countable" condition rules out advice classes like $P/poly$, and the "downward closed wrt polytime many-one reducibility" rules out fixed resource-bound classes like $SPACE[n]$. (Recall that the usual proof that $SPACE[n] \neq P$ uses the fact that $SPACE[n]$ is not closed under such reductions.)


Is there a mathematical analysis/proof available for correctness of solutions to inter process communication problems? I've been going over some material related to IPC recently from Tanenbaum's "Modern Operating Systems" and revisited semaphore after many years. There is a lot of code and pseudo code based explanations and solutions to classic IPC problems like dining philosophers etc and scenario based deadlock situations.

However, I didn't come across any reference to proving the correctness of those solutions. I had a look at Dijkstra's original paper (following a link on Wikipedia reference section). I did a quick run through and found the explanations to be more code and pseudo code based that mathematically rigorous. The google results at best give simulation cases, which are again code based.

My question is as the title says: Are there any mathematically rigorous analyses and proofs about the correctness of the solutions to the IPC problems available, freely (without membership to access information)?

There has been various brand of work for formalizing such tricky code. The one I know about are (but I'm no expert on the topic):

using "temporal logic" to study distributed systems; one important tool beeing the TLA+ tool is a program that verifies properties of specifications expressed in temporal logic; googling for "TLA+ dining philosopher" links to this 2007 PhD thesis (PDF) that has a TLA specification of the dining philosophers on page 24
using "concurrent separation logic" to verify implementation of concurrent programs, including rather low-level primitives. See for example the 2014 paper GPS: Navigating Weak Memory with Ghosts, Protocols, and Separation by  Aaron Turon, Viktor Vafeiadis and Derek Dreyer has correctness proofs for lock-free queues, circular buffers and "ticket locks", implemented in C using the C11 atomic concurrency pri


Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$.

A bitstring $B$ is generated by drawing 0s and 1s from a uniform distribution and is of length $n=\ell(B)$.

Kolmogorov complexity for a bitstring $B$ is the length of the shortest program $B^*$ that generates $B$, $K(B) = \ell(B^*)$.

A typical $B$ is difficult to define precisely.  Intuitively, it is the sort of bitstring that will be generated most of the time by randomly drawing 0s and 1s.  However, the concept can be clarified by examining properties.  A property $p$ applies to typical $B$s if the proportion of $B$s having that property approaches 1 as $\ell(B)$ is increased,
\begin{align*}
\underset{n\rightarrow \infty}{\lim} \frac{|\{B: p(B) \wedge \ell(B) \leq n\}|}{|\{B: \ell(B) \leq n\}|} \rightarrow 1.
\end{align*}

For instance, a typical $B$ has the property that $K(B) = \ell(B)$.  In other words, a typical $B$ is not compressible.  Note: this is not a sufficient condition for typicality.  It is possible for a $B$ to be atypical and incompressible.

There are atypical $B$s that can be compressed, and for these $K(B) < \ell(B)$.

Conditional Kolmogorov complexity, $K(B_2|B_1)$, is the length of the shortest program that generates $B_2$ when given $B_1$ as input.

Algorithmic mutual information is $I(B_1:B_2) = K(B_2) - K(B_2|B_1^*) = K(B_1) - K(B_1| B_2^*)$.  This expression is accurate to within a constant independent of $B_1$ and $B_2$.

A Kolmogorov structure function for a bitstring $B$ is the set generating program $P_B$ such that $B$ is in the set $S_B$ generated by $P_B$ when given $n$ as input.  The shortest $P_B$, such that $\ell(P_B) + \log_2(|S_B|) \leq K(B)$, is called the minimal Kolmogorov structure function, denoted by $P^*_B$.  $\log_2(|S_B|)$ is close to the "randomness" in $B$ that cannot be captured by $P^*_B$.

In the case of a typical $B$ the length of $P^*_B$ is minimal, since knowing $n$ we can enumerate all bitstrings of length $n$ with a constant size program $C$.  On the other hand, in the case of atypical $B$s, the length of $P^*_B$ may be significantly larger than $C$.

My question: is the algorithmic mutual information between a typical $B$ and a $P^*_{B'}$ for any bitstring $B'$ ever larger than $C$?  Although $\ell(B')$ is not constrained by $\ell(B)$, the $P^*_{B'}$ is provided with $n=\ell(B)$ in this case, since the goal is to generate $B$.  However, this does not mean that $B\in S_{B'}$, since $\ell(B)$ does not necessarily cause $P^*_{B'}$ to generate a set that contains $B$.

Note in the case of a typical $B$ that trivially $I(P^*_B:B)=\ell(C)$ since $\ell(P^*_B)=\ell(C)$.  However, this does not mean that there is not another $P^*_{B'}$ from an atypical $B'$ such that $K(B|P^*_{B'}) < K(B)-\ell(C)$, and thus $I(P^*_{B'}:B) > \ell(C)$.

I think the answer is always $I(B:P^*_{B'}) = \ell(C)$ for a typical $B$. If $K(P^*_{B'}|B) < K(P^*_{B'})-\ell(C)$, then part of the randomness of $B$ describes $P^*_{B'}$, so $P^*_{B'}$ is not a minimal structure function for $B'$. I don't know how to prove this formally.

To provide context for this question, I am trying to derive a law of minimal Kolmogorov sufficient statistic nongrowth, based on  Leonid Levin's conservation independence in "Randomness Conservation Inequalities;
Information and Independence in
Mathematical Theories".
Levin's law states
$I(z:y) > I(x:y)$
where $x$ is the result of applying a Turing machine $U$ to $z$, so $x=U(z)$.
I would like to similarly prove $\ell(P^*_z) > \ell(P^*_x)$, and am using $I(B:P^*_{B'})=\ell(C)$ for typical $B$ as one of the premises in my proof.

EDIT 2: Updated the answer for the updated definition of typical.

I may be misunderstanding your definition of $P^*_{B'}$.  With that caveat, though, I believe your conjecture does not hold.  The proof is in two steps.

Lemma 1. For some $c_0>0$, for all $n>0$, there are strings $B$ and $B'$ such that $K(P^*_{B'} | B) \le c_0$ and $K(P^*_{B'}) = \ell(B) \ge n$.

Proof sketch.  Let $c_0$ be the length of any universal TM. Fix any $n>0$.

Fix any string $B'$ such that $K(P^*_{B'}) \ge 2n$.  (We discuss below our assumption that $B'$ exists.)
Let $B$ be the shortest program that generates $P^*_{B'}$, so that $K(P^*_{B'}) = \ell(B)$.
And $K(P^*_{B'} | B) \le c_0$, because given input $B$, the universal TM outputs $P^*_{B'}$.

Here's the justification for Step 1.  If $B'$ does not exist, then there are only finitely many minimal Kolmogorov structure functions.  I assume this is known not to hold, because otherwise $I(B : P^*_{B'}) \le K(P^*_{B'}) = O(1)$ for all $B$ and $B'$, and the conjecture would be trivially true (for some constant, at least).  Also, the post states "On the other hand, in the case of atypical $B$s, the length of $P^*_{B}$ may be significantly larger than $C$." Perhaps someone who knows more about this topic could confirm that there are infinitely many minimal Kolmogorov structure functions. $~~\Box$

This concludes the proof sketch for Lemma 1.  Next we show that the conjecture does not hold.

Lemma 2. For any $c > 0$, there are $\epsilon>0$ and a string $B'$ such that, for all sufficiently large $n$, for a random $n$-bit string $B$, with probability at least $\epsilon$, $I(B : P^*_{B'}) \ge c$.

Proof. Fix any $c> 0$.  Assume WLOG that $c\ge c_0$ from Lemma 1, and $c + \log(c) + c_1 + c_2 \le 2c$ for fixed constants $c_1, c_2$ defined in Steps 4 and 5 below. (Otherwise just increase $c$.)

Fix strings $B_0$ and $B'$ such that $K(P^*_{B'} | B_0) \le c$ and $K(P^*_{B'}) = \ell(B_0) \ge 4c$. (These exist by Lemma 1.)
Let $\epsilon=2^{-\ell(B_0)}$.  Consider any $n\ge \ell(B_0)$ and let $B$ be a random $n$-bit string.
The event that $B_0$ is a prefix of $B$ happens with probability at least $\epsilon$.  Assume this event occurs. To complete the proof we show that $I(B:P^*_{B'}) \ge c$.
First note that $$K(P^*_{B'} | B) \le K(P^*_{B'} | B_0) + K(B_0 | B) + c_1$$ (for some fixed $c_1$) because, given $B$, we can compute $B_0$ from $B$, then compute $P^*_{B'}$ from $B_0$.
Using $K(P^*_{B'} | B_0) \le c$ (from Step 1), and $K(B_0|B)\le \log \ell(B_0) + c_2$ (for some fixed $c_2$, using a TM that truncates its input $B$ to its first $\ell(B_0)$ bytes), this implies $$K(P^*_{B'} | B) \le c + \log \ell(B_0) + c_1 + c_2 \le \ell(B_0)/2.$$
(Using above our assumptions on $c$ and $\ell(B_0) \ge 4c$ from Step 1.)
Using this and $K(P^*_{B'}) = \ell(B_0) \ge 4c$ (from Step 1), we have $$I(B : P^*_{B'}) = K(P^*_{B'}) - K(P^*_{B'} | B) \ge \ell(B_0) - \ell(B_0)/2 \ge 2c.$$ $\Box$

I guess this completes the proof, but I'm unsure whether I've properly interpreted the post, because of the following statement in the post "the $P^∗_{B′}$ is provided with $n=\ell(B)$, in this case, since the goal is to generate $B$."  I'm not sure what it this means, as it seems to contradict the earlier definition of $P^*_{B'}$ in the post (which is used in the proof above).