Finding shortest path while maximizing the number of overlapping edges The shortest path problem between 2 arbitrary nodes is one that has been covered extensively and the solution is well-known. Consider the edge costs to be arbitrary.

Consider the following variant:

Find the two shortest paths between 2 pairs of arbitrary nodes, however the cost is considered to be the length of the paths minus a positive coefficient times the number of common edges in the two paths, i.e. cost is $|P_1|+|P_2|-C|P_1\cap P_2|$.

Has this problem been addressed before?

There is a polynomial-time algorithm for this problem in the case where $C \le 2$.  There is also a polynomial-time algorithm when $C > 2$, assuming paths are not required to be simple.  If you require paths to be simple and have $C>2$, the problem is NP-hard, as explained by Neal Young.   So in the remainder of this answer I will assume that either $C \le 2$, or $C >2$ and you allow non-simple paths.  I will describe the polynomial-time algorithm below.

First, note that in an optimal solution (wlog) the common part of the two paths must be contiguous, i.e., there is a single contiguous segment of $P_1$ that overlaps with $P_2$, and the rest does not.  In particular, if we want shortest paths between $s_1 \leadsto t_1$ and $s_2 \leadsto t_2$, then there must exist some vertices $v,w$ such that $P_1$ has the form $s_1 \leadsto v \leadsto w \leadsto t_1$ and $P_2$ has the form $s_2 \leadsto v \leadsto w \leadsto t_2$ and the $s_1 \leadsto v$ and $w \leadsto t_1$ parts have no overlap with $P_2$, and the $v \leadsto w$ is common to both.  The cost of this solution is then

$$|s_1 \leadsto v| + |w \leadsto t_1| + |s_2 \leadsto v| + |w \leadsto t_2| + (2-C) |v \leadsto w|.$$

So, compute all-pairs shortest paths and all-pairs longest paths; let $d(a,b)$ denote the distance (length of the shortest path) from $a$ to $b$, and $d^*(a,b)$ the length of the longest path.  If $C \le 2$, iterate over all possible choices for $v,w$, and compute

$$d(s_1,v) + d(w,t_1) + d(s_2,v) + d(w,t_2) + (2-C) d(v,w).$$

If $C > 2$, do the same but for the expression

$$d(s_1,v) + d(w,t_1) + d(s_2,v) + d(w,t_2) + (2-C) d^*(v,w).$$

Keep the smallest value of this obtainable (i.e., the minimum over all $v,w$).  That will be the solution to your problem.  (We don't need to enforce the lack of overlap between, say, $s_1 \leadsto v$ and $s_2 \leadsto v$ in this calculation, because any overlap will only further lower the cost of the solution.)

The running time is something like $O(n^3)$, since the time is dominated by the time to compute all-pairs shortest paths.  I make no claim that  this is optimal.

My thanks to Neal Young for showing how to solve this when $C\le 2$, and for helping me make explicit my assumptions about whether paths are required to be simple or not.


Efficient algorithm for near-optimal edge-colourings of hypergraphs Graph colouring problems are, already, hard enough for most people. Even so, I'm going to have to be difficult and ask a problem about hypergraph colouring.
Question.
What efficient algorithms are there for finding an approximately-optimal edge-colouring  for k-uniform hypergraphs?
Details ---

A k-uniform hypergraph is one in which each edge contains precisely k vertices; the usual case of a simple graph is k=2. More precisely, I'm interested in labelled k-uniform hypergraphs, in which two edges may actually have the same vertex-set; but I'll settle for something on k-regular hypergraphs with edges intersecting at no more than k−1 vertices.

An edge-colouring of hypergraphs is one in which edges of the same colour do not intersect, as with the case of graphs. The chromatic index χ'(H) is the minumum number of colours required, as usual.

I would like results on deterministic or randomized polynomial time algorithms.

I'm looking for the best known approximation-factor/additive-gap between what can be efficiently found, and the actual chromatic index χ'(H) --- or for that matter, the best efficiently-attainable result in terms of parameters such as the maximum vertex degree Δ(H), the size of the hypergraph, etc.

Edit: prompted by Suresh's remarks about hypergraph duals below, I should note that this problem is equivalent to the problem of finding a strong vertex colouring of a k-regular hypergraph: that is, where each vertex belongs to k distinct edges [but the edges may now contain differing numbers of vertices], and we want a vertex colouring such that any two adjacent vertices have different colours. This reformulation also does not seem to have an obvious solution.

Remarks
In the case of graphs, Vizing's Theorem not only guarantees that the edge-chromatic number for a graph G is either Δ(G) or Δ(G)+1, standard proofs of it also give an efficient algorithm for finding a Δ(G)+1-edge-colouring. This result would be good enough for me if I were interested in the case k=2; however, I'm specifically interested in k>2 arbitrary.
There doesn't seem to be any well-known results about bounds on hypergraph-edge-colouring, unless you add restrictions such as every edge intersecting in at most t vertices. But I don't need bounds on χ'(H) itself; just an algorithm which will find a "good enough" edge-colouring. [I also don't want to place any restrictions on my hypergraphs, except for being k-uniform, and perhaps bounds on the maximum vertex-degree, e.g. Δ(H) ≤ f(k) for some f ∈ ω(1).]
[Addendum. I have now asked a related question on MathOverlow about bounds on the chromatic number, constructive or otherwise.]

The answer below breaks your condition that you don't want serious restrictions placed on your hypergraph, but it might be of interest if only as related work.

Your hypergraph (which I'll rename as a range space) has a corresponding dual range space (hypergraph) by interchanging the roles of vertices and edges. Your problem then amounts to coloring the elements of this range space so that a range of cardinality $r$ has $r$ colors. Let's call such a range colorful.

There's been some recent work on such "colorful coloring" problems for geometric range spaces, motivated partly by problems in sensor networks. A standard question that's asked is:

  Given a parameter $k$ and range space
  $S$, determine the function $c_S(k)$
  such that a $c_S(k)$ coloring of the
  elements of S guarantees that each
  range $r$ of $S$ has $\min(|r|, k)$
  colors.

Thus, $c_S(\Delta)$ is the quantity you're looking for (where $\Delta$ is the maximum cardinality of a range).

A related question is to determine $c_\tilde{S}(k)$, where $\tilde{S}$ is the dual range space (in effect, your original hypergraph). One example of the kind of results obtained is that:

  For $S$ being the space of halfplanes
  in $\Re^2$, $c_S(k) \le 3k-2$

A good reference for this body of work is the DCG paper by Aloupsis et al, and the references therein.


Complexity of Homogenizing a String Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of integers to the other. We were able to reduce that problem to the following very natural problem that seems to have connections to edit distance, grouping by swapping, and minimum common string partition.

Problem: We are given a string, i.e., a sequence of letters, and our goal is to  homogenize it at minimum cost. That is, we want a rearranged sequence such that all letters that are alike are next to each other.

The only operation that is permitted is to pick up a subsequence of letters that are alike, and move that subsequence anywhere, and that costs me 1 unit.

Any help characterizing the complexity of this problem would be much appreciated!

Example:

a a b c d a b: Input
b c d a a a b: After moving the first a a to the position right after "d"
b b c d a a a: After moving the trailing b to the first position

Since the resulting string is homogeneous, we have a cost of 2.

Note that we are not constrained in any way with respect to the output: as long as it is homogeneous, we don't need to ensure any specific order.

This problem is NP-complete, by reduction from Minimum Hitting Set.

In minimum hitting set, we are given a universe, $U$, and a set of sets $S$ such that $\forall s \in S, s \subset U$. The objective is to find $H \subset U$ of smallest size such that $\forall s \in S, \exists h \in H$ such that $h \in s$.

The reduction is as follows:

The string is as follows: For each element $u \in U$, there will be a two characters of the string, $u'$. Between these characters will a character $s'$ for each $s \in S$ such that $u \in s$. Between the pairs of $u'$s, there will be unique characters that are not repeated in the string.
To homogenize the string, the $s'$ character must be moved $|s|-1$ times, for each $s$.  Additionally, for each $u$, the $u'$ character must be moved once, unless every $s'$ between the pair of $u'$ has been moved elsewhere.
Therefore, to minimize the number of moves necessary to homogenize the string, we wish to maximize the number of $u'$ such that every $s'$ has been moved elsewhere. The $u'$s where the $s'$s have not been moved elsewhere must together contain a $s'$ for every $s \in S$, so they must for a hitting set. Moreover, any such hitting set may serve as the ending locations of the $s'$s, by moving each $s$ to the $u$ which hits it.
Thus, the number of moves to homogenize this string is equal to $\sum |s| + |H^*|$, where $H^*$ is the minimum hitting set.

Since minimum hitting set is NP-Hard, optimally homogenizing a string is as well. Since the moves form a witness, it is NP-Complete.


Nonlocal Games and Quantum Communication I'm currently on the look out for some good reference material relating non-local games with beneficial aspects in quantum communication. For instance, I am aware that non-local games are good at lower bounding communication complexity as well as ensuring the security of QKD protocols.

What I'd like to know is, what are some of the big papers in regard to non-local games in quantum communication? Have there been any recent advancements in this field that have been exceptionally important? Are there any good video abstracts/lectures/presentations on the web that parallel this material?

Specifically finding some material that relates quantum communication and the CHSH game would be of specific interest to myself as well.

Any feedback on this for any one of my questions would be very much appreciated. Thanks!

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


DAG reachability with O(n log n) space and O(log n)-time queries? For a directed acyclic graph ${\langle}V,E{\rangle}$, is there a data structure that allows for reachability queries without requiring quadratic space or linear time?  Ideally I seek an algorithm using only O(log n) space per vertex and logarithmic time where $n=|V|+|E|$.

It seemed intuitively obvious to me that a data structure like this ought to exist, based on some generalization of standard sorting algorithms.  But I was surprised that I couldn't find any.  Everything I came across either made assumptions about the graph (e.g. planarity) or solved a harder problem in quadratic time/space (e.g. queries interleaved with graph modifications).

The Wikipedia page on Reachability only covers one general algorithm (Floyd-Warshall); the rest of the page deals with special cases involving assumptions like the graph being planar (it isn't).

The most commonly cited paper in this space appears to be Amortized efficiency of a path retrieval data structure, but this and all the papers it cites involve either O(n^2) space or else O(n^2) time in order to allow updates to the graph interleaved with the queries (i.e. no preprocessing).

This question wasn't answered, but it deals with the harder problem of allowing edge insertions interleaved with queries.

This question asked for a persistent (pure functional) data structure, which isn't required here.  The "Succinct Posets" paper needs $O(n^2)$ space but it achieves $O(1)$-time queries; I seek a worse-time, better-space algorithm.

Mostly looking for a foothold in the literature here.  If there's a survey paper on graph reachability that doesn't spend 99% of its time on the planar-graph case, that would help.

See "interval labeling" and "2-hop labeling" which are apparently quite efficient in practice, both in time and space, and may give you what you want. In general there's quite a bunch of "reachability indexing" schemes for DAGs.


What are good approximation algorithms for the subset sum problem so far? By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.

Kellerer et al. (1997) gives with accuracy $\epsilon$ a $O(\min \{ n/ \epsilon, n + 1/ \epsilon^2 \log(1/ \epsilon) \})$ time and $O(n + 1/ \epsilon)$ space approximation scheme.

Further improving on this, Kellerer et al. (2003) gives a FPTAS with $O(\min \{n \cdot 1/ \epsilon , n + 1/ \epsilon^2 \log( 1/ \epsilon) \} )$ time and $O(n+1/ \epsilon)$ space. In addition, answering your question on "relatively fast running time", they noted that (based on computational results) that the scheme efficiently solves instances with up to $5000$ items with a guaranteed relative error smaller than $1/1000$.

I am unsure if there are any newer results. As noted, because subset sum is a special case of the knapsack problem, one will probably find even more results when searching for that.

UPDATE: You might also want to take a look at The Design of Approximation Algorithms, Williamson and Shmoys, 2011, see the chapter starting at page 65 about the Knapsack problem. They give a FPTAS (on page 68) for the Knapsack problem that runs in $O(n^3/\epsilon)$ time. It might be that the algorithms specifically designed for the Subset sum problem are faster than the more general ones for the Knapsack.


Is "two or zero" matching in a bipartite graph NP complete? I have this problem, which I haven't seen before in the literature: given a bipartite graph and a natural number $k$, can we select at least $k$ of the edges such that each left-hand vertex is incident to exactly two or exactly zero selected edges, and each right-hand vertex is incident to at most one selected edge?

Obviously if replace "two" with one we have the matching problem, which can be solved in polynomial time. I've tried in vain to solve my problem using network flow or matching, and am also stumped when I try to reduce from NP-complete problems.

The answer here seems to imply there is a more general result. For this particular case, here is a self contained way to reduce the problem to maximum weight perfect matching. Assume $k$ is even.

Given $G=(L\cup R, E)$, we construct a new graph $G'=(V',E')$ as follows, let $|R|=n$.

Add vertices in $R$ to $V'$.
For each vertex $v \in L$, add vertices $v_1,v_2$ to $V'$.
Add vertices $t_1,\ldots,t_{n-k}$ to $V'$.
Add edge $v_1v_2$ to $E'$ for each $v\in L$. It has weight $0$.
Add edge $v_iu$ to $E'$ for each $vu\in E$,$u\in R,v\in L,i\in \{1,2\}$. It has weight $1$.
Add edge $ut_i$ for each $u\in R$ and $1\leq i\leq n-k$. It has weight $0$.

Claim: The maximum weight perfect matching in $G'$ has value $k$ iff the "two or zero" matching has a solution of at least $k$ edges.


$\overline{SAT} \in NTIME(subexp)$? Is it possible that $\overline{SAT} \in NTIME(\exp(n^{0.9}))$ ?
Are there interesting consequences of such containment?
Would it contradict the Exponential Time Hypothesis?

It is possible ;-)

It would give new circuit lower bounds.  Since you are making a pretty strong assumption this could follow from the seminal work by Impagliazzo, Kabanets, and Wigderson, I haven't checked.

If you use Williams' approach, tightened here, you get a lower bound of $n^{1+\Omega(1)}$ for a function on $n$ bits in the class E$^{NP}$.  (For this approach, a fast co-nondeterministic algorithm for satisfibility is sufficient, as you are postulating.)  Specifically, the latter paper shows that a lower bound for size $s$ follows from a satisfiability algorithm for circuits of size $O(s)$, which we can translate to a 3SAT instance with $O(s)$ variables by Cook-Levin.

It would not directly contradict ETH because that's for deterministic algorithms.


No Fair Merge via Nondeterminstic Data Flow Streams While reading Wikipedia, I ran across a proof given on Unbounded Nondeterminism that I do not understand.

The proof is given as,
An example of the role of fair or unbounded nondeterminism in the merging of strings was given by William D. Clinger, in his 1981 thesis. He defined a "fair merge" of two strings to be a third string in which each character of each string must occur eventually. He then considered the set of all fair merges of two strings merge(S, T), assuming it to be a monotone function. Then he argued that merge(⊥,1ω)⊆ merge(0,1ω), where ⊥ is the empty stream. Now merge(⊥,1ω) = 1ω, so it must be that 1ω is an element of merge(0,1ω), a contradiction.

My misunderstanding is, "merge(⊥,1ω) = 1ω." Previously it said that "merge(S, T)" is "the set of all fair merges of two strings".

Why is "merge(⊥,1ω) = 1ω," instead of merge(⊥,1ω) = {1ω}. If so, isn't {1ω} ⊆  merge(0,1ω)? What am I missing?

When in doubt, consult the original source: Clinger's Thesis. Clinger shows that fair merge cannot be written in a nondeterministic dataflow program. He does this by considering the semantic domains in which such a function would be defined, ultimately deriving a contradiction to the assumption that fair merge exists.

Firstly, as Daniel Apon points out, $merge(\bot,1^\omega)=\{1^\omega\}$. This is the only reasonable definition of merge for these arguments (see page 84 of Clinger's thesis).

Secondly, $merge(\bot,1^\omega)\subseteq merge(0,1^\omega)$, because  $\bot\le 0$, as stream $0$ is a possible extension of stream $\bot$ (bottom of page 73),  and by assumption $merge$ is monotone. In more detail, the ordering on the domain of strings states that any prefix of a string, is $\le$ the string, thus the empty string $\bot$ is the smallest element, and hence $\bot\le 0$, where $0$ is the string with just the element $0$. The function $merge$ has type $S\times S\to\mathcal{P}(S)$, where $S$ is string and $\mathcal{P}(-)$ is powerset.  The assumption that $merge$ is monotone means that if $a\le b$ then $merge(a,s)\subseteq merge(b,s)$. (Similarly for the second argument.)

Now $1^\omega\in merge(0,1^\omega)$ violates the assumption that $merge$ is fair – a fair merge of $0$ and $1^\omega$ should to contain the $0$. In more detail, $merge(S,T)$ is interleaving the "cards" from $S$ and $T$, without shuffling them. The significance of the stream $1^\omega$ is that it is infinite. $0$ is simply some character different from $1$. A fair merge of $0$ and $1^\omega$ should result in a string such as $1^*01^\omega$. Fairness means that within some finite time it selects elements from each string, thus the character $0$ is eventually chosen.

Hence $merge$ cannot be written as a nondeterministic dataflow program.


Memory requirement for fast matrix multiplication Suppose we want to multiply $n \times n$ matrices. The slow matrix multiplication algorithm runs in time $O(n^3)$ and uses $O(n^2)$ memory. The fastest matrix multiplication runs in time $n^{\omega + o(1)}$, where $\omega$ is the linear algebra constant, but what is known about its memory complexity?

It seems that it may be possible a priori that fast matrix multiplication consumes $n^{\omega}$ memory. Is there are any guarantee that it can be done in $O(n^2)$ memory? Is it the case that the currently-known matrix multiplication algorithms use $O(n^2)$ memory?

(I am actually interested in rectangular matrix multiplication, but I assume that the answer would be the same in that case as for the square case, and the square case is better studied.)

The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See Space complexity of Coppersmith–Winograd algorithm

However, I realized in my previous answer that I did not explain why the space usage is $O(n^2)$... so here goes something hand-wavy. Consider what a Strassen-like algorithm does. It starts from a fixed algorithm for $K \times K$ matrix multiplication that uses $K^c$ multiplications for some constant $c < 3$. In particular, this algorithm (whatever it is) can WLOG be written so that:

It computes $K^c$ different matrices $L_1,\ldots,L_{K^c}$ which multiply entries of the first matrix $A$ by various scalars and $K^c$ matrices $R_1,\ldots,R_{K^c}$ from the second matrix $B$ of a similar form,
It multiplies those linear combinations $L_i \cdot R_i$, then
It multiplies entries of $L_i \cdot R_i$ by various scalars, then adds all these matrices up entrywise to obtain $A \cdot B$.

(This is a so-called "bilinear" algorithm, but it turns out that every "algebraic" matrix multiplication algorithm can be written in this way.) For each $i=1,\ldots,K^c$, this algorithm only has to store the current product $L_i \cdot R_i$ and the current value of $A \cdot B$ (initially set to all-zeroes) in memory at any given point, so the space usage is $O(K^2)$.

Given this finite algorithm, it is then extended to arbitrary $K^{\ell} \times K^{\ell}$ matrices, by breaking the large matrices into $K \times K$ blocks of dimensions $K^{\ell-1}\times K^{\ell-1}$, applying the finite $K \times K$ algorithm to the block matrices, and recursively calling the algorithm whenever it needs to multiply two blocks. At each level of recursion, we need to keep only $O(K^{2\ell})$ field elements in memory (storing $O(1)$ different $K^{\ell} \times K^{\ell}$ matrices). Assuming the space usage for $K^{\ell-1}\times K^{\ell-1}$ matrix multiplication is $S(\ell-1)$, the space usage of this recursive algorithm is $S(\ell) \leq S(\ell-1) + O(K^{2\ell})$, which for $S(1) = 2K^2$ solves to $S(\ell) \leq O(K^{2\ell})$.


Lower bounds for learning in the membership query and counterexample model Dana Angluin (1987; pdf) defines a learning model with membership queries and theory queries (counterexamples to a proposed function). She shows that a regular language that is represented by a minimal DFA of $n$ states is learnable in polynomial time (where the proposed functions are DFAs) with $O(mn^2)$ membership-queries and at most $n−1$ theory-queries ($m$ is the size of the largest counter-example provided by the tutor). Unfortunately, she does not discuss lower bounds.
We can generalize the model slightly by assuming a magical tutor that can check equality between arbitrary functions and provide counterexamples if different. Then we can ask how hard it is to learn classes bigger than regular languages. I am interested in this generalization and the original restriction to regular languages.
Are there any known lower bounds on the number of queries in the membership and counterexample model?
I am interested in lower bounds on the number of membership queries, theory queries, or trade-offs between the two. I am interested in lower-bounds for any class of functions, even for more complicated classes than regular languages.
If there are no lower-bounds: Are there known bariers to proving query lower bounds in this model?

Related questions
Are there improvements on Dana Angluin's algorithm for learning regular sets

Yes, some lower bounds are known. For example, assuming $NP \neq coNP$, you cannot even properly learn read-thrice DNF formulas in polynomial time.  There is a whole paper developing such hardness results using something called the "representation problem".

To answer your linked-to question: Schapire, in his dissertation, in addition to proving that "weak learning" = "strong learning," also improved on Angluin's bound and gave an algorithm that uses $O(n)$ equivalence queries and $O(n^2+ n \log m)$ membership queries for learning DFA.

One easy way to get lower bounds is information-theory.  You can figure out how many distinct targets there are and how many bits a query gives you, etc.  These upper bounds come close but aren't there.  There are also issues one needs to think about regarding how the "counterexamples" arrive to the learner.  A well-chosen counterexample can give away quite a lot of information.

Update to the discussion above: Angluin and Dohrn address the question learning with random counterexamples in a recent paper.


What is the most Accurate way of Determining an Object's Color? I have written a computer program that can detect coins in a static image (.jpeg, .png, etc.) using some standard techniques for computer vision (Gaussian Blur, thresholding, Hough-Transform etc.). Using the ratios of the coins picked up from a given image, I can establish with good certainty which coins are which. However, I wish to add to my confidence levels and also determine if a coin that I deduce to be of type-A (from radius ratios) is also of the correct colo[u]r. The problem is that for British coins et al. (copper, silver, gold), the respective colors (esp. of copper to gold) are very similar.

I have a routine that extracts the mean color of a given coin in terms of the RedGreenBlue (RGB) 'color-space' and routines to convert this color into HueSaturationBrightness (HSB or HSV) 'color-space'.

RGB is not very nice to work with in attempting to differentiating between the three coin colors (see attached [basic] image for an example). I have the following ranges and typical values for the colours of the different coin types:

Note: the typical value here is one selected using a 'pixel-wise' mean of a real image.

Copper RGB/HSB: typicalRGB = (153, 117, 89)/(26, 0.42, 0.60).

Silver RGB: typicalRGB = (174, 176, 180)/(220, 0.03, 0.71).

Gold RGB: typicalRGB = (220, 205, 160)/(45, 0.27, 0.86)

I first tried to use the 'Euclidian distance' between a given mean coin color (using RGB) and the typical values for each coin type given above treating the RGB values as a vector; for copper we would have:

$$D_{copper} = \sqrt((R_{type} - R_{copper})^{2} + (G_{type} - G_{copper})^{2} + (B_{type} - B_{copper})^{2})$$

where the smallest value of the difference ($D$) would tell us which type the given coin is most likely to be. This method has shown itself to be very inaccurate.

I have also tried just comparing the hue of the coins with the typical values of the types provided above. Although theoretically this provides a much better 'color-space' to deal with varying brightness and saturation levels of the images, it too was not accurate enough.

Question: What is the best method to determine a coins type based on color (from a static image)?

Thanks very much for your time.

You can fit a model to estimate a posterior probability of a color space point to belong to a certain coin type. Take a look at Gaussian mixture model. Another (somewhat arbitrary, but simpler) approach is to use nearest-neighbour interpolation.


A simple inference in rewriting theory I was puzzled by a seeming simple inference in rewriting theory:

if $y_1 \overset{*}{\leftarrow} x \overset{*}{\rightarrow} y_2$ then $y_1 \overset{*}{\leftrightarrow} y_2$.

I don't understand how could the consequence be inferred. For example, given $b_2 \leftarrow b_1 \leftarrow a \rightarrow c_1 \rightarrow c_2$, how could you say that $b_2$ and $c_2$ can reduce to each other?

EDIT:

After reading Ohad's answer, in particular

  a sequence of reverse rewrites followed by a sequence of direct rewrites is indeed a sequence of (either direction) rewrites.

I suddenly realized that the inference is indeed immediate, because $\rightarrow$ represents a (rewriting) relation, which means it's just a set of pairs. Its reflexive closure ($\overset{=}{\rightarrow}$), symmetric closure ($\leftrightarrow$), transitive closure ($\overset{+}{\rightarrow}$) are all defined as a superset of it. In particular, its reflexive, transitive and symmetric closure ($\overset{*}{\leftrightarrow}$) also contains it. In other words, we have $\rightarrow\;\subset \overset{*}{\leftrightarrow}$, then recall that a subset relation can be read as an inference which is exactly the statement that puzzled me. [EDIT: this reading doesn't help here!] Take the example I gave, $\rightarrow = \{(a, b_1), (b_1, b_2), (a, c_1), (c_1, c_2)\}$, its reflexive, transitive and symmetric closure $\overset{*}{\leftrightarrow} = \{(a, b_1), (b_1, b_2), (a, c_1), (c_1, c_2), (a, b_2), (a, c_2), (b_2, b_1), (b_1, a), (c_2, c_1), (c_1, a)\}$, the subset relation definitely holds. I hope this may also help others.

*EDIT*${}^2$:

I just realized that back then, I forgot to give the context of the inference.  The inference is formed via transitivity of logical inference from two others:

$y_1 \overset{*}{\leftarrow} x \overset{*}{\rightarrow} y_2 \Rightarrow y_1 \downarrow y_2$
$y_1 \downarrow y_2 \Rightarrow y_1 \overset{*}{\leftrightarrow} y_2$

where $y_1 \downarrow y_2$ means $\exists z . y_1 \overset{*}{\rightarrow} z \overset{*}{\leftarrow} y_2$ and the first is known to be the confluence.

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

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

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


What is the time complexity of base conversion on a multi-tape Turing machine? Base conversion is the problem of converting an integer between representations in two fixed bases. Without loss of generality consider the case of relatively prime bases. I think it's easier to imagine a single type of machine that can handle all cases even though the bases are fixed, so consider a base-$b$ number as being represented by a concatenation of $\lceil \log_2{(b)} \rceil$-bit words, and let our multi-tape Turing machines have a binary input and output alphabet. But equivalently we can build a machine whose input and output tape alphabet sizes match the source and target bases.

Is base conversion known to be computable in better than essentially quadratic time?

This question has been asked many times but every reference I can find is in a practical context. I have seen claims that it can be accomplished in quasilinear time, but I can't understand how this is supposed to work, in part because assumptions about the model are often unstated in such discussions.

Base conversion can be done in time $O(M(n)\log n)$, where $M(n)$ is a bound on the time complexity of multiplication of two $n$-bit integers. (We assume that $M(n)$ satisfies usual regularity conditions: it is monotone, and $2M(n)\le M(2n)$.)

The standard divide-and-conquer algorithms are described e.g. in Brent&Zimmermann, Modern computer arithmetic, and go as follows:

Conversion from binary to base $b$

Let $a$ be the input number, of length $n$. By repeated squaring, compute the sequence $b$, $b^2$, $b^4$, $b^8$, ..., $b^{2^k}$, where $k\le\log n$ is such that $a<b^{2^k}$.

Using division with remainder, compute $a_0,a_1<b^{2^{k-1}}$ such that $a=a_1b^{2^{k-1}}+a_0$. Recurse with $a_0$ and $a_1$:

That is, in the second stage, compute $a_{00},a_{01},a_{10},a_{11}<b^{2^{k-2}}$ such that $a_0=a_{01}b^{2^{k-2}}+a_{00}$ and $a_1=a_{11}b^{2^{k-2}}+a_{10}$. In the third stage, split each of the 4 numbers in two using division by $b^{2^{k-3}}$, and so on. After the $k$-th stage, we will have a sequence of numbers $<b$, which is the base-$b$ expansion of $a$.

($a$ is its own expansion in base $b^{2^k}$. After the first stage, $a_1a_0$ is the expansion of $a$ in base $b^{2^{k-1}}$. After the second stage, we have the expansion of $a$ in base $b^{2^{k-2}}$, etc.)

The running time is
$$O(M(n)+2M(n/2)+4M(n/4)+\dots)\le O(M(n)\log n).$$

Conversion from base $b$ to binary

Reverse the process above: given the base-$b$ expansion $a_ma_{m-1}\dots a_0$, in the first stage, combine the elements in pairs as $a_{2i+1}b+a_{2i}$ to form the base-$b^2$ expansion; in the second stage, combine the blocks to larger blocks using multiplication by $b^2$ to obtain the base-$b^4$ expansion, and so on. After $\log n$ stages, we will have a single number. The running time is as above.


Rounding to minimise the sum of errors in pairwise distances What is known about the complexity of the following problem:

Given: rational numbers $x_1 < x_2 < \dotso < x_n$.
Output: integers $y_1 \le y_2 \le \dotso \le y_n$.
Objective: minimise $$\sum_{1 \le i < j \le n} e(i,j),$$ where $$e(i,j) = | (y_j-y_i) - (x_j-x_i)|.$$

That is, we would like to round the rational numbers to integers so that we minimise the sum of errors in pairwise distances. For each pair $i, j$ we would like to have the rounded distance $y_j-y_i$ as close as possible to the true distance $x_j-x_i$.

Motivation: a boring metro trip, and a poster that shows the "locations" of the stations at the resolution of one minute of travelling time. Here we are minimising the error that people make if they use the poster to look up the travelling time between stations $i$ and $j$, averaging over all pairs $i<j$.

(source)

For example, here we can read the following approximations of the pairwise distances between the four stations (using A, B, C, D for brevity):

A–B ≈ 1 minute, B–C ≈ 2 minutes, C–D ≈ 2 minutes
A–C ≈ 3 minutes, B–D ≈ 4 minutes
A–D ≈ 5 minutes

Is this the best possible approximation? If you knew the actual travelling times, could you find a better solution?

At first, this sounded like a simple exercise in dynamic programming, but now it seems that some amount of actual thinking is required.

Does anyone recognise this problem? Or see a clever algorithm for solving it?

Edit: There are some natural variants of the question that have been mentioned in the comments; let's give them some names:

floor/ceil version: it is required that $y_i \in \{ \lfloor x_i \rfloor, \lceil x_i \rceil \}$ for all $i$.
integer version: it is sufficient that $y_i \in \mathbb{Z}$ for all $i$.
monotonic version: it is required that $y_1 \le y_2 \le \dotso \le y_n$.
non-monotonic version: we can have $y_i > y_j$ for $i < j$.

The original question considers the monotonic integer version, but answers related to any of these versions are welcome.

OK. The DP algorithm seems to be unnecessarily complicated. After reading comments I think this might solve the Monotonic version of the problem (but I have not checked every detail).

First, assume each $x_i = \lfloor x_i\rfloor +\{x_i\}$, where $\lfloor x_i\rfloor$ is the integral part, $\{x_i\}$ is the fractional part. Assume $x_i$ is rounded to $\lfloor x_i \rfloor + v_i$, where $v_i$ is a nonnegative integer (of course in general $v_i$ can be negative, but we can always shift so that the smallest $v_i$ is 0).

Now, consider the cost for a pair $x_i$, $x_j$ when doing this rounding. The cost should be

$$
||v_i-v_j+ \lfloor x_i\rfloor -  \lfloor x_j\rfloor| - |\{x_i\}-\{x_j\} + \lfloor x_i\rfloor - \lfloor x_j\rfloor||
$$

The expression is complicated because of the absolute values. However, notice that we have monotonicity, so the things inside the two inner absolute values should have the SAME sign. Since we have an outer absolute value, it really doesn't matter what that sign is, the expression just simplifies to

$$
|v_i-v_j - (\{x_i\} - \{x_j\})|
$$

From now on we do not assume the solution is monotonic, but instead, we change the objective to minimize the sum of the above term for all pairs. If the solution to this problem happens to be monotonic, then of course it is also the optimal solution for the monotonic version. (Think of this as: original problem has an infinite penalty when the solution is not monotonic, the new problem has smaller penalty, if a monotonic solution wins even in the new version, it must be the solution to the monotonic version)

Now we would like to prove, if $\{x_i\} > \{x_j\}$, in the optimal solution we must have $v_i \ge v_j$.

Assume this is not true, that we have a pair $\{x_i\} > \{x_j\}$ but $v_i < v_j$. We shall show that if we swap $v_i$ $v_j$ the solution gets strictly better.

First we compare the term between $i$ and $j$, here it is really clear that swapping is strictly  better because in the non-swap version, $v_i-v_j$ and $\{x_j\}-\{x_i\}$ has the same sign, the absolute value will be the sum of the two absolute values.

Now for any $k$, we compare the sum of pairs $(i,k)$ and $(j,k)$. That is, we need to compare

$|v_i-v_k-(\{x_i\}-\{x_k\})|+|v_j-v_k-(\{x_j\}-\{x_k\})|$ and $|v_j-v_k-(\{x_i\}-\{x_k\})|+|v_i-v_k-(\{x_j\}-\{x_k\})|$.

Use $A$, $B$, $C$, $D$ to denote the four terms inside the absolute value, it is clear that $A+B = C+D$. Also it is clear that $|A-B| \ge |C-D|$. By convexity of the absolute value, we know $|A|+|B| \ge |C|+|D|$. Take the sum over all $x_k$'s, we know swapping can only be better.

Notice that now we already have a solution for the Monotonic floor/ceil version: there must be a threshold, when $\{x_i\}$ is bigger always round up, when it is smaller always round down, when it is equal round some up and some down, while the solution quality only depends on the number. We enumerate all these solutions and pick the one with smallest objective function. (All these solutions are necessarily monotonic).

Finally we would like to go to the monotonic integer version of the problem. We can actually prove the optimal solution is the same as Monotonic floor/ceil version.

As we assumed, the smallest $v_i$ is 0. Group all the $x_i$'s according to their $v_i$'s, and call them group $0,1,2,...,\max\{v_i\}$. We shall first prove that there are no empty groups, but this is simple, if the $k$-th group is empty, for any $v_i > k$ just let $v_i = v_i-1$. It is easy to see the objective function always improves (basically because $|\{x_i\}-\{x_j\}| < 1$).

Now we shall prove, the average of $\{x_i\}$ in group $k+1$ is at least the average of $\{x_i\}$ in group $k$ plus $1/2$. If this is not true, simply let $v_i = v_i-1$ for all $v_i > k$, computation again shows the objective function improves.

Since the average of $\{x_i\}$ is in range $[0,1)$, there are really at most two groups, which corresponds to the floor/ceil version.


Detecting undirected cycles in logarithmic space I have a lot of difficulties with constructing algorithms that use $O(\log n)$ space, as I am unsure about how much can be stored on the worktape.

I am trying to figure out an algorithm for the problem:

UCYCLE = {<G>|G is an undirected graph that contains a simple cycle}

I can't seem to understand how to create an algorithm in logspace that can solve this problem. In my head, it has to store all the previously visited nodes (since it can't visit the same node twice). Also, I am really stuck on how to start searching, when I can't use non-determinism. Can someone help me with some pointers on how to go forward so I can figure out an algorithm?

(PS: This is not homework, but I need to understand how to create algorithms for problems in L and NL)

For the undirected cycle problem, you can traverse each connected component: at each node, when coming in through edge $k$, leave through edge $k+1$. (We can assume edges are ordered at each vertex.)

Now vou start such a traversal once from every node $v$, remembering only $v$ and the edge you left $v$ through. If the traversal returns to $v$ through a different edge, then $v$ lies on a cycle. If this is not the case for all $v$, then the graph is acyclic.

In general, in a logarithmic space algorithm you can only store constantly many pointers into the input and counters.


A variant of #POSITIVE-2-DNF Let $G=(V,E)$ be an undirected graph. I call a valuation of $G$ a function $\nu: V \to E$ that maps every node $x \in V$ to an edge incident to $x$ (so that there are $\prod_{x \in V} d(x)$ valuations of $G$, where $d(x)$ is the degree of node $x$). I say that $\nu$ is satisfying if there exist an edge $e\in E$ such that both endpoints of $e$ are mapped to $e$ by $\nu$. I am interested in the following problem:

INPUT: An undirected graph $G$

OUTPUT: The number of satisfying valuations of $G$

My question: What is the complexity of this problem, and does it already have a name?

My guess is that it is #P-hard, even for bipartite graphs. A closely related #P-hard problem is #POSITIVE-2-DNF, or even [#PARTITIONED-POSITIVE-2-DNF][1]. Indeed, you can see an instance of #(PARTITIONED-)POSITIVE-2-DNF as a (bipartite) graph $G$, and you say that a valuation of $G$ either maps a node $x$ to all of its incident edges or to none of them. So my problem is somewhat a variant of #POSITIVE-2-DNF, but where valuations map variables to a single clause in which they occur, instead of mapping them to $0$ of $1$.

==== UPDATE ====

As a3nm showed in his answer, the problem is hard on 3-regular graphs with multi-edges. My answer shows that the problem is also hard on $2$-$3$ regular simple graphs. There is the minor question of knowing if it is hard one $3-regular simple graphs. I don't really care about it, but I still leave it here for completeness.

Note: this reduction is written in the wrong direction, and when fixed it only works for multigraphs. See explanations in the edit to the original question.

I think the problem is #P-hard already on 3-regular graphs using the results of Cai, Lu and Xia, Holographic Reduction, Interpolation and Hardness, 2012. I will do this by showing the #P-hardness of counting the non-satisfying valuations of $G$, i.e., the valuations $\nu$ where for every edge $e$ at least one of the endpoints of $e$ is not mapped to $e$ by $\nu$. Indeed, counting this reduces in PTIME to counting the satisfying valuations of $G$ as you ask: this uses the fact that the total number of valuations (both satisfying and non-satisfying) can be computed in PTIME, using the closed-form formula in your question.

To show the hardness of counting non-satisfying valuations on 3-regular graphs, consider a 3-regular graph $G = (V, E)$, and construct the bipartite graph $G' = (V \cup E, W)$ between $V$ and $E$: it is a 2-3-regular graph in the sense that vertices in $V$ all have degree $3$ and vertices in $E$ all have degree $2$. Now, a non-satisfying valuation of $G$ in your sense amounts to picking one edge of $W$ incident to each vertex of $V$ in $G'$, so that we never pick the two edges of $W$ incident to a vertex of $E$. In other words, I'm claiming that counting the non-satisfying valuations of $G$ is exactly to counting the subsets $W'$ of $W$ such that each vertex of $V$ has exactly one incident edge in $W'$ (= we pick one edge for each vertex of $V$), and each vertex of $E$ has 0 or 1 incident edges in $W'$ (= no edge of $E$ has both its endpoints selected).

If I'm not mistaken, this is precisely the problem #[1,1,0][0,1,0,0] in the notation of Valiant used in the paper I quote: note that there's a hopefully legible explanation in Appendix D of this paper (which, incidentally, we co-authored ;-P). Now looking at the table on page 23 of Cai, Lu and Xia, we see that #[1,1,0][0,1,0,0] is #P-hard.

As for the problem having an established name more palatable than #[1,1,0][0,1,0,0], I don't know, but maybe this can be one direction in which to look.


Is Magic: the Gathering Turing complete? A very specific question, I'm aware, and I doubt it will be answered by anyone that isn't already familiar with the rules of Magic. Cross-posted to Draw3Cards. Here are the comprehensive rules for the game Magic: the Gathering. See this question for a list of all Magic Cards. My question is - is the game Turing Complete?

For more details, please see the post at Draw3Cards.

Alex Churchill (@AlexC) has posted a solution that does not require cooperation between the players, but rather models the complete execution of a universal Turing machine with two states and 18 tape symbols.  For details, see  https://www.toothycat.net/~hologram/Turing/ [archive].


Is it easy to "fit a wrapped chain in a graph"? Given a directed graph $G=(V,A)$ with a unique source node $s$ (a node without incoming edges) and a unique sink node $t$ (a node without outgoing edges).

Given a sequence of variables $SEQ = (x_{i_1},x_{i_2},...,x_{i_m})$ with $|SEQ| > 2$ and each $i_j \in [1..m]$

For example $SEQ = (x_1,x_2,x_3,x_4,x_2,x_3,x_5)$ (m=5).

A node assignment is a function $f: \{x_1,...,x_m\} \rightarrow V$ such that if $i \neq j$ then $f(x_i) \neq f(x_j)$ (it maps each $x_j$ to a different node of the graph). Now, if in $SEQ$ we substitute $x_j$ with $f(x_j)$ we obtain a sequence $NODESEQ$ of nodes.

We want to start from $s$ and end in $t$ so trivially $x_1 = s, x_m = t$.

For example: $NODESEQ = (s,v_1,v_7,v_9,v_1,v_7,t)$

A valid node assignment is an assignment such that if we substitute each $x_{i_j}$ with $f(x_{i_j})$ in the sequence $SEQ$ we obtain a valid path from $s$ to $t$.

Problem 1:

Given a directed graph $G$ with one source and one sink and a sequence of variables $SEQ$ check if a valid node assignment exists.

I'm not an expert, but if we take $m=n=|V|$ and $SEQ=(x_1,...,x_n)$ then the problem becomes the Hamiltonian Path problem. Informally HAM-PATH can be reduced to Problem 1, adding a source node $s$ and a sink node $t$, two extra variables at the beginning and end of $SEQ$: $(x_s,x_1,...,x_n,x_t)$ and edges $(s,u), (v,t)$ for every $u,v \in V$, (hence Problem 1 is in NPC).

But we can modify it and drop the condition that if $i \neq j$ then $f(x_i) \neq f(x_j)$ i.e we can assign the same node $v$ to more than one $x_i$ (I call it relaxed node assignment). We get an (apparently) simpler problem.

Problem 2:

Given a directed graph $G$ with one source and one sink and a sequence of variables $SEQ$ check if a valid **relaxed node assignment** exists.

An informal way to describe the problem: we have a chain made of segments. Now we wrap it up in some casual order and join some innermost endpoints. The problem 2 consists in checking if such wrapped chain can "fit" in a given graph.

Is this problem known?

Is it still an NPC problem?

Allow me to try to redeem my previous incorrect answer with an attempt at showing that this problem is NP-complete via a reduction from GRAPH 3-COLORABILITY. The key idea is to identify SEQ as a list of edges of some graph and observe that a "relaxed node assignment" corresponds to a graph homomorphism.

Let $H = (U, E)$ be a connected, undirected graph with $U = \{u_1, u_2, \ldots, u_n\}$. Let $P = (u_{a_1}, u_{a_2}, \ldots, u_{a_p})$ be a (non-simple) path in $H$ that traverses every edge at least once (i.e.: if there is an edge between $u_i$ and $u_j$, then they appear consecutively in $P$ in either order). First, we need to show that $P$ is not too long. We can construct $P$ as follows:

Start at $u_1$.
Visit each neighbor of $u_1$, returning to $u_1$ after each visit. I.e., if the neighbors of $u_1$ are $u_{n_1}, u_{n_2}, \ldots, u_{n_d}$, we have the following sequence: $u_1, u_{n_1}, u_1, u_{n_2}, u_1, \dots, u_1, u_{n_d}, u_1$.
Travel to $u_2$.
Visit each neighbor of $u_2$.
etc...

By visiting each vertex's neighbors, each edge in $H$ is traversed. Each neighbor visitation step adds $O(n)$ steps to the path. Each travel to a successive vertex adds another $O(n)$ steps. So, in total length of $P = (u_{a_1}, u_{a_2}, \ldots, u_{a_p})$ is $O(n^2)$.

Let $SEQ = (x_0, x_{a_1}, x_{a_2}, x_{a_3},\ldots,x_{a_p}, x_{n+1})$ be the sequence of variables.

Let $G = (V, A)$ be the complete, directed graph on three vertices adjoined with a universal source and a universal sink. Explicitly, let $V = \{v_1, v_2, v_3, v_{source}, v_{sink}\}$. There is an arc from $v_{source}$ to $v_i$ and from $v_i$ to $v_{sink}$ for $i=1,2,3$. And, for all $i,j = 1,2,3, i \neq j$ there is an arc from $v_i$ to $v_j$.

Finally, we claim that a valid relaxed node assignment from $SEQ$ to $G$ exists iff $H$ is 3-colorable. Let $c:U \rightarrow \{1,2,3\}$ be a 3-coloring of $H$. Let $f:X \rightarrow V$ be defined by:

$f(x_0) = v_{source}$
$f(x_{n+1}) = v_{sink}$
$f(x_i) = v_{c(u_i)}$

It should be clear that $f$ is a valid relaxed node assignment. It should be equally clear that we can reverse this construction to use any valid relaxed node assignment to define a 3-coloring of $H$.


FPT algorithm for Partial k-tree Isomorphism H.L. Bodlander in Polynomial algorithms for graph isomorphism and chromatic index on partial $k$-trees given a polynomial time algorithm for graph isomorphism when $k$ is constant.

Is there any FPT algorithm for partial $k$-tree isomorphism.

As M. Kanté pointed out, it's open whether or not graph isomorphism is FPT when parameterized by tree-width. Furthermore, I don't believe there is any complexity-theoretic barrier to creating an FPT algorithm in this case.

For a survey of what's known about the fixed-parameter tractability of graph isomorphism, see the introduction of my paper with Anuj Dawar and Eryk Kopczyński here. In the paper we show graph isomorphism is FPT in the tree-depth of a graph, which is a necessary (but not sufficient) condition for graph isomorphism to be FPT in tree-width.


Determining the convexity of a set on $S^n$ While pondering a problem on separating objects in $R^n$ by hyperplanes, I came across the following puzzle:

Suppose we are given a convex subset of $S^n$ which we call $M$.

For each point $p \in S^n$, let $C(p)$ define the great circle obtained by considering the point $p$ as the north pole and $C(p)$ as the equator. (If we imagine $p$ to correspond to a unit vector $v(p)$ in the obvious manner, then $C(p)$ corresponds to the set of all unit vectors orthogonal to $v(p)$).

Now, define the set $X = \{x \in S^n$ s.t $C(x) \cap M \neq \phi \}$

Is $X$ necessarily convex? The above definition is equivalent to saying that $X$ is the set of all unit vectors orthogonal to at least one unit vector in $M$.

Edit: Sasho has clarified in his answer that $X$ need not be necessarily convex. I am wondering if we may say something weaker about the topology of $X$. I will conjecture that $X$ would be decomposable into $2$ separate convex components?

Yes, at least if you define your terms correctly.

Following standard usage in Riemannian geometry, a subset $M \subseteq S^n$ is convex if and only if, for every pair of points $x$ and $y$ in $M$, some shortest path from $x$ to $y$ lies entirely within $M$.  With this standard definition, any convex subset $M  \subseteq S^n$ is both the convex closure of the points in $M$ and the intersection of all closed hemispheres that contain $M$.  In particular, the only convex subset of $S^n$ that does not lie entirely in a closed hemisphere is the entire sphere $S^n$.  (And yes, $S^n$ is the intersection of the empty set of closed hemispheres containing $S^n$!) Your definition of convexity allows some non-standard convex sets, like the complement of a single point.

Let's assume that the sphere $S^n$ is centered at the origin of $\mathbb{R}^{n+1}$.  Following the standard definitions, a subset $M\subseteq S^n$ is convex if and only if $M$ is the intersection of $S^n$ with a convex cone in $\mathbb{R}^{n+1}$.   So let $C$ be a convex cone in $\mathbb{R}^{n+1}$, and let $M = C \cap S^n$.  Let $C^*$ denote the dual cone of $C$; this is also a convex cone, so the intersection $S^n\cap C^*$ is convex.  Your set $X$ is $S^n \cap (C^* \cup -C^*)$ = $(S^n\cap C^*) \cup -(S^n\cap C^*)$.  Thus, $X$ is the union of two  antipodal convex subsets of $S^n$.


Enumerate all allocations of points in a simplex Consider the standard 2-simplex $\{(x,y)~|~x+y=1~;~ x,y\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y by the following process:

Fix two positive weights $(w_x,w_y)$;
For each point $(x,y)\in M$, calculate $w_x x$ and $w_y y$;
If $w_x x > w_y y$ then give the point to X; else give the point to Y.

From the set of $2^m$ possible allocations, only $m+1$ allocations can be attained by the above procedure. Why? Because if a point $(x_1,y_1)$ is given to X, then all the points $(x_2,y_2)$ with $x_2>x_1,y_2<y_1$ are given to X too. Thus, each allocation can be found by cutting the line at some point,  giving to X all the points between the cut and $(1,0)$, and giving to Y the remaining points. Thus, it is easy to enumerate all possible allocations.

The question is: what happens when we move to a higher-dimensional simplex? For example, consider the standard 3-simplex $\{(x,y,z)~|~x+y+z=1~;~ x,y,z\geq 0\}$.
Given a set $M$ of $m$ points in this simplex, we allocate each point either to X or to Y or to Z by the following process:

Fix 3 positive weights $(w_x,w_y,w_z)$;
For each point $(x,y,z)\in M$, calculate $w_x x$ and $w_y y$ and $w_z z$;
If $w_x x$ is larger than the other two - give the point to X; else, if $w_y y$ is larger than $w_z z$ - give the point to Y; else, give the point to Z.

What is an efficient algorithm, with run-time polynomial in the output size, for enumerating all and only the allocations attainable by the above procedure?

I'd suggest using a recursive search.  Suppose you have a subset of $k$ of the points and a proposed allocation for those $k$ points into X/Y/Z.  Then you can test whether there exists $w_x,w_y,w_z$ that would lead to that allocation, by testing feasibility of a linear program.  (For the allocation to be feasible, there are a bunch of linear inequalities that must hold on the variables $w_x,w_y,w_z$; test whether these can all simultaneously hold.)

Now, given a feasible allocation for $k$ points, pick one more point and try all three possibilities for whether that additional point is allocated to X, Y, or Z.  (In other words, you extend it to three possible allocations on $k+1$ points.)  Test which ones are feasible, and recurse on each of the feasible ones.

One can show that if there are $N$ feasible allocations in all, then this process will require at most $3mN$ recursive invocations.  Each recursive invocation involves solving a linear program, which can be done in polynomial time.  Thus, we obtain a procedure whose running time is polynomial in the number of feasible allocations.  The same result generalizes to more than three dimensions.


Dynamic and/or practical succinct data structures for triangulations Does anybody know of any results on succinct data structures for triangulations that can be constructed efficiently, and preferably also updated efficiently?

Does anybody know of practical implementations of succinct data structures for triangulations?

Is there a good and up-to-date survey that discusses this topic?

Take a look at the theoretical work of Castelli et al.  and also the latest papers of J. Barbay.

"Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer: Succinct Representation of Triangulations with a Boundary. WADS 2005: 134-145"

"Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer: Dynamic updates of succinct triangulations. CCCG 2005: 134-137"

"Jérémy Barbay, Luca Castelli Aleardi, Meng He, J. Ian Munro: Succinct Representation of Labeled Graphs. Algorithmica 62(1-2): 224-257 (2012)"

For the implementation side, i would check CGAL and its triangulation data structures.


Quasipolynomial and polynomial time hierarchy Consider the following two scenarios:

$NP\subseteq RTIME[2^{(\log n)^c}]$ or $NP\subseteq DTIME[2^{(\log n)^c}]$, i.e., $NP$ can be solved in quasipolynomial randomized or deterministic time.
$NP$ has quasipolynomial size circuits.

Does the polynomial time hierarchy $PH$ collapse under any of the above conditions?

The first condition implies $EXP=NEXP$. Does the second imply the same or something weaker?

Could $P=BPP$ still hold in such situations?

Separately what implications follow from $EXP=NEXP$ and/or $EXP$ having quasipolynomial circuits?

If $NP$ can be solved in quasipolynomial time, then $NP$ has quasi polynomial size circuit.
The second condition implies that the exponential time hierarchy collapses to the second level (as was shown in the paper of Buhrman and Homer). It was improved the collapse to $S_2^{exp}$ in a paper of Pavan et al.
As far as I know, these hypotheses do not easily imply a collapse of PH.


How come Wikipedia says that Random Turing Machines can provide uncomputable output? Wikipedia article mentioned : Hypercomputation
The third paragraph starts off with:

Technically, the output of a random Turing machine is uncomputable; however, most hypercomputing literature focuses instead on the computation of deterministic, rather than random, uncomputable functions.

Furthermore, according to another article, Random Turing Machine:

In theoretical computer science, a probabilistic Turing machine is a non-deterministic Turing machine that chooses between the available transitions at each point according to some probability distribution.

Am I then correct to say, that in this context, the word random actually means unknown secondary input?
Because from my understanding:

Probability is a well defined area of mathematics
Randomness is rather a layman's term for "I don't really know what's going on here" or rather "I can't know what's going on here".

Sort of like seeds in PRNGs, an argument can be made that PRNGs are not random at all, after all, the very word pseudo-random is an oxymoron. Given an input and the "hidden input" (seed) I can get the same input back every time.
So in this context, is the output of a RTM reaaaallly uncomputable?

It's not uncommon for Wikipedia to say dubious things.  Don't trust it as a primary reference.  Beware that hypercomputation is potentially a "crank-adjacent" subject, so the Wikipedia article on it might be especially at risk of containing material of uncertain reliability.  When you find something in Wikipedia you don't understand, my advice is to look at primary sources, such as good textbooks on the subject.
The statement "the output of a random Turing machine is uncomputable" does not look accurate to me.  It's not even clear to me what that would mean.  I'm not sure how computability would be defined for probabilistic machines -- that would need to be specified before such a statement can be assigned any truth value.
No, in computer science "random" does not mean the same thing as "unknown".  In lay language "random" can mean "arbitrary" or "I don't understand it" or "hard to predict" or "I don't know what's going on here" or "I don't see an obvious pattern", but in computer science "random" has a  specific technical meaning taken from probability theory.  See, e.g., https://cs.stackexchange.com/q/13893/755, https://cs.stackexchange.com/q/7729/755.


What is a precise definition of "in-place"? "In-place" is a seemingly informal adjective used to describe algorithms. Does it have a precise definition?

To further clarify the discussion, what models of computation can we say are in-place? We can probably say whether a specific C program running on a specific machine is in-place. Can we say whether a C program is in-place, independent of its implementation? Can we say whether a Turing machine is in-place? Can we identify in-place algorithms with known complexity classes?

An in-place algorithm assumes its input is given in working memory, and it cannot use any other working memory than what the input initially occupies. We can consider any fixed amount of working memory to be part of the algorithm itself.

For example,

finite automata are in-place;
pushdown automata are not;
linear bounded automata are;
Turing machines are not.

A formalization of the notion can be a random-access machine with limited memory.


What if a problem is both in $\Pi_2^p$ and $NP$-hard? If a problem $P$ belongs to both $\Pi_2^p$ and $NP$-hard (thanks to some reduction from a $NP$-complete problem) but not to $NP$, does it imply that $P$ is $\Pi_2^p$-complete?

If the answer is no, are there some problems with these properties which have not been shown to be $\Pi_2^p$-complete?

The answer is "no".

In fact, in addition to the general argument pointed to by Tsuyoshi, there are a number of well-studied complexity classes which contain NP, but are contained in $\Pi_2^P$.

Two interesting containment chains are:

$NP \subseteq \Delta_2^P \subseteq S_2^P \subseteq \Sigma_2^P \cap \Pi_2^P \subseteq \Pi_2^P$

and

$NP \subseteq MA \subseteq BP \cdot NP = AM \subseteq \Pi_2^P$

To help clarify the letter soup, see Wikipedia's article on the Arthur-Merlin protocol and $S_2^P$. There's also of course the complexity zoo for descriptions of these various classes.

Also take a look at this question asking about canonical $\Delta_i^P$-complete problems.


How are imperative languages more different from each other than functional languages? I'm reading Simon Peyton Jones's The Implementation of Functional Programming Languages and there's one statement that surprised me a little bit (on page 39):

  To a much greater extent than is the
  case for imperative languages,
  functional languages are largely
  syntactic variations of one another,
  with relatively few semantic
  differences.

Now, this was written in 1987 and my thoughts on this subject might be influenced by more modern programming languages that weren't around or popular then.  However, I find this a bit hard to believe.  For instance, I think that the described Miranda programming language (an early predecessor to Haskell) has much more different semantics compared to a strict language like ML than say C has to Pascal or maybe even C has to smalltalk (although I'll cede that C++ provides some validation of his point :-).

But then again, I'm basing this on my intuitive understanding.  Is Simon Peyton Jones largely correct in saying this, or is this a controversial point?

Simon is basically correct, from an extensional point of view. We know pretty well what the semantics of modern functional languages are, and they really are relatively small variations of one another -- they each represent slightly different translations into a monadic metalanguage. Even a language like Scheme (a dynamically typed higher-order imperative language with first-class control) has a semantics which is pretty close to ML and Haskell's.

From a denotational point of view, you can start by giving a pretty simple domain equation for the semantics of Scheme -- call it $V$. People could and did solve equations like this in the late 70s/early 80s, so this isn't too bad. Similarly, there are relatively simple operational semantics for Scheme as well. (Note that when I say "Scheme", I mean untyped lambda calculus plus continuations plus state, as opposed to actual Scheme which has a few warts like all real languages do.)

But to get to a category suitable for interpreting modern typed functional languages, things get quite scary. Basically, you end up constructing an ultrametric-enriched category of partial equivalence relations over this domain. (As an example, see Birkedal, Stovring, and Thamsborg's "Realizability Semantics of Parametric Polymorphism, General References, and Recursive Types".) People who prefer operational semantics know this stuff as step-indexed logical relations. (For example, see Ahmed, Dreyer and Rossberg's "State-Dependent Representation Independence".) Either way, the techniques used are relatively new.

The reason for this mathematical complexity is that we need to be able to interpret parametric polymorphism and higher-order state at the same time. But once you've done this, you're basically home free, since this construction contains all the hard bits. Now, you can interpret ML and Haskell types via the usual monadic translations. ML's strict, effectful function space a -> b translates to $\left<a\right> \to T\left<b\right>$, and Haskell's lazy function space translates to $\left<a\right> \to \left<b\right>$, with $T(A)$ the monadic type of side effects interpreting the IO monad of Haskell, and $\left<a\right>$ is the interpretation of  the type ML or Haskell type a, and $\to$ is the exponential in that category of PERs.

So as far as the equational theory goes, since these languages can both be described by translations into slightly different subsets of the same language, it is entirely fair to call them syntactic variations of one another.

The difference in feel between ML and Haskell actually arises from the intensional properties of the two languages -- that is, execution time and memory consumption. ML has a compositional performance model (i.e., the time/space cost of a program can be computed from the time/space costs of its subterms), as would a true call-by-name language. Actual Haskell is implemented with call-by-need, a kind of memoization, and as a result its performance is not compositional -- how long an expression bound to a variable takes to evaluate depends on whether it has been used before or not. This is not modelled in the semantics I alluded to above.

If you want to take the intensional properties more seriously, then ML and Haskell do start to show more serious differences. It is still probably possible to devise a common metalanguage for them, but the interpretation of types will differ in a much more systematic way, related to the proof-theoretic idea of focusing. One good place to learn about this is Noam Zeilberger's PhD thesis.


What's the simplest to implement of all decent LTL-to-Buchi translation or other LTL verification algorithms? I'm writing a toy modelchecker, and I'm at the point where it's time to implement LTL to Buchi automata translation.

For a variety of obvious reasons, I wish the algorithm to be simple :) e.g. I want the code to remain extremely clear and concise for as long as possible.

I've looked at the "local automata + eventuality automata" approach, described in multiple tutorials, but it seems to be neither simple to implement/understand (the correctness proof is quite large), nor does it yield small automata. So I'm not implementing it until I'm sure I won't regret it :)

So, I'd be grateful for references to papers describing simple and efficient algorithms for this translation, or perhaps simple and inefficient ones - then papers on minimization of Buchi automata would be welcome too :)

...Or perhaps there are interesting alternative approaches to LTL verification?

For reference, here's a genealogy of LTL-to-Buchi translation algorithms http://spot.lip6.fr/wiki/LtlTranslationAlgorithms . Can anyone say something about these?

One construction not listed on the SPOT website is given in a survey by Demri & Gastin, Specification and Verification using Temporal Logics, 2009.  The construction is simple and yields reasonably small automata, so it can be carried out by hand for small formulæ, which is good for teaching (which is how I use it), but might also be helpful for debugging an implementation.  I wouldn't bet on it being more efficient than the one used by SPOT though.

About minimization, there is no canonical minimal Büchi automaton for a given $\omega$-regular language.  In order to get smaller automata, one can quotient the automaton by some simulation relation.  A classical paper on the subject is by Etessami, Wilke & Schuller, Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata, SIAM Journal on Computing 34: 1159--1175, 2005.


Classifying noetherian simple groups by order type? A (possibly infinite) group $G$ is noetherian if it satisfies the following equivalent conditions:

(1) every subgroup of $G$ is finitely generated,

(2) there is no infinite strict ascending chain of subgroups,

(3) any non-empty collection of subgroups has a maximal element under inclusion.

Note that this property is hereditary: if $G$ is noetherian then so are all its subgroups. Also, being noetherian is equivalent to require that the poset of subgroups $(Sub(G),\subseteq)$ is a well-order.

The order type of a well-order $(S,\leq)$ is defined as the supremum of the order type of its linear extensions. By extension, we may define the order type of a noetherian group $G$, denoted by $ot(G)$, as the order type of $(Sub(G),\subseteq)$. We may then ask the following questions:

(1) What ordinals $\alpha$ can be obtained as the order type of a noetherian
group?

(2) Is it possible to reduce that question to noetherian simple groups? For instance, if $H$ is a normal subgroup of $G$, is it true that $ot(G) = ot(H) + ot(G/H)$?

Here's an argument handling a special case. Consider a fixed poset $P = (S,\leq)$. Say that a (well-founded) forest $F$ is a branching-representation of $P$ if:

the nodes of $F$ are bijectively labelled by the elements of $P$;
for each node $u$ of $F$, its children are ???

(SORRY, CAN'T FIGURE THE RIGHT DIFINITION NOW, I'M PUTTING THIS ON STANDBY)

We may then assign an ordinal $o(u)$ to each node of $T$ inductively: (i) if $u$ is a leaf then $o(u) = 1$, (ii) if $u$ has children $(u_i)$, then $o(u) = \sum_i o(u_i)$. The order type of $T$ is then defined as $o(T) = o(r)$ where $r$ is the root.

Is the following true?

  Conjecture: the order type of $P$ equals the minimum of $o(T)$ over all possible branching-representations $T$ of $P$.

Suppose this is true. Consider a poset $P = (S,\leq)$, and let $P^{\natural} = (S',\leq')$ where $S'$ consists of the finite antichains of $S$ and where the order satisfies $X \leq Y$ iff there is an injection $\phi : X \rightarrow Y$ s.t. $u \leq \phi(u)$ (f.a. $u \in X$). Suppose that $ot(P) = \lambda$ with $\lambda$ a limit ordinal, it should then follow that $ot(P^{\natural}) = \omega^{\lambda}$: starting with a b.p. $T$ of $P$, we would construct a b.p. $T'$ for $P^{\natural}$ by 'iterated substitution'.

This might help to analyze the case of ordered free groups. In this case, we have an ordered alphabet $P = (S,\leq)$, and we consider the free group $P^{\sharp}$ over $\{S \cup S^{-1}\}^*$, equipped by the relation $u \preceq v$ iff $u_i \leq v_{\phi(i)}$ for some injection $\phi$. Now, given an element $B = \{b_1,\ldots,b_k\} \in (P^{\sharp})^{\natural}$, we may define the subgroup $\langle B \rangle$ of $P^{\sharp}$ generated by $\cup_{i = 1}^{k} (b_i \downarrow)$.

It follows that the map $\chi : (P^{\sharp})^{\natural} \rightarrow Sub(P^{\sharp})$ defined by $\chi(B) = \langle B \rangle$ is surjective. Consider the equivalence over $(P^{\sharp})^{\natural}$ s.t. $B \sim B'$ iff $\chi(B) = \chi(B')$. Assuming that the equivalence classes of $\sim$ are finite (which seems intuitively true), I think that it would imply $ot(Sub(P^{\sharp})) = ot((P^{\sharp})^{\natural}) = \omega^{\omega^{\omega^{\lambda}}}$ (possibly up to some lower degree terms).

So if the above is correct, you've got at least the ordinals of the form $\omega^{\omega^{\omega^{\lambda}}}$ in question (1).


Parallel pseudorandom number generators This question is primarily related to a practical software-engineering problem, but I would be curious to hear if theoreticians could provide more insight in it.

Put simply, I have a Monte Carlo simulation that uses a pseudorandom number generator, and I would like to parallelise it so that there are 1000 computers running the same simulation in parallel. Therefore I need 1000 independent streams of pseudorandom numbers.

Can we have 1000 parallel streams with the following properties? Here $X$ should be a very well-known and widely-studied PRNG with all kinds of nice theoretical and empirical properties.

The streams are provably as good as what I would get if I simply used $X$ and split the stream generated by $X$ into 1000 streams.
Generating the next number in any stream is (almost) as fast as generating the next number with $X$.

Put otherwise: can we get multiple independent streams "for free"?

Of course if we simply used $X$, always discarding 999 numbers and picking 1, then we certainly would have property 1, but we would lose in the running time by factor 1000.

A simple idea would be to use 1000 copies of $X$, with seeds 1, 2, ..., 1000. This certainly would be fast, but it is not obvious if the streams have good statistical properties.

After some Googling, I have found, for example, the following:

The SPRNG library seems to be designed for exactly this purpose, and it supports multiple PRNGs.
Mersenne twister seems to be a popular PRNG nowadays, and I found some references to a variant that is able to produce multiple streams in parallel.

But all this is so far from my own research areas, that I couldn't figure out what is really the state-of-the-art, and which constructions work well not only in theory but also in practice.

Some clarifications: I do not need any kind of cryptographic properties; this is for scientific computation. I will need billions of random numbers, so we can forget any generator with a period of $< 2^{32}$.

Edit: I cannot use a true RNG; I need a deterministic PRNG. Firstly, it helps a lot with debugging and makes everything repeatable. Secondly, it allows me to do, e.g., median-finding very efficiently by exploiting the fact that I can use the multi-pass model (see this question).

Edit 2: There is a closely related question @ StackOverflow: Pseudo-random number generator for cluster environment.

There seem to be many ways to tackle this problem, but one simple way would be to use the Blum Blum Shub PRNG. This PRNG is defined by the recurrance relation $x_{i+1} = x_i^2 \mbox{ mod }N$, where $N$ is a semiprime. To get a random bit out of this you can simply take the bit parity of $x_i$. What's nice about this is that since $x_{i+k} = x_i^{2^k}\mbox{ mod }N = x_i^{2^k \mbox{ mod } \lambda(N)}\mbox{mod }N$ you can directly calculate any step in time constant in $k$ (i.e. $O(\log(N)^3)$ or faster depending on which multiplication algorithm you use for the modular exponential). Thus is you have $M$ machines, then for the machine indexed by $y$ you can use the generator $x_{i+1,y} = x_i^{2^M \mbox{mod }\lambda(N)}\mbox{ mod }N$, where $x_{0,y} = x_0^{2^y \mbox{ mod }\lambda(N)}\mbox{ mod }N$, where $x_0$ is your seed. Conveniently this generates exactly the same stream of numbers as if you used a single stream and distributed it's output to each of the machines in turn.

This isn't the fastest of PRNGs, though, so it will only be useful if the overhead of whatever you are doing in the simulation is significantly more than the cost of the PRNG. However it is worth pointing out that it will be much faster for certain combinations of $M$ and $N$ than others, particularly if the binary representation of $2^M \mbox{ mod }\lambda(N)$ contains few 1s or is small.


Primitive Recursive Isomorphisms What is the relationship between invertible primitive recursive functions (that is, a primitive recursive function that is an isomorphism) and all primitive recursive functions? Can every primitive recursive function be mimicked in some way (like Bennett’s result about reversible computation) by a reversible/invertible primitive recursive function?  Using pairing functions and Godel numbering can we look at all invertible primitive recursive functions from N to N?

Also, has anyone ever looked at the group of all invertible primitive recursive functions from N to N? Are there generators to this group? Can we talk about properties of this group? What is the relationship with its supergroup of all recursive isomorphisms? What about its relationship with the monoid of all primitive recursive functions from N to N? What about the monoid of all recursive functions from N to N?

Yes, people have looked at this and related groups, though not a whole lot as far as I can tell. For example:

Morozov, A. S. Turing reducibility as algebraic embeddability. Siberian Math. J. 38 (1997), no. 2, 312–313. Let $G_d$ denote the group of permutations of $\mathbb{N}$ computable below the Turing degree $d$. Morozov shows that $d_1 \leq_{T} d_2$ if and only if $G_{d_1} \hookrightarrow G_{d_2}$. (Note that a permutation and its inverse always have the same Turing degree. This no longer holds if we restrict to primitive recursive or poly-time reductions.)

Kent, C. F. Constructive analogues of the group of permutations of the natural numbers. Trans. Amer. Math. Soc. 104 (1962) 347–362.

In fact, if I recall correctly, the primitive recursive permutations generate the group of all computable permutations. (If you restrict attention to the group of permutations $\pi$ such that both $\pi$ and $\pi^{-1}$ are primitive recursive, you get a smaller group.) Furthermore, every computable permutation can be written as a word of length six in the primitive recursive permutations and their inverses. I think the same result holds if you replace "primitive recursive" by "polynomial time." [I don't recall the reference just now, but I have a physical copy of the paper at home. I will post the reference when I return from traveling.]

Slightly different but related:

Combarro, E. F. Classification of subsets of natural numbers by computable permutations. Siberian Math. J. 45 (2004), no. 1, 125–135.

The group of computable permutations is not finitely generated (Is that what you meant by "Are there generators to this group?" Every group has generators, for example, the entire group...). If it were, then there would be a c.e. set $I$ of indices such that the set $\{\varphi_i : i \in I\}$ was exactly the set of computable permutations (where $\varphi_i$ is the $i$-th computable function in some acceptable enumeration). It then takes a little argument to show that this cannot happen (start from the fact that the set of all indices of computable permutations is $\Pi^0_2$-complete).


Rules about Prop and Set in UTT In Luo's UTT (type theory which is used in Agda, Idris, and other dependently typed programming languages), there're are two rules for $\Pi$ types. One for $\mathsf{Prop}$ and one for $\mathsf{Set}$. In the one for $\mathsf{Prop}$ we have no constraints on the universe of a parameter. In the one for $\mathsf{Set}(i)$, we have.

Why it was done in this way? Will anything bad happen in such a case?

P.S. Basically I want to understand why $\mathsf{Prop}$ has special treatment in the theory. I.e. why we can't choose $\mathsf{Type}(0)$ for propositions, then removed the $\mathsf{Type}(i)$ condition in the $\Pi$ types' argument, and as a consequence have more uniform set of axioms.

P.P.S. In Luo's thesis I read that Calculus of inductive constructions (CIC) where this universe was introduce was created as a mix between Martin-Löf type theory (MLTT) and System F. Does $\mathsf{Prop}$ correspond to the union of all the existing universes?

P.P.P.S. UTT is described in Luo's PhD thesis and book here: http://www.cs.rhul.ac.uk/home/zhaohui/books.html

Say that a universe $U$ is impredicative if the product $\prod_{x : A} B(x)$ is in $U$ whenever $B(x)$ is in $U$ for all $x$, and $A$ is arbitrary, i.e., not necessarily in $U$.

Are there any impredicative universes? Let us think about what an impredicative universe would be for sets: a set $U$ such that for every family of sets $B : A \to U$, no matter how large $A$ is, $\prod_{x : A} B(x)$ is in $U$. That's only possible in two cases: when $U$ contains the singleton (or many copies of it) and when it contains the empty set and the singleton (or many copies of it). This is so because a product of sets which are all singletons or empty is again such a set. If $U$ contains a set $S$ with at least two elements then $S^U$ (which is a special case of a product) will fail to be contained in $U$ for cardinality reasons.

Of course, we recognize that the case $U = \{\emptyset, \{\emptyset\}\}$ is just the case when $U$ is the set of truth values, i.e., $\mathsf{Prop}$. This is one reason why $\mathsf{Prop}$ is treated differently: it is impredicative – not only in classical set theory but also more generally, because truth values are closed under $\forall$. Note that $\forall$ and $\prod$ coincide on families of sets that all contain at most one element.

In system $F$ we have impredicativity because types there are closed under $\forall$ ranging over the whole universe of types, and $\forall$ behaves like $\prod$.

One could hope that there are other models, where for instance $\mathsf{Type}_i$ is impredicative. Indeed, there are realizability models of (extensional) type theory that contain an impredicative universe of sets (as opposed to truth values). However, one cannot have two impredicative universes such that one is a member of the other, because one can then cook up a Burali-Forti paradox.


Partition of a set of integers into subsets with prescribed sums I saw this problem:

A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,...,S_k$ such that $\sum_{x\in S_i} x = m_i$ for each $1\leq i \leq k$.

in the paper "PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH
PRESCRIBED SUMS", by Fu-Long Chen, Hung-Lin Fu, Yiju Wang and Jianqin Zhou

http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028

They have solved the problem under certain constraints. But I can't find anything about its complexity in general. Does anyone know a reference about the complexity of this problem?
It reminds me of the bin-packing problem, or in some sense, it is similar to the subset sum problem. So, I guess it must be NP-complete in general?

More precisely, I like to prove the NP-completeness for the fixed value of $k$, for example, when $k = 3, 4, \ldots$?
In this case, it is very similar to bin-packing or knapsack problem, but as we want the equality it is different. Maybe there are variations of these problems that match my question?

For any fixed $k$, isn't it in P, by dynamic programming?

For each $i\in\{0,\ldots,n\}$ and $t_1, t_2, ..., t_k$ such that each $t_i \in \{0,\ldots,m_i\}$, define $S(i, t_1, t_2, \ldots, t_k)$ to be true iff $(t_1, t_2, .., t_k)$ is $i$-realizable.  Then there are $O(n^{2k+1})$ such subproblems (assuming WLOG that $\max_i m_i\le n^2$), and you have a recurrence like

$ S(i, t_1, t_2, \ldots, t_k)$

$~ = S(i-1, t_1 - i, t_2, \ldots, t_k) $

$~\vee~ S(i-1, t_1, t_2 - i, t_3, \ldots, t_k)$

$~\vee~ \cdots$

$~\vee~ S(i-1, t_1, t_2 , t_3, \ldots, t_{k-1}, t_k- i)?$


Separating DAGs using separators consisting of lists of nodes and all ancestors Suppose we are given a DAG, $G = (V, E)$ where $n = |V|$. We consider the sets $J_1, J_2, \dots, J_n$ to be lists of vertices where list $J_i$ consists of vertex $v_i \in V$ and all ancestors of $v_i$. I want to find a set of lists $\mathcal{J}$ such that removing all vertices in $\mathcal{J}$ from $G$ results in disjoint subgraphs where each subgraph has at most $O(1)$ vertices. Has anyone seen an algorithm in any work that solves this problem and finds a minimum number of lists in $\mathcal{J}$ efficiently? It also seems to me that there exists a $\mathcal{J}$ for any DAG $G$ that has size $O(\log n)$ always. This seems like a question that should be closely related to finding balanced separators but I haven't seen anything yet in this literature regarding this specific or a closely related problem.

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path.
This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover:
Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to every set that contains it.
Now picking a list corresponding to a set means deleting the set and all the elements in it.
For every element add some new dummy vertices and add arcs from each element to its own private dummy vertices.
Now observe that as long as all elements have not been deleted there are still components of more than $O(1)$ vertices left - an element plus its dummies.


Appilicability of Theoritical Computer Science in Malware research I would like to know the importance of TCS in Malware research. Due to the large volume of new malware variants received per day (~50,000 samples/day according to McAfee), malware researchers are heavily dependent on dynamic analysis (i.e. running the samples in a sandbox and monitoring their behavior) and moving away from static analysis and Reverse engineering as these approaches are very time consuming and sometimes becomes very challenging due to  obfuscation/encryption.

I found a very useful talk (BlackHat 2010) by Greg Hoglund on Malware attribution where the speaker talks about the importance of bringing in the malware authors and their networks into the picture which gives valuable information than just analyzing the binary itself.

I have two questions:

If malware researchers move towards analyzing the behavior of malware authors and their network, in the future does TCS has any importance in malware research.
As I am not strong in TCS, I would like to know where exactly TCS fits
in malware research.

Thank you.

Fred Cohen is an authority & early researcher on the theory of computer viruses.  see that wikipedia page for references. his 1987 paper is given credit as maybe the 1st analogy of the virus checking problem to the halting problem.

the basic idea is to create a program X that calls a virus checking subroutine with a program code as parameter. then, if the subroutine returns "is a virus", exit. if it returns "is not a virus", infect the system. such a program cannot exist by diagonalization/contradiction, passing its own code as the parameter. therefore there is no perfect virus checker.

but it would seem an easy counterargument to this statement could be, program X contains a harmful section of code, and that its irrelevant whether it is called or not-- the program is potentially harmful if it contains any "harmful section of code".

as I recall this result was published separately in a mathematical journal but cant find the reference right now.

a more recent/advanced topic is detecting polymorphic viruses that change their code in equivalent but random ways.

another promising approach that seems to avoid the halting problem issue (in a way that demonstrates abstract theoretical "no-go theorems" can be misleading or even inapplicable in practice) is to create a secure "sandbox" in which a program can run but cannot do anything harmful.

the modern web browser can be seen as an attempt to build such a system. the complexity of securing it arises mainly with Javascript.

Google is building the NaCL[3] framework that partly originated in academia and is the current leading contender for a high functional sandbox system integrated into the modern browser that still allows machine code. a provably secure software checker validates candidate programs. there are recent dramatic improvements announced[4].

a novel recent idea is to use graph based analysis of execution traces[5].

a more recent topic of virtualization has various security implications/applications as you note eg virus vendors building virtualization systems to find/detect viruses etc.[6]

the sophistication of the recent stuxnet virus, apparently the worlds 1st state/govt-sponsored, military-agency-developed virus for cyber/espionage/sabotage purposes, has led to serious/heavy academic study, see the extensive references on wikipedia. there is a recent/new variant discovered targeting the financial industry called flame.

[1] An Undetectable Computer Virus David M. Chess and Steve R. White

[2] Trends in computer virus research Cohen, 1991

[3] Native Client: A Sandbox for Portable, Untrusted x86 Native Code by Yee et al 2009

[4] NaCl to give way to RockSalt: Computer scientists develop a tool to improve software fault isolation 2012

[5] Graph-based malware detection using dynamic analysis by Anderson et al

[6] Detection of Metamorphic and Virtualization-based
Malware using Algebraic Specification by Webster, Malcolm


Combinations with symbols Suppose we have the following symbols: $\{a,b\}$. Now there are some rules. More than 3 $b$'s are now allowed and $aa$ is not allowed. So $ababab$ is allowed, but for example $abbbbaba$ not (more than 3 $b$'s). There is an easy way to get this working. Suppose you have a string of $n$ characters. Just add between every two numbers a new number so the string is correct. Decoding is not hard: just remove all numbers on even positions. So $abbbbaba \rightarrow axbxbxbxbxaxbxax$ and decoding is the same as just removing the $x$'s. But the problem is that the string size doubles. Is there a more efficient way to accomplish encoding and decoding? So encoding means encode all strings to valid strings and decoding means decode that string back to the original string.

This is called run-length-limited coding, there has been lots of research done on it by the information theory community, and I will just refer you to the existing literature. After a brief glance at the wikipedia article I linked to, my impression is that you shouldn't rely on the references it contains, but do your own search of the literature.

One simple thing you could do that does better than doubling the string size is:

(1) add a 0 to the end of the original sequence,
(2) break the original sequence greedily into blocks of either 0, 10, or 11,
(3) encode using the encoding

     0 → ab
  10 → abb
  11 → abbb

Step (2) is always possible, since after step (1) the sequence ends with a 0. Except for step (1), which adds at most two bits to your encoded sequence, this cannot do worse than double the string size, and generally does better.

For example, you encode
0110100101 → 0.11.0.10.0.10.10 → ababbbababbababbabb,
taking 10 characters into 19.

If I did my calculations right, starting with $n$ random bits, this encoding gives an expected length of 11/6 $n$ bits, which is only slightly more than the optimal value of around 1.813 $n$ bits.


What is resolution ((in FOL))? I'm searching for an authoritative definition of resolution (logic resolution).

Preferably on a reference freely available on the Internet (so I can read it right now).

If this is too broad then resolution for first order logic.

Thank you.

Unlike the question you threaten for inference rule, this has a nice, simple answer:

  Robinson (1965) A machine-oriented logic based on the resolution principle. Journal of the ACM.

Resolution only applies to a subfragment of FOL, the Horn clauses, that lack disjunction and existential quantification, but combined with Herbrandisation, this is sufficient to encode satisfiability in the following sense: for any formula of FOL, we can find a Horn clause such that each is satisfiable if the other is.

Resolution is related to cut-elimination, but is more efficient.

Extending resolution to the whole of FOL requires a more sophistcated approach to unification than Robinson's algorithm.  Uniform provability offers a technique for reading off such a computational mechanism from a cleaned-up proof theory of intuitionistic logic, higher-order unification, and the double-negation translation.


Search for all nearest neighbors within a certain radius of a point in 3D? I have about 80 million spatial points(3D) and I want to find all the nearest neighbors of a query point which lie under a sphere of a certain radius(can be given as input) with the query point as center.

I have read about some data structures that are used for such kind of search, such as Kd-trees, octrees or range trees. For my application, I only need to populate the data structure once and then search for multiple query points.

My question is:

Is there any better way or a better data structure than Kd-trees in this case?

With kd trees, I'll have to find the median of such a large dataset multiple times, which may take a lot of time to populate the tree.

I don't know much about any of these data structures so could you please refer some tutorials about whatever solution you may recommend. I know this question may seem repeated but from all the questions I found and read, no one was using such a large set of points.

My recommendation is NOT to roll your own for now. There are two software packages that I'd recommend you try first.

ANN (by Arya and Mount) is state-of-the-art for low dimensional near neighbor search and includes the "fixed radius" search that you're looking for.
Nearpt3 (Wm Randolph Franklin) is another package that is specifically optimized for 3D, and supposedly can handle 100s of millions of points. I'm not entirely sure it handles fixed radius queries as well as regular nearest neighbor search, but you can look into it.

If neither of these is appropriate, then you can return and ask :).


Coloring complexity of graphs Suppose $G$ is a graph with coloring number $d = \chi(G)$. Consider the following game between Alice and Bob. At each round, Alice picks a vertex, and Bob answers with a color in $\{1,\ldots,d-1\}$ for this vertex. The game ends when a monochromatic edge is discovered. Let $X(G)$ be the maximal length of the game under optimal play by both players (Alice wants to shorten the game as possible, Bob wants to delay it as possible). For example, $X(K_n) = n$ and $X(C_{2n+1}) = \Theta(\log n)$.

Is this game known?

It looks fairly similar to

  Coloring random graphs online without creating monochromatic subgraphs (Reto Spöhel, Torsten Mütze, and Thomas Rast)
  Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), PR 137, 145-158.

SODA PDF
Journal version
Conference proceedings


What are the differences between logical relations and simulations? I'm a beginner working on methods proving program equivalence. I've read a few papers about defining logical relations or simulations to prove two programs are equivalent. But I am quite confused about these two techniques.

I only know logical relations are inductively defined while simulations are based on coinduction. Why are they defined in such ways? What are their pros and cons respectively? Which one should I choose in different situations?

I have an answer to this question which is possibly novel.  In fact, I am still thinking through it for the last 6 months or so, and it hasn't been written about in papers yet.

The general thesis is that relational reasoning principles like "logical relations", "simulations", and even "invariants" are manifestations of data abstraction or information hiding.  Wherever there is information hiding, these principles crop up.

The first people to discover it were automata theorists.  Automata have hidden state.  So you need relational reasoning to talk about their equivalence.  Automata theorists struggled with homomorphisms for a while, gave up, and came up with a notion called "relational covering", which is a form of simulation relations.

Milner picked up the idea in a little-known but very fundamental paper called "An algebraic notion of simulation between programs" in 1971.  Hoare knew it and used it in coming up with "Proof of correctness of data representations" in 1972 (but used abstraction functions instead of relations because he thought they were "simpler").  He later retracted the simplicity claim and went back to using relations in "Data refinement refined".  Reynolds used relational reasoning in "Craft of Programming", Chapter 5 (1981).  He thought relations were more natural and general than abstraction functions.  If you go back and read this chapter, you will find relational parametricity ideas lurking around, waiting to be discovered.  Sure enough, two years later, Reynolds published "Types, abstraction and parametric polymorphism" (1983).

It looks like all these ideas have nothing to do with types, but they really do.  Stateful languages and models have built-in data abstraction.  You don't need to define an "abstract data type" to get information hiding.  You just declare a local variable and hide it.  We can teach it to first year students in Java classes in the first few weeks.  No sweat.

Functional languages and models, on the other hand, have to get their information hiding via types.  Functional models don't have built-in data abstraction.  We have to add it on explicitly, using $\forall$ or $\exists$.  So, if you translate a stateful language into a functional language, you will notice all the local state getting translated into type variables.  For an explicit description of how this works, see my paper "Objects and classes in Algol-like languages", but the ideas really come from Reynolds 1981 ("The Essence of Algol"). We are just understanding those classic ideas better now.

Take two machines $M$ and $M'$ that you want to prove equivalent.  Milner 1971 says, define a relation between the states of $M$ and $M'$ and show that the two machines preserve the relation.  Reynolds parametricity says, think of the states of the machines as belonging to types $X$ and $X'$.  Define a relation $R$ between them.  If the machines are of type $F(X)$ and $F(X')$, parameterized by the types of their states, then check that the two machines are related by the relation $F(R)$.

So, simulations and relational parametricity are essentially the same idea.  It is not merely a superficial resemblance.  The former is made for stateful languages where there is built-in data abstraction.  The latter is made for stateless languages where data abstraction is obtained via type variables.

What about logical relations then?  On the surface, logical relations appear to be a more general idea.  Whereas parametricity talks about how to relate type variables within the same model, logical relations appear to relate types across different models.  (Dave Clarke wrote a brilliant exposition of this earlier.)  But my feeling is (and it still needs to be demonstrated) that this is an instance of some form of higher-type parametricity which hasn't yet been formulated.  Stay tuned for more progress on that front.

[Note added] The connection between logical relations and simulations is discussed in our recent paper Logical relations and parametricty: A Reynolds programme for Category Theory and Programming Languages.