Permutation game redux This is a restatement of an earlier question.

Consider the following impartial perfect information game between two players, Alice and Bob.  The players are given a permutation of the integers 1 through n.  At each turn, if the current permutation is increasing, the current player loses and the other player wins; otherwise, the current player removes one of the numbers, and play passes to the other player.  Alice plays first.  For example:

(1,2,3,4) — Bob wins immediately, by definition.
(4,3,2,1) — Alice wins after three turns, no matter how anyone plays.
(2,4,1,3) — Bob can win on his first turn, no matter how Alice plays.
(1,3,2,4) — Alice wins immediately by removing the 2 or the 3; otherwise, Bob can win on his first turn by removing the 2 or the 3.
(1,4,3,2) — Alice eventually wins if she takes the 1 on her first turn; otherwise, Bob can win on his first turn by not removing the 1.

Is there a polynomial-time algorithm to determine which player wins this game from a given starting permutation, assuming perfect play?  More generally, because this is a standard impartial game, every permutation has a Sprague–Grundy value; for example, (1,2,4,3) has value *1 and (1,3,2) has value *2.  How hard is it to compute this value?

The obvious backtracking algorithm runs in O(n!) time, although this can be reduced to $O(2^n poly(n))$ time via dynamic programming.

The "permutation game" is isomorphic to the following game:

  Disconnect. Players alternately remove vertices from a graph $G$.  The player that produces a fully disconnected graph (i.e., a graph with no edges) is the winner.

The graph $G_{\pi}$ corresponding to a particular initial permutation $\pi\in S_n$ contains just those edges $(i,j)$ for which $i-j$ and $\pi(i)-\pi(j)$ have opposite signs.  That is, each pair of numbers in the wrong order in the permutation is associated with an edge.  Clearly the allowed moves are isomorphic to those in the permutation game (remove a number = remove a node), and the winning conditions are isomorphic as well (no pairs in descending order = no edges remaining).

A complementary view is obtained by considering playing a "dual" game on the graph complement $G^{c}_\pi = G_{R(\pi)}$, which contains those edges $(i,j)$ for which $i$ and $j$ are in the correct order in the permutation.  The dual game to Disconnect is:

  Reconnect. Players alternately remove vertices from a graph $G$.  The player that produces a complete graph is the winner.

Depending on the particular permutation, one of these games may seem simpler than the other to analyze.  The advantage of graph representation is that it is clear that disconnected components of the graph are separate games, and so one hopes for some reduction in complexity.  It also makes the symmetries of the position more apparent.  Unfortunately, the winning conditions are non-standard... the permutation game will always end before all moves are used up, giving it something of a misère character.  In particular, the nim-value cannot be calculated as the nim-sum (binary XOR) of the nim-values of the disconnected components.

For Disconnect, it is not hard to see that for any graph $G$ and any even $n$, the game $G \cup \bar{K}_n$ is equivalent to $G$ (where $\bar{K}_n$ is the edgeless graph on $n$ vertices).  To prove it, we need to show that the disjunctive sum $G + G\cup\bar{K}_n$ is a second-player win.  The proof is by induction on $|G|+n$.  If $G$ is edgeless, then the first player loses immediately (both games are over).  Otherwise, the first player can move in either $G$, and the second player can copy his move in the other one (reducing to $G' + G'\cup \bar{K_n}$ with $|G'|=|G|-1$); or, if $n\ge 2$, the first player can move in the disconnected piece, and the second player can do the same (reducing to $G + G\cup\bar{K}_{n-2}$).

This shows that any graph $G$ is equivalent to $H \cup K_p$, where $H$ is the part of $G$ with no disconnected vertices, and $p=0$ or $1$ is the parity of the number of disconnected vertices in $G$.  All games in an equivalence class have the same nim-value, and moreover, the equivalence relation respects the union operation: if $G \sim H \cup K_p$ and $G' \sim H' \cup K_{p'}$ then $G \cup G' \sim (H \cup H')\cup K_{p\oplus p'}$.  Moreover, one can see that the games in $[H \cup K_0]$ and $[H \cup K_1]$ have different nim-values unless $H$ is the null graph: when playing $H + H \cup K_1$, the first player can take the isolated vertex, leaving $H+H$, and then copy the second player's moves thereafter.

I do not know any related decomposition results for Reconnect.

Two special types of permutations correspond to particularly simple heap games.

The first is an ascending run of descents, e.g., $32165487$.  When $\pi$ takes this form, the graph $G_{\pi}$ is a union of disjoint cliques, and the game of Disconnect reduces to a game on heaps: players alternately remove a single bean from a heap until all heaps have size $1$.
The second is a descending run of ascents, e.g., $78456123$.  When $\pi$ takes this form, the graph $G^{c}_{\pi}$ is a union of disjoint cliques, and the game of Reconnect reduces to a game on heaps: players alternately remove a single bean from a heap until there is only one heap left.

A little thought shows that these two different games on heaps (we can call them 1-Heaps and One-Heap, at some risk of confusion) are, in fact, themselves isomorphic.  Both can be represented by a game on a Young diagram (as initially proposed by @domotorp) in which players alternate removing a lower-right square until only a single row is left.  This is obviously the same game as 1-Heaps when columns correspond to heaps, and the same game as One-Heap when rows correspond to heaps.

A key element of this game, which extends to Disconnect and Reconnect, is that the duration is related to the final game state in a simple way.  When it is your turn, you will win if the game has an odd number of moves remaining, including the one you're about to make.  Since a single square is removed each move, this means you want the number of squares remaining at the end of the game to have the opposite parity that it has now.  Moreover, the number of squares will have the same parity on all of your turns; so you know from the outset what parity you want the final count to have.  We can call the two players Eve and Otto, according to whether the final count must be even or odd for them to win.  Eve always moves in states with odd parity and produces states with even parity, and Otto is the opposite.

In his answer, @PeterShor gives a complete analysis of One-Heap.  Without repeating the proof, the upshot is the following:

Otto likes $1$-heaps and $2$-heaps, and can tolerate a single larger heap.  He wins if he can make all heap sizes except one $\le 2$, at least without giving Eve an immediate win of the form $(1,n)$.  An optimal strategy for Otto is to always take from the second-largest heap except when the state is $(1,1,n>1)$, when he should take from the $n$.  Otto will lose if there are too many beans in big heaps to start with.
Eve dislikes $1$-heaps.  She wins if she can make all heap sizes $\ge 2$.  An optimal strategy for Eve is to always take from a $1$-heap, if there are any, and never take from a $2$-heap.  Eve will lose if there are too many $1$-heaps to start with.

As noted, this gives optimal strategies for 1-Heaps as well, although they are somewhat more awkward to phrase (and I may well be making an error in primary-to-dual "translation").  In the game of 1-Heaps:

Otto likes one or two large heaps, and can tolerate any number of $1$-heaps.  He wins if he can make all but the two largest heaps be $1$-heaps, at least without giving Eve an immediate win of the form $(1,1,\dots,1,2)$.  An optimal strategy for Otto is to always take from the third-largest heap, or from the smaller heap when there are only two heaps.
Eve dislikes a gap between the largest and second-largest heaps.  She wins if she can make the two largest heaps the same size.  An optimal strategy for Eve is to always take from the largest heap, if it is unique, and never if there are exactly two of the largest size.

As @PeterShor notes, it isn't clear how (or if) these analyses could be extended to the more general games of Disconnect and Reconnect.


Exact number of comparisons to compute the median Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element from an unsorted set of size $n$, for all $1\le t \le n\le 10$.  This table, along with the well-known closed-form expressions $V_1(n) = n-1$ and $V_2(n) = n - 2 + \lceil n/2 \rceil$, represents most of the state of the art as of 1976.

Have any more exact values of $V_t(n)$ been computed in the last 36 years?  I'm particularly interested in exact values of $M(n) = V_{\lceil n/2 \rceil}(n)$, the minimum number of comparisons required to compute the median.

As @MarkusBläser points out, Knuth's table seems to already incorporate more recent results from Bill Gasarch, Wayne Kelly, and Bill Pugh (Finding the ith largest of n for small i,n. SIGACT News 27(2):88-96, 1996.)

Kenneth Oksanen has published an expanded table of values up to $n=15$, based on his own computer search.  Okansen also provides descriptions of the optimal comparison trees for most of the values he reports.  Here's a screenshot of his table:

Thanks to @MarkusBläser for the lead!


Is the isomorphism problem between posets represented by DAGs GI-complete? Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?

I believe this problem is equivalent to asking whether their transitive closures (or their transitive reductions) are isomorphic.

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI.

The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a bipartite graph into a DAG, that is, either directing all edges from partition 1 to partition 2 or directing all edges from partition 2 to partition 1.


Average height of the least common ancestor of 2 random nodes in a binary tree We have a binary tree with height $h$, and for the sake of analysis assume it's a complete tree.

If we pick two nodes at random (with or without replacement, your choice), what is the expected height of the subtree rooted at the least common ancestor of those nodes?

I believe I've calculated the first few results, by exhaustive case analysis (for the situation of choosing a node at random with replacement, i.e. both nodes may be the same):

Tree height 1 (1 node), height of subtree: 1

Tree height 2 (3 nodes), height of subtree: 1.666... (5/3)

Tree height 3 (7 nodes), height of subtree: 2.551... (125/49)

What is the actual formula?

It took me a while to see the nice formula, but there is one.
Consider a node $w$ at height $k$. The root is at height $h$ and the leaves at height $1$.

The probability that $w$ is the least common ancestor of the two nodes is the probability that:

  (1) Both random nodes are in the subtree rooted at $w$;

and we do not have that

  (2) Both nodes are in $w$'s left subtree or both nodes are in $w$'s right subtree.

The size of a subtree at height $k$ is $2^k-1$.
The probability of #1 is therefore $\left(\frac{2^k-1}{2^h - 1}\right)^2$. The probability of #2 is $2 \left(\frac{2^{k-1}-1}{2^h - 1}\right)^2$.

The probability of the event that #1 happens and #2 does not (since #2 is a subset of #1) is thus
\begin{align}
\Pr[\text{$w$ at height $k$ is lca}] &= \frac{\left(2^k-1\right)^2 - 2\left(2^{k-1}-1\right)^2}{\left(2^h - 1\right)^2} \\
&=\frac{2^{2k-1} - 1}{\left(2^h -1 \right)^2}
\end{align}
once you work it out. (You can check that these probabilities sum to $1$.)

There are $2^{h-k}$ nodes at height $k$. So the probability that the lca is at height $k$ is $\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2}$.

The expected height is thus
\begin{align}
  &\sum_{k=1}^h (k)\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2} \\
  &\approx \sum_{k=1}^h \frac{(k)\left(2^{k-1} - 2^{-k}\right)}{2^h} \\
  &\approx h - 1 - \Theta\left(\frac{1}{2^h}\right) .
\end{align}
Simulations bear this out up to three decimal points anyway. By the way, this is very easy to simulate: Suppose the nodes are numbered $1,2,\dots, 2^h - 1$. Pick two random numbers from this range. Now each node $x$'s parent is $\lfloor \frac{x}{2} \rfloor$. To find the lca of two numbers, continue halving (and rounding down) the larger number until they are equal. To find the height of a number, continue halving (and rounding down) until it is one and count the steps. So if your random number generator is comfortable giving you random numbers in the range $[1,2^{100}]$ (as python's seems to be) then you can simulate easily.


Results on universal approximation for learners other than ANNs I have an applied machine-learning and statistics background, and when I read the Universal approximation theorem, which (in the context of the learning theory of ANNs - Artificial Neural Networks) states (Wikipedia):

  "the standard multilayer feed-forward
  network with a single hidden layer
  that contains finite number of hidden
  neurons, and with arbitrary activation
  function are universal approximators
  on a compact subset of $R^n$. "

I wondered if there are any similar results (in terms of approximation power) for other types of learners (e.g. decision trees, boosting methods, SVMs, etc.).

This leads me to a second but related question: Is this a topic that is formally studied in TCS? If so, are there any good texts for somebody with an applied background?

Thanks

Let me attempt to partly answer the learning part, or to at least address some connections.
In learning (distributional issues aside), we usually want our algorithms to be able to not only approximate the target function (from a class) with a hypothesis, but also to be able find such a hypothesis (efficiently).  So, even though a certain class can universally approximate a given target, we are not done.

I am not an expert in neural networks, but training a neural network is not easy.  We have algorithms for training a neural network, like backpropogation, but they won't always converge, or converge quickly enough, to meet the PAC learning criteria.
Boosting, on the other hand says (roughly) how to turn a weak "approximator" into a strong one, but it in some sense assumes the difficulty away but giving the learner access to the weak approximator.


Separation of  space complexity classes: differeces between uniform class and nonuniform one as an analogy of circuit lower bounds project Boolean circuit is used to measure  time in a nonuniform way, which Pippenger showed the relation between a time complexity of uniform model (Turing Machines) and size complexity of boolean circuits.  In the theory of space complexity, branching programs are considered to measure nonuniform space complexity.

I want a survey to answer the following question. My motivation came from the state of the art of attempts for separation between NL and L, that is , proving L vs NL problem. I would like to know whether there is any analogous approach for proving separation between  time complexity classes (deriving circuit lower bounds is useful for separation of time complexity classes because this approach is supported by Pippenger's theorem).  Thus I would like to know whether there is an analogue of Pippernger's theorem which would support non-uniform approaches for separation of the space complexity classes like circuit lower bounds.

Question:

  Is there a Nondeterministic polynomial size branching program solving
  an NL-complete problem  if we take a Nondeterministic Turing Machine
  solving the same problem ?

Reference:

N.Pippenger and M.Fischer, Relations among complexity measures, J of ACM, 1979.

Perhaps you'd be interested in switching networks. According to Potechin's Bounds on monotone switching networks for directed connectivity, one way to separate L from NL is to show that there is no polysize switching network for directed connectivity. There is in fact a (trivial) polysize switching-and-rectifier network for directed connectivity. The difference between the two models is that the former is undirected and the latter directed.

Potechin has been working on separating L and NL, but so far his method only works for monotone networks. See also his STOC 2012 paper with Siu Man Chan. (More papers are on the way.)


algorithms to split data into roughly equal sized quantiles What is the state-of-the art on algorithms that calculate/estimate approximate quantiles?

I don't even worry about errors in terms of the value of quantiles (here meaning the cutoff) but having roughly equal sized bins. E.g. if I need vingtiles, I want to have low risk of having any bin having less than 4% of the data or more than 6%.

If I need to implement this in an existing high-level statistical system, I think the question inevitable becomes restricted to downsampling from a population of $N$ to a subsample of $n$ and take quantiles using sorting at costs at the order $O(n \log n)$ instead of $O(N \log N)$, but at the right ratio as a function of the original sample size. I am looking for guidance on how to pick $n$ for any $N$.

It is possible to find the quantiles in $O(N)$ using a straightforward modification of the selection algorithm based on quicksort (see http://en.wikipedia.org/wiki/Selection_algorithm).


What does "hold uniformly" mean in the context of asymptotic analysis? What does "hold uniformly" mean in the statement of Theorem 1.7 in
A Faster Subquadratic Algorithm for Finding Outlier Correlations? Here's the theorem text ("hold uniformly" is in the last line):

We say a bound on a family of objects holds uniformity if there is a single bound that applies to all objects in the family, as opposed to a bound that is dependent upon the parameter that determines which element of the family is under discussion.

For example, $f_n(x)= \sin(nx)$ is uniformly bounded by $1$, while $g_n(x)=n\cos(nx)$ is not. In fact, $g_n$ isn’t uniformly bounded by anything, as any bound on it needs to depend on $n$.


Deciding whether a metric is a tree metric An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, i.e. a metric is a tree metric iff every 4 point subspace is a tree metric. In particular this implies that one can decide in polynomial time whether a given metric is a tree metric by examining all quadruples of points in the space.
My question now is what other (than the trivial) algorithms are there? Can one check in linear (in the number of points) time whether a metric is a tree metric?

If the given metric space embeds into a tree metric, the tree must be its tight span. The O(n^2) time algorithms referred to in Yoshio's answer can be extended to certain two-dimensional tight spans: see arXiv:0909.1866.

One method for solving the problem is incremental (as in the linked preprint, but much simpler): maintain a tree T containing the first i points from your metric space (that is, having the same distances as the corresponding entries of your input distance matrix) and extend it one point at a time; at each step there's at most one way to extend it.

To test whether to attach your new point r along edge uv of your existing tree, find points p and q of your metric space that are on opposite sides of edge uv. The new point attaches to a point inside edge uv iff d(p,r) > d(p,u) and d(q,r) > d(q,v); using this test on each of the edges of the existing tree, you can find where it attaches in O(n) time. Once you've found where to attach it you can test in O(n) time whether the distances to all the other points are correct. So each point you add takes time O(n) and the whole algorithm takes time O(n^2), optimal since that's the size of your input distance matrix.


Why do timeouts require synchronized clocks? In Impossibility of distributed consensus with one faulty process @1985 by Fischer at al., the authors state (p375)

  We also assume that processes do not have access to synchronized clocks, so algorithms based on timeouts, for example, cannot be used.

Why do algorithms that employ timeouts require that clocks be synchronized across processes?

Note that the authors also assume the following:

  Crucial to our proof is that processing is completely asynchronous; that is, we make no assumptions about the relative speeds of processesor about the delay time in delivering a message.

The notion of "timing out processes" refers to the ability of knowing when to conclude that a process must have crashed.
If you have a completely asynchronous system, then it does not help to equip processes with perfectly synchronized clocks, as these cannot be used to distinguish a slow process from one that has crashed.


Do these set systems imply a partition? During research, I hit a set theoretic claim that I could neither proof nor disproof.

Let $S_1,S_2,S_3$ be three set systems over the same finite universe $U$ such that

$S_1,S_2,S_3$ are closed w.r.t. $\cap$ and $\cup$ and

for each pair $u,v \in U$, there are two disjoint sets $X \in S_i, Y \in S_j$, $i,j \in \{1,2,3\}$, $i \neq j$, such that $u \in X$ and $v \in Y$.

Then, there is a partition of $U$ into at most three sets, each from a different set system.

They don't necessarily imply a partition, here is a counterexample.
Each set in each $S_i$ will have an even size, while $U$ will have an odd number of elements, this already guarantees that a partition is impossible.
$U$ is the nine vertices of a cycle of length $9$, whose edges are colored with $3$ colors, in an alternating way.
With the union operation each color class generates a set system, these will be the $S_i$.
In more detail, the generating edges are 01, 34, 67 for $S_1$, 12, 45, 78 for $S_2$ and 23, 56, 80 for $S_3$.
It is easy to check that your separating condition holds.


Parse structure of a range concatenation grammar (RCG) I know that with a context-free grammar, one can represent the results of a parse as a parse-tree. Specifically, each node represents one application of a production rule, is usually named for the LHS nonterminal, and its children are the nonterminals on the RHS.

For a context sensitive grammar, it's arguably possible to do the same thing, and to just decorate each node with its production rule's left and right context (non)terminals (or even ignore them entirely).

I've been staring at range concatenation grammars for a few hours now and am slightly boggled with respect to their parse representation. They're weaker than CSGs, stronger than CFGs, and yet I can't seem to digest how their parses are represented. Yes, I could say, "Oh, for this grammar it's clearly a tree because you can construct a tree of the production rules!" But that seems unsatisfactory to me because with CSGs and with CFGs one can trivially recreate the string by infix walking the parse tree. With an RCG, I don't see that being possible without an excess of bookkeeping due to rules like

$A(xay) \rightarrow B(by)$

(where ASCII symbols $\leq d$ are terminals and $\geq x$ are variables).

Here to recreate the string one would need to crawl back up the parse tree from any unary production rule $B$ just to figure out that some other production rule $A$ added a symbol $b$ (a new instance non-existent in the original string) to what had been 'produced' in $B$.

It makes me uncomfortable in a, "This seems oddly inelegant," sort of way. The feeling is of course unfounded and arbitrary, but it's there.

What's up with range concatenation grammars' parse representations? Is there a more elegant/useful way of representing their parse results than the trivial [production-rule $=$ subtree] intuition?

EDIT

As I read more into Earley parser designs for RCGs, it seems that there's the shared 'forest' way of representing them in papers by Boullier and Kallmeyer, but that doesn't give a particularly clear intuition for what an individual parse is; they may call it a 'forest' but that doesn't seem to imply the existence of nice and clean 'trees'. :-/

EDIT 2

I might be conflating features of literal movement grammars with range concatenation grammars. The interpretation I gave of the predicate clause above may be entirely incorrect...

EDIT 3

Okay, a key point to all of this is that a terminal appearing in a predicate on the RHS of a clause is actually just a range that is defined to span a part of the input string that is exactly that terminal. This lends credence to the equivalence of these two clauses in the presence of $C(c) \rightarrow \epsilon$:

$A(x) \rightarrow B(xc)$
$A(x) \rightarrow B(xy)C(y)$

Navigating the parse tree still requires bookkeeping, but the rationale behind that bookkeeping makes more sense.

Also, I might still very well be writing invalid rules in this example. I don't know if it's a requirement that the ranges present on the RHS be within the ranges of the LHS or if they may both span anywhere within the original string. If the former, maybe the tree makes a whole lot of sense and that's why I've been misunderstanding this.

EDIT 4

If I'm understanding Kallmeyer in 'Parsing Beyond Context-Free Grammars' correctly, the ranges appear to be able to span anywhere in the original string. Maybe. I'm still feeling that's a bit ambiguous.

EDIT 5

It is necessarily the case that the ranges are allowed to span anywhere in the input string being recognized by the grammar regardless of the ranges spanned by the arguments on the LHS of a clause, otherwise Boullier's remarks at the top of page 274 in "Recent Developments in Parsing Technology" (doi:10.1007/1-4020-2295-6_13) would make jack little sense.

Which correspondingly means that my original question still stands.

So, I'm actually going to reply to your edits first, then come back to your original question.

re: Edit 1

In your first edit, you express some confusion over what a parse emitted by an Earley parser is; to explain that I'll jump into a quick refresher on the difference between parsers for deterministic context-free grammars (such as LR parsers) and an Earley parser (or other parsers, such as GLL or GLR) which can handle nondeterministic context-free grammars.

Fundamentally, a parser for a deterministic context-free grammar is one that, for any input, will parse it in at most one way: It can either give a unique parse, or fail to parse. As a result, its output is either nothing, or a valid parse tree.

A parser for a nondeterministic context-free grammar, on the other hand, may admit multiple valid parses. Grammars which can actually give rise to such situations are said to be ambiguous, though determining whether a given context-free grammar is ambiguous is undecidable. Because of this, its output is a potentially-empty set of parse trees. This is generally referred to as a "parse forest".

The shared parse forest, then, is merely a compact representation of such a set. Because the grammar is still context-free, a rule $R$ matching a subrange of the input $x$ will always result in the same parse forest - regardless of what sequence of rules led to applying $R$ at $x$. As a result, those two parse trees can share the parse forest generated by $R$ at $x$, drastically reducing the space and time requirements. (Another phrasing might be that, as $R(x)$ is a pure function, it can be memoized.)

re: Edit 2

As far as the interpretation of the predicate clause, I feel that the usual notation of range concatenation grammars somewhat obscures their nature.

Fundamentally, a range concatenation grammar is:

A set of predicates

Taking some number $n$ of arguments
Consisting of a disjunction of clauses

Splitting the arguments into ranges
Consisting of a conjunction of predicates

Queried at concatenations of ranges

The usual notation (as used in your original question) of $A(xay) → B(xy)$ can thus be desugared into:

$$
A(text) :=\\
let\ (x, a, y) := split(text, 3)\ in\\
B(concatenate(x, y)) \wedge a = ``a"
$$

re: Edit 3

  I don't know if it's a requirement that the ranges present on the RHS be within the ranges of the LHS

This is almost exactly the case. The "almost" comes from the concatenation behavior: If I have the example rule I used above, and I apply it at $A(``cbabc")$, I will arrive at $B(``cbbc")\wedge ``a" = ``a"$. If $B$ is defined as $B(xbby) → \epsilon$, then it will succeed - despite "bb" appearing nowhere in the original input. Thus, terminals match not against ranges, but against concatenations thereof.

re: Edit 4

The ranges spanning "anywhere in the original string" is as a result of the concatenation, rather than them being free to span arbitrary parts of the original string.

re: Edit 5

I presume you mean where Boullier says (found in the standalone paper (PS))

  The arguments of a given predicate may denote discontinuous or even overlapping ranges.

However, this does not mean they can be "anywhere freely" (introduced on the RHS), merely that they may "have come from anywhere". Consider the following rule: $A(xyz) → B(xy, yz)$ - here, $B$ takes two overlapping ranges as arguments.

re: Question

In a context-free grammar, a single parse tree is a recursive data structure, consisting of:

The rule name
The range of the input it matched at
The index of the matching clause
The parse trees of the rules the clause refers to

We can extend this bit by bit, and thus arrive at what a single parse tree for a range concatenation grammar looks like, and then apply the same optimization as Earley grammars do to recover a shared parse forest.

First, let's extend it to support concatenation. To do this, we'll move from ranges represented as $(start, end)$ pairs to lists of such ranges - the classic rope data structure.

Next, let's extend it to support splitting. This is a single additional member in the node: a list of positions the input rope was split at.

The third step is to support multiple arguments. Now, we will store an $n$-tuple of ropes, where $n$ is the predicate's arity. In addition, we need to store split information for each argument, making it a tuple of lists.

At this point, a node in our parse tree looks like this:

the predicate name
the $n$-tuple of ropes it was matched at
the index of the matching clause
the $n$-tuple of lists of split points
the parse trees of the predicates the matching clause refers to

That's it - a single parse tree of a range concatenation grammar.

Now, there are two members of the node that could differ between two parse trees matching the same input. The first is the same as for a CFG: the index of the matching clause. If two clauses can match, then we get two parse trees; one for each.

The second is the list of split points. Let's go back to the example rule $A(xay) → B(xy)$ for a minute, and ask it to match "cbabcacb". There are two points it could split at: $(``cb", ``bcacb")$ or $(``cbabc", ``cb")$. Each of these, then, also generates a distinct parse tree - assuming $B$ succeeds.

However, the predicates of a range concatenation grammar - like those of a context-free grammar - have bodies that refer only to the inputs to the predicate. They are thus context free (i.e. pure functions), and can be memoized.

Thus, one can follow a relatively simple evaluation strategy when parsing:

procedure match_A(args, already_matched)
  if contains(already_matched, ("A", args))
    return reference_to(already_matched[("A", args)])
  else
    results = []
    for C in clauses(A)
      SPLIT: for split_tuple in valid_splits(args)
        pred_results = {}
        for P in predicates(C)
          pred_results[P] = P.match(split_tuple)
          if empty(pred_results[P])
            next SPLIT
        push(results, {
          name: "A",
          matched: arg,
          clause: C,
          splits: split,
          subforests: pred_results
        })
    already_matched[("A", args)] = results
    return reference_to(already_matched[("A", args)])


Finding maximum number of disjoint set covers Let $U = [1..n]$ be the universe of $n$ elements and $C$ be a  collection of subsets of $U$, $C= S_1, \dots, S_m$, where $S_i \subset U$. Then the problem is to find as many partitions of $C$, such that each partition covers the universe U. The hardness results can be  derived for this problem, but are there any approximation algorithms known for this ? I gather that the geometric version of this problem has some approximation algorithms, but is there any thing known in the general case ?

Yes, this is closely related to the Domatic Partition problem. See the paper below.
http://epubs.siam.org/doi/abs/10.1137/S0097539700380754

One can get the following results. Given a set cover instance let $k$ be the minimum over all elements in $U$, the number of sets that contain that element. Then it is clear that we can have at most $k$ disjoint set covers. The paper above shows that there always exist $\max\{1, k/(c \log n)\}$ disjoint set covers where $c$ is a sufficiently large constant. This immediately gives an $O(\log n)$-approximation. Moreover, it is hard to approximate to within this factor (modulo constants). And there are examples where the number of disjoint set covers is $O(k/\log n)$.


Why isn't Montgomery modular exponentiation considered for use in quantum factoring? It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is the preferred method. Modular exponentiation is also prominently featured in the quantum factoring algorithm, and it is expensive there as well.

So: why isn't Montgomery modular exponentiation apparently present in current detailed subroutines for quantum factoring?

The only thing I can imagine is that there's a high qubit overhead for some non-obvious reason.

Running montgomery quantum "modular exponentiation" through Google Scholar yields no useful results. I am aware of work by Van Meter and others on quantum addition and modular exponentiation, but examining their references (I have yet to read this work) shows no indication that Montgomery methods are considered there.

The single reference I have found that appears to discuss this is in Japanese, which lamentably I cannot read, though apparently it is from a 2002 conference proceedings. A machine translation yields nuggets appended below that indicate there might be something useful. However, I can't find any indication that this has been followed up, which makes me think that the idea has been a) considered and then b) discarded.

  Quantum circuit in performing
  arithmetic Noboru Kunihiro

  ...In this study, but requires
  relatively large qubit, we propose a
  modular exponentiation circuit quantum
  computation time is short. Montgomery
  Reduction [8] and right binary method
  [9] Combined, they constitute a
  circuit Ru. Reduction Montgomery is, m
  randomly chosen as a natural number,
  mod 2m by the operation, perform the
  remainder operation If, mod n
  operations in eliminating. This will
  lead to reduction of computation
  time...

  Application of 3.2 Montgomery
  Reduction Montgomery Reduction [8] is
  formulated as follows...This algorithm
  can return the correct values can be
  easily confirmed. M R (Y) he asks for
  a law 2m Polynomials with 2m points
  are important and only requires
  division by. In addition, Montgomery
  Reduction in, there are different
  calculation methods....In general,
  Reduction Montgomery is not one-to-one
  function...

  ...The proposed method uses a right
  binary method, Montgomery Reducton has
  a feature that is adopted. Than the
  conventional method, characterized by
  a small component of the circuit Have.
  qubit fault that is required to have a
  lot of expectations can be computed in
  less computational time Be. The
  future, Montgomery Reduction and
  control circuitry specifically NOT
  described by the qubit really needed
  Evaluate the number is expected to
  evaluate the computation time. In
  addition, each taking advantage of
  research findings, more than modular
  exponentiation Non-arithmetic (Euclid
  mutual division, etc.) also with
  respect to the planned configuration
  of an efficient quantum circuit.

  ...[8] PL Montgomery, "Modular
  Multiplication Without Trial
  Division," Mathematics of Computation, 44, 170, pp. 519-521, 1985...

Could you post the original Japanese title/reference?
Also, you might consider just writing to the author - assuming it's the same guy he is a professor at the University of Tokyo:
http://www.it.k.u-tokyo.ac.jp/~kunihiro/
and almost certainly would reply.
Sorry to post this as an answer, it should be a comment but I don't have the rep for that yet apparently...
EDIT:  So, I took a look at the original Japanese.  As a preface, I am currently a PhD student in the EE department at U. Tokyo, originally from the U.S., and I do technical JA->EN translation as a part-time job. However, this topic area is well outside my comfort zone so please take my opinion with a grain of salt!
Basically the conclusion (4) says:

べき乗剰余演算を行う量子回路を提案した。提案方式は、右向きbinary methodを採用し、Montgomery Reductionを採用するという特徴を持っている。従来の方式よりも、回路の構成要素が少ないという特徴を持っている。qubitが多く必要となるという欠点は持つが、より少ない計算時間で計算ができると期待される。
[In this paper] We proposed a new quantum circuit for computing modular exponentiation. The proposed method utilizes an LR binary method, and is also characterized by use of the Montgomery Reduction.  Compared with previous methods, the proposed method requires fewer components to construct the circuit.  The proposed method does however, have the drawback of requiring a large number of qubits, but we are confident that it will be computationally efficient ( lit: require very little computation time ).

I tried searching for related follow-up papers in both English and Japanese but was unsuccessful.   My guess is that the approach proved unsuccessful, or the professor got busy with something else (looks like this was around when he switched universities).
I think that your best bet at this point, assuming you want to follow up the rest of the way and get a concrete answer, is to write professor Kunihiro directly (in English!)


Name for a special family of languages? I was wondering whether there is a standard name in the literature for the following family $\mathcal{F}$ of languages over any finite alphabet $\Sigma = \{a_1,\ldots,a_k\}$:

$\mathcal{F}$ consists of all languages of the shape $\{a_{i_1}^{c_1}a_{i_2}^{n_2}a_{i_3}^{c_3}\ldots a_{i_{k-1}}^{n_{k-1}}a_{i_k}^{c_k}: n_2,n_4,\ldots,n_{k-1} \geq 0 \wedge R(n_2,n_4,\ldots,n_{k-1})\}$, where $c_1,c_3,\ldots,c_k$ are fixed nonnegative constants and $R$ is any fixed relation on $m$ variables $u_1,u_2,\ldots,u_m$ such that for some $S \subseteq \{1,2,\ldots,m\} \times \{1,2,\ldots,m\}$, $R(u_1,u_2,\ldots,u_m)$ holds iff $\left((\forall i,j \in \{1,\ldots,m\})[u_i = u_j \Leftrightarrow (i,j) \in S]\right)$.

So $\mathcal{F}$ contains languages like $\{a_1^n a_2^n a_3^n: n \geq 0\}$ (the "standard" context-sensitive but non-context-free language) and $\{a_1^2 a_1^n a_2^m a_1 a_1^m a_2^n a_1: n,m \geq 0\}$.

This family of languages cropped up in my work recently and I was wondering whether anything interesting could be said about it..

Thank you!

The closest related family of languages seem to be the "bounded semilinear languages" defined in this paper.  But since the commutative image of each language in the family defined in the original post is a linear set, it might be appropriate to call such languages "bounded linear".


Why Tomita created GLR and didn't use Earley? When I look at Earley parsing, it looks very elegant, and I wonder why GLR techniques become popular? Does anyone know what was wrong with Earley parsing that Tomita created GLR?
Performance? Any publications on these discussion is highly appreciated.

Better late than never.

If I understand correctly, Earley is top-down, and will spend time and memory creating Earley items for every production at a given S(i). This means that for natural language, in S(0) we create and check an Earley item for every possible word that starts a sentence, and there are quite a lot of those.

But GLR is bottom up, so assuming efficiently hashed table/state lookups, the first token selects the next transition(s) in constant time.

This is true specifically for natural languages, with the huge number of distinct productions. But not really meaningful for programming languages, with the very small set of productions.


Is just one W-type enough for formalizing mathematics? We work in intensional Martin-Löf type theory with $0$, $1$, $2$, $\Pi$, $\Sigma$, $W$ and a cumulative hierarchy of universes. Suppose our goal is to formalize constructive mathematics.
Now if we were to drop general $W$-types but keep just one $W$-type with infinitely many closed terms how much more difficult would our life become? Would it be much harder to express interesting theorems?

We certainly do not need very many $W$-types.
If we also have universes, we only need one $W$-type, namely the natural numbers. For example, the UniMath library uses just the natural numbers and no other inductive types (if we discount the fact that standard types constructors, such as products and sum, are defined inductively in Coq).


Select two numbers that sum to $p$, using sub-linear query time Here is a nearest neighbor problem.

Given reals $a_1, \ldots, a_n$ (very large $n$!), plus target real $p$, find $a_i$ and $a_j$ whose SUM is closest to $p$. We allow reasonable pre-processing/indexing of $a_1, \ldots, a_n$ (up to $O(n \log n)$), but at query time (given $p$), the result should be returned very fast (e.g., $O(\log n)$ time).

(Simpler example: if we only wanted the SINGLE $a_i$ that is closest to $p$, we would sort $a_1, \ldots, a_n$ offline, $O(n \log n)$, then do binary search at query time, $O(\log n)$).

Solutions that don't work:

1) Sort $a_1, \ldots, a_n$ offline, then at query time, start from both ends & move two pointers inward (http://bit.ly/1eKHHDy). Not good, because of $O(n)$ query time.

2) Sort $a_1, \ldots, a_n$ offline, then at query time, take each $a_i$ and perform binary search for a "buddy" that helps it sum to something close to $p$. Not good, because of $O(n \log n)$ query time.

3) Sort all pairs $(a_{1}, \ldots, a_{n})$ offline, then do binary search. Not good, because of $O(n^2)$ pre-processing.

Thanks!

ps. Further generalizations needed for practice: (1) $a_1, \ldots, a_n$ and $p$ to be 50-dimensional vectors, (2) "close" to be vector cosine distance, and (3) $k$-best closest pairs-that-sum, not just 1-best.

This is almost certainly impossible.

Suppose you could solve your problem with preprocessing time $P(n)$ and query time $Q(n)$.  Then there is a simple algorithm to solve the 3SUM problem—Given a set of $n$ real numbers, do any three elements sum to zero?—in $P(n)+n\cdot Q(n)$ time.  We pre-process all the numbers, then for each number $a_k$, we find the value of $a_i+a_j$ that is closest to $-a_k$; if it matches $-a_k$ exactly, we have found a solution to the 3SUM problem.

However, the fastest algorithm known for 3SUM runs in $O(n^2)$ time, and this algorithm is widely conjectured to be optimal.  Moreover, there is a matching $\Omega(n^2)$ lower bound in a restricted but natural decision tree model of computation.  For sets of integers, there are slightly subquadratic-time algorithms that "play games with bits", but even in the integer RAM model, 3SUM is conjectured to require $\Omega(n^2/\text{polylog}\,n)$ time.

So assuming that conjecture is correct, your problem either requires (near-)quadratic preprocessing time or (near-)linear query time.


Problems that are NP-hard to approximate even when the input graph is regular Are there graph problems which are NP-hard to approximate even when the input graph is regular?

For instance, are there optimization problems that are NP-hard to approximate within $O(n^\epsilon)$ even when the input graph is regular?

PS: The input graph is a simple undirected graphs

For all $k\geq 3$, the problem maximum induced matching is APX-hard for $k$-regular bipartite graphs. See this paper.

A matching $M$ of a graph $G$ is induced if for every pair of edges $e,e'$ in M, there is no edge between them in $G$.


A variant of betweenness problem Is there any non-trivial approximation algorithm for a variant of betweenness problem: namely, we want to minimize the number of unsatisfied triples rather than to maximize the number of satisfied ones?

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

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

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

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


Kernighan–Lin algorithm and multiple gain functions I want to know if there is an algorithm like KERNIGHAN-LIN for graph partitioning that can handle several (different) gain functions.

Is there some technique to combine gain functions in one algorithm?

The KL algorithm and its gain function is defined here for example:

http://www.cs.berkeley.edu/~demmel/cs267/lecture18/lecture18.html#link_4.2

Kim and Moon (2004) compare variants of Kernighan-Lin which combine the usual gain and a lock-based gain, which is relative to the locked vertices. You can combine two gain functions in the range $-n\ldots n$ using an implementation of Fiduccia-Matheyses with $O(n^2)$ buckets.

Kim, Moon, Lock-gain based Graph Partitioning, J Heuristics, 10, 37-57, 2004.


Packing rectangles into convex polygons but without rotations I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps.  In my problem you are not allowed to rotate the rectangles and can assume that they are oriented parallel with the axes. You are just given the dimensions of a rectangle and the vertices of the polygon and asked how many identical copies of the rectangle can be packed into the polygon.  If you are allowed to rotate the rectangles this problem is known to be NP-hard I believe. However, what is known if you cannot? How about if the convex polygon is simply a triangle?  Are there known approximation algorithms if the problem is indeed NP-hard?

Summary so far (21 March '11). Peter Shor observes that we can regard this problem as one of packing unit squares in a convex polygon and that that problem is in NP if you impose a polynomial bound on the number of squares/rectangles to be packed.  Sariel Har-Peled points out there is a PTAS for the same polynomially bounded case.  However, in general the number of squares packed can be exponential in the size of the input which only consists of a possibly short list of pairs of integers.  The following questions appear to be open.

Is the full unbounded version in NP?
Is there a PTAS for the unbounded version?
Is the polynomially bounded case in P or NPC? And my personal favourite, is the problem any easier if you just restrict yourself to packing unit squares into a triangle?

The problem can be reformulated as picking a maximum number of points inside a convex polygon, such that the every pair of them is in distance (under the $L_\infty$ metric) at least $1$ from each other (just think about the centers of the squares). This in turn is related to the same problem where one uses the regular Euclidean distance. This is in turn related to meshing, where one is interested in breaking a polygon into nicely behaved regions (i.e., you take the Voronoi diagram of the centers [see Centroidal Voronoi tessellations]).

Anyway, a $(1-\epsilon)$-approximation is quite easy. You randomly slide a grid of sidelength $O(1/\epsilon)$. Clip the polygon into the grid, and solve the problem inside each piece of intersection of the polygon with the grid using brute force. An algorithm with running time $O(M*noise(\epsilon))$ should easily follow, where $M$ is the number of points (i.e., rectangles), and $noise(\epsilon)$ is some horrendous function that depends only on $\epsilon$.


Define metric for systems of set of points Given a set of points $p_1, p_2, ..., p_n$ and a collection of sets from $n$ points $S_1, S_2,...,S_m$. The pairwise distance between any three points $(p_1, p_2, p_3)$ satisfies triangle inequality $d(p_1,p_2) + d(p_2, p_3) \geq d(p_1, p_3)$. How to define the distance between sets such that the pairwise distance between any three sets $S_1, S_2, S_3$ satisfies triangle inequality $d(S_1,S_2) + d(S_2, S_3) \geq d(S_1, S_3)$.
For example, when every set is $\textbf{pairwise disjoint}$ and has the $\textbf{same cardinality}$, we can define the distance between any two set to be the sum of the distances between elements of the two sets $$d(S_1, S_2) = \sum_{x \in S_1, y \in S_2} d(x,y)$$. we can show that the triangle inequality is satisfied for any three sets.

Hausdorff distance is what you are looking for.


counting independent sets What algorithms/mathematical techniques are available to exactly/approximately count number of independent sets?

Is/Are there a good reference/good references on this topic?

I am interested in regular graphs.

The problem can be restated as a #2SAT. See

http://en.wikipedia.org/wiki/2-satisfiability

under the "Counting the number of satisfying assignments" section for some references to the currently best exact counting algorithms.


On low rank graph isomorphism Is there a $c>1$ (maybe $c=2$) such that every lower than rank $n^{1/c}$ graphs on $n$ vertices can be tested to be in polynomial time?

There is such a c if and only if GI "can be tested to be in polynomial time",

since one can pad with nc isolated vertices.

I don't know of any results on random self reducibility of GI.


A game of positioning overlapping circles to maximize travel time between them I encountered the following game. I'll migrate this as requested.

A bug is visiting circles, and an adversary wishes to maximize his travel time.
The adversary places a circle on every turn.
The bug walks from it's current position directly toward the center of the newest circle, then stops when it encounters the interior of the circle (thus: it doesn't walk if a circle is played covering its location). This is the bug's turn.
There are $N$ circles available to the adversary.
Each subsequent circle has radius less than the previous circle.
Each circle must intersect the intersection of all previously played circles. That is, all circles must have a common intersection once all are played.

EDIT:  The adversary is free to choose the radii of the circles, subject to the constraint that the radii monotonically decrease.

Questions and Answers:

Is the distance as $N\to\infty$ bounded? A: No, an example of an adversary strategy is given by this Answer
What is the maximum distance the bug must travel over the playing of $N$ circles. A: it grows at $\Theta(\log(N))$, by the same answer.

Variant 2: The bug walks directly toward the intersection of the two most recently played circles.

UPDATE: This variant was addressed, under the assumption that the bug can only remember the last 2 circles played here. The result was again an unbounded distance.

What impact does unliminted memory have? i.e., the bug goes to the intersection of all previously played circles. This produced a "loose" bound of $O(d)$, where $d$ is the diameter of the first circle. Obviously it cannot be less than this. See here. The current upper bound was $1000\times d$. This was obtained by approximating the worst-case path as a tour around progressively smaller circles. It was shown that the bug always makes progress towards the final intersection, thus reducing the next-step distance it must travel.

I suspect the distance traveled is a small constant times the circumference of the first circle, but I'm not currently able to provide a good proof.

This answer has two parts, together showing that the correct bound is $\Theta(\log N)$:

A lower bound of $\Omega(\log N)$ (times the radius of the first circle).
A matching upper bound of $O(\log N)$.

Lower bound of $\Omega(\log N)$

Consider two unit circles that touch at a point $p$. (See below; $p$ is on the right, the bug starts on the left.)  Alternate between one circle and the other.  The bug will travel up and down zig-zagging across the crevice between the two circles, moving mostly up and down but also progressing slowly to the right.  If I've done the trigonometry correctly, after $N$ steps, the distance from the common point will be $\Theta(1/\sqrt N)$, and the $N$th step will cause the bug to walk $\Theta(1/N)$, for a total distance of $\Theta(\log N)$.

Here's a sketch of the calculations.  Consider some two consecutive steps that the bug makes.  He goes from some point $a$, to $b$, to $c$.  Points $a$ and $c$ are on same circle; point $b$ is on the other circle.  Let $o$ be the center of the circle that $a$ is on.  Consider the following three triangles, in order of decreasing size:

The isoceles triangle $\triangle oap$ (recall $p$ is the common point).
The triangle $\triangle abp$.
The little triangle $\triangle abc$

These triangles are almost similar (i.e., congruent modulo scaling).
More precisely, for $\epsilon = |ap|$,
all three have the following property:
the ratio of the length of the short leg to the long leg is $\Theta(\epsilon)$.
(I won't prove this in any more detail here, but note that $\epsilon\rightarrow 0$
as the bug walks, and by perturbing one vertex in each triangle by a negligible amount, the triangles can be made similar.)

The long legs $co$ and $po$ of the first triangle have length 1.
Its short leg $|ap|$ has length $\epsilon$.
Segment $ap$ is a long leg of the second triangle,
so that triangle's short leg $ab$ has length $\Theta(\epsilon^2)$.
Segment $ab$ is a long leg of the third triangle,
so that triangle's short leg $ac$ has length $\Theta(\epsilon^3)$.
Thus, in these two steps that the bug takes:

The distance $|ab|+|bc|$ the bug travels is $\Theta(\epsilon^2)$.
The distance from the bug to the common point $p$ decreases from $\epsilon$ to $\epsilon-\Theta(\epsilon^3)$.

Define time $t_k$ to be the number of steps before $\epsilon_t \approx 1/2^k$.
By (2) above, $\epsilon$ decrease by a constant factor after about $\Theta(1/\epsilon^2)$ steps,
so $t_{k+1} = t_k + \Theta(2^{2k}) = t_k + \Theta(4^k)$.
Thus, $t_k = \Theta(4^k)$.
That is, after $\Theta(4^k)$ steps,
the distance from the bug to the common point $p$ will be about $1/2^k$.
Changing variables, after $N$ steps,
the distance from the bug to the common point will be $\epsilon = \Theta(1/\sqrt N)$.
And, in the $N$th step, the bug travels $\Theta(\epsilon^2) = \Theta(1/N)$.
So the total distance traveled in the first $N$ steps is $\Theta(1+1/2+1/3+...+1/N) = \Theta(\log N)$.

This is the lower bound.

It extends to proposed Variant 2 (as I understand it), as follows:

Adding the restriction that the bug should move to the nearest point in the intersection of the two most recently placed circles does not help.  That is, the $\Omega(\log N)$ lower bound above still applies.  To see why, we will modify the example above by adding a single extraneous circle that allows the bug to meet the restriction while still traveling the same path:

The green and blue circles are the two circles from the example above.  The intersection points $a$ and $b$ are the same $a$ and $b$ as in the example above.  The red circle is the new "extraneous" circle.  The previous sequence alternated between the blue and green circles.  The new sequence will be this sequence, but with the red circle added before every circle in the old sequence: red, blue, red, green, red, blue, red, green, red, blue, ...

Suppose the bug is sitting at $a$ after blue is placed.  The next circle placed is red.  Red contains the bug, so the bug doesn't move.  The next circle placed is green.  Now the bug moves to $b$ (which is the closest point on the intersection of the green and red circles).  By repeating this, the bug travels as before.

Upper bound of $O(\log N)$

I only sketch the proof.

Fix any sequence of circles.  We will argue that as $N\rightarrow \infty$,
the total distance traveled by the bug in the first $N$ steps is $O(\log N)$.
Assume without loss of generality that the first circle has radius 1.

Fix an arbitrarily large $N$.  Let $p$ by any point in the intersection of the first $N$ circles.
Note that because of the way the bug moves, in each step that the bug moves it gets closer to $p$.

First, consider steps where the following ratio is at least $1/\log N$:
$$ \frac{\mbox{the reduction in the distance to } p}{\mbox{the distance traveled in the step}}.$$
The total distance traveled in such steps is $O(\log N)$,
because the total distance traveled in such steps
is $O(\log N)$ times the initial distance to $p$.
So we only need to bound the total distance traveled in the other steps ---
those in which that ratio is at most $1 / \log N$.

First, we argue something slightly weaker:
that the total distance traveled in such steps
before the circle radius decreases to 1/2 or less is $O(\log N)$.
(We show later this is enough to give the bound.)

Consider any such step.
Let $a$ and $b$, respectively, denote the locations of the bug before and after the step.
Let $o$ denote the center of the current circle.
Let $b'$ denote the point on the ray $\overrightarrow{pb}$ such that $|pa| = |pb|$:

Consider the following triangles:

$\triangle opb$
$\triangle pba$
$\triangle abb'$

By geometric arguments similar to those in the lower bound,
for some $\epsilon$,
each of these triangles has two long legs and one short leg,
and the ratio (for each triangle) of the short leg length
to the long leg lengths is $\Theta(\epsilon)$:
$$\frac{|bb'|}{|ab|}
= \Theta\big(\frac{|ab|}{|pa|}\big)
= \Theta\big(\frac{|pa|}{|bo|}\big)
= \Theta(\epsilon).$$

This equation and the assumption that $|bo|$, which is the circle radius,
is in $[1/2,1]$ imply
that $|ab| = \Theta(|pa|^2/|bo|) = \Theta(|pa|^2)$,
and then that $|bb'| = \Theta(|ab||pa|/|bo|) = \Theta(|pa|^3)$.

Now we focus on the bug's distance to $p$.
Call it $d$ before the step, and $d'$ after the step.
(Note $d=|pa|$, $d'=|pb|$, and $d-d' = |bb'|$.)

In this step, this distance $d$ reduces by $|bb'|$,
which by the above observations is $\Omega(d^3)$.

Thus, the number of additional steps required to reduce the distance
by a factor of 2 (to at most $d/2$) is $O(1/d^2)$.
Changing variables, if $d=1/2^k$,
the number of additional steps required to bring the distance below
$1/2^{k+1}$ is $O(4^k)$.  Since the sum is geometric,
the total number of steps required to bring the distance below $1/2^{k}$ is $O(1/4^k)$.
Changing variables again,
after $n$ steps, the distance to $p$ will be $O(1/\sqrt n)$.

Finally, recalling the displayed equation several paragraphs up,
in the $n$th step, the distance that the bug travels, i.e. $|ab|$,
is $O((\mbox{the current distance to } p)^2) = O(1/n)$.  Thus,
the total distance traveled in the first $N$ such steps
while the circle radius is in $[1/2,1]$
is at most
$$\sum_{n=1}^N O(1/n) = O(\log N).$$

By scaling, we conclude that, for any $k$, the total distance traveled
while the circle radius is in the range $[1/2^k, 1/2^{k+1}]$
is $O(\log(N)/2^k)$.
Summing over $k$, the total distance traveled is $O(\log N)$.
QED


Definition of a monotone machine. There is a definition of a 'monotone machine' in Li &  Vitany's Book, and another one which is for example stated in this paper via c.e. (computably enumerable) sets. I can't see why these definitions should be equivalent.
Furthermore in Li & Vitany's book, there is a statement which says that monotone machines compute p.r. (primitive recursive) functions f with $f(x) \le f(y)$ when $x \le y$ (lexicographical ordering).
I don't see how such a function can be computed by a monotone machine.

Maybe someone can explain this to me or refer to a paper / book which descripes these connections.

Thanks

edit:
The first definition:
A monotone machine has a one-way read-only input tape, a one-way write-only output tape and work tapes. The input is read one bit at a time, and the output written one bit at a time, with the one-way nature of the output tape allowing no revisions. For such a machine M, we have M(x) terminates with output y, where x is a finite string and y is a possibly infinite string, if either M halts after reading the bits of x from the input tape and y is what is on the output tape at that point, or M computes forever after reading exactly the bits of x, and y is on the output tape on the limit.

The second one:
A monotone machine L is a c.e. (computably enumerable) set of pairs of finite strings such that if , is in L and $x \le x'$ then $y$ and $y'$ are comparable (i.e. $y \le y'$ or $y' \le y$).

When we say that a monotone machine is a set $L$ of pairs of strings $(x,y)$, the first component $x$ is the part of the input tape being read in order to produce the output $y$.

This set is c.e. (computably enumerable) because we can run computations with all (finite parts of) oracles in parallel, and watch for pairs $(x,y)$ where this happens.

The condition that if $(x,y)\in L$, $(x',y')\in L$ and $x\preceq x'$ then $y\preceq y'$ or $y'\preceq y$ just says that we have consistency, i.e., if you see more of the input bits you can't go back and say that you now outputted something different on an earlier input after all.

Conversely, given such a c.e. set we can produce a machine that monitors the c.e. set $L$ and looks for pairs $(x,y)$ entering $L$, and checks whether $x$ is a prefix of what's on the input tape given to the machine. If so, it extends its output string to $y$.


An extension of the noise operator In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator $T_{\varepsilon}$ on real-valued Boolean functions. Given a function $f: \{0,1\}^n \to \mathbb{R}$ and $\varepsilon$, $p$ s.t $0 \leq \varepsilon \leq 1$, $\varepsilon = 1 - 2p$,
we define $T_{\varepsilon} \to \mathbb{R}$ as
$T_{\varepsilon} f(x) = E_{y \sim \mu_p} [f(x+y)]$

$\mu_p$ is the distribution on $y$ obtained by setting each bit of a $n$-bit vector to be $1$ independently with probability $p$ and $0$ otherwise. Equivalently, we can think of this process as flipping each bit of $x$ with independent probability $p$. Now this noise operator has many useful properties, including being multiplicative $T_{\varepsilon_1} T_{\varepsilon_2} =
T_{\varepsilon_1 \varepsilon_2}$ and having nice eigenvalues and eigenvectors($T_{\varepsilon}(\chi_S) = \varepsilon^{|S|} \chi_S$ where $\chi_S$ belongs to the parity basis).

Let me now define my extension of $T_\varepsilon$, which I denote as $R_{(p_1,p_2)}$.  $R_{(p_1,p_2)} \to \mathbb{R}$ is given by $R_{(p_1,p_2)} f(x) = E_{y \sim \mu_{p,x}} [f(x+y)]$. But here our distribution $\mu_{p,x}$ is such that we flip the $1$ bits of $x$ to $0$ with probability $p_1$ and $0$ bits of $x$ to $1$ with probability $p_2$. ( $\mu_{p,x}$ is now clearly a distribution dependent on the $x$ where the function is evaluated, and if $p_1 = p_2$ then $R_{(p_1,p_2)}$ reduces to the 'regular' noise operator.)

I was wondering, has this operator $R_{(p_1,p_2)}$ already been well-studied somewhere in the literature? Or are the basic properties of it obvious? I am just starting with Boolean analysis, so this might be straightforward to someone more familiar with the theory than I am. In particular I am interested in if the eigenvectors and eigenvalues have some nice characterization, or whether there is any multiplicative property.

I'll answer the second part of the question.

I. Eigenvalues and Eigenfunctions

Let's first consider the one dimensional case $n=1$. It is easy to check that the operator $R_{p_1,p_2}$ has two eigenfunctions: $1$ and
$$\xi(x) = (p_1+p_2)x - p_1 =
\begin{cases}
-p_1, &\text{ if } x =0,\\
p_2, &\text{ if } x =1.
\end{cases}$$
with eigenvalues $1$ and $1-p_1 - p_2$, respectively.

Now consider the general case. For $S\subset \{1,\dots,n\}$, let $\xi_S(x) = \prod_{i\in S} \xi(x_i)$. Observe that $\xi_S$ is an eigenfunction of $R_{p_1,p_2}$. Indeed since all variables $x_i$ are independent, we have
\begin{align*}
R_{p_1,p_2}(\xi(x)) &= R_{p_1,p_2}\left(\prod_{i\in S} \xi(x_i)\right) = \prod_{i\in S} R_{p_1,p_2}(\xi(x_i)) \\
&= \prod_{i\in S}\left((1-p_1 - p_2)\xi(x_i)\right) = (1-p_1 - p_2)^{|S|} \xi_S(x).
\end{align*}

We get that $\xi_S(x)$ is an eigenfunction of $R_{p_1,p_2}$ with eigenvalue $(1-p_1-p_2)^{|S|}$ for every $S\subset \{1,\dots,n\}$. Since functions $\xi_S(x)$ span the whole space, $R_{p_1,p_2}$ has no other eigenfunctions (that are not linear combinations of $\xi_S(x)$).

II. Multiplicative Property

In general, the “multiplicative property” doesn't hold for $R_{p_1,p_2}$ since the eigenbasis of $R_{p_1,p_2}$ depends on $p_1$ and $p_2$. However, we have
$$R_{p_1,p_2}^2 = R_{p_1',p_2'},$$
where $p_1' = 2p_1- (p_1+p_2)p_1$ and $p_2' = 2p_2- (p_1+p_2)p_2$. To verify that, first note that $R_{p_1,p_2}$ and $R_{p_1',p_2'}$ have the same set of eigenfunctions $\{\xi_S\}$. We have,
$$R_{p_1,p_2}^2(\xi_S) = (1-p_1-p_2)^{2|S|} \xi_S=(1-p_1'-p_2')^{|S|}\xi_S = R_{p_1',p_2'} (\xi_S) $$
since
\begin{align*}
 1-p_1'-p_2' &= 1 - p_1\cdot (2- (p_1+p_2)) - p_2\cdot (2- (p_1+p_2)) \\
&= 1 - (p_1+p+2) (2- (p_1+p_2)) \\
&= 1 - 2(p_1 +p_2) + (p_1 + p_2)^2 = (1-p_1-p_2)^2.
\end{align*}

III. Relation to the Bonami—Beckner operator

Let us think of functions from $\{0,1\}^n$ to ${\mathbb R}$ as polylinear polynomials. Let $\delta = \frac{1}{2}\cdot \frac{p_1-p_2}{p_1+p_2}$. Consider the operator
$$A_{\delta}(f) = f(x_1 + \delta, \dots, x_n + \delta).$$
It maps every multilinear polynomial $f$ to a multilinear polynomial $A[f]$. We have,
$$R_{p_1,p_2}(f) = A_{\delta}^{-1} T_{\varepsilon}A_{\delta}(f),$$
where $\varepsilon = 1 - p_1 - p_2$. Note that parts I and II follow from this formula and properties of the Bonami—Beckner operator.


Sampling distinct values with probability proportional to their frequency This is a variant of my previous question (Reservoir sampling of distinct values)

I'm faced with a situation where I need to get m samples from a data stream (without replacement). Only one pass through the data is possible.

In my case, the stream contains many duplicate values, and I need to make sure that my sample set won't include any duplicate values. It is important to note the the number of distinct values in the stream is huge as well (to big to fit memory).

I need to make sure that the probability of any value being sampled is proportional (or about proportional) to its frequency in the stream.

Is there any way to achieve this?

If the problem is well-defined, I suspect it should be achievable using the following method.  Pick a $m$ values uniformly at random from the stream.  For each value, the expected value of the number of times it is included in the sample will be proportion to its frequency in the stream.  If the frequency of every item is small compared to $1/m$, the probability that an item appears in the sample will be approximately proportional to its frequency in the stream.

If some items appear more often than that, use a sketch (e.g., a CountMin sketch) to estimate the frequency of frequently-occurring items.  You don't need to estimate the frequency of all items, only those whose frequency is higher than $1/(1000m)$ (say), so the sketch can be very efficient.  Then, you select $m$ values uniformly at random from the stream, removing duplicates; if any of the selected values is in the CountMin sketch and has probability close to $1/m$ or larger, then you fix things up (e.g., by dropping it with some probability, as needed).  I'll let you work out the exact arithmetic for how to make the probabilities work out however you want (as it's not clear to me exactly what you want to have happen), but this should work and be very efficient, as the sketch only needs to track frequencies for a small number of items.


Can Non-termination be considered an algebraic effect? Non-termination is sometimes considered an effect.  I have been reading about algebraic effect systems (What is algebraic about algebraic effects and handlers?), and I suspect non-termination (like that arising from a fixed point operator) could fit in the algebraic effect framework.

For instance if effects systems act like continuations, it seems easy to add a handler that supplies "fuel" for possibly non-terminating computations.

Another way to encode a non-termination effect might be though SKI combinators, since they are Turing complete and I think they can be presented as an algebra.

The programing language Koka has a non-termination effect, but it is a built in "primitive" effect.  So it's unclear to me if it could be encoded by a user in their standard effect system.

Can non-terminating computation be considered an algebraic effect?  If so, are there standard ways to do it?  Any references would be great.

Non-termination can be considered an algebraic effect up to a point. It's an exception that cannot be handled. More precisely, we may introduce a nullary operation (constant) $\bot$ which signifies non-termination, but then we disallow handling it, as that would allow us to implement the Halting oracle.

Such treatment of non-termination is a bit naive. A more satisfactory account of non-termination would use domain-theoretic semantics, or a lifting monad.


Consequences of Polynomial & QuasiPolynomial time algorithms for UP, FewP and CoC=P I have came up with two alternate universe scenarios that I need some help figuring out the outcome of. Thank you in advance.

There exists two complexity classes $\mathsf{A}$ and $\mathsf{B}$. By definition $\mathsf{A}$ $\subseteq$ $\mathsf{B}$ but then it can be easily seen that $\mathsf{A}$ is truth table reducible to $\mathsf{B}$. Furthermore, $\mathsf{B}$ $\subseteq$ $\mathsf{coC_{=}P}$ (Zoo) and $\mathsf{FewP}$ $\subseteq$ $\mathsf{A}$ (Zoo).

1)What are the consequences of a Quasi Polynomial Time Algorithm for $\mathsf{B}$ ?
a)Does it put $\mathsf{A}$ in $\mathsf{QP}$ as well?
b)Other than proving that $\mathsf{P}$ $\neq$ $\mathsf{PSPACE}$ and $\mathsf{P}$ $\neq$ $\mathsf{PP}$ does it also show that $\mathsf{P}$ $\neq$ $\mathsf{NP}$?
2)What are the consequences of a Polynomial Time Algorithm for $\mathsf{A}$?
a)Does it put $\mathsf{B}$ in $\mathsf{P}$ as well?
b)Since $\mathsf{P} \subseteq \mathsf{UP} \subseteq \mathsf{FewP} \subseteq \mathsf{A}$ we will have $\mathsf{P} = \mathsf{UP} = \mathsf{FewP} = \mathsf{A}$ . Then can it still be the case $\mathsf{P}$ does not equal $\mathsf{NP}$?
c)Does it also show that $\mathsf{NP} \subseteq \mathsf{RP}$ since now  $\mathsf{RP}^\mathsf{UP} = \mathsf{RP}$?

1a) yes by the inclusion.
b) Not sure what you mean by "it". If P=PSPACE then A and B are both in P.

2a) Not necessarily, A could be much easier than B.
b) There are relativized worlds where P=FewP<>NP.
c) No, RP^UP does not necessarily contain NP. Don't confuse UP with Promise-UP.


Does LOGLOG = NLOGLOG? Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of languages which can be computed in space O(log log n) by a non-deterministic Turing machine (with two-way access to the input). Is it really not known that these classes differ?

I could only find some older surveys and a theorem that if they equal then L=NL (which is not just a trivial padding argument!), but somehow I feel that separating these classes cannot be that hard. Of course I might be completely wrong, but if every second bit of the input is the numbers from 1 to n in increasing order in binary, separated by some symbols, then the machines can already learn loglog n and with every other second bit we can input a problem that can fool a deterministic machine but not a non-deterministic one. I don't see yet exactly how this could be done but feels like a possible approach, as with this trick we can basically input a depth log n binary tree along with its structure instead of the usual linear tape.

The entry in the complexity zoo is surprisingly detailed; it claims that
NLOGLOG = co-NLOGLOG in the paper

  Nondeterministic computations in sublogarithmic space and space constructibility, Viliam Geffert, SIAM Journal on Computing, 1991.

But after a brief reading, I do not see any claim about the fact that NLOGLOG is closed under complement; maybe a deeper look is needed.
And the main result they have is that there are no nondeterministic fully space-constructible unbounded monotone increasing $s(n)$ functions for $s(n) = o(\log n)$. It is known that if such functions exists, then

$\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$.

And in the conclusion the author claimed that " ...this main separation problem remains open. "

As @chazisop said, the relations of these low-level complexity classes are depended on the models, and it is stated in the entry of the zoo that

  "There are several possible definitions of this class; the most common is the class of languages which can be computed in space O(log log n) by a deterministic Turing machine with two-way access to the input. "

Which is coincident to your definition and also the paper's.


Lower Bounds for Data Structures Are results known which rule out the existence of "too-good-to-be-true" data structures?

For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz and Sleator STOC '87) and still obtain $\mathcal{O}(1)$ time operations?

Or: can one implement an ordered set with integer keys and $\mathcal{O}(1)$ time operations? Of course this is at least as hard as discovering a linear time algorithm for sorting integers.

Has the answer been proven to be no for either of these questions? Are lower bound results known for any natural data structure?

There is a really nice talk on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t_q$ and update time $t_u$ (insert an edge):

See the paper for details. Some other papers by Mihai are relevant and nice, too.

UPDATE: I found that his PhD thesis "Lower Bound Techniques for Data Structures" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.


Classes of graphs with superconstant treewidth There are several interesting classes of graphs with bounded treewidth. For instance, trees (treewidth 1), series parallel graphs (treewidth 2), outerplanar graphs (treewidth 2), $k$-outerplanar graphs (treewidth O(k)), graphs of branchwidth $k$ (treewidth O(k)),...

Question: Are there examples of interesting classes of graphs whose treewidth is not bounded by a constant, but by a low-growing function?

Are there well known graph classes with treewidth $O(\log\log n)$?
Are there well known graph classes with treewidth $O(\log n)$?

I would also be interested in classes of graphs with treewidth
$O(\log^k n)$ or $O(\log\log...n)$ where the logarithm is repeated a constant number of times.

Obs: Of course it is easy to cook up artificial families of graphs with a given treewidth, like the family of $\;O(\log n)\times n\;$ grids. So I'm primarily looking for family of graphs which have been studied in other branches of graph theory and which happen to have treewidth $O(\log n)$ or $O(\log\log n)$, but non-constant treewidth.

I believe that the universal graphs for trees constructed by Chung and Graham 1983 have treewidth $\Theta(\log n)$. Or for a slightly simpler but similar example consider the transitive closures of balanced binary trees.

However, there's a negative result here, too. All the examples you give of interesting graph families are minor-closed, or very closely related to minor-closed families. But a minor-closed graph family either contains all planar graphs (and hence has maximum treewidth $\Theta(\sqrt n)$) or has a forbidden planar minor (and hence has bounded treewidth).


Help with the definition of clique percolation So I can find the Wiki article okay, as I think I understand that this is a definition of a special community in a graph.  However their image in Fig. 1 confuses me from the description.

As I understand it, the definition of a clique percolation within a graph is:

You have a set of k-maximal cliques, which contain k nodes.
You are said to have k-adjacent cliques if each k-maximal cliques are connected by (k-1)-nodes.

So a graph that was (1)<-->(2)<-->(3) could be considered a community because it has 2 2-maximal cliques, [[1,2], [2,3]], and each of them are connected by 1 vertex.

Am I reading the Wiki correctly, because I feel like I'm missing something. Thanks for any help your able to lend.

Technically yes, the graph you describe is one 2-clique percolated community. However, this is a reduced case, since a 2-clique is no more than an edge, and so a 2-clique percolated community is just a connected component.

For k > 2, clique percolation results in communities that are only detectable using this method. The example in Wiki uses 4-cliques.


Constant-time bounds on offline 2-choice hashing? I'm reading up on cuckoo hashing and came across Michael Mitzenmacher's blog posts on the subject. In his motivation of why cuckoo hashing seems like a reasonable strategy, he mentions a connection to 2-choice hashing:

  In the course of these results [about 2-choice hashing], the question arose as to whether one could do better if placing the elements offline. That is, if you had all n elements and their hashes in advance, could you place each element in one of their bucket choices and achieve a better load than the O(log log n) obtained by the sequential placement? The answer turns out to be yes. The best placement only has a constant maximum load. Another way to think of this is to say that if we place the elements sequentially, but retain the power to move them later, as long as each element ends up at one of its bucket choices, we could get down to constant maximum load.

I found this result really intriguing and have been trying to track down a source on it. However, I can't seem to find any papers on the subject that prove this particular result. I'm aware that cuckoo hashing itself can be thought of as an offline version of 2-choice hashing, but given that cuckoo hashing sometimes fails and requires a rehash, it doesn't seem like the traditional analysis of cuckoo hashing itself would meet the description given above (or does it?)

Does anyone have a source I could use to learn more about this?

You're missing the (obvious but) unstated caveat of "with high probability", I think.  If you're hashing randomly, there's some chance all items choose the same two buckets.  With high probability, you can get constant load.  I think I recall this was first shown to me by Alan Frieze, but I can't recall the reference.  Cuckoo hashing provides another way of showing this is true.


Set Cover with bounded intersection size So, the set cover problem is trivial if none of the candidate sets intersect eachother.

However, what if the size of the intersection for any pair of candidate sets was at most 1? Is this problem NP-hard?

I would appreciate any insight.

Thanks,
Garrett

If I'm not missing something, you can use a reduction from SINGLE OVERLAP RESTRICTED EXACT COVER BY 3 SETS (SINGLE OVERLAP RX3C) which I proved to be NPC in this cstheory question.

EXACT COVER BY THREE SETS (X3C):

Instance: Set $X=\{x_1,x_2,...,x_{3q}\}$ and a collection $C=\{C_1,...,C_m\}$ of 3-element subsets of $X$.
Question: Does C contain an exact cover for $X$, i.e. a subcollection $C′\subseteq C$ such that every element of $X$ occurs in exactly one member of $C′$?

X3C is NP-complete (see G&J), and as shown in [1] it remains NP-complete even if every element $x_i$ is contained in exactly 3 subsets of $C$ (RESTRICTED EXACT COVER BY THREE SETS, RX3C).

I proved that it remains NP-complete even if every pair of subsets in $C$  share at most one element; i.e. for all $i\neq j$, $|C_i \cap C_j|\leq 1$ (I called this restricted version SINGLE OVERLAP RX3C).

The SET COVER WITH BOUNDED INTERSECTION SIZE 1 (its decision version)  is simply a generalization of SINGLE OVERLAP RX3C, indeed you can pick the same universe $X$  and the same collection of subsets $C_1,...C_m$ of the SINGLE OVERLAP RX3C and ask for a cover with $q$ subsets or less.

Obviously a cover with $< q$ subsets cannot exist because every subset contains three elements and there are $3q$ elements in $X$. A cover with $q$ subsets must be exact: if two subsets contain a shared element then there are less than $3q$ elements covered.

[1] Teofilo F. Gonzalez: Clustering to Minimize the Maximum Intercluster Distance. Theor. Comput. Sci. 38: 293-306 (1985).


Can one amplify P=NP beyond P=PH? In Descriptive Complexity, Immerman has

  Corollary 7.23. The following conditions are equivalent:
  1. P = NP.
  2. Over finite, ordered structures, FO(LFP) = SO.

This can be thought of as "amplifying" P=NP to an equivalent statement over (presumably) larger complexity classes.  Note that SO captures the polynomial-time hierarchy PH, and that FO(LFP) captures P, so this can be thought of as P=NP iff P=PH.

(The interesting part of this is the statement that P=NP implies P=PH; it is trivial that P=CC implies P=NP for any class CC that contains NP.  Immerman simply remarks "if P=NP then PH=NP", presumably because P=NP can be used with the oracle definition of PH to show inductively that the whole hierarchy collapses.)

My question is:

  How much further can P=NP be amplified in this way?

In particular, what is the largest known class CC' such that P=NP implies P=CC', and the smallest class CC such that P=NP implies CC=NP?  This would allow P=NP to be replaced by the equivalent question CC=CC'.  P appears to be a rather powerful class, which seems to provide little "wiggle room" for arguments trying to separate it from NP: how far can the wiggle room be amplified?

I would of course also be interested in an argument that shows that P=PH is the limit of this approach.

Edit: note the closely related question Why doesn't P=NP imply P=AP (i.e. P=PSPACE)? which focuses on the other direction, why we don't have proofs that P=PSPACE.  Answers there by Kaveh and Peter Shor argue that the number of alternations being fixed is key.  Another related question is A decision problem which is not known to be in PH but will be in P if P=NP which asks for a candidate problem; the answers there also can be used to construct answers for this question, although these classes are somewhat artificial (thanks to Tsuyoshi Ito for pointing this out).  In a more general setting, Collapsing of exptime and alternation bounded turing machine asks whether a local collapse at any level in an alternation hierarchy induces an upward collapse, as happens with the polynomial-time hierarchy.

From  Russell Impagliazzo's comment:

  As a way of formalizing
  what languages are in $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$,
  Regan introduced the complexity class $\mathsf{H}$.
  A language $L$ is in $\mathsf{H}$ if and only if $L$ is in $\mathsf{P}^O$
  relative to every oracle $O$ so that $\mathsf{P}^O=\mathsf{NP}^O$.
  Thus, $L$ is in $\mathsf{H}$ if the statement
  $\mathsf{P}=\mathsf{NP} \implies L\in\mathsf{P}$ relativizes.
  $\mathsf{PH} \subseteq \mathsf{H} \subseteq \mathsf{AltTime}(O(\lg\lg n),\mathsf{poly})$.
  From Toda's theorem, and some of the lemmas in Toda's theorem,
  it is also true that $\mathsf{H} \subseteq \mathsf{P}^{\mathsf{mod}_q \mathsf{P}}$ for every $q$.
  Basically, any oracle satisfying $\mathsf{P}^O=\mathsf{NP}^O$
  gives a new upper bound on $\mathsf{H}$.
  It is open whether $\mathsf{H}=\mathsf{PH}$.

And from Lance Fortnow's comment:

  Let $f(n)$ be any unbounded function.
  $\mathsf{H}$ is not contained in $\mathsf{AltTime}(f(n),\mathsf{poly})$ and
  if you could prove
  $\mathsf{P}=\mathsf{NP}$ implies $\mathsf{P}=\mathsf{AltTime}(f(n),\mathsf{poly})$ then $\mathsf{NP}$ is different than $\mathsf{L}$.

For definition of $\mathsf{H}$ see definition 6.3 in

Kenneth W. Regan, "Index sets and presentations of complexity classes", 1999


What notable automaton models have polynomially-decidable containment? I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if you have machines $M_1, M_2$ you can test if $L(M_1) \subseteq L(M_2)$ efficiently.

The obvious ones that come to mind are DFAs and reversal-bounded counter machines where the number of counters is fixed (see this paper).

What other notable classes can be added to this list?

The more powerful the automata, the better. For example, DFA's aren't enough to solve my problem, and the counter machines can't do it with a fixed number of counters. (Naturally, if you get too powerful, then containment is either intractible, like for NFA's, or undecidable, for CFG's).

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can be solved in polynomial time. For more details, see the paper by Alur and Madhusudan, especially Chapter 6.

By the way, the nondeterministic variant of visibly pushdown automata is exponentially more succinct than the deterministic variant, but there the language inclusion problem is EXPTIME-complete and thus intractable.

Alur, R.; Madhusudan, P. (2009). "Adding nesting structure to words". Journal of the ACM 56(3): 1–43.


Is there a FNP problem that's NP-hard but not FNP-hard? For the reductions, choose a class C such that [it's clear what FC means]

and FC is not known to be able to solve the satisfaction search problem,

and assume that FC indeed can't solve that search problem.

With the following definitions of hardness for FNP problems R,

NP-hard   -   The corresponding decision problem is NP-hard (with respect to C reductions).

FNP-hard   -   There is a C reduction f from satisfiability to the corresponding decision problem

and a function g in FC such that for all instances x of the satisfiability problem,

for all strings y, if  f(x) R y  then g(x,y) is a satisfying assignment to x.

is there a FNP problem that's NP-hard but not FNP-hard?

I'm going to argue that the answer is probably "Yes", i.e.,

there probably are FNP problems that are NP-hard but not FNP-hard.

Warmup:  With respect to polynomially-closed reduction classes that can't solve all of FNPSPACE, FNPSPACE-hardness is different from NPSPACE-hardness.

Proof:        Let R be the relation given by xRy if and only if [x$\in$QBF$\hspace{.02 in}$ and y is the empty string].

QBF $\in$ PSPACE-complete $=$ NPSPACE-complete ,  so R is in FNPSPACE and NPSPACE-hard.

Let f and g form an arbitrary reduction from an arbitrary

relation S to R, and let x be an arbitrary instance of S.

x has an S-witness  $\implies$  f(x) has an R-witness  $\implies$

f(x) R empty_string  $\implies$  x S g(x,empty_string)  .

In other words, an arbitrary reduction from a search problem to R can be used

to solve the search problem.    Therefore R is not FNPSPACE-hard with respect

to polynomially-closed reduction classes that can't solve all of FNPSPACE.

Cryptographic Assumptions and sub-P reductions:

For each positive integer j, let R$\hspace{.02 in}$j be the relation given by  x R (C,v)  if and only if C is a circuit

and x is a CNF-SAT instace and  size(C) ≤ (number_of_variables_in_(x))$\hspace{.03 in}$j  and C(v) satisfies x.    Obviously, each R$\hspace{.02 in}$j is in FNP and NP-hard.    If they are all FNP-hard under non-uniform parallelizable reductions, then there can't even be a version of time-lock puzzles against

non-uniform adversaries that is otherwise very weak, namely, ones in which [the size of the

puzzle can be polynomial in the time for an honest user to solve it] and [there is no restriction

on the resources needed to create the puzzle] and [security only needs to hold infinitely often].  Furthermore, if there are efficiently-computable functions that are one-way against probabilistic

parallel adversaries then one can replace both instances of "non-uniform" with "probabilistic".

Probabilistic Polynomial-Time Reductions and handwaving:

(This is essentially tautological, but) If all NP-hard FNP problems are FNP-hard, then all

proof systems for SAT are "somewhat constructive", in the sense that any original instance can

be efficiently turned an equisatisfiable instance so that one will be able to go from any proof of

satisfiability of the equisatisfiable instance to a satisfying assignment of the original instance.

Non-interactive zaps are certainly not obviously "somewhat constructive" in that sense.


Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$? I expect the answer is no, but I could not actually construct a counterexample.  The difference is that in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$, we might not be able to pick an $O(n^{2+ε})$ algorithm uniformly in $ε$.

By a dovetailing argument (for example, see this question), if there is a c.e. set of Turing machines $M_i$ deciding a language $L$ such that $∀ε>0 ∃M_i ∈ O(n^{2+ε})$, then $L$ is in $\mathrm{DTIME}(n^{2+o(1)})$.

Given a Turing machine, whether the machine runs in time $n^{2+o(1)}$ is $Π^0_3$-complete. Whether a language (given a code for a machine recognizing it) is in $\mathrm{DTIME}(n^{2+o(1)})$ is $Σ^0_4$ (and $Π^0_3$-hard); whether a language is in $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε}))$ is $Π^0_3$-complete.  If we can prove $Σ^0_4$ completeness (or just $Σ^0_3$-hardness) of $\mathrm{DTIME}(n^{2+o(1)})$, that would solve the problem, but I am not sure how to do that.

The problem would also be solved if we find a sequence of languages $L_i$ such that
* $L_i$ has a natural $O(n^{2+1/i})$ decision algorithm (uniformly in $i$).
* Each $L_i$ is finite.
* Not only is the size of $L_i$ undecidable, but an algorithm cannot rule out $w∈L_i$ much faster than $O(n^{2+1/i})$ (for worst case $w$), except for finitely many $i$ (dependent on the algorithm).

I am also curious whether there any notable/interesting examples (for $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) \setminus  \mathrm{DTIME}(n^{2+o(1)})$ or an analogous relation).

Here is a counterexample, i.e. a language with an $O(n^{2+ε})$ algorithm (using multitape Turing machines) for every $ε>0$, but not uniformly in $ε$:
Accept $0^k 1^m$ iff $k>0$ and the $k$th Turing machine halts in less than $m^{2+1/k}$ steps on the empty input.  Other strings are rejected.

For every $ε$, we get an $O(n^{2+ε})$ algorithm by hardcoding all sufficiently small nonhalting machines, and simulating the rest.

Now, consider a Turing machine $M$ deciding the language.

Let $M'$ (on the empty input) be an efficient implementation of the following:
for $n$ in 1,2,4,8,...:
     use $M$ to decide whether $M'$ halts in $<n^{2+1/M'}$ steps.
     halt iff $M$ says that we do not halt but we can still halt in $<n^{2+1/M'}$ steps.

By correctness of $M$, $M'$ does not halt, but $M$ takes $Ω(n^{2+1/M'})$-steps on input $0^{M'} 1^{n-M'}$ for infinitely many $n$.  (If $M$ is too fast, then $M'$ would contradict $M$.  The $Ω(n^{2+1/M'})$ bound depends on $M'$ simulating $M$ in linear time and otherwise being efficient.)


Lower bounds on the period in integer factorization? In 1975, Miller has shown how to reduce the factorization of integer $N$ to finding the period $r$ of a function $f(x)=a^x\;\bmod\;N$ such that $f(x+r)=f(x)$ with some randomly chosen $a<N$. It is well known that Shor's algorithm can find $r$ efficiently on a quantum computer, whereas it is believed to be intractable for a classical computer to find $r$.

My question now is: Are there any known lower bounds on $r$ for random $N$? Are there any bounds on $r$ given $N=pq$ is chosen as in RSA? Clearly, $r$ must be $\Omega(\log(N))$ as otherwise one could just evaluate $f(x)$ on $O(\log(N))$ successive points to figure out $r$ classically. Would it suffice to break RSA if there was a classical factoring algorithm which only works under some assumption on the distribution of $r$, e.g. $r \in \Theta(N/\log(N))$ or $r \in \Theta(\sqrt{N})$?

A presentation of Carl Pomerance on "The multiplicative order mod $n$ on average" cites evidence that $r$ is $O(N/\log(N))$ on average over all $N$, yet I'm not sure whether a classical algorithm which can factor $N$ under the hypothesis of $r \in O(N/\log(N))$ would conclusively break RSA. Can $N$ be adverserially chosen to have $r \in O(N))$ or $r \in O(\sqrt{N})$?

(Note: There is a related question on generic factoring vs. RSA factoring)

If $N=pq$, the period $r$ will always be a divisor of $\phi(N)=\mathrm{lcm}(p-1,q-1)$. If you choose $p-1=2p'$ and $q-1=2q'$ for $p',q'$ prime, then unless you are incredibly lucky, we will have $r \geq p'q' \approx N/4$. I also believe that we can efficiently find primes $p$ with $p=2p'+1$ by choosing candidates randomly and testing them (this is true if the events that $p$ and $p'$ are prime are roughly independent; I don't know whether this has been proven). Thus, by carefully choosing your primes, RSA will still be secure against attacks even with the additional hypothesis about easy factoring.

I suspect random numbers $N$ or random $N=pq$ are extremely unlikely to have $r \in O(\sqrt{N})$, but I don't have a proof of this offhand. The hypothesis $r\in O(\sqrt{N})$ is extremely strong, and I wouldn't be surprised if an efficient factoring algorithm were already known for this case.


Kolmogorov Complexity of a Decidable Language The Kolmogorov Complexity (KC) of a string $y$ is the size of the smallest program $f$ and input $x$ that: $y = f(x)$. Let's define a variation of Kolmogorov's complexity$^1$. Suppose a decidable language L, the Kolmogorov Complexity of a Decidable Language (KCDL) $^2$ is the size of the smallest program that decides on L.

  Is it possible to reduce KC to KCDL? If so, is it possible to do the reverse?

Notes

I don't know if anyone has already defined this concept, so if you have any reference to that definition or even it doesn't make sense, I would be happy if someone commented.
we can generalize this concept to more classes of languages, but I prefer to keep it simple here.

Addendum: $f(w)$ is a computable function that decides $w$ is a word in the language $L$. And, KCDL is define as:
$$\text{KCDL}(f) = \min \{ \text{length}(p) : \forall p \in TM, p \text{ compute } f\}$$

And, note that there is a difference between:

the compressed version of a program that computes a function;
the smallest program that computes the same function.

If you want to think of the compressed version of a program as the program itself, you cannot forget to take into account the size of the smallest program that does the decompression. Because, first you need to unzip the program file to be able to use it.

Yes, depending on what kinds of inputs you consider (see below). $KC(x) =^* KCDL(L_x)$, where $L_x$ is the language which consists only of the string $x$, and $=^*$ means equals up to an additive constant.

The reverse is probably not possible (I think I proved this at one point but can't find it right now). The idea is that Kolmogorov complexity can be solved with a Halting Problem oracle, but KCDL (when the input is a TM) is, if I recall correctly, hard for a higher level of the arithmetic hierarchy.

If you want to talk about the complexity of KCDL you also have to be careful to define what the input is. You want the input to be some finite object - languages are generally not. One natural thing for decidable languages is that the input should be a (total) TM. Another possibility is that the input is a TM, along with a proof (in some fixed, formal language) that the TM is total. Other possibilities exist too.

I haven't seen published work about it, but I thought about it a bit in grad school and proved/observed some elementary results. You can do the same for any computable function, not just a language.