Splay tree potential function: why sum the logs of the sizes? I'm teaching a course on data structures and will be covering splay trees early next week. I've read the paper on splay trees many times and am familiar with the analysis and intuition behind the data structure. However, I cannot seem to find a solid intuition for the potential function that Sleator and Tarjan use in their analysis.

The analysis works by assigning each element in the tree an arbitrary weight $w_i$, then setting the size $s(x)$ of a node to be the sum of the weights of the nodes in the subtree rooted at $x$. They then take the log of this value to get the rank $r(x)$ of the node, so $r(x) = \log s(x)$. Finally, the potential function of the tree is defined as the sum of the ranks of all the nodes.

I understand that this potential function works correctly and I can follow the analysis, but I don't see why they would choose this potential. The idea of assigning a size to each node makes sense to me, since if you sum up the sizes, you get the weighted path length of the tree. However, I can't figure out why they decided to take the logs of the weights and then sum those up instead - I don't see any natural property of the tree that this corresponds to.

Does the potential function of the splay tree correspond to some natural property of the tree? Is there a particular reason, other than "it works," that they would choose this potential? (I'm specifically curious because this set of course notes mentions that the "analysis is black magic. [N]o idea how discovered")

Thanks!

How to come up with sum-of-logs potential

Let's consider the BST algorithm $A$ that for each access for element $x$, it rearranges only elements in the search path $P$ of $x$ called before-path, into some tree called after-tree. For any element $a$, let $s(a)$ and $s'(a)$ be the size of subtree rooted at $a$ before and after the rearrangement respectively. So $s(a)$ and $s'(a)$ may differ iff $a \in P$.

Moreover, $A$ only rearranges constantly many elements in the search path at any moment. Let's call this type of algorithm "local" algorithm. For example, splay tree is local. It rearranges only at most 3 elements at a time by zig, zigzig and zigzag.

Now, any local algorithm that creates "many" leaves in the after-tree, like splay tree, has the following nice property.

  We can create a mapping $f: P \rightarrow P$ such that

  There are linearly many $a \in P$,  where $s'(f(a)) \le s(a)/2$.
  There are constantly many $a \in P$, where  $s'(f(a))$ can be large but trivially at most $n$.
  Other elements $a \in P$, $s'(f(a)) \le s(a)$.

We can see this by unfolding the change of search path. The mapping is actually quite natural. This paper, A Global Geometric View of Splaying, precisely shows the details how to see the above observation.

After knowing this fact, it is very natural to choose sum-of-logs potential.
Because we can use the potential change of the type-1 elements to pay for the whole rearrangement. Moreover, for other-type elements, we have to pay for the potential change by at most logarithmic.
Hence, we can derive logarithm amortized cost.

I think the reason why people think this is "black magic" is that the previous analysis do not "unfold" the overall change of the search path, and see what really happens in one step.
Instead, they show the change in potential for each "local transformation", and then show that these potential changes
can be magically telescoped.

P.S. The paper even shows some limitation of sum-of-logs potential.
That is, one can prove satisfiability of access lemma via sum-of-logs potential to only the local algorithm.

Interpretation of sum-of-logs potential

There is another way to define the potential of BST in Georgakopoulos and McClurkin's paper which is essentially the same as sum-of-logs potential in Sleator Tarjan's paper. But this gives good intuition to me.

Now I switch to the notation of the paper. We assign a weight $w(u)$ to every node $u$. Let $W(u)$ be the sum of the weight of $u$'s subtree. (This is just the size of $u$'s subtree when the weight of every node is one.)

Now, instead of defining the rank on the nodes, we define the rank to the edges, which they called progress factor.

$$pf(e)=\log(W(u)/W(v)).$$

And the potential of tree $S$ is

$$\Phi(S) = \sum_{e\in S} pf(e).$$

  This potential has a natural interpretation: if during a search we traverse an edge $(u,v)$ we reduce the search space from the descendants of $u$ to the descendants of $v$, a frantional reduction of $W(u)/W(v)$. Our progress factor is a logarithmic measure of this 'progress', hence its name. [From Section 2.4]

Observe that this is almost equal Sleator Tarjan's potential, and it is additive on paths.

edit: It turns out that this alternative definition and the intuition behind it was described long ago by Kurt Mehlhorn. See his book "Data Structures and Algorithms" Volume I, Section III. 6.1.2 Splay Trees,  pages 263 - 274.


Halting time of non deterministic machine Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever.

The Machine have no input. A configuration of a Minsky Machine is the triplet (a state, value of counter 1, value of counter 2). (There is a similar notion of configuration for every machine).  The initial configuration is (state0, 0, 0)

Its computation is a list of successive configuration, that halts in an halting state. The lenght of the computation $s$ is the size of the list, and is denoted by $|s|$.

Let $H(K)$ be the set of computation of this machine that halts.  Then let $S(K)$ be the set of the length of those computation, that is $S(K)=\{|s|\mid s\in H(K)\}$.  It is similar to the "spectral theory" notion http://en.wikipedia.org/wiki/Spectrum_of_a_theory . That is, we forgot everything from a set apart a number.

Finally, let $\mathcal S$ be the set of $S(K)$ for every machine $K$. $\mathcal S=\{S(K)\mid K\}$.
Is there anything we can say about $\mathcal S$ ? Trivially, I can say that it contains only computable sets. It contains every finite set; but between those information, I'm lost.

In an intuitive sense, I'm interested by finding the most complex set of $\mathcal S$.

I should  emphasize that this problem is very different from the $\#P$ class, since: 1) the machine doesn't have any input. 2) I'm not interested in the number of halting path.

Claim: $S\subseteq NEXP$.

To prove it, take $L\in S$. It follows that there exists a machine $K$ s.t. $L=S(K)$. I imagine $K$ to be a Turing machine because I am more familiar with them. Now $n\in L$ iff there exists some computation of $K$ on empty input of length $n$. So we can verify whether $n\in L$ by non-deterministically guessing first $n$ steps of $K$ on empty input and verifying whether $K$ halts after this $n$ steps. $\square$

Considering that the problem of verifying whether a non-deterministic TM makes at most $n$ steps on empty inpuit on some computation is NEXP-complete (NEXP-complete problems), I would guess that $S$ contains arbitrary hard NEXP problems.


Ensemble of tree decompositions for all-pairs problem Suppose we have a bounded tree width graph $G=\{E,V\}$ and want to count the number of self avoiding walks on $G$ passing through nodes $u$ and $v$ for all pairs of nodes $(u,v)$. For a single pair $(u,v)$, one approach is dynamic programming on a  tree decomposition of the graph constrained to have a bag containing both $u$ and $v$. For all pairs of nodes, one may need to consider several tree decompositions, so that every pair of vertices is contained in some bag of some decomposition. The interesting question is how to come up with a such a set of tree decompositions so that they the overall problem complexity is kept low. Has this kind of problem been studied?

Some other problems where "tree decomposition ensemble" might be useful

all pairwise marginals in a graphical model
two-point correlation function for Ising/Potts/hardcore models on finite graph
Hessian of $f:\mathbb{R}^{|V|}->\mathbb{R}$ where $f$ is some function whose computation relies on tree decomposition of $G$. For instance, $f$ could be multivariate Potts polynomial of $G$, some general labeled graph polynomial or partition function of Gibbs distribution on $G$
computing how some FP+C definable graph invariant is affected by deletion of any pair of vertices

I would simply do as follows:

Start with a tree decomposition $T$ of $G$. Each time you would like to compute the number of self avoiding walks on $G$ passing through $u$ and some other node, do dynamic programming on the tree decomposition $T'$ obtained from $T$ by adding $u$ to each bag of the tree decomposition. The width of $T'$ is at most the width of $T$ plus one, and you cannot hope for anything better in general.


Relationship between two graph optimization problems Let $Q$ be a polynomial time computable graph property of simple, undirected graphs. Consider the following two optimization problems on any input graph:

P1. Find a largest induced subgraph of the input graph with property $Q$, or detect if no such subgraph exists. (Largest = maximum number of vertices.)

P2. Partition the vertices of the input graph, such that the number of partition classes is minimum, and each class induces a subgraph with property $Q$, or detect if no such partition exists.

Several choices of $Q$ lead to classical problems, for example:

$Q(G)$="$G$ is an independent set." Then P1 is the max independent set problem, P2 is minimum coloring. Both are NP-hard.
$Q(G)$="$G$ is a clique." Then P1 is the max clique problem, P2 is minimum clique cover. Both are NP-hard.
$Q(G)$="$G$ is Hamiltonian." Then P1 looks for a largest circle, P2 looks for a minimum partition into Hamiltonian subgraphs. Both are NP-hard.
$Q(G)$="$G$ is connected." Then P1 looks for the largest connected component, while P2 looks for the number of connected components. Both are solvable in polynomial time.
$Q(G)$="$G$ has a perfect matching." Then P1 looks for a maximum matching, if the input graph has at least one edge, otherwise there is no subgraph with the property. The solution for P2 is the trivial partition with one class if the input graph has a perfect matching, or otherwise there is no feasible partition. Both cases are solvable in polynomial time.

Question: is there any (preferably natural) choice for the property $Q$, which makes one of the problems P1,P2 NP-hard, while the other is solvable in polynomial time?

One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the minimum size dominating set, which is NP-hard.


Fun with inverse Ackermann The inverse Ackermann function occurs often when analyzing algorithms. A great presentation of it is here: http://www.gabrielnivasch.org/fun/inverse-ackermann.
$$\alpha_1(n) = [n/2]$$
$$\alpha_2(n) = [\log_2 n]$$
$$\alpha_3(n) = \log^* n$$
$$...$$
$$\alpha_k(n) = 1 + \alpha_k(\alpha_{k−1}(n))$$
and
$$\alpha(n) = \min\{k: \alpha_k(n)\leq 3\}$$
[Notation: [x] means that we round up x to the nearest integer, while log∗ is the iterated log function discussed here: http://en.wikipedia.org/wiki/Iterated_logarithm ]

My question is: What is the function
$$k(n) = \min \{k: \alpha_k(n) \leq k\}$$
Clearly $1\ll k(n) \leq \alpha(n)$. What tighter bounds can one give on $k(n)$? Is $k(n) \leq \log\alpha(n)$?

Let $A_k$ be the inverse of $\alpha_k$. $A_1(x) = 2x, A_2(x) = 2^x, \dots$. I claim that $k^{-1}(x) = A_x(x)$.

Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) > \alpha_x(z)$, $\alpha_y(A_x(x)) > \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.

Now consider the value of $\alpha(k^{-1}(n)) = \alpha(A_n(n))$. By definition of $\alpha$, this is $\min_z \{\alpha_z(A_n(n)) \leq 3\}$. We know that $\alpha_n(A_n(n)) = n$, so $\alpha(A_n(n)) > n$. I claim that $\alpha(A_n(n)) \leq n+2$. $\alpha_{n+1}(A_n(n)) = 1+\alpha_{n+1}(n)$. Now $\alpha(n) = \min_z\{\alpha_z(n) \leq 3\}$, so $\alpha_{\alpha(n)}(n) \leq 3$. Since $n+1 > \alpha(n)$, $\alpha_{n+1}(n) \leq 3$, so $\alpha_{n+1}(A_n(n)) \leq 4$. Thus, $\alpha_{n+2}(A_n(n)) = 1 + \alpha_{n+2}(\alpha_{n+1}(n)) \leq 1 + \alpha_{n+2}(4) \leq 3$.

So, we have $n < \alpha(k^{-1}(n)) \leq n+2$, so $k$ and $\alpha$ are essentially equal.


Does the following 2-rounds distributed algorithm approximates a maximal matching well? Let $G$ be an undirected graph.

I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.

Consider the following protocol for vertex $v$.

Use a fair coin to choose a ``status'' $s_v\in\{\mathit{active},\mathit{passive}\}$.

2.a. If $s_v=\mathit{active}$ send request to a random neighbor.

2.b. If $s_v=\mathit{passive}$ and you have received at least one request, respond with accept to a single requestor, chosen at random.

Each request paired with accept adds an edge to the resulting matching.

Let $M$ be a minimum maximal matching (i.e., the maximal matching with the smallest cardinality) of $G$, and let $M'$ be the matching generated by the above algorithm.

  What can we say about $\mathbb E[|M'|] / |M|$? is the generated matching expected to be a good approximation for a maximal matching? e.g., do we have $\mathbb E[|M'|] / |M|=\Omega(1)$ for any graph $G$?

No. For the following graph the expected size of the generated matching is $O(\sqrt n)$, but any maximal matching has size $\Theta(n)$.

The graph consists of a $k$-vertex core $C$ and a matching $M_0$ of $k^2$ edges and vertices (disjoint from $C$), plus all edges $(u,w)$ where $u\in C$ and $w\in M_0$.

lemma 1. Any maximal matching $M$ has $\Omega(k^2)$ edges

Proof. Every edge in $M_0$ is either in $M$ or is touched by an edge in $M$ into $C$, but all at most $k$ edges of $M$ can touch $C$. QED

lemma 2. In your random process, the expected number of edges chosen in the random matching is $O(k)$.

Proof.  Clearly at most $k$ edges are chosen that are not in $M_0$ (as there are only $k$ vertices in $C$).  For a given edge $(u,w)$ in $M_0$, the chance that it is chosen is $O(1/k)$, because, given that, say, $u$ is active and $w$ is passive, the chance that $u$ picks $w$ is $O(1/k)$, as $w$ has $k$ other edges (to $C$). QED

(One thing you can prove about your process is that, for any graph, in expectation, a constant fraction of the edges will touch the edges in the generated matching.  See e.g. here.  Roughly, if you direct each edge $(u,w)$ from the lower-degree vertex to the higher-degree vertex, and call a vertex good if more than one-third of its incident edges are directed into it, then at least half the edges must be directed into good vertices (Lemma 6).  And each good vertex has constant probability of being matched in your process.  So, at least half the edges touch vertices that have a constant probability of being matched.

EDIT: So after $O(\log n)$ rounds of your process, it will have a maximal matching with high probability.)


Learning k-parities with Membership Queries and Persistent Noise Random independent misclassification error is an inappropriate noise model for a membership query (MQ) oracle because for any noise rate $\eta<1/2$ one can eliminate noise to an arbitrary extent by simply querying the oracle $p(1/(1-2\eta))$ times with the same input for some polynomial $p(\cdot)$ and taking the majority label returned.

The random persistent misclassification noise model of Goldman, Kearns, and Schapire, plugs this "loophole" by stipulating that an oracle that assigns a label $l$ to some sample $x$, always assigns label $l$ to sample $x$.

My question is: What are the known best upper bounds on the time and queries required to solve the learning parities problem with membership queries and random persistent misclassification noise for some constant value of $k$ (the number of relevant attributes)? Is the problem known to be solvable in $O(n \log (n/\delta))$ time and $O(\log (n/\delta))$ queries w.r.t. $n$, the number of attributes and $\delta$, the probability of error?

If I understand correctly, this is exactly equivalent to local decoding of the Hadamard code.

We can think of the oracle (with the noise) as being chosen beforehand, and after that we can view the oracle as a corrupted codeword of the Hadamard code. Learning the parity in this case is exactly the task of local decoding the original message from the corrupted codeword.

This is well-known to be possible using $O(n \log n/\delta)$ queries, using the Goldreich-Levin theorem, e.g.:
https://lucatrevisan.wordpress.com/2009/03/09/cs276-lecture-12-goldreich-levin/

On the other hand, it clearly can not be done using $o(n)$ queries, since the algorithm has learn $n$ bits about the parity - i.e., its attributes.


Provable gaps between decision tree complexity and "true" complexity The title is a little misleading: but hopefully the question isn't:

Grønlund and Pettie's new result showing that 3SUM has only $O(n^{3/2})$ decision tree complexity got me wondering:

  Is there a simple example of a problem with a decision tree complexity of $O(f)$ but that admits a lower bound (in a more detailed model) of $\omega(f)$ ?

In other words, how should the result on 3SUM change our view of the possibility of getting a significantly lower than $n^2$ upper bound on the complexity of the problem ?

Meyer auf der Heide described a non uniform family of linear decision trees for Subset Sum with depth $O(n^4\log n)$.  A similar result can be deived from a later algorithm of Meiser for point location in hyperplane arrangements. Of course the problem is NP-hard.


When is the Journal of the ACM issued? Is there a specific time that the Journal of the ACM is released? Monthly, quarterly, etc? Or does it depend on how many significant papers have been gathered to warrant a new issue? I couldn't find anything specific on their website on this point.

Judging from their archive, it seems that since 1994 the Journal of the ACM is issued 6 times a year, so roughly every other month. Until 2006 it was published on odd months. From 2007 on, the schedule seems to be somewhat random, but there are still 6 issues a year (though sometimes one of them is published on the wrong year, as in 2009 and 2010).


multi-commodity flow acyclic digraphs I am faced with the following question on max. integer multiflow:

INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function d:{1,…,k}→N.
Objective: Find the integer flows satisfying maximum demand.

what is the hardness status of this problem?

The problem is at least as hard the maximum edge-disjoint paths problem (MEDP) since we can set $d(i) = 1$ for each pair. The approximability of MEDP has been investigated extensively and in particular it is known that MEDP in directed graphs is hard to approximate to within a factor of $m^{1/2-\epsilon}$ (technically it is $n^{1/2-\epsilon}$ since the graphs are sparse). This was shown in a paper of Guruswami etal. http://www.sciencedirect.com/science/article/pii/S0022000003000667. Roughly at the same time there was another paper by Ma and Wang established hardness of $2^{\log^{1-\epsilon} n}$ for acyclic graphs. More recent work by Chuzhoy etal showed hardness results even with congestion allowed; my understanding is that the hardness holds even for instances that are acyclic and these results are stronger than the one by Ma and Wang, however, one should look more carefully at the paper to make sure or ask the authors.


Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$ Say I have an undirected, weighted graph $G=(V,E)$ and I know a hamiltonian cycle of minimum weight in that graph. Can I use that information to efficiently find a hamiltonian cycle in $G'=(V',E')$ where $V'=V-\{v\}$ for some vertex $v$ and $E'$ is $E$ with all edges touching $v$ removed?

It is safe to assume that there still exists a hamiltonian cycle in $G'$.

I believe the answer is no and here is why.

Assume that I can efficiently find a hamiltonian cycle of minimum weight in $G'$ given a hamiltonian cycle of minimum weight in $G$. I can use this procedure to find a hamiltonian cycle in any graph, say $A$.

The procedure would work like this. Take $A$ and add vertices and edges (with weight $0$) such that a hamiltonian cycle of weight $0$ is easy to find. The cycle, for example, could alternate between new vertices and the original vertices of $A$. Since all new edges have weight $0$, the cycle weight would be $0$. If we call the new graph $A_1$, we know a simple hamiltonian cycle in $A_1$. Remove one of the newly added vertices from $A_1$ to create $A_2$ then run our procedure to efficiently find a hamiltonian cycle in $A_2$. Then repeat the procedure.

Eventually we will arrive at a graph, say $A_k$, which only has one extra vertex when compared to $A$. We will know a hamiltonian cycle in $A_k$ from the procedure above. So we can use this information to efficiently find a hamiltonian cycle in $A$ (using the same procedure as above).

Therefore, finding a hamiltonian cycle in $G'$ given one in $G$ must be at least as hard as finding a hamiltonian cycle in general.


complexity of CSPs with 2-variable constraints and multi-valued variables (CSP = "constraint satisfaction problem")

CSPs for which either the variables are restricted to less than two values or the constraints
take less than two inputs are obviously trivial, and Schaefer's dichotomy theorem

gives the complete situation for variables with two possible values.

How hard is it to solve CSPs with 2-variable constraints

but variables that can take more than two values?

With 3 values and binary relations, the CSP is still NP-complete (it is denoted with (3,2)-CSP). A quick reduction is from graph coloring:

add a variable $x_i \in \{1,2,3\}$ for each node; then for each edge $(x_i,x_j)$ add the constraint $x_i \neq x_j$


Compactly representing the solution set of a SAT instance This question has risen in my mind after reading András Salamon's and Colin McQuillan's contributions to my previous question Counting solutions of Monotone-2CNF formulas.

EDIT 30th Mar 2011
Added question n° 2.
EDIT 29th Oct 2010
Question rephrased after András proposal to formalize it through the notion of nice representation of a solution set (I've modified his notion a little bit).

Let $F$ be a generic CNF formula with $n$ variables. Let $S$ be its solution set. Clearly, $|S|$ may be exponential in $n$. Let $R$ be a representation of $S$. $R$ is said to be nice if and only if the following facts are all true:

$R$ has polynomial size in $n$.
$R$ allows to enumerate the solutions in $S$ with polynomial delay.
$R$ allows to determine $|S|$ in polynomial time (i.e. without enumerating all the solutions).

It would be great if it is possible, in polynomial time, to build such a $R$ for every formula.

  Questions:

  Did anyone ever prove that there exists a family of formulas for which such a nice representation can't exist?
  Did anyone study the relationship between the representation of $S$ and the symmetries exhibited by $F$? Intuitively, symmetries should help to compactly represent $S$ because they avoid the explicit representation of a solution subset $S' \subset S$ when $S'$ actually boils down to just one solution (i.e. from every $s_i \in S'$ you can recover every other $s_j \in S'$ by applying a proper symmetry, thus every $s_i \in S'$ is itself representative of the whole $S'$)

As stated (revision 3), the question has a simple answer: no.

The reason is that even for the highly restricted class of representations given by Boolean circuits with AND, OR, and NOT gates, no nontrivial lower bounds are known.  (Clearly a circuit that represents $F$ will also represent $S$ implicitly, and it is easy to enumerate the solutions by changing the inputs to the circuit.)

For even more restricted representations, like monotone or constant depth circuits, exponential lower bounds are known.  There are also exponential lower bounds for representing formulas in CNF or DNF form, although these can be seen as special cases of constant depth circuits.  Finally, BDD representations can be seen as compact forms of DNF, but there exist formulas for which the BDD requires exponential size for any variable ordering.

To make your question more precise, please consider @Joshua's answer in some detail, and please clarify what you mean by "trivial to enumerate every single solution".

For revision 4, note the statement about BDD size.  Part of what you seem to be asking is: is there a more compact representation of DNF formulas than BDDs?  Let "BDD $B$ has superpolynomial size" mean "every BDD representing the same function as $B$, regardless of variable ordering, has superpolynomial size", and let "nice representation" mean "a representation that allows solutions to be enumerated with polynomial delay".  This more specific question then becomes:

  is there a family of formulas and a nice representation that has polynomial size while its BDDs have superpolynomial size?

Does this capture the essence of what you are asking?


Complexity of comparison unary>binary What is the smallest widely-known complexity class to which
$$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\land & j\ \text{is a binary encoding of a nonnegative integer}\ \hat\jmath\\\land & \hat\imath>\hat\jmath\end{array}\right\}$$
belongs to? The language is probably nonregular, but definitely in DLOGSPACE. Does this language lie in any smaller well-known class?

The problem is in coNLOGTIME, for example using the following algorithm. As is well known, one can determine the length of input $n$ in binary in DLOGTIME. Then, read off at most $\log n$ bits from the end of the input to find $j$ (if it is longer, reject). This also determines $i=n-1-\lfloor\log(j+1)\rfloor$ (I am assuming one character for the separator), so it remains to check that $i>j$, and that the beginning of the input is indeed a valid unary encoding: only the last part uses nondeterminism. (That is, the problem would be in DLOGTIME if it were defined so that any string of length $i$ counted as a unary encoding of $i$.)


Minimum shortest path cover of $n$ vertices in $R^m$ Informally, we define minimum shortest path cover to be the smallest number of shortest paths that cover all vertices of a graph. In other words, every vertex should belong to at least one of those shortest paths (there is no problem if one vertex belongs to more than one paths). Formally, we define the problem as follows. Assume the directed graph $G=(V,E)$ with vertices $V=\{v_1, ..., v_n\}$, with non-negative edge weights $w(v_i,v_j) \ge 0$. We have following definitions respectively:

weight of a path: if $P=u_1, ...,u_{|P|}$ then $w(P) = \sum w(u_i,u_{i+1})$
set of all path covers of $G$: $PC(G)=\{\{P_1, ..., P_k\} |\forall i \exists j: v_i \in P_j\}$.
Size of a path cover: if $PC=\{P_1, ..., P_k\}$ then $Size(PC)= k$
set of all paths of $G$ starting from $v$ and ending in $u$: $P(G, v, u)=\{v, v_{i_1},...,v_{i_l}, u | \forall j: v_{i_j}, u, v \in V, (v_{i_j},v_{i_{j+1}}), (v,v_{i_1}), (v_{i_{|P|}},u)\in E\}$
set of all shortest paths of $G$ by $SP(G) = \{P =
   v_{i_1}, ..., v_{i_{|P|}} | \forall Q \in P(G,v_{i_1},v_{i_{|P|}}), w(P) \le w(Q)\}$.
Set of shortest path covers of $G$: $SPC(G)=\{PC=\{P_1, ..., P_k\} | PC \in PC(G), \forall i: P_i \in SP(G)\}$
Minimum shortest path cover of G: if $PC \in SPC(G)$ and $\forall Q \in SPC(G): Size(P) \le Size(Q)$ then $MSPC(G) = PC$

To give a concrete example, suppose graph $G=(V,E)$, with vertices $ V=\{1,2,3,4\}$, and edges $E=\{1\rightarrow 2,1\rightarrow 5, 2\rightarrow 3,4\rightarrow 5\}$. It is clear that $G$ could be covered by two paths. The minimal set would be $MSPC(G)=\{1\rightarrow 2 \rightarrow 3,\ 4\rightarrow 5 \}$.

Now we informally construct the graph $G$ as follows. Its set of vertices ${v_1, v_2, ..., v_n}$ are points in $R^m$. Then we put the $k$ nearest vertices to $v_i$ (euclidean distance) in its adjacency list $Adj(n_i)$. Noting that $n_i \in Adj(n_j)$ does not imply $n_j \in Adj(n_i)$, the formed graph is directed and not necessarily symmetric. We can hold $k$ to be constant or $k \ll n$, in a way that the graph would become sparse.More formally we have following definitions:

vertices: $V={v_1, v_2, ..., v_n}, \forall i: v_i \in R^m$
distances: $d(u,v)$ denotes euclidean distance between $d(u,v)=||u-v||_2$
k-nearest neighbours: $N_k(u)=\{u_1, ..., u_k\}$ in that $\forall u_1 \in N_k(u), u_2 \notin N_k(u)$ implies $d(u,u_1) \le d(u,u_2)$.
edges: $E=\{(u,v) | u,v \in V, v \in N_k(u)\}$. Alternatively, $Adj(u)=N_k(u)$.
weights: if $(u,v) \in E$ then $w(u,v) = d(u,v)$.
Graph: $G=(V,E)$.

UPDATE: Some additional notes:

Shortest paths are unique.
k is chosen large enough to keep $G$ connected
A special case of interest is when nodes are dense $n \rightarrow \infty$ in a limited space (say unit hypercube $(0,1)^m$), and they follow a specific distribution (namely uniform).

Using the above definitions, the question is what is the asymptotic value of $Size(MSPC(G))$ or $E\{Size(MSPC(G))\}$ in the case of stochastic points? My intuition is that it is of the form $O(n^\frac{m-1}{m})$, which comes from the number of necessary paths to cover a $m$-dimensional regular grid in $R^m$. Suppose we have $l^m$ vertices $(a_1, ..., a_m), a_i \in \{1, ..., l\}$. You could cover this grid by $l^{m-1}$ paths like this: $Path-Cover = \{\{(1, P), (2, P), ..., (l, P)\}| P \in \{1,...,l\}^{m-1}\}$. Substituting $l^m$ by $n$ the $O(n^\frac{m-1}{m})$ bound could be achieved.

Without further assumptions about the point set, the answer can be anywhere between $1$ and $n/(k+1)$.

Lower bound: Consider the 1-dimensional point set in which $v_i = 2^i$.  For every  index $i > 1$, the nearest neighbor of $v_i$ is $v_{i-1}$.  So the directed $1$-nearest-neighbor graph can be covered by a single shortest path $v_n \to v_{n-1} \to\cdots \to v_1$.
Upper bound:  Consider the 1-dimensional point set where
$$v_i = n^2 \lfloor i/(k+1) \rfloor + (i\bmod (k+1)).$$  This point set consists of $n/(k+1)$ tight clusters of $k+1$ points, with large gaps between the clusters.  The $k$ nearest neighbors of any point $v_i$ are in the same cluster as $v_i$.  Thus, the $k$-nearest-neighbor graph has $n/(k+1)$ components.  It follows that we need at least  $n/(k+1)$ shortest paths to cover the graph.


$\omega$-regular properties of a 2-state Markov Chain Let $X$ be a Markov Chain on a state space $\{0,1\}$ with a transition matrix
$$
P =  \left(
\begin{align}
1-p & &p
\\
q & &1-q
\end{align}
\right)
$$
with both $p,q \in (0,1)$ so in particular it is irreducible. Define $p_\delta = p +\delta$, $q = q+\delta$ and let $P_\delta$ be the corresponding transition matrix defining a Markov Chain $X_\delta$. It is well-known that no matter how small $\delta$ is, for some tail event $A$ it holds that
$$
  \mathsf P(A) = 0,\quad \mathsf P_\delta(A) = 1 \tag{1}
$$
where $\mathsf P$ and $\mathsf P_\delta$ are corresponding probability measures over the paths. I wonder, however, whether $A$ can be always taken to be an $\omega$-regular event.

For a particular example, let $\pi$ and $\pi_\delta$ be invariant probability distributions for $X$ and $X_\delta$. Pick any vector $f$ such that $\pi f\neq \pi_\delta f$ and define
$$
  A_f :=\left\{\limsup_{n\to\infty}\frac1n\sum_{k=0}^n f(X_k) = \pi_\delta f\right\},
$$
then $(1)$ holds for $A_f$. Is $A_f$ $\omega$-regular?

I am not sure whether $A_f$ is an $\omega$-regular event, but for any $\delta>0$ we can pick some $\omega$-regular $A_\delta$ such that $|\mathsf P(A_\delta) - \mathsf P_\delta(A_\delta)| \geq 1-\delta$. This follows from the fact that $\omega$-regular events form an algebra that generates a $\sigma$-algebra where $A_f$ does belong to.


Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if my terminology is not exactly right.

I have a database system where user can add/remove/move objects by creating/deleting and altering relationships. As such, I can see the objects as been vertices in a graph and the relationships been edges and edges can be weighted depending on the type of relationships (either composition, association, or aggregation).

From the user's point of view, adding a new element can be a single click and underneath the hood, the program creates a graph of objects linked by relationships. This graph, is then added to the main graph that defines the entire database. Removing an element, would be the reverse where links/edges are disconnected and the graph becomes two disjoint graphs where 1 is the database, and the other consists of vertices formed by the element and its sub elements.

I need a really quick way to determine when I have a disjoint graphs and when 2 disjoint graphs becomes 1 again. I had a brief look at Holm, de Lichtenberg, and Thorup (2001; pdf). It seems like the way to go, but the author did mention they are only considering a graph with fixed number of vertices. Just wondering do algorithms usually extend themselves to adding/removal of vertices by just performing the adding of edges incrementally? Or has there been works that tailors specifically for such scenario?

This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for.

You could also try Bhadra & Ferreira, they're probably getting a bit off-topic for what you want, but they do have references to other material that could be useful.


Find worst case input for a program solving an NP-hard problem I am trying to find a way to find a worst-case input for a black-box implementation of an algorithm with worst-case exponential runtime.

The problem that the program solves (integer linear programming) is NP-hard, but since the proof is by reduction from vertex cover, there is no construction of a hard subset or such. Also vertex cover is in NP due to a reduction from 3SAT. Now for 3SAT it is in no way certain that a hard case for a given 3sat solver would translate to a hard problem for one of my black-box ILP implementations.

Is there a systematic way to find a worst-case runtime example for a given problem of size n?

See Fast Reduction from RSA to SAT for some ways to get hard instances of SAT.  Then, you can use the known reductions to turn these into hard instances for ILP.  You could also use the SAT instances at http://www.satcompetition.org/, too.


How well do subspaces hit sets Let $S\subset F_2^n$ be a subset of size $\epsilon\cdot 2^n$.
Say I choose a random subspace $V$ of dimension $k$ in $F_2^n$.
I want to know what is the smallest $k$ such that $V$ `hits' $S$, i.e., $V\cap S \neq \emptyset$, with probability $\geq 1-\delta$.
As the points of $V$ are pairwise independent, one can show that $k=\log(\frac{1}{\epsilon\cdot \delta})$ suffices (See appendix C of Goldreich's "A sample of samplers").

I'm wondering whether smaller $k$ can suffice.
An argument for why this might be true is that a subspace should be ``better'' than a general collection of pairwise independent points, as many subsets of points in $V$ are more than pair-wise independent.

Here's an $\Omega(\log(\frac{1}{\epsilon\cdot \delta}))$ lower bound following the discussion here with Yuval, and another one with Ross Berkowitz.
I assume for simplicity that the sampling process chooses $k$ completely random elements $v_1,\ldots,v_k$ of $F_2^n$ and outputs their span $V$.
A little extra work is needed to bound the probability that the $k$ vectors sampled are not independent, and in fact, this might be problematic when $k$ is close to $n$.
Denote $\ell\triangleq \log(1/\epsilon)$, and let $S$ be an affine subspace of co-dimension $\ell$. Let $S_0$ be the linear subspace of which $S$ is a shift.
Denote by $T\triangleq F_2^n/S_0$ the quotient space, which is a linear space of dimension $\ell$ who's elements are the cosets of $S_0$ in $F_2^n$. For each $v_i$ denote by $\bar{v}_i\in T$, the coset in which $v_i$ landed.
Denote by $T'\subset T$ the linear span of $\bar{v}_1,\ldots,\bar{v}_k$.
Assume $k\triangleq (\ell-1) + t$, we can lower bound the probability of the event $T' \subsetneq T$ by $2^{-t}$:
Condition on $\bar{v}_1,\ldots,\bar{v}_{\ell-1}$ being linearly independent - this can only decrease the probability of $T'\subsetneq T$.
Denote $T''\triangleq \mathrm{span}(\bar{v}_1,\ldots,\bar{v}_{\ell-1})$
Now, there is a probability of at least $2^{-t}$ that the rest of the $\bar{v}$'s all land in $T''$, and in such a case $T'\subsetneq T$
Now, note that $V\cap S \neq \emptyset$ is exactly equivalent to $x\in T'$ for some fixed $x\in \{0,1\}^{\ell}$ (that correspond to the what coset $S$ is of $S_0$). Furthermore, conditioned on the event $T'\subsetneq T$ $x\notin T'$ with probability at least $1/2$. Thus $V\cap S = \emptyset$ with probability at least $2^{-t}$. So we need $2^{-t}\leq \delta$ which implies $k\geq (\ell-1) + \log(1/\delta) = \log(1/\epsilon) + \log(1/\delta) -1$.


finding "hubs" in a graph consider the problem: given a graph and a number of vertices $n$ less than the vertices in the graph, and a distance $d$. find a set of $n$ vertices such that all vertices of the graph are within $d$ distance of the $n$ vertices (measured in edge count of the shortest path). in a sense the $n$ vertices are "hubs" of the graph. (there may be other constraints on their selection.) suspect this problem may arise in a variety of guises. am not nec. looking for an exact solution.

  looking for the contexts this arises (applications) & recent literature/survey(s) on this problem, finding the "natural" "hubs" of a graph.

possibly somewhat related is finding/adding a few edges to yield "good" hubs (hub sets that are small relative to the vertices they "reach").

When n is given and the objective is to minimize d, it is the well-known n-center problem.


Randomized algorithm that "looks" deterministic? Is there an interesting example of a randomized algorithm for a search problem that always outputs the same (correct) answer, regardless of its internal randomness, but which exploits the randomness so that its expected running time is better than the running time of the fastest known deterministic algorithm for the problem?

In particular, I was wondering if there is such an algorithm for finding a prime between n and 2n.  There's no known polynomial time deterministic algorithm.  There's a trivial randomized algorithm that works just by sampling random integers in the interval, which works thanks to the prime number theorem.  But is there an algorithm of the above kind whose expected running time is intermediate between the two?

EDIT: To refine my question slightly, I wanted such an algorithm for a problem where there are many possible correct outputs, and yet the randomized algorithm settles on one independent of its randomness.  I realize that the question is probably not fully specified...

Shafi Goldwasser communicated to me that she and coauthors have been investigating exactly such algorithms for number-theoretic problems!  The following is known:

Lenstra has shown that there is such an algorithm for finding a quadratic non-residue mod a given prime.
Gat and Goldwasser have shown that there is such an algorithm for finding a generator of $\mathbb{Z}_p^*$, where $p$ is a given prime of the form $2q + 1$ for a prime $q$.

(I don't know of citable references.) There is also ongoing research on the question I asked about finding a prime between $n$ and $2n$.

EDIT: The paper by Gat and Goldwasser is now published: http://eccc.hpi-web.de/report/2011/136/. This paper though doesn't resolve the question of finding a prime between $n$ and $2n$.


Symbolic Execution of the Quine-McCluskey Algorithim If I understand correctly, the Quine–McCluskey algorithm will find the minimum boolean formula size for given boolean function.  Has there been any attempts to (for lack of a better term) symbolically execute the algorithm with a class of boolean functions rather than a single one to find a circuit unconditional lower bound?  Just curious to see if anybody has tried this before, and if so,(presumably) why it wouldn't work.

https://en.wikipedia.org/wiki/Symbolic_execution

Since you stated your purpose is considering circuit bounds:

Taking a boolean function and "minimizing" using Karnaugh maps or the Quine–McCluskey algorithm, then converting the formula to AND and OR gates will give you a circuit calculating that function.  This however does not actually give you a minimum sized circuit.  Karnaugh maps minimize the number of product terms in the sum of products form of specifying a function, this is NOT the same as minimizing the number of gates in a circuit.

Consider for instance the $N$ input parity function. The sum of products form will have $2^{N-1}$ minterms, which means you'd need an exponential number of gates using this method.  However if it takes us $M$ of whatever gates are your basis to make a 2-input XOR gate, we can make the $N$ input parity function with only $M(N-1)$ gates: a linear bound.


Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs My question is about the following maximization problem, which is the "fixed cardinality" version of MIN VERTEX COVER. I am interested in the restriction to subcubic graphs (i.e. of maximum degree 3).

MAX k VERTEX COVER (aka MAX k-COVERAGE)
INPUT: a graph $G$, an integer $k$
OUTPUT: a set $C\subseteq V(G)$ of vertices of size $k$
MEASURE: the number of edges of $G$ that have at least one endpoint in $C$

MAX k VERTEX COVER is proved to be APX-hard on subcubic graphs, by a reduction from MIN VERTEX COVER (itself well-known to be APX-hard on subcubic graphs), in this 1994 paper by Petrank (Theorem 5.4). However, the proof is very succinct and in a formalism that I do not know, hence I could not grasp the details of it. I would like to have a formal proof in a more standard language. (For example, a proof that this reduction is an L-reduction would be perfect!)

  Question: Can someone explain the proof of Petrank's reduction (for example in terms of standard L-reductions)? Alternatively, give (or point to) a different reduction with such a proof.

Note: in Lanberg's 1998 master thesis, a stronger result than Petrank's is proved (the hardness remains valid for a wide range of values of $k$), but only for graphs of maximum degree 30 (see Lemma 3.1). I do not know if other results of APX-hardness for the problem exist in the literature.

Here is the proof of Petrank's reduction. This was suggested to me by Édouard Bonnet. I still do not know whether this can be turned into an L-reduction.

  Suppose there is a PTAS algorithm $\mathscr{A}$ for MAX k VERTEX COVER, thus giving a $(1-\varepsilon)$-factor-approximate solution on a cubic graph $G=(V,E)$ with $|V|=n, |E|=m=3n/2$.
  We can use $\mathscr{A}$ to solve MIN VERTEX COVER on $G$ by invoking it for $k=1,2,\dots, n$, and keep the best of all the produced solutions. Assume that it is obtained for $k=k_0$.
  We claim that $\mathscr{A}$ for $k=k_0$ produces a solution where $k_0$ vertices cover at least $(1-\varepsilon)m$ edges. Indeed, when $k=opt_{VC}(G)$ (where $opt_{VC}(G)$ denotes the minimum solution size for MIN VERTEX COVER on $G$), at least $(1-\varepsilon)m$ edges must be covered by the result of $\mathscr{A}$. Since the result of $\mathscr{A}$ for $k=k_0$ is at least as good as this, the claim follows.

  Thus, at most $\varepsilon \cdot m$ edges are not covered. We construct a set $C$ with the $k_0$ vertices selected by $\mathscr{A}$, to which we add one arbitrary vertex of each of the remaining $\varepsilon \cdot m$ uncovered edges.
  This set $C$ is a vertex cover for $G$, and its size is $k_0 + \varepsilon \cdot m$.
  However, in a cubic graph, $m \leq 3k_0$ (in any optimal solution for MIN VERTEX COVER, each vertex can cover at most 3 edges).
  Therefore, $|C| \leq k_0 + \varepsilon \cdot 3k_0 = k_0(1+\varepsilon')$, by setting $\varepsilon' = 3\varepsilon$. This contradicts the APX-hardness of MIN VERTEX COVER on cubic graphs.


Examples of algorithms and proofs that seem correct, but aren't In my intro to programming course, we're learning about the Initialization-Maintenance-Termination method of proving an algorithm does what we expect it to. But we've only had to prove that an algorithm already known to be correct, is correct. We've never been asked to show that an algorithm isn't correct.

Are there any classic examples of algorithms that look correct, but aren't? I am looking for cases where the Initialization-Maintenance-Termination approach catches something that first-glance intuition doesn't.

2D local maximum

input: 2-dimensional $n \times n$ array $A$

output: a local maximum -- a pair $(i,j)$ such that  $A[i,j]$ has no neighboring cell in the array that contains a strictly larger value.

(The neighboring cells are those among $A[i, j+1], A[i, j-1], A[i-1, j], A[i+1, j]$ that are present in the array.)  So, for example, if $A$ is

$$\begin{array}{cccc}
0&1&3&\mathbf{4}\\
\mathbf{3}&2&\mathbf{3}&1\\
2&\mathbf{5}&0&1\\
\mathbf{4}&0&1&\mathbf{3}\end{array}$$

then each bolded cell is a local maximum.  Every non-empty array has at least one local maximum.

Algorithm. There is an $O(n^2)$-time algorithm: just check each cell.  Here's an idea for a faster, recursive algorithm.

Given $A$, define cross $X$ to consist of the cells in the middle column, and the cells in the middle row.  First check each cell in $X$ to see if the cell is a local maximum in $A$.  If so, return such a cell.  Otherwise, let $(i, j)$ be a cell in $X$ with maximum value.  Since $(i, j)$ is not a local maximum, it must have a neighboring cell $(i', j')$ with larger value.

Partition $A \setminus X$ (the array $A$, minus the cells in $X$) into four quadrants -- the upper left, upper right, lower left, and lower right quadrants -- in the natural way.  The neighboring cell $(i', j')$ with larger value must be in one of those quadrants.  Call that quadrant $A'$.

Lemma. Quadrant $A'$ contains a local maximum of $A$.

Proof.  Consider starting at the cell $(i', j')$.  If it is not a local maximum, move to a neighbor with a larger value.  This can be repeated until arriving at a cell that is a local maximum.  That final cell has to be in $A'$, because $A'$ is bounded on all sides by cells whose values are smaller than the value of cell $(i', j')$.  This proves the lemma. $\diamond$

The algorithm calls itself recursively on the $\frac{n}{2}\times\frac{n}{2}$ sub-array $A'$ to find a local maximum $(i, j)$ there, then returns that cell.

The running time $T(n)$ for an $n\times n$ matrix satisfies $T(n) = T(n/2) + O(n)$, so $T(n) = O(n)$.

Thus, we have proven the following theorem:

Theorem. There is an $O(n)$-time algorithm for finding a local-maximum in an $n\times n$ array.

Or have we?


NP-hard problems with very fast exponential-time algorithms NP-hard problems with very fast exact exponential-time algorithms, say with $O(1.01^n)$ time, are very rare.

Is any fact like

"For any constant $\epsilon>0$ there is an NP-hard 'natural' problem $\Pi_{\epsilon}$ that is not solvable in subexponential time $O(2^{o(n)})$
(assuming ETH) but can be solved in $O\left((1+\epsilon)^n\right)$ time by an exact algorithm."

in the literature somewhere?

(Actually, I am not able to find such an NP-hard problem that can be solved in time near $O(1.01^n)$.)

I do not have a formal definition for natural problems. (but I think each of us has an idea what a natural problem should be?)
Searching the literature I found the following paper which is very close to my question.
The informal discussion on page 2 of this paper is perhaps what I mean
by natural (graph)problems. On page 15, the authors also ask for (sporadic)
problems not solvable in subexponential time but have very fast exponential-time
algorithms. (My question goes a step further by expressing 'very fast' in $\epsilon$:
Given $\epsilon$, is there such a problem, depending on $\epsilon$, that can solved in
$O((1+\epsilon)^n)$ time?)

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width.

Fix any constant $\epsilon>0$ and consider the Independent Set problem restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices.  Call this problem $\Pi_\epsilon$.

Lemma 1. The problem $\Pi_\epsilon$ has an algorithm running in time $O((1+\epsilon)^n n^{O(1)})$.

Proof. This is a direct corollary of a result in [1] --- that Independent Set has an algorithm running in time $O(2^{\text{tw}(G)} n^{O(1)})$, where $\text{tw}(G)$ is the tree width of the given graph $G$.  $~~\Box$

Lemma 2. Assuming ETH, there is no algorithm for $\Pi_\epsilon$ that runs in time $2^{o(n)}$.

Proof. Per [2] Theorem 3.3, assuming ETH, there is no $2^{o(n)}$-time algorithm for Independent Set.  Suppose for contradiction that there is an algorithm $A$ for $\Pi_\epsilon$ running in time $2^{o(n)}$.  Construct an algorithm $B$ for Independent Set as follows:

Algorithm $B$ on input $G$, an arbitrary graph with $n$ vertices:

Let $G'$ be the graph obtained from $G$ by adding artificial vertices, each with no edges, to bring the total number of vertices to $n'=n/\log_2(1+\epsilon)$.
Run the algorithm $A$ for $\Pi_\epsilon$ on $G'$ to find a maximum independent set $I'$ in $G'$.
Let $I$ be $I'$ minus all artificial vertices.  Return $I$.

Graph $G'$ has tree width at most $n'\log_2(1+\epsilon) = n$ because $G$ has tree width at most $n$.  So $A$ returns a maximum independent set $I'$ for $G'$ in time $2^{o(n')} = 2^{o(n)}$. $I'$ must consist of a maximum independent set $I$ in $G$ together with all the artificial vertices.  So $B$ returns a maximum independent set in $G$ in time $2^{o(n)}$, contradicting Theorem 3.3 of [2]. $~~~\Box$

Note: Edited 12/30/2019 to correct an error in the lower-bound argument.

[1] Invitation to Fixed-parameter Algorithms. Rolf Niedermeier. Oxford Lecture Series in Mathematics and its Applications, Vol. 31. Oxford University Press, Oxford

[2] Lower bounds based on the exponential time hypothesis. D Lokshtanov, D Marx, S Saurabh - Bulletin of the EATCS no 105, pp. 41 71, October 2011


Are there any cases where quantum has given insight for classical algorithms? To be more specific, has it ever happened that we've made some kind of significant improvement to a classical algorithm or problem as a result of some "trick" or insight gained from looking at quantum algorithms?

There is at least one example that I can remember, but there are probably more that I am not aware of.

Recently, Maarten Van den Nest and Wolfgang Dürr found a  new classical algorithm (arXiv:1304.2879) to approximate certain types of partition functions (of 3-body classical Ising models on two-dimensional lattices.  Their algorithm is completely classical, but several connections to quantum physics are employed in the design (read below). The algorithm was found to be exponentially faster than previously known algorithms that solve the same problem, at the time of writing*.

*I am ignorant of whether better classical or quantum algorithms have been found a posteriori.

So, there are at least two quantum ingredients used in the design of the VdND algorithm. On the one hand, the authors use a classical-quantum connection between classical Ising models and topological quantum systems (precisely, some color codes). On the other hand, the authors use classical techniques to simulate quantum systems in the derivation of the algorithm: in their proof, they first write a small quantum algorithm for the problem of interest; then, the authors show how to simulate the former quantum  algorithm efficiently on a classical computer, obtaining a classical algorithm (this is rather remarkable, in my view).


Information complexity of query algorithms? Information complexity has been a very useful tool in communication complexity, mainly used to lower bound the communication complexity of distributed problems.

Is there an analogue of information complexity for query complexity? There are many parallels between query complexity and communication complexity; oftentimes (but not always!) a lower bound in one model gets translated to a lower bound in the other model. Sometimes this translation is quite nontrivial.

Is there a notion of information complexity that is useful for lower bounding the query complexity of problems?

A first pass seems to indicate that information complexity is not very useful; for example, the query complexity of computing the OR of $N$ bits is $\Omega(N)$ for randomized algorithms and $\Omega(\sqrt{N})$ for quantum algorithms, whereas the most straightforward adaption of the notion of information complexity indicates that the information learned by any query algorithm is at most $O(\log N)$ (because the algorithm stops when it sees the first $1$ in the input).

Yes, information theory is useful for proving lower bounds on the query complexity of problems in Computer Science.

Alexander Golynski gave a good example in his ground breaking paper titled "Cell probe lower bounds for succinct data structures", presented at SODA 2009. He uses information theory to prove a lower bound on query complexity, which in turns yields a lower bound in the bit-probe model for (succinct) data structures. You can download the paper from citeseer's cache or from ACM's repository. There does not seem to be a journal version of the article.

You might be interested also in the following articles from his bibliography, which also relate communication complexity with information theory:

Peter Bro Miltersen, Noam Nisan, Shmuel Safra, and
Avi Wigderson. On data structures and asymmetric
communication complexity. Journal of Computer and
System Sciences, 57(1):37–49, 1998. [link]
Anna Gal and Peter Bro Miltersen. The cell probe
complexity of succinct data structures. In International
Colloquium on Automata, Languages and Programming,
pages 332–344, 2003. [link]


Rings and the set of all minimum s-t-cuts Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let $\mathcal{R}(N)$ be the set of the source sides of all minimum $s$-$t$ cuts of $N$. $\mathcal{R}(N)$ is now a non-empty family of sets over the universe $E$. Due to submodularity, the intersection of two source sides and the union of two source sides yields the source side of a min-cut. As such, $\mathcal{R}(N)$ is a ring. Hence, for every network $N$, $\mathcal{R}(N)$ is a finite ring of sets.

By ring of sets, I refer to the definition of a non-empty family of sets closed under union and intersection. Hence, a ring of sets is commutative.

I wonder if the converse direction is true, that is if the following statement holds:

  For every ring of sets $\mathcal{R}$ over a finite universe $U$ there is a flow network $N$ with nodes $U$ such that $\mathcal{R}(N) = \mathcal{R}$.

I was unable to come up with a counter example, at the same time literature seems not to know this either. To me it seemed like a constructive proof could work where the family of sets is analyzed in order to determine whether the nodes of $U$ need to be parallel or in series.

Here I'll show that the statement is true, assuming that $V=U\cup\{s,t\}$, i.e. source and sink are not elements of $U$.

Let $S=\bigcap\limits_{R\in\mathcal R}R$, $P=\bigcup\limits_{R\in\mathcal R}R\setminus S$ and $T=U\setminus(S\cup P)$. Construct a flow network $N$ with nodes $U\cup\{s,t\}$ and the following edges:

From $s$ to every element of $S$.
From every element of $T$ to $t$.
For all ordered pairs $(x,y)$ such that $x\in P$, $y\in P$ and $\forall R\in\mathcal R:x\in R\rightarrow y\in R$, from $x$ to $y$.

Each edge can have any positive capacity. Since $t$ is not reachable from $s$, maximal flow is $0$.

What remains is to prove that the set of source sides of minimal $s$-$t$ cuts is exactly $\mathcal R$. Firstly, I'll show that any set $R\in\mathcal R$ is a source side of an $s$-$t$ cut. By definition, $S\subset R$ and $T\cap R=\emptyset$, so edges from $s$ and edges to $t$ don't cross the cut. Edges in $P$ also don't cross the cut by definition, since for any such edge $x\rightarrow y$, if $x$ is in $R$, $y$ must be in $R$ as well.

Now I'll show that if $Q$ is a source side of a minimal $s$-$t$ cut, $Q$ must be in $\mathcal R$. Since maximal flow is zero, there must be no edges crossing the cut. Therefore, $S\subset Q$ and $T\cap Q=\emptyset$. If $Q=S$, the proof is done, because $S$ is a member of $\mathcal R$ by definition. Otherwise, let $Q'=\bigcup\limits_{x\in Q}\bigcap\limits_{R\in\mathcal R\wedge x\in R}R$. By definition, $Q'\in\mathcal R$, so it remains to show that $Q=Q'$.

Note that every intersection in the definition of $Q'$ is nonempty, because $Q\subset S\cup P$. Also, $Q'\subset S\cup P$. By definition, every element of $Q$ is contained in $Q'$. Suppose that there is an element $y\in Q'$ which is not in $Q$. Then $y\in P$ and there is an element $x\in Q$ such than $\forall R\in\mathcal R:x\in R\rightarrow y\in R$. Then $x\in P$, since otherwise $x\in S$ and $S\in\mathcal R$ is a counterexample. So, there must be an edge from $x$ to $y$, and it crosses the cut, a contradiction. Therefore, $Q=Q'$, so $Q\in\mathcal R$.

By the way, while the above solution requires directed edges, the answer is the same even if all the edges must be undirected (with the same capacity in both directions). The idea for the solution in this case is that you need such a network that, after the maximal flow is pushed through it, the residual graph is the same as the graph constructed using the solution above plus some edges from $T$ to $P$ and from $P$ to $S$ which don't change the set of minimal cuts. The details are left as an exercise to the reader.


Intersection of two unsorted sets or lists Suppose you are given two lists $L_1$ and $L_2$, each of which contains pairwise distinct elements from some set $S$.

What is the complexity of computing the intersection $L_1\cap L_2$ of the two lists?

If you have an order on $S$, you can sort your both lists and then compute the intersection in linear time, achieving $O(n\log n)$ complexity where $n=\max(|L_1|,|L_2|)$. More specific questions are then:

Can you compute the intersection in linear time, or at least faster than $O(n\log n)$?
If there is no natural order on $S$, what complexity can you achieve without using a sorting algorithm?

The second bullet point is quite vague. What I want to understand is whether sorting the lists (or one of them) is necessary though the answer does not need to be sorted.

In the algebraic decision/computation tree models, your problem has an $\Omega(n\log n)$ lower bound, even if you know in advance that one of your lists contains the integers $1$ through $n$ in sorted order, and you only need to check whether the second list is a permutation of the first.

  Proof (for algebraic computation trees): The set of points whose coordinates are permutations of $(1,2,\dots,n)$ has $n!$ components. Ben-Or proved that for any algebraic computation tree of height $h$, the set of points in $R^n$ that reach YES leaves has at most $2^h 3^{n+h}$ components. Solve for $h$.

If you are restricted to equality tests, an $\Omega(n^2)$ lower bound follows from a straightforward adversary argument.


Small $\epsilon$-nets for points and half-planes without VC dimension I have recently learned the proof of Haussler and Welzl of the following theorem.

Theorem. Suppose we have a set system $\mathcal{F} \subseteq 2^X$, where $X$ is a finite set. Suppose $\mathcal{F}$ has VC-dimension $d$. Then for every $\epsilon > 0$ there exists a hitting set ($\epsilon$-net) of size $O(\frac{d}{\epsilon} \log \frac{1}{\epsilon})$ of the following subfamily of $\mathcal{F}$: $\{F \in \mathcal{F} \mid |F| \geq \epsilon |X|\}$.

The proof itself is essentially a probabilistic argument. Despite its simplicity it looks very unnatural (we consider very mysterious coupling).

There is an interesting non-trivial case: suppose $X$ is a finite set of points in $\mathbb{R}^2$ and $\mathcal{F}$ is a family of subsets of $X$ which can be separated from their complements by half-planes. It is easy to check that in this case $d = 3$.

Is there a proof of the existence of a good $\epsilon$-net in this case from the first principles (without introduction of VC-dimension)?

For the particular case of points and half-planes, there is a simple (but a little tricky) argument that there is $R\subset X$ of size $r$ such that the supporting open half-planes of the convex hull of $R$ each contain at most $O(\log r)/r$ points of $X$. (Such half-planes are exactly the set of half-planes that are bounded by a line through two points of $R$ and contain no points of $R$.)

Also, any open half-plane that contains no points of $R$ is contained in two such supporting half-planes. (I won't give a proof of this.)

Therefore, $R$ is an $\epsilon$-net for a size $r$ which is $O(\log(1/\epsilon)/\epsilon$.

For the existence of such an $R$, suppose $R$ is a random sample of $X$ of size $r$, each member of $R$ chosen independently. Let $\cal H$ be the set of at most $r(r-1)$ open half-planes $H$ bounded by lines through two (or more) points of $R$, and let $\cal H'\subset \cal H$ be the set of $H\in\cal H$ that contain at least $\alpha |X|$ points of $X$, where $\alpha > 0$ is to be determined. For a given $H\in {\cal H}$, the probability that it is in $\cal H'$, and that none of the other $r-2$ points of $R$ falls in $H$, is at most $(1-\alpha)^{r-2}\le \exp(-\alpha(r-2))$. There is $\alpha = O(\log r)/r$ such that this probability is at most $1/2r(r-1)$. Since $\cal H'$ has at most $r(r-1)$ members, by a union bound, the probability that every member of $\cal H'$ contains a point of $R$ is at least $1/2$. So there is some $R$ such that every supporting half-plane of its convex hull contains at most an $\alpha = O(\log r)/r$ fraction of the points of $X$.

This sort of argument goes back to at least 1985, where $\epsilon$-net results were given for balls and halfspaces, and given in more generality in 1986, where results for $\epsilon$-nets and a kind of partial $\epsilon$-approximation were given. The set $\cal H$ above, a collection of half-planes defined by a set of points, is generalized to a collection of "regions" defined by a set of "objects", where the number of defining objects is typically a function of the dimension, but the simple union bound argument is the same. However, not all range spaces of bounded VC dimension fit in this framework.


Is the lower bound proof in this paper correct? In this paper on "Circle Packing for Origami Design Is Hard" by Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, on page 15, figure 13, they claim that the side length of the smallest square that encloses two circles of area 1/2 each is 1.471299. By my calculations I am getting side length 1.362 and area 1.855. Have I made a mistake or is there a mistake in the paper?

I get the same answer as you, $\frac{1+\sqrt{2}}{\sqrt{\pi}}$.

If I place two unit disks inside a larger square, their centers are one unit away from the left and right sides, and $\sqrt{2}$ units apart from each other in $x$-coordinates, so the side of the larger square is $2+\sqrt 2$. The unit disks have area $\pi$, and we want area $\frac{1}{2}$, so dividing the side length and the disk radius by $\sqrt{2\pi}$ gives the result.


For what k is MAX-2-SAT-k NP-complete? It is well-known that it is NP-complete to decide whether in a 2-CNF at least s clauses are satisfiable. It also follows from the reduction from 3-SAT-3 that we can suppose that every literal occurs in at most k clauses of the 2-CNF for some constant k. Can someone give me a good bound on k?

Can we suppose that every variable occurs at most twice negated or at most twice unnegated?

3-OCC-MAX 2SAT: given a CNF formula $\varphi$ in which each clause contains at most 2 literals and each variable appears in at most three clauses (counting together both positive and negative literals); does there exist an assignment that satisfies at least $k$ clauses?

In P. Berman, M. Karpinski, On some tighter inapproximability results (1998). Lecture
Notes In Computer Science, vol. 1644 (1999), pp. 200-209 :

... for any $\epsilon > 0$ it is NP hard to decide whether an
instance of 3-OCC-MAX 2SAT
with $2016 n$ clauses has a truth assignment that satisfies
at least $(2012 - \epsilon)n$ clauses.

As noted in the domotorp's comment, if a variable appers only positive or negative we can fix its value (satisfying and deleting all the clauses in which it appears); so we can assume that the 3 occurrences are not-all-equal ending up in a "3-NAE-OCC-MAX 2SAT" instance :-)


More complex integers In connection to this question:
Expected values of Kolmogorov complexity in a random sample

Let $n$ be number of bits. Let $A = \{0,1,2,\dots,2^{n}-1\}$ be indexed by the $n$-bits. Let $ \delta > 0$ be fixed. Is there an estimate of what fraction of integers in $A$ can have Kolmogorov complexity be greater than $\delta n$?

The argument is the same, there are only $1 + 2 + 4 + ... + 2^{\delta n - 1}$ programs shorter than $\delta n$ so there are at least $2^n - (2^{\delta n} - 1)$ integers with $K(x) \geq \delta n$.


LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better? Given any Integer Linear Program (ILP) there are 2 ways to approximate it:

Write down ILP, convert to LP by relaxing the integer constraints and round the solution
Write down the ILP, convert to LP by relaxing the integer constraints, write it's dual and solve it

Why is the second approach considered 'better'? What makes it the preferred way of approximating the solution to an ILP? What is that #2 has that #1 doesn't?

In Vazirani's Approximation Algorithms book he approximates set cover using both of the methods above, but I'm unable to discern the underlying concept of choosing #2 over #1? What "IS" the intuitive 'aha' to help me understand this?

If one uses an ILP formulation and its LP relaxation then clearly it does not hurt to look at the dual. In many cases the dual helps to understand/interpret the lower/upper bound that the relaxations give. This can be exploited algorithmically in a direct fashion, or some times indirectly to provide intuition. Several classical combinatorial optimization results are based on min-max results where duality based analysis/interpretation is very direct and useful.

Making the comment an answer based on Suresh's suggestion.


Is case analysis on normal forms of lambda terms sufficient to prove parametricity results? There are many closed terms of a given type. For instance, both of these terms:

$$ \lambda x . x $$
$$ \lambda x . (\lambda y . y) x $$

have a type of a polymorphic identity function:

$$ \forall X . X \rightarrow X$$

On the other hand, there is only one normalized term of that type i.e: $\lambda x . x$.
Similarly, given the type of Church natural numbers:

$$ \mathtt{Nat} = \forall X . (X \rightarrow X) \rightarrow X \rightarrow X $$

one can argue that all the normal form terms of type $\mathtt{Nat}$ are in the form:

$$\lambda s . \lambda z . s (\ldots (s\; z)) $$

Is there any research that goes along these lines and perhaps formalizes this intuition?

Is this idea correct and strong enough to prove (by case analysis on the normal forms of the terms) 'free theorems' or more general parametricity results?

Clarification: The type system in question is System F

I'd like to offer some pointers.

  Is there any research that goes along these lines and perhaps formalizes this intuition?

Parametricity by analysis of the shape of (simply-typed) normal forms preceded by a normalisation argument was proposed by Girard, Scedrov, and Scott [1]. This connects parametricity, cut-elimination in logic, and a proof technique for coherence in category theory. Here, parametricity is understood as a property of dinaturality, originally proposed for system F in [2].

  Is this idea correct and strong enough to prove (by case analysis on the normal forms of the terms) 'free theorems' or more general parametricity results?

In [1], it is noted that this includes the so-called "free theorems" as a special case. But the argument does not extend to all of system F, and dinaturality fails to capture relational parametricity (see e.g. [3]). On the other hand, a work by Paolo Pistone shows that one indeed thus obtains a syntactic characterisation of parametricity for a class of types a bit larger than the simple types including your examples [4]:

  Our results imply that, for positive second order types, realizability, parametricity, dinaturality and typability are equivalent properties of closed normal lambda-terms.

So there is indeed an elementary technique based on looking at shapes of normal forms, which provides a syntactic characterisation of some parametricity results including the "free theorems", that also hints at a connection with categorical coherence.

[1]: Girard, J.-Y.; Scedrov, A. & Scott, P. J. Normal Forms and Cut-Free Proofs as Natural Transformations. Logic From Computer Science, Mathematical Science Research Institute Publications 21, Springer-Verlag, 1992, 217-241.
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.41.811

[2]: Bainbridge, E. S.; Freyd, P. J.; Scedrov, A. & Scott, P. J. Functorial polymorphism. Theoretical computer science, Elsevier, 1990, 70, 35-64.
https://core.ac.uk/display/82270459

[3]: De Lataillade, J. Dinatural Terms in System F. Logic in Computer Science, 24th Annual IEEE Symposium, 267-276, 2009. https://www.irif.fr/~delatail/dinat.pdf

[4]: Pistone, P. On completeness and parametricity in the realizability semantics of System F. https://arxiv.org/abs/1802.05143


clustering (lat,lng) pairs, with clusters having the same number of elements Imagine you have a list of (lat,lng) pairs. You have k employees. And you want each employee to visit roughly the same number of places, making the least distance possible.

I've tried to solve this with K-Means clustering, but found that it didn't produce clusters with the same number of elements.

Is this possible? Is there a known algorithm that could solve this?

This sounds like it may be a NP-hard problem. But perhaps a relatively simple heuristic will give good enough results, something like:

Use one of the heuristic approximations to the travelling salesman problem to find a (relatively) short loop that passes through all of your N locations.
Then arbitrary pick some location on that loop as a "starting" point location number 0, and number each location along that path from 0 to (N-1).
Each employee i (from 0 to k-1) gets the approximately N/k consecutive locations along that loop, from location i*N/k to location (i+1)*N/k - 1.


Efficiently ordering typed programs Sometimes it is useful to enumerate in increasing order
  programs that have a given type.  A
  simple example  is test
  generation for compilers: we want to test a new optimising phase and
  are interested in generating programs that trigger that phase (we
  use types for this purpose). Since we want to find 'minimal'
  examples exhibiting  bugs in the new optimising phase, it makes
  sense to start with the smallest programs as test cases first.
Another (somewhat trivial) example is superoptimising compilation where
we enumerate all possible assembly programs by increasing length. The typing system is trivial in the sense that all assembly programs are admissible.

  There is a trivial algorithm solving this problem: lazily enumerate
  all untyped programs and do type inference on each, reject those
  that fail to type. The trivial algorithm is unlikely to be
  efficient since for reasonable typing systems, most programs don't have the target type.  Surely one can do better by interspersing typing and
  enumeration. Let's express this problem in a more abstract setting.

  Assume fixed an untyped programming language $L$ and a well-founded partial-order (or
  preorder) $\sqsubseteq$ on $L$ programs. We are also given a typing
  system for $L$. We write $\Gamma \vdash P : \tau$ to indicate that
  program $P$ has type $\tau$ assuming $P$'s free variables are typed
  as described in the typing environment $\Gamma$.

Problem.  Given a typing environment $\Gamma$
  and a type $\tau$, (lazily) enumerate (in increasing
  $\sqsubseteq$-order) all programs $P$ such that $\Gamma \vdash P :
  \tau$.

Note that my formulation of the problem has been deliberately vague,
  for it's likely that a lot depends on $\sqsubseteq$ and the typing
  system. Most orders $\sqsubseteq$ will be too complicated to admit
  efficient algorithms, I imagine. The orders I have in mind are program size, or weighted program size (some program constructors are 'heavier' than others).

    Question. What is the state-of-the-art of research on efficient algorithms for
  such (and related) problems?

Two remarks first:

I have used the "randomly generate terms and check that they are well-typed" approach (you mention that "untyped" terms are generated, you can also randomly generate terms in a Church-style grammar with explicit type annotations) and it worked very well in practice, it revealed all the bugs there was to find on this particular part of the project. For practical purposes I would recommend trying this first. (On the other hand, the generator was aware of scoping rules -- it maintained a set of currently bound variables for top-down generation, this is easy to implement.)
The choice of order depends a lot on the application you have in mind: two distinct applications will require different orders. For example, people that work on type-directed program synthesis are not usually interested in enumerating equivalent programs, so they will make simplification rules such as assuming that "any term of type A -> B can be chosen to start with a lambda-abstraction" -- in your framework, ordering lambda-terms before all terms at this type. This order is very bad for compiler testing: if you only generate programs that are in normal form, you are unlikely to exercise much of your optimization strategies or runtime semantics. So I believe that assuming an order to abstract away from the intended usage is not a good modeling choice: its choice is tightly coupled with the intended usage, and I would rather reason about the usage than the corresponding order.

Now for some references.

For typed-term generation for testing purposes, you may be interested in "Making random judgments: Automatically generating well-typed terms from the definition of a type-system" by Burke Fetscher, Koen Claessen, Michał Pałka, John Hughes, and Robert Bruce Findler, 2015.

  This paper presents a generic method for randomly generating well-
  typed expressions. It starts from a specification of a typing judgment in PLT Re-
  dex and uses a specialized solver that employs randomness to find many different
  valid derivations of the judgment form.
  Our motivation for building these random terms is to more effectively falsify
  conjectures as part of the tool-support for semantics models specified in Redex.
  Accordingly, we evaluate the generator against the other available methods for
  Redex, as well as the best available custom well-typed term generator. Our results
  show that our new generator is much more effective than generation techniques
  that do not explicitly take types into account and is competitive with generation
  techniques that do, even though they are specialized to particular type-systems
  and ours is not.

For typed term enumeration for program synthesis, two recent works that I know are Example-Directed Synthesis: A Type-Theoretic Interpretation by  Jonathan Frankle, Peter-Michael Osera, David Walker, and Steve Zdancewic, 2016, and Program Synthesis from Polymorphic Refinement Types by Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama, 2016. Note that both works use refinement types as a way to encode more desired properties of the searched program -- such as a testsuite that it should pass. These refinements often constrain the search space substantially more than just types, but they are also harder to invert -- interleave with search.


Is this behavior in a programming language inconsistent? I'm developing a tiny programming language to try to wrap my head around type inference, and I'm trying to figure out if its behavior makes sense or not. Here's the problem:

The identity function \x.x can't be unified to a single type, but applied to something, it can, i.e. (\x.x) 10 : Int. However, right now, the expression:

((\x.x) (\x.x)) 10

can't be unified, because the expression (\x.x) (\x.x) doesn't have a single type. The type checker doesn't do any evaluation, so it can't tell that the above expression is equivalent to \x.x. The type checker only sees the expression, tries to determine the type of it, and fails before trying to apply it to 10.

Is this typical behavior, or am I being inconsistent with my type inference?

Yes, your type inference seems incomplete. This example can be dealt with fairly trivially, by computing the respective type equations, e.g. in the style Hindley/Milner does it.
Alpha-renaming the example makes it easier to follow:
((\x.x) (\y.y)) 10

For maximum clarity, let's start by assigning type variables to each sub expression:

x : A
(\x.x) : B
y : C
(\y.y) : D
(\x.x) (\y.y) : E
10 : F
((\x.x) (\y.y)) 10 : G

Now, the typing rules of the language impose certain equality constraints for each language construct:

From the typing rule for lambda, applied to (\x.x), it follows that B = A -> A
Likewise, D = C -> C
From the typing rule for application, applied to (\x.x) (\y.y), it follows that A = D and E = D
From the typing rule for integers it follows that F = Int
From the typing rule for application, applied to (...) 10, it follows that E = F -> G

In summary, this yields the following equations:

B = A -> A

D = C -> C

A = D

E = D

F = Int

E = F -> G
Now you just solve the equations using unification:

From (2) and (3) it follows that A = C -> C

From (2) and (4) it follows that E = C -> C

From (5) and (6) it follows that E = Int -> G

From (8) and (9) it follows that C -> C = Int -> G, and thus, C = Int and C = G, and thus, G = Int

From (7) and (10) it follows that A = Int -> Int

A and C are the types you are ultimately interested in, because they are the ones you have to assign to x and y, respectively. They yield the typed term
((\x:(Int->Int).x) (\y.Int.y)) 10

Its overall type is G = Int.


Factoring as a decision problem I've seen in multiple places stating that factoring is in BQP and referencing Shor's algorithm, but Shor's algorithm is not solving a decision problem. How can factoring be restated in a decision problem? And is there a paper which shows that Shor's algorithm implies this decision problem is in BQP?

Here the goal is to construct a decision problem D so that (a) if you can factor you can solve the decision problem in polynomial time and (b) if you can solve the decision problem you can factor in polynomial time.   There are a number of ways to do this.  To name just two:

D:  given n and k, does n have a divisor d satisfying 1 < d <= k?
D:  given n and j, is the j'th bit of the smallest nonunit divisor of n equal to 1?

If you can solve 1, then you can identify d using binary search.  Once you have d, you can then continue with n/d until the complete factorization is achieved.  2 is similar.


Open or Interactive Constraint Satisfaction In the past, I implemented coordination models using SAT and regular constraint satisfaction as the core workhorse in their engines. Continuing in this line of work, I would like to make the models more interactive, and the best way I see of doing this is to open up the constraint solver so that it is no longer a black box.

Thus,
I'm interested in learning more about constraint satisfaction where the constraints have what I will call external variables, predicates and functions,
that is, the constraint language may have predicates such as $\mathbf{P}(x)$ which can only be satisfied by consulting some agent external to the solver, and then only when $x$ is ground. A scenario where this is useful is whenever $\mathbf{P}$ corresponds to some external decision process that cannot be incorporated into the constraint solver. Such constraint solvers could be called open (as constraints are not entirely known) or interactive (as interaction is required to proceed with constraint satisfaction).

I would like to know both:

theoretical research done in this direction
tools or libraries that implement constraint solvers that allow interaction with the external world during the constraint solving process.

I'm not altogether convinced by the previous work on open and interactive constraints.

An attempt to study the tractability questions was:

Martin J. Green and Christopher Jefferson, Structural Tractability of Propagated Constraints, CP 2008.
doi: 10.1007/978-3-540-85958-1_25

although this paper does leave several major questions unanswered.  The approach via propagators in this paper is closely related to existing constraint solver implementations.

I think work on SMT (satisfiability modulo theories) is also closely related to your question.  SMT theories are often motivated by problems from software and hardware verification, but there do exist theories with an AI flavour.  I look forward to more applications built with SMT as the core technology, and to more work in constraints applying ideas from SMT.


Common false beliefs in theoretical computer science EDIT AT 10/12/08:

I'll try to modified the question so it may interest more people to share their opinions. We NEED your contributions!

This post is inspired by the one in MO: Examples of common false beliefs in mathematics. Big lists sometimes generate a massive number of answers the qualities of which are hard to control, but after the success of the related post on MO I am convinced that it would be helpful to list a bunch of common false beliefs in TCS.

Still, since the site is designed for answering research level questions, examples like $\mathsf{NP}$ stands for non-polynomial time should be not on the list. Meanwhile, we do want some examples that may not be hard, but without thinking in details it looks reasonable as well. We want the examples to be educational, and usually appears when studying the subject at the first time.

  What are some (non-trivial) examples of common false beliefs in theoretical computer science, that appear to people who are studying in this area?

To be precise, we want examples different from surprising results and counterintuitive results in TCS; these kinds of results make people hard to believe, but they are TRUE. Here we are asking for surprising examples that people may think it is true at the first glance, but after a deeper thought the fault within is exposed.

As an example of proper answers on the list, this one comes from the field of algorithms and graph-theory:

For an $n$-node graph $G$, a $k$-edge separator $S$ is a subset of edges of size $k$, where the nodes of $G \setminus S$ can be partition into two non-adjacent parts, each consists of at most $3n/4$ nodes. We have the following "lemma":

  A tree has a 1-edge separator.

Right?

This is one is common to computational geometry, but endemic elsewhere: Algorithms for the real RAM can be transferred to the integer RAM (for integer restrictions of the problem) with no loss of efficiency.  A canonical example is the claim “Gaussian elimination runs in $O(n^3)$ time.”  In fact, careless elimination orders can produce integers with exponentially many bits.

Even worse, but still unfortunately common: Algorithms for the real RAM with floor function can be transferred to the integer RAM with no loss of efficiency.  In fact, a real-RAM+floor can solve any problem in PSPACE or in #P in a polynomial number of steps.


On complexity of arithmetic operations Though there have been many questions asked in this forum on complexity of integer operation, I could not find an answer to the following question: What implications are there to complexity theory if integer addition and multiplication of two integers have the same asymptotic complexity in the worst case?

If integer multiplication is in linear time, then the Hartmanis-Stearns conjecture on real-time computation is false. See this post by Richard Lipton (and Ken Regan?).


Fast extraction of pairs overlapping an interval I am trying to find a fast algorithm to extract pairs that overlap with a specified interval.

Lets say I have a long list of pairs of integers, each pair (x1, x2) assuming x1 <= x2, (you can imagine them two points on the x-axis or on a timeline to visualise the problem better). Provided 2 other values V1, and V2, also assuming V1 <= V2, I want to extract the set of all pairs that satisfy at least one of the following criteria.

V1 <= x1 <= V2
V1 <= x2 <= V2
x1 <= V1 <= V2 <= x2

So intuitively what I need to extract is all interval pairs that overlap with V1 and V2, either partially (criteria 1 and 2) or completely (criteria 3).

I wish to find a fast way to extract them (I know this depends on how large the interval between V1 and V2 is). The solution I came up with so far is organising the pairs in a balanced binary search tree sorted with just x1 and traversing it for items that are x1 <= V2, and then checking the rest of the criteria as I am traversing the tree. I could also enhance it by adding another binary search tree sorted by x2 of the same pairs, and traversing similarly for pairs x2 >= V1, and maybe using this tree instead when the V1, V2 interval is biased towards the right of the midpoint of the whole range of values of the pairs.

Is there any better idea how I could achieve this? It seems I can only get O(n) complexity.

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


Anti-chromatic number What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its neighbour vertices?

Is there anything in literature about this variant of coloring?

Your problem is equivalent to maximum matching. In an optimal coloring, each color class is connected. Choosing one edge from each color class, we get a matching. This shows that the maximum matching is at least the antichromatic number. In the other direction, take any maximal matching, and color each of the pairs using a different color. Every other vertex is adjacent to some colored vertex (otherwise the matching isn't maximal), so you can extend this to an antichromatic coloring, showing that the antichromatic number is at least the size of a maximum matching.


NP-Completeness of the decision problem for the generalized 15-puzzle I am interested in the natural generalization of the famous 15-puzzle, where you have to slide blocks until you have sorted all given numbers (usally there is a gap of 1 block).

Now the generalization would be to extend the size of the puzzle from 15 to $p \times q$, where one field is free. I have created a small illustration (the dashed arrows show permitted moves and the lower configuration shows the solved puzzle):

Given an initial configuration of a puzzle, I ask myself the following question:

  Decision question: Given a puzzle of size $p \times q$, and a number $k \in \mathbb{N}$. Is there a sequence of $k$ or less allowed moves
  that transform the puzzle into the solved configuration?

I already did some investigation and found the article "The $(n^2−1)$-puzzle and related relocation problems" from 1990, which shows that deciding my question for $p=q$ is NP-Complete and therefore that deciding my question is NP-Complete (as the general algorithm could also decide the question for symmetric fields).

The question that remains open is if the decision problem is also NP-Complete for fixed $q>1$. I am particularily interested in the special cases $q=2,3$. It also remains open if allowing more free spaces than one field makes the decision problem harder or easier.

All the articles I could find sadly omit the asymmetric case, thus I think there might be no known results about this. As the proof in the article is quite complicated and doesn't translate at all for fixed height, I rather hope that someone might come up with a different reduction/article that answers some of the questions.

Other related articles (to be extended):

http://larc.unt.edu/ian/pubs/saml.pdf
http://red.cs.nott.ac.uk/~gxk/papers/icga2008_preprint.pdf
http://erikdemaine.org/papers/AlgGameTheory_GONC3/

I think that I found a partial (although quite disappointing) answer to my problem:

I stumbled across this paper (2007):

"The Complexity of Three-Dimensional Channel Routing" by     Satoshi Tayu and Shuichi Ueno

They show (Theorem 4) that the "3d-channel routing problem" with "2-nets" and dimension $p,q$ can be solved if and only if the corresponding (check article for more details) $p \times q-1$ puzzle can be solved.

Below Theorem 1 they propose some problem they call "2.5-D CHANNEL ROUTING", which is basically "3d-channel routing" with fixed depth $k$. They also say "the complexity of
the following problem [2.5-D Channel Routing] is open for any fxed integer $k \geq 2$".

If we knew that the decision version of the $p \times q-1$ puzzle is NP-Complete for some fixed $k \geq 2$ we would also know that 2.5-D Channel Routing is difficult for that $k$, therefore it seems the question can be reduced to some open problem.

It could of course be that the answer to my question would be that $p \times q-1$ puzzle is in P for all fixed $k$, which would still leave their question open (as the general routing doesn't only handle $2$-Nets). Therefore this is no complete answer, it is also rather disappointing that they include no references when claiming that the problem is still open.


Minimum number of triangles required to cover a complete graph? Let $K_n$ be a complete graph, I am interested in knowing the minimum number of triangles required to get a edge cover of $K_n$. In case there is no closed-form solution to this problem, then I would like to know the best known upper bound (the naive bound is $n\choose 3$ i.e all possible triangles).
An example:
Let $K_4 = \{1,2,3,4\}$, then any three of the following triangles make a full edge cover on $K_4$:
{1,2,3}
{1,2,4}
{1,3,4}
{2,3,4}

Furthermore, I would also like to add a generalisation i.e you assign a weight $w$ to each triangle such that $w \in [0,1] $, now I want to have a cover that minimises the sum of $w$, given that each edge's weight contribution sums to more than one.
What is the lower bound on this sum ?

Let $N(n)$ be the number of triangles needed to cover $K_n$.
Because every triangle covers only three of the $n\choose 2$ edges, we have $\frac{1}{3}{n\choose 2}\leq N(n)$ as a lower bound.
Note that the case $n=2$ is degenerate, as $K_2$ has only one edge and no triangles.
In the following analysis, I will allow myself to use triangles that cover only one edge (for $n>2$, this is without loss of generality because you can use an arbitrary third vertex to create a triangle).
To obtain an upper bound, we apply divide and conquer as follows.
For some $k+m=n$, think of $K_n$ as the union of $K_m$, $K_k$, and $K_{k,m}$.
In particular, let's pick $m:=\lfloor n/2\rfloor$ and $k:=\lceil n/2\rceil$.
Label the vertices of $K_k$ by $u_0,\dots,u_{k-1}$ and the vertices of $K_m$ by $v_0,\dots,v_{m-1}$.
For each edge $\{u_i,u_j\}$ of $K_k$, place the triangle $\{u_i,u_j,v_{i+j\pmod m}\}$.
This covers each edge of $K_k$ using $k\choose 2$ triangles, and also covers the edges $\{u_i,v_l\}$ of $K_{k,m}$ as long as $l\neq 2i\pmod m$.
We can cover the remaining edges $\{u_i,v_{2i\pmod m}\}$ of $K_{k,m}$ using $k$ triangles.
Now, it remains to cover the edges of $K_m$, which we do recursively.
This yields the upper bound $N(n)\leq N(m)+{k\choose 2}+k\leq N(\lfloor n/2\rfloor)+{\lceil n/2\rceil\choose 2}+\lceil n/2\rceil$.
For $n\leq 1$, we have $N(n)=0$, so we can write out the recurrence:
$$\begin{align}N(n)&\leq
\sum_{i=1}^{\log_2 n} \left[{\lceil n/2^i\rceil\choose 2} + \lceil n/2^i\rceil\right]\\
&\leq
\sum_{i=1}^{\log_2 n} \left[{\frac{n}{2^i}+1\choose 2} + \frac{n}{2^i} + 1\right]\\
&=
\sum_{i=1}^{\log_2 n} \left[\frac{1}{2}(\frac{n}{2^i})^2+\frac{3}{2}\frac{n}{2^i} + 1\right]\\
&= \frac{n^2-1}{6} + \frac{3(n-1)}{2} + \log_2 n\\
&= \frac{1}{3}{n\choose 2} + O(n).
\end{align}$$
Therefore, the lower bound is tight up to a linear function of $n$.


Why is the polymorphic weight 1 I am reading through through a paper called HMF: Simple Type Inference for First-Class Polymorphism by Daan Leijen of Microsoft Research.

In the paper it describes how to calculate the polymorphic weight of an expression:

I am having trouble understanding why the above example [[forall a. [forall b. a -> b]]] has a weight of 1 rather than two. there are two type abstractions where both type variable are not free in their bodies, should these not be added together?

You asked why

  [[forall a. [forall b. a -> b]]] has a weight of 1

It doesn't. It has a polymorphic weight of 1. The polymorphic weight strips the binder before it looks at the weight. For the $\rho$ you chose:

$[\![\forall \overline{\alpha} . \rho]\!] = wt(\rho) = 1 \neq 2 = wt(\forall \overline{\alpha} . \rho)$


Are all problems in the same time hierarchy related to each other? In this problem, "runtimes" refer to worst-case complexity compared up to constant factor.
Say you have two problems, A and B, in the same time hierarchy, and it is clear that algorithm P solves A with that time complexity.
Suppose an oracle spits out the result of problem A using algorithm P. Then does problem B, with the help of this oracle (call this B^P), necessarily have an algorithm running in less time than problem B without the oracle?

If problem A is complete for the class, the class is higher than P, and problem B cannot be solved in polynomial time, then yes, there is some polynomial algorithm that makes use of the oracle and solves the problem.
By definition, if a problem A is complete for some class C, then every problem of this class is reducible in polynomial time to this problem. As a result, a polynomial algorithm for a problem B given an oracle P of the (complete for the class) problem A (we assume that the oracle spits out the answer to an instance of A in constant time) is the following:
Input: instance of problem B

Reduce the instance of B to an instance of A (polytime)
Answer the obtained instance of A using P (constant time)

However, it is not always easy to find the reduction from one problem to another in the same class.


Is that particular case of the "minimum weight solution to linear equations" still NP-complete? We in our research group are working in the application of heuristic methods to the inverse illumination problem (that is, given a set of constraints about the illumination conditions in a scene, find the places where the light sources have to be placed and their intensities in order to fulfill the constraints and minimize the cost). We would like to justify the use of heuristic methods by proving the problem to be NP-hard and we have found it to be closely related to the "minimum weight solution to linear equations" (MWSLE) NP-complete problem of Garey and Johnson's "Computers and intractability", with the particularity that, given that light source emittances can not be negative, the solution to the linear equations system has to be formed only by non-negative values.
Summarizing, the problem is the following:

MINIMUM WEIGHT POSITIVE SOLUTION TO LINEAR EQUATIONS.

INSTANCE: Finite set $X$ of pairs $(\vec{x},b)$, where  $\vec{x}$ is an m-tuple of non-negative integers and $b$ is a non-negative integer, and a positive integer $K \leq m$.

QUESTION: Is there an m-tuple $\vec{y}$ of non-negative rational entries such that $\vec{y}$ has at most $K$ non-zero entries and such that $\vec{x} \cdot \vec{y}=b$ for all $(\vec{x},b)\in X$?

Garvey and Johnson state that MWSLE's NP-completeness can be proved from the "exact covering by 3-sets" problem but don't give more details. Exact cover by 3-sets is a natural generalization of the perfect matching problem to hypergraphs G=(V,E) with all edges e∈E containing 3 vertices (instead of 2) and |V|  is divisible by 3. The problem is to find a subset of the hyperedges such that each vertex is incident to exactly one of the selected hyperedges.

We are trying to prove that the restricted problem is still NP-complete but we don't see the way to do it. Any clues?

Thanks in advance

Esteve

Here's a sketch of an NP-hardness proof. Exact cover by 3-sets is a natural generalization of the perfect matching problem to hypergraphs $G=(V,E)$ with all edges $e \in E$ containing 3 vertices (instead of 2) and $|V|$ is divisible by 3. The problem is to find a subset of the hyperedges such that each vertex is incident to exactly one of the selected hyperedges. Let $x_e$ be a 0/1 variable for each hyperedge $e$ indicating whether or not it is used. Clearly the system of equations

$\sum_{e \in E : v \in e} x_e = 1$    for all $v \in V$

has only non-negative coefficients and has a solution with at most $|V|/3$ positive coefficients if $G$ has an exact cover. The other direction, namely showing that this system has such a solution only if $G$ has an exact cover, is less trivial but still easy.