Other applications of Karger-Stein branching amplification? I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class.  This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don't know  any other applications of the main technique.  (So it's hard to assign homework that drives the point home.)

Karger and Stein's algorithm is a refinement of an earlier algorithm of Karger, which iteratively contracts random edges until the graph has only two vertices; this simple algorithm runs in $O(n^2)$ time and returns a minimum cut with probability $\Omega(1/n^2)$, where $n$ is the number of vertices in the input graph.  The refined "Recursive Contraction Algorithm" iteratively contracts random edges until the number of vertices drops from $n$ to $n/\sqrt{2}$, recursively calls itself twice on the remaining graph, and returns the smaller of the two resulting cuts.  A straightforward implementation of the refined algorithm runs in $O(n^2\log n)$ time and returns a minimum cut with probability $\Omega(1/\log n)$.  (There are more efficient implementations of these algorithms, and better randomized algorithms.)

What other randomized algorithms use similar branching amplification techniques?  I'm especially interested in examples that don't (obviously) involve graph cuts.

@JeffE,  Here is a paper that counts min weight cycles in a graph. As far as I remember, it was definitely inspired by Karger's technique/result and it was a fun proof.  Hope this helps with the teaching.


Complexity of counting m-cycles in a graph with n nodes G is a planar graph with n nodes.
What are the complexity of following problems?

1-A: Does G contain an m-cycle? (m-cycle is a simple cycle with m nodes, m< n)
2-B: complexity of counting all m-cycles in G, (Complexity of #A).

3- what is the complexity of A and B if G is an arbitrary given graph?

Pointing to books and papers is also useful...

Perhaps this paper which deals with cycle lengths in planar graphs might be of value:

Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225.


VC dimension of polynomials (in one variable) of degree d Linear functions in one variable have VC dimension =3 and I remember reading somewhere that the VC for polynomials of degree $d$ is $(d^2 + 3d + 2)/2$.

I am searching for ideas that can prove the above claim (and perhaps generalize to many variables as well, though that seems too much to hope for).

Any approach, even an incomplete one, will be appreciated.

To define the problem properly: Given a plane (2D, x and y coordinates) what is the size of maximum set that can be shattered if you can use classifying functions that are polynomial ($y=p(x)$) of degree at mode $d$, and you are free to choose which side of the curve you want to label positive.

For example, label (x,y) as positive iff $y > x^2 +5x +9$.

The basic method works like this: Assume your inequalities are of the form

$$ \sum_{i \le d} a_i x^i \le 0$$

Then you construct a lifting map to a space of higher dimension in which each monomial corresponds to one dimension. Now the polynomial can be expressed as a linear combination of the new dimensions and you can invoke the usual result for half spaces in the resulting space.

I'm not sure where you get your bound from: the correct expression for the VC dimension of polynomials in d variables of degree D is $\binom{d + D}{d}$, which is the number of monomials of degree at most D formed from d variables.


Generating hard satisfiability problems with given constraint graph Is there a systematic way to tune the hardness of a set of satisfiability problems (say 3-SAT or MAX2SAT) where the constraint graphs are always embeddable into a fixed given graph?

It sounds like what you want are universal factor graphs. Such graphs exist for every NP-hard boolean CSP and in many cases are optimally inapproximable.


Are recursive forms of Godel's statement possible? The self-referentiality of the P/NP problem has sometimes been highlighted as a barrier to its resolution, see, for instance, Scott Aaronson's paper, is P vs. NP formally independent?  One of the many conceivable resolutions to P/NP would be a demonstration that the problem is formally independent of ZFC or true but unprovable.

It's conceivable that the self-referentiality of the problem can pose a deeper challenge in proofs of independence, for example, if statements about its provability are themselves unprovable or otherwise impossible to reason about.

Suppose we call a theorem T Godel_0 if it is true but unprovable in the sense of Godel's theorem.  Call T Godel_1 if the statement "T is Godel_0" is true, but unprovable. Call T Godel_i if the statement "T is Godel_{(i-1)} is true.

We know that Godel_0 statements exist, and a few examples have been found "in the wild" that are not constructed explicitly for this purpose, as in this article.

My question is: do there exist any Godel_1 statements or higher?  Are such statements a natural consequence of Godel's theorem?

What about a statement about which we can prove absolutely nothing: ie, one for which for every k > 0, T is Godel_k?

I can ask an analogous question for formal independence, although I suspect the answer is "no" there.

To return to the P vs. NP question, let me ask whether there's even a hint that Godel's theorem is relevant to questions of class separability.  Have any true but unprovable statements been identified with respect to complexity classes -- beyond, of course, the obvious connection between halting problem and Godel's theorem?

As others have pointed out, there are certain technical difficulties with the statement of your question.  To straighten them out, let's start by avoiding the use of the term "unprovable" without qualification, and be explicit about which set of axioms your statement T is supposed to be unprovable from.  For instance, let's suppose that we're interested in statements T that are unprovable from PA, the axioms of first-order Peano arithmetic.

The first annoyance is that "T is true" is not expressible in the first-order language of arithmetic, by Tarski's theorem.  We could get around this by working in a metatheory that is powerful enough to define the truth of an arithmetical statement, but I think for your purposes this is an unnecessarily complicated route to take.  I think you're not so interested in truth per se but in provability.  That is, I suspect you'd be satisfied with defining T to be Godel_0 if T is true but unprovable in PA, and defining T to be Godel_1 if T is unprovable in PA but "T is unprovable in PA" is unprovable in PA, and defining T to be Godel_2 if T is unprovable in PA and "T is unprovable in PA" is unprovable in PA but "‘T is unprovable in PA’ is unprovable in PA" is unprovable in PA, etc.  That way we don't have to fuss with truth predicates.

This suffices to make your question precise, but unfortunately there is then a rather trivial solution.  Take T = "PA is consistent."  Then T is true because PA is consistent, and T is unprovable in PA by Goedel's 2nd incompleteness theorem.  Furthermore, "T is unprovable in PA" is also unprovable in PA for a somewhat silly reason: any statement of the form "X is unprovable in PA" is unprovable in PA because "X is unprovable in PA" trivially implies "PA is consistent" (since inconsistent systems prove everything).  So T is Godel_n for all n, but I don't this really gets at your intended question.

We could try to "patch" your question to avoid such trivialities, but instead let me try to address what I think is your intended question.  Tacitly, I believe you are conflating the logical strength needed to prove a theorem with the psychological difficulty of proving it.  That is, you interpret a result of the form "T is unprovable in X" as saying that T is somehow beyond our ability to understand.  There are these monstrous conjectures out there, and we puny humans crack PA-whips or ZFC-whips or what have you at those ferocious beasts, trying to tame them.  But I don't think that "T is unprovable in X" should be interpreted as meaning "T is impossible to reason about."  Rather, it's just measuring a particular technical property about T, namely its logical strength.  So if you're trying to come up with the über-monster, I don't think that finding something that is not only unprovable, but whose unprovability is unprovable, etc., is the right direction to go.

Finally, regarding your question about whether unprovability seems at all related to separability of complexity classes, there are some connections between computational intractability and unprovability in certain systems of bounded arithmetic.  Some of this is mentioned in the paper by Aaronson that you cite; see also Cook and Nguyen's book Logical Foundations of Proof Complexity.


Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$ I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup \text{PSPACE-complete}$.

Is it known any such a problem ?

(It would be very nice to have examples of $\text{PSPACE}\cap\text{coNP-hard}$ combinatorial games with these properties, but any other kind of example would be high appreciated)

Formula Isomorphism is in $\mathsf{\Sigma_2 P} \subseteq \mathsf{PSPACE}$, is easily seen to be $\mathsf{coNP}$-hard, but is not known to be $\mathsf{NP}$-hard. Note that FI is not $\mathsf{\Sigma_2 P}$-complete unless $\mathsf{PH}$ collapses to the third level. All of this can be found in Agrawal & Theirauf.


Why is HAMILTONIAN CYCLE so different from PERMANENT? A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$  such that $f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$. That is, it is possible to
replace each variable $y_j$ of $g$ by a variable $x_i$ or a constant $0$ or $1$ so that
the resulting polynomial coincides with $f$.

I am interested in (the reasons for) the difference between the permanent polynomial PER and the Hamiltonian cycle polynomial HAM:
$$
\mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \  \mbox{and} \ \ \ \
\mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}
$$
where the first summation is over  all permutations $h:[n]\to[n]$,
and the second is only over all cyclic permutations $h:[n]\to[n]$.

Question: Why HAM is not a monotone projection PER? Or it still is?

I am not asking for proofs, just for intuitive reasons.

Motivation: the largest known monotone circuit lower bound for PER (proved by Razborov) remains "only" $n^{\Omega(\log n)}$. On the other hand, results of
Valiant imply that
$$
\mbox{CLIQUE$_n$ is a monotone projection of HAM$_{m}$}
$$
where
$$
\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i < j\in S}x_{i,j}
$$
with the summation is over all subsets $S\subseteq [n]$ of size $|S|=\sqrt{n}$. I myself couldn't get a "simple, direct" reduction form these general results, but Alon and Boppana claim (in Sect. 5) that already $m=25n^2$ is sufficient for this reduction.

But wait: it is well known that CLIQUE requires monotone circuits of size $2^{n^{\Omega(1)}}$ (first proved by Alon and Boppana using Razborov's method).

So, were HAM a monotone projection of PER, we would have $2^{n^{\Omega(1)}}$ lower bound also for PER.

Actually, why HAM is not even a non-monotone projection  of PER? Over the boolean semiring, the former is NP-complete, while the latter is in P. But why? Where is a place where being cyclic for a permutation makes it so special?

P.S. One obvious difference could be: HAM covers [n] by just one (long) cycle, whereas PER can use may disjoint cycles for this. Thus, to project PER to HAM the hard direction seems to be: ensure that the absence of a Hamiltonian cycle implies the absence of any covering with disjoint cycles in the new graph. Is this the reason for HAM not being a projection of PER?

P.P.S. Actually, Valiant proved a more impressing result: every polynomial $f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$ with $c_u\in\{0,1\}$, whose coefficients $c_u$ are p-time computable, is a projection (not necessarily monotone if the algo is non-monotone) of HAM$_m$ for $m$ = poly$(n)$. PER also has this property, but only over fields of characteristic $\neq 2$. So, in this sense, HAM and PER are indeed "similar", unless we are not in GF(2) where, as Bruno remembered, PER turns to DETERMINANT, and is easy.

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone projections of polynomials with nonnegative coefficients lead to the Newton polytope of one being an extended formulation of the Newton polytope of the other, and then applying the recent lower bounds on extended formulations.

Let $f(x_1,\dotsc,x_n)$ and $g(y_1,\dotsc,y_m)$ be polynomials with nonnegative coefficients (as is the case here). Suppose that $f$ is a monotone projection of $g$ under the assignment $\pi$ (following the notation of the question). Under $\pi$, each monomial of $g$ gets mapped either to 0 (iff one of its variables gets mapped to 0) or to a monomial of $f$: there can't be any cancellations because of non-negativity.

Let $New(f)$ denote the Newton polytope of $f$, and similarly for $New(g)$.

Claim: there is an extended formulation for $New(f)$ in $\mathbb{R}^m$, using $\leq n+m$ variables, and a number of constraints that is at most $n+m$ plus the number of constraints defining $New(g)$.

Here's how: Let $e_1,\dotsc,e_m$ be the coordinates on $\mathbb{R}^m$ (in which $New(g)$ lives; viz., an integer point in $\mathbb{R}^m$ with coordinates $(e_1,\dotsc,e_m)$ corresponds to the monomial $y_1^{e_1} \dotsb y_m^{e_m}$). For those $i$ such that $\pi(y_i)=0$, intersect $New(g)$ with $\{e_i = 0\}$ (since only monomials that do not involve $y_i$ can contribute to the projection); this adds at most $m$ additional constraints. Let $P$ denote the resulting polytope. Then $\pi$ induces a linear map $L_{\pi}\colon \mathbb{R}^{m} \to \mathbb{R}^{n}$, such that $L_{\pi}(P) = New(f)$. This last part follows from the lack of cancellations. Thus we get an extended formulation for $New(f)$ by taking $n+m$ variables, the constraints for $P$ on the $m$ variables, and the constraints defining $L_{\pi}$ (of which there are at most $n$, one for each $x_i$). QED Claim

Now take $f$ to be the $n$-th Hamilton cycle polynomial and $g$ to be the $m$-th permanent, and suppose that $f$ is a monotone projection of $g$. The Newton polytope of the permanent (and determinant, incidentally), is the cycle cover polytope. This polytope is easily described by the "edge" variables $e_{ij}$ and the $m$ equations stating that every vertex has degree exactly 2.

The Newton polytope of the Ham. Cycle polynomial is the Hamiltonian cycle polytope (surprise, surprise). But this polytope is the TSP polytope, which requires $2^{n^{\Omega(1)}}$ equations to describe any extended formulation of, which, when $m$ is subexponential, contradicts the small extended formulation given by the cycle cover polytope and $L_{\pi}$ as above.

(Note that this argument fails if $f$, $g$, or $\pi$ can have negative coefficients, as then there can be cancellations, so $L_{\pi}$ need not map onto $New(f)$.)

It's interesting to note that the geometry of these polytopes is closely related to the fact that matching is in $\mathsf{P}$ while Hamilton cycle is $\mathsf{NP}$-complete, but I think the above reasoning shows how the geometric structure here really can add something beyond that complexity classification.


Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question I am reading the paper "Kernelizations for Parameterized Counting Problems", and had a question regarding some of the notation in the paper (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8295&rep=rep1&type=pdf).

In section 4, the author begins by defining the notion of a crown as follows:

Let $\mathcal{G} := (V, E)$ be a graph. A crown in $\mathcal{G}$ is a bipartite subgraph $\mathcal{C} = (I, N(I), F)$ of $\mathcal{G}$ satisfying the following three conditions.

$I$ is an independent set in $\mathcal{G}$ and $N(I)$ is the set of all neighbours of vertices from $I$ in $\mathcal{G}$.
$F$ contains all of the edges of $E$ that connect vertices from $I$ to $N(I)$.
$\mathcal{C}$ has a matching of cardinality $|N(I)|$.

In then goes on to define a few other pieces of notation. Let $\mathcal{G} - \mathcal{C}$ be the graph obtained from $\mathcal{G}$  by deleting all of the vertices in $\mathcal{C}$ and all edges incident to vertices in $\mathcal{C}$. Also, let $S_\mathcal{C}$ be a vertex cover of $\mathcal{C}$ and let $\mathcal{G}' := (V', E')$ be the graph obtained from $\mathcal{G} - \mathcal{C}$ by deleting all edges covered by vertices in $S_\mathcal{C}$.

What confuses me here is the difference between $\mathcal{G} - \mathcal{C}$ and $\mathcal{G}'$. Since the vertex cover contains only vertices in $I$ or $N(I)$, when removing $\mathcal{C}$ from $\mathcal{G}$, haven't we already removed all of the edges that can be covered by vertices in $S_\mathcal{C}$? It would seem to me that the edges in $\mathcal{G} - \mathcal{C}$ do not have any vertices that are incident, making it identical to $\mathcal{G}'$. Where is the error in my reasoning/understanding?

Thanks!!

I agree with the OP: $\mathcal{G} - \mathcal{C} = \mathcal{G}'$.

I assume the author of the paper wanted to define $\mathcal{G}'$ as $\mathcal{G} - S_{\mathcal{C}}$. With this modification, the next sentence in the paper makes sense:

  One can easily see that $\#vc(\mathcal{G}',k-|S_{\mathcal{C}}|)$ equals the number of size $k$ vertex covers $S$ in $\mathcal{G}$ with $S \supseteq S_{\mathcal{C}}$.

Here, $\#vc(\mathcal{G},k)$ denotes the number of size $k$ vertex covers in $\mathcal{G}$.


Auditable encrypted ledger Consider a cloud-based accounting system that needs access to aggregate information such as an account's balance but doesn't need access to individual transaction amounts in a ledger.

Does there exist a homomorphic encryption scheme that allows a public observer (such as a cloud computing provider) to compute the plaintext sum of a set of encrypted unsigned integers without being able to decode any individual transaction value (n=1 notwithstanding)?

As another example, regulations exist to ensure capital reserves. An institution could use such a scheme to furnish proof of compliance without disclosing individual transactions.

For all non-negative integers $n_0$,$n_1$,$n_2$ and random strings $r_0,r_1,r_2$

$n_0 \:\: = \:\: (n_0+n_1+n_2)-(n_1+n_2)$
$=$
$\operatorname{plaintextsum}(\operatorname{encrypt}(n_0,r_0),\operatorname{encrypt}(n_1,r_1),\operatorname{encrypt}(n_2,r_2))$

$- \: \operatorname{plaintextsum}(\operatorname{encrypt}(n_1,r_1),\operatorname{encrypt}(n_2,r_2))$

.

Therefore any such scheme would be completely insecure

if more than 2 non-negative integers are encrypted with it.


Algorithms for factorization using the decision version Are there any practical algorithms for integer factorization that work by solving the decision version of the problem $\log N$ times to isolate a factor? Or is the decision version of only theoretical interest?

All of the following algorithms either find a complete factor or a complete non-trivial factorization:

Trial division.
Pollard rho.
Pollard $p-1$ and its variants, including the elliptic curve method (ECM).
Shanks' SQUFOF.
Quadratic sieve (QS).
Number field sieve (NFS).

As far as I understand this list includes all algorithms actually used to factor integers in real life.

Finding just one bit of a factor sounds very unnatural to me, and I can't imagine an algorithm which can find one bit without finding all bits. (Even the SAT algorithm for factorization will find all bits at once.)


Merging Graph Edges to form a 2 color-able Graph (with weight constraints)? Given an undirected graph $G$. Each vertex has a weight 1.

We define shrinking an edge as merging and replacing 2 adjacent vertices $(A, B)$ with a new vertex $C$ such that all the vertices that were connected to $A$ or $B$ are now connected to $C$. Moreover the weight of the new vertex $C$ is sum of weight of $A$ and $B$.

Question: Determine if for a given graph $G$, we can merge vertices such that in the new Graph:

Each vertex has a weight 2.
The new graph is 2 color-able.

How do we approach this problem?

Your problem is exactly equivalent to the 2-colorable perfect matching problem:
On input a graph, color the vertices of the graph with two colors such that each vertex has exactly one neighbor of the same color.

The 2-colorable perfect matching problem was introduced in "The complexity of satisfiability problems" by T. J. Schaefer and is NP-complete.


How can I compute knots? Is there a documented way to compute knots? (circumferences embedded in a 3-dimensional Euclidean space).

I mean, a datatype to represent them, and an algorithm to determine if two instances of the datatype represent the same knot.

If the answer is positive, what about the complexity of that problem?

The most natural ways to represent knots are either to embed them piecewise linearly in $\mathbb{R}^3$ (just store the coordinates of the vertices and where you want to put segments) (any tame knot can be embedded piecewise linearly) or with a knot diagram, i.e. storing a projection on $\mathbb{R}^2$ as a graph where at every crossing you specify which strand is above.

As Suresh pointed out, checking knot equivalence is highly non-trivial (not known to be in P) but experimental results for unknot recognition are polynomial-like -- knot equivalence looks much harder though. If you are looking for software, peek at Regina .


Breadth first search and Eppstein K shortest paths algorithm I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf

I have trouble particularly with this quote on page 7, paragraph 2.3:

"If G contains cycles, the path tree is infinite. By Lemma 3, the path tree is heap-ordered. However since its degree is not necessarily constant, we cannot directly apply breadth first search (nor Frederickson’s heap selection technique, described later in Lemma 8) to find its k minimum values."

Why can we not use breadth first search (BFS) here? I've tried to look for an answer and to come up with different graphs where the degree of the nodes varies, but so far I do not understand this. Could someone explain how the non-constant degree prevents us from using BFS?

The main reason is that the non-constant degree would imply that the time per result is too high. The number of nodes found by the search, in the end, is going to be k, but all but the last one needs to have their children expanded, so the number of expanded nodes is kd where d is the degree. Unless d is O(1) this will be larger than the eventual time bound of the algorithm.


Uncountability in intuitionistic logic I've read snippets here and there that inside intuitionistic logic, uncountable can be a subset of the naturals ?

What is the correct intuition to think about this? Andrej Bauer replied above, saying that:

Given any sequence alleged enumeration e : Integer -> (Integer -> Bool), e will miss the sequence contra i = not (e i i). Hence, we cannot enumerate the type in Haskell.

I understand this argument, and yet, I am uncomfortable with it. I'm not sure when to think "inside the model" versus "outside the model". This seems to imply that things inside the model can believe as absurd facts as they want, perhaps something even like powerset(X) = X? How should one think about the difference between what happens 'inside' and 'outside'?

I have been picking up fragmentary references to the weirdness of intuitionistic logic (relative to, say, ZFC) here and there. I'm unaware of a textbook that lays out these results in an orderly fashion. Can I please have a textbook recommendation?

I tried to address the questions you raise in "Five stages of accepting constructive mathematics".
And here are some textbooks:

Constructive analysis by D. Bridges and E. Bishop is the "bible" of constructive mathematics.
Varieties of constructive mathematics by D. Bridges and F. Richman considers several varieties of constructive mathematics, and discusses some of the pathologies and niceties that they possess.
Constructivism in mathematics (volumes 1 and 2) by D. van Dalen and A. Troelstra provides an in-depth treatment of constructive mathematics.


NP completeness of linear $0-1$ assignment problem Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each.

Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables each.

Make another partition $\Pi_2$ the following way. Pick $1$ variable in every disjoint set of variables in $\Pi_1$ form a new subset of variable of size $n$.  Pick $1$ variable in every disjoint set of variables in $\Pi_1$ not picked before to form a new subset of variable of size $n$. So we have another disjoint partition into $n$ disjoint sets of $n$ variables each.

(1a) Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set?

(1b) Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment that satisfies exactly $n$ of assignments to be $1$ with exactly $1$ assignment per disjoint set $\Pi_1$ AND with exactly $1$ assignment per disjoint set $\Pi_2$?

Does subset sum reduce to both of these?

What is a good reduction from any $\mathsf{NP}$-complete problem?

It seems to me that the problem (1a) and (1b) qualify as some restricted version of $n$-sum problems. This seems to imply problem is $\mathsf{NP}$-complete. That is it is likely that some special case of $n$-sum reduces to these problems. Since $n$ is a function of number of variables $n^2$ are these problems $\mathsf{NP}$-complete?

What if we add the promise that any satisfying assignment will have exactly $n$ $1$s?

(2) Is it $\mathsf{NP}$-complete to decide if there is a valid (valid here means vanishing) $0/1$ assignment with exactly $n$ of assignments to be $1$ (without regard to partition)?

has a trivial reduction as shown by Michael Wehar.

A guess that we can think of (1a) as following:

Consider problem:

(3) Given $n^2$ integers is there a way to partition the integers into disjoint subsets of size $n$ such that at least one of the subsets sum to $0$?

This problem sounds much similar to problem in definition $2$ in section $1.2$ here http://dreamboxx.com/mark/data/njc08.pdf.

May be we can show (3) is $\mathsf{NP}$-complete and find a way to reduce (1a) to (3)?

If I understood it well, (1) is also NP-complete, a possible reduction is from SUBSET SUM:

Given a set of $m$ positive integers $A = \{a_1, ..., a_m\}$, and a positive integer $B$, is there a subset of $A' \subseteq A$ a such that $\sum_{a_i \in A'} a_i$

You simply pick $n = (m+1)$ and build your set in this way:

add $ a_1, a_2, , ..., a_m$
add $m$ zeros
add the only negative number $-B$
"fill" the other remaining $n^2 - 2m - 1$ elements with $C = \sum_{a_i} + B +1$

($\Rightarrow$) If the original subset sum has a solution $A'$ then it is sufficient to use this partition $\Pi_1$

a1  C  C  ... C  0  C
 0 a2  C  ... C  C  C
        ....
 C  C     ... 0 am  C
 C  C     ... C  C -B

and for each "row" pick $a_i$ if $a_i \in A'$, $0$ otherwise (and pick the final $-B$)

($\Leftarrow$) If there is a partition $\Pi_1$ with a vanishing 0/1 assignment then note that:

(i)  none of the $C$s can be picked (they are too large);
(ii) at least one row must contain all elements different from $0$ (because there are $m+1$ rows and only $m$ zeros); so at least one nonzero element must be picked;
(iii) in every case the $-B$ element must be picked to vanish the sum

So the elements $a_i$ picked, no matter how the elements are partitioned between the rows, sum exactly to $B$; i.e. they are a valid solution for the original SUBSET SUM problem.

OUCH! I just read Michael's answer about problem (2) and the reduction is almost the same ... so you can also accept his answer!

EDIT: the reduction remains valid for the (1b) case:

The ($\Leftarrow$) direction it uses only the constraints on $\Pi_1$ which are the same of case 1a (exactly 1 "pick" from each row).

The ($\Rightarrow$) direction is also valid; to see it "visually", just build the main diagonal of $\Pi_1$ with the elements of $a_i \in A'$, the element $-B$, while the remaining elements of the diagonal are $0$s.

For example if $m = 5$ and the solution of the subset sum is $A' = \{ a_1, a_2, a_4 \}$, $\Pi_1$ is:

 a1  0  C   C  C   C
  C a2  0   C  C   C
  C  C  0  a3  C   C
  C  C  C  a4  0   C
  C  C  C   C  0  a5
  C  C  C   C  c  -B

In this way you can build $\Pi_2$ setting the element $j$ of row $i$-th equal to element $j$ of column $i$ in $\Pi_1$. The assignment clearly vanishes both $\Pi_1$ and $\Pi_2$ and the constraints are met.


Chaos and the $P{=}NP$ question I am interested in learning connections between "chaos," or more broadly, dynamical systems, and
the $P{=}NP$ question.
Here is an example of the type of literature I am seeking:

  Ercsey-Ravasz, Mária, and Zoltán Toroczkai. "Optimization hardness as transient chaos in an analog approach to constraint satisfaction." Nature Physics 7, no. 12 (2011): 966-970. (Journal link.)

Has anyone written a survey, or made a bibliographic compendium?

the paper you cite by Ercsey-Ravasz, Toroczkai is very crosscutting; it fits in with/ touches on several lines of NP complete problem/ complexity/ hardness research. the connection to statistical physics and spin glasses was uncovered mainly via "phase transitions" in the mid 1990s and that has led to a large body of work, see Gogioso[1] for a 56p survey. the phase transition coincides with what is known as "the constrainedness knife edge" in [2]. the exact same transition point does turn up in very theoretical analyses of computational complexity/ hardness eg [3] that also relate to early studies of transition point behavior in clique problems by Erdos. [4] is a survey/ video lecture on phase transitions and computational complexity by Moshe Vardi. [5][6] are overviews of phase transition behavior across NP complete problems by Moore, Walsh.

then there is scattered but maybe increasing study of the diverse connections of dynamical systems with computational complexity and hardness in a variety of contexts. there is a general connection found in [7] possibly explaining some of the underlying reasons for frequent "overlap". refs [8][9][10][11] are diverse but show a reoccuring theme/ crosscutting appearance between NP complete problems and various dynamical systems. in these papers there is some concept/ examples of a hybrid link between discrete and continuous systems.

chaotic behavior in NP complete systems is analyzed in [11].

A somewhat similar ref to Ercsey-Ravasz/ Toroczkai in the area of quantum algorithms in that the dynamical system is found to run "apparently" in P-time [12]

  In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm.

[1] Aspects of Statistical Physics in Computational Complexity / Gogioso

[2] The constrainedness knife edge / Toby Walsh

[3] The Monotone Complexity of k-Clique on Random Graphs / Rossman

[4] Phase transitions and computational complexity / Moshe Vardi

[5] Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore

[6] Phase transition behavior / Walsh

[7] Determining dynamical equations is hard / Cubitt, Eisert, Wolf

[8] The steady state system problem is NP-hard even for monotone quadratic Boolean dynamical systems / Just

[9] Predecessor and Permutation Existence Problems for Sequential Dynamical Systems / Barret, Hunt III, Marathe, Ravi, Rosenkrantz, Stearns. (also goes by Analysis Problems for Graphical Dynamical Systems: A Unified Approach Through Graph Predicates)

[10] A Dynamical Systems Approach to Weighted Graph Matching / Zavlanos, Pappas

[11] On chaotic behaviour of some np-complete problems / Perl

[12] New quantum algorithm for studying NP-complete problems / Ohya, Volovich


Art gallery variants with pairwise visibility? The traditional art gallery problem sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region.

Has anyone ever looked at art gallery variants where the visibility region is instead defined by a pair of guards. For example, one formulation might be that a point is covered if there's a pair of guards whose minimum bounding disk covers it ?

I'm not aware of any such work.  However, I would expect that such a problem would be NP-complete and, for polygons with holes, would be as hard to approximate as Set Cover.  The relatively straightforward vertex/vertex guarding problem, in which guards can only lie on vertices and only vertices need to be guarded, is this hard (Eidenbenz, Stamm, and Widmayer (2001)).

For simple polygons, I expect such a problem would be:

NP-complete
APX-hard
Approximable to within a factor of $O(\log(\rm{opt}))$, where opt is the optimum number of guards.

The vertex/vertex guarding problem is APX-hard for simple polygons (Eidenbenz (1998)).

The best algorithms for the art gallery problem for simple polygons are based on building small $\varepsilon$-nets.  In simple polygons, the range spaces induced by visibility polygons have constant VC-dimension.  Circles do as well.  Therefore a range space induced by visibility polygons in a simple polygon, circles, and the intersections and unions thereof, will also have constant VC-dimension and you can get a $O(\log(\rm{opt}))$-approximation algorithm.

I thought about this problem a little for my thesis, but came to the opinion that there weren't any particularly interesting variants that didn't seem to reduce fairly closely to a known problem involving single-guarding.


Are there known "completion" operations over languages ? Assume that $P \neq NP$ and let $NPI = NP \setminus (P \cup NPC)$.

Let $L \in NPI$ be a language over an alphabet $\mathcal{A}$.

Does there always exist $S \subset \mathcal{A}^*$ such as $(L \cup S) \in NPC$ ?

On the removal side, Ladner showed that for each $L \in NPI$, there exists $S \subset L$, $S \neq L$ such as $S \in NPI$.

What are known theorems around those kind of operations ?

Some observations:

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

This rasises a potentially interesting question:

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

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

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


Why does LTL equivalence (with next oeprator) implie trace equivalence in finite transition machines? I am following Katoen's YouTube course about Model Checking.
I am trying to understand how finite transition machines are different from infinite transition machines in terms of equivalences. That lead me to the following question regarding equivalences, but the focus there was on infinite transition machines. Comments in the thread claimed that LTL equivalence = trace equivalence in finite transition machines, when LTL includes the next operator but I do not see how.
The direction from trace equivalence to LTL equivalence is immediate, due to the fact that only traces satisfy LTL formulas.
The other direction is problematic for me:
If we have two transition machines that are LTL equivalent, I understand that they are equivalent with respect to finite traces, because I can use the next operator, but what happens with infinite traces?
If I try and assume the claim is false in hopes of reaching a contradiction, I get that an infinite number of prefixes from each infinite trace from either transition system would have to be in both trace sets, but where's the problem? Can't I express infinitely many different prefixes using a finite transition machine?

The important thing to notice is that in finite transition systems, two systems $K_1,K_2$ over an alphabet $\Sigma$ are not trace equivalent (for infinite traces) if and only if there exists a finite trace $w\in \Sigma^*$ that is in one of them, but not the other.
Indeed, if $K_1$ and $K_2$ are not trace equivalent, denoted $L(K_1)\neq L(K_2)$, then w.l.o.g. there exists an infinite trace $x\in L(K_1)\setminus L(K_2)$, but we can say something stronger: since the transition systems are finite, we can actually assume $x$ is of the form $x=uv^\omega$ for finite words $u,v\in \Sigma^*$.
This "lasso" structure of $x$ tells us that there is a finite trace $uv^m\in L(K_1)\setminus L(K_2)$, for some $m\in \mathbb{N}$, thus getting rid of the "infinitely many prefixes" problem.
Now, we can define an LTL formula, using "next" operators, that states "$uv^m$ is not a prefix of the trace". This formula holds in $K_2$, but not in $K_1$.


Why are these two definitions of PPAD equivalent? The complexity class PPAD is usually defined by stating that End-Of-The-Line is PPAD-complete.

  End-Of-The-Line is a search problem. The input consists of a directed graph in which each node has in-degree and out-degree at most 1. The graph is given by a polynomial-time computable function $f(x)$ that returns the predecessor and successor of $x$. In addition, one is given a node $v$ with a successor but no predecessor. Find a node $t\ne v$ that has no successor or no predecessor.

Recently, I heard a different definition of PPAD. As far as I recall, it was based on the following problem.

  A directed graph (again specified by a polynomial-time computable function) and a node whose in-degree is not equal its out-degree is given. Find another node with this property.

Clearly, End-Of-The-Line is a special case of the latter problem but is the latter problem really more difficult to solve? My question is this:

  Are both problems complete for the same complexity class PPAD? If yes, why? If not, what is the complexity class resulting from the second problem?

For issues with the cited paper, (and hence this answer) see Does PPAD really capture the notion of finding another unbalanced vertex?

Yes. These two problems are equivalent and hence PPAD-complete. The reduction is given on page 505 of Papadimitriou's original 1994 paper (pdf) introducing End of the Line. This is valid even if the degree of the graph is exponential, provided we are given an "edge-recognition algorithm" and a "pairing function". This is also mentioned on the same page. The reduction is given for PPA (the undirected version of PPAD). It can be extended to PPAD as well.


In what sense are coroutines dual to (sub)routines? The name coroutine suggests that in some sense they should be dual to (sub)routines. Is there a real mathematical duality? I'm hoping for something like "in category theory subroutines are X and coroutines are Y, where X is dual to Y".

I think this a misanalysis of the "co" prefix in this case.

"Coroutine" is "co" in the sense of "co-worker"; something that works together with another.

The term precedes by a long way the gross overuse for programming concepts of the prefix "co" in the Category Theoretic sense of a dual of another concept.

(Yes, there is editorial content there. ;-) )


A stronger Flow Decomposition Theorem? In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows:

Every nonnegative arc flow x can be represented as a path and cycle flow (though not necessarily uniquely) with the following two properties:
(a) Every directed path with positive flow connects a deficit node to an excess node
(b) At most n+m paths and cycles have nonzero flow; out of these at most m cycles have nonzero flow with m the number of edges and n the number of nodes in the graph

My question is, if the theorem can be formulated more strongly modifying point b as follows:

(b) At most m paths and cycles have nonzero flow

My question arises as going through the lecture nodes of a more modern optimization course at Stanford, I find the flow decomposition theorem formulated exactly with this "stronger" assertion (page 58 with proof here or a similar theorem here).
Going through the proofs in the lecture nodes and the book, I find the stronger formulation justified. Especially in Network Flows: Theory, Algorithms, and Applications the following argument is given for their m+n bound on paths:

Now observe that each time we identify a directed path, we reduce the excess/deficit of some node to zero or the flow on some arc to zero;

As I understand it, reducing the excess/deficit of some node to zero implies setting the flow on some arc to zero, as the excess/deficit flow of a node has to go/come over an arc whose flow is now set to zero. This however would imply bounding the number of paths with m instead of n+m, as each construction of a flow-path would remove one edge and not one edge or node from the graph.
Have I misunderstood the proof and are the lecture nodes from Stanford wrong? Do you know other books which one could possible cite for the stronger version of the flow decomposition theorem?
Thank you!
Note: In this question with the very promising title, a different question has been asked. It took the theorem from one of the aforementioned Stanford notes, and in the answers the correctness of it was discussed albeit for different reasons.

The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound $m+n$.
In the case of $(s,t)$-flows, we may note that during decomposition the nodes $s$ and $t$ becomes balanced at the same time. This gives the already the bound $m+1$ on the number of paths and cycles. If we look at the flow decomposition, when finding the final path flow (this is where the balance of $s$ and $t$ becomes balanced), if no flow on some arc is made 0, it means that we will still find a cycle flow. Now the final cycle flow will make at least two arcs have flow 0 at the same time. This sharpens the bound to $m$ in case of $(s,t)$-flows.
P.S. The proofs of the notes you link are not quite correct, see the comments.


Asymptotics for Coin changing Given $n$ coin denominations, with $c_1=1$ and $c_2<c_3<..<c_{n}$ being random numbers uniformly distributed in the range $[2,N]$. Asymptotically, for what fraction of coins does the greedy algorithm generate optimal change using this set of denominations?

The answer is known for  3 denominations ; but what about the general case?

This is not an answer but maybe this will point you or someone else in the right direction.

I found the paper by D. Kozen and S. Zaks called "Optimal Bounds for the Change-Making Problem" wherein they give conditions for when a coin change instance's greedy change making algorithm is optimal.  I will use their notation.

  Given a coin change instance of $m$ distinct coins
  $$ ( c_1, c_2, c_3, \cdots, c_{m-1}, c_{m} ) $$
  $$ c_1 = 1 < c_2 < c_3 < \cdots < c_{m-1} < c_m $$
  a function $M(x)$ representing the optimal number of coins needed to make change for $x$ and a function $G(x)$ representing the number of coins needed to greedily make change for $x$, then if $M(x) \ne G(x)$, there exists a counterexample in the range
  $$ c_3 + 1 < x < c_{m-1} + c_m $$

They go on to show that

  If for every $x$ in the range $c_3 + 1 < x < c_{m-1} + c_m $
  $$ G(x) \le G(x-c) + 1$$
  $$ c \in (c_1, c_2, \cdots, c_m )$$
  then $G(x) = M(x)$ (i.e. the greedy algorithm is the optimal).

This gives us an "efficient" (up to pseudo polynomial time) test to determine whether a coin change instance is greedy or not.

Using the above, I have run a short simulation the results of which are plotted on a log-log scale below

Each point represents the average of 10000 instance creations for $m$ shown and each element chosen to be distinct but otherwise uniform and at random from the range of $[1 \cdots N]$.

Given that we know the probability of the greedy algorithm being optimal for $m=3$ goes as $\frac{8}{3} N^{-\frac{1}{2}}$, from just looking at the graph I would hazard a guess that the probability of the greedy algorithm being optimal goes as:

$$ p_m(N) \propto N^{-\frac{(m-2)}{2} } $$

where $p_m(N)$ is the probability that $m$ distinct coins drawn uniformly at random from the range of $N$ is greedy optimal (otherwise known as 'canonical').

In the large $m$ limit, the probability that the greedy solution is optimal goes quickly to 0 for any non-trivial value of $N$.  If the above equation holds, then it is easy to see, but there might be other ways of looking at it that give the same conclusion.  For example, looking at Borgs, Chayes, Mertens and Nair's Random Energy Model work indicate that the energy is too jagged at the bottom to expect local moves (i.e. greedy moves) to give an optimal solution.  This is of course for the Number Partition Problem and is only provided to give some intuition rather than a definite answer.

At the risk of answering a question that you did not ask, I wanted to point out that "real world" coin systems do not follow a uniform distribution for coin denominations.  For example, the USA has at least 12 denominations (including bills: $ (1, 5, 10, 25, 50, 100, 200, 500, 1000, 2000, 5000, 10000)$ ) which do not appear to be uniformly distributed.  Perhaps looking at other distributions to generate the coin denominations would yield non-trivial results in the large system limit.  For example, a power law distribution might yield coin denominations that are more similar to the USA's.


How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ? A lot of pathfinding algorithms have been developed in recent years which can calculate the best path in response to graph changes much faster than A* - what are they, and how do they differ?  Are they for different situations, or do some obsolete others?

These are the ones I've been able to find so far:

D* (1994)
Focused D* (1995)
DynamicSWSF-FP (1996)
LPA (1997)
LPA*/Incremental A* (2001)
D* Lite (2002)
SetA* (2002)
HPA* (2004)
Anytime D* (2005)
PRA* (2005)
Field D* (2007)
Theta* (2007)
HAA* (2008)
GAA* (2008)
LEARCH (2009)
BDDD* (2009 - I cannot access this paper :|)
Incremental Phi* (2009)
GFRA* (2010)
MTD*-Lite (2010)
Tree-AA* (2011)

I'm not sure which of these apply to my specific problem - I'll read them all if necessary, but it would save me a lot of time if someone could write up a summary.

My specific problem:  I have a grid with a start, a finish, and some walls.  I'm currently using A* to find the best path from the start to the finish.

The user will then move one wall, and I have to recalculate the entire path again.  The "move-wall/recalculate-path" step happens many times in a row, so I'm looking for an algorithm that will be able to quickly recalculate the best path without having to run a full iteration of A*.

Though, I am not necessarily looking for an alteration to A* - it could be a completely separate algorithm.

So, I skimmed through the papers, and this is what I gleamed.  If there is anyone more knowledgable in the subject-matter, please correct me if I'm wrong (or add your own answer, and I will accept it instead!).

Links to each paper can be found in the question-post, above.

Simple recalculations

D* (aka Dynamic A*) (1994):  On the initial run, D* runs very similarly to A*, finding the best path from start to finish very quickly.  However, as the unit moves from start to finish, if the graph changes, D* is able to very quickly recalculate the best path from that unit's position to the finish, much faster than simply running A* from that unit's position again.  D*, however, has a reputation for being extremely complex, and has been completely obsoleted by the much simpler D*-Lite.
Focused D* (1995):  An improvement to D* to make it faster/"more realtime."  I can't find any comparisons to D*-Lite, but given that this is older and D*-Lite is talked about a lot more, I assume that D*-Lite is somehow better.
DynamicSWSF-FP (1996): Stores the distance from every node to the finish-node.  Has a large initial setup to calculate all the distances.  After changes to the graph, it's able to update only the nodes whose distances have changed.  Unrelated to both A* and D*.  Useful when you want to find the distance from multiple nodes to the finish after each change; otherwise, LPA* or D*-Lite are typically more useful.
LPA*/Incremental A* (2001):  LPA* (Lifelong Planning A*), also known as Incremental A* (and sometimes, confusingly, as "LPA," though it has no relation to the other algorithm named LPA) is a combination of DynamicSWSF-FP and A*.  On the first run, it is exactly the same as A*.  After minor changes to the graph, however, subsequent searches from the same start/finish pair are able to use the information from previous runs to drastically reduce the number of nodes which need to be examined, compared to A*.  This is exactly my problem, so it sounds like LPA* will be my best fit.  LPA* differs from D* in that it always finds the best path from the same start to the same finish; it is not used when the start point is moving (such as units moving along the initial best path).  However...
D*-Lite (2002):  This algorithm uses LPA* to mimic D*; that is, it uses LPA* to find the new best path for a unit as it moves along the initial best path and the graph changes.  D*-Lite is considered much simpler than D*, and since it always runs at least as fast as D*, it has completely obsoleted D*.  Thus, there is never any reason to use D*; use D*-Lite instead.

Any-angle movement

Field D* (2007):  A variant of D*-Lite which does not constrain movement to a grid; that is, the best path can have the unit moving along any angle, not just 45- (or 90-)degrees between grid-points.  Was used by NASA to pathfind for the Mars rovers.
Theta* (2007): A variant of A* that gives better (shorter) paths than Field D*.  However, because it is based on A* rather than D*-Lite, it does not have the fast-replanning capabilities that Field D* does.  See also.
Incremental Phi* (2009): The best of both worlds.  A version of Theta* that is incremental (aka allows fast-replanning)

Moving Target Points

GAA* (2008): GAA* (Generalized Adaptive A*) is a variant of A* that handles moving target points.  It's a generalization of an even earlier algorithm called "Moving Target Adaptive A*"
GRFA* (2010): GFRA* (Generalized Fringe-Retrieving A*) appears (?) to be a generalization of GAA* to arbitrary graphs (ie. not restricted to 2D) using techniques from another algorithm called FRA*.
MTD*-Lite (2010): MTD*-Lite (Moving Target D*-Lite) is "an extension of D* Lite that uses the principle behind Generalized Fringe-Retrieving A*" to do fast-replanning moving-target searches.
Tree-AA* (2011): (???) Appears to be an algorithm for searching unknown terrain, but is based on Adaptive A*, like all other algorithms in this section, so I put it here.  Not sure how it compares to the others in this section.

Fast/Sub-optimal

Anytime D* (2005):  This is an "Anytime" variant of D*-Lite, done by combining D*-Lite with an algorithm called Anytime Repairing A*.  An "Anytime" algorithm is one which can run under any time constraints - it will find a very suboptimal path very quickly to begin with, then improve upon that path the more time it is given.
HPA* (2004): HPA* (Hierarchical Path-Finding A*) is for path-finding a large number of units on a large graph, such as in RTS (real-time strategy) video games.  They will all have different starting locations, and potentially different ending locations.  HPA* breaks the graph into a hierarchy in order to quickly find "near-optimal" paths for all these units much more quickly than running A* on each of them individually.  See also
PRA* (2005): From what I understand, PRA* (Partial Refinement A*) solves the same problem as HPA*, but in a different way.  They both have "similar performance characteristics."
HAA* (2008): HAA* (Hierarchical Annotated A*) is a generalization of HPA* that allows for restricted traversal of some units over some terrains (ex. a small pathway that some units can walk through but larger ones can't; or a hole that only flying units can cross; etc.)

Other/Unknown

LPA (1997): LPA (Loop-free path-finding algorithm) appears to be a routing-algorithm only marginally related to the problems the other algorithms here solve.  I only mention it because this paper is confusingly (and incorrectly) referenced on several places on the Internet as the paper introducing LPA*, which it is not.
LEARCH (2009):  LEARCH is a combination of machine-learning algorithms, used to teach robots how to find near-optimal paths on their own.  The authors suggest combining LEARCH with Field D* for better results.
BDDD* (2009): ??? I cannot access the paper.
SetA* (2002): ??? This is, apparently, a variant of A* that searches over the "binary decision diagram" (BDD) model of the graph?  They claim that it runs "several orders of magnitude faster than A*" in some cases.  However, if I'm understanding correctly, those cases are when each node on the graph has many edges?

Given all this, it appears that LPA* is the best fit for my problem.


Time complexity analysis for Reingold's UST-CONN algorithm What is the exact time complexity of the undirected st-connectivity log-space algorithm by Omer Reingold ?

It seems that the time complexity of Reingold's algorithm is not treated in either the Reingold's paper or in Arora-Barak textbook. It would also appear that the analysis is rather tedious, as the time complexity depends on the exact expander graph used in the construction and on some constants that are chosen to "sufficiently large".

To get some rough idea on the time complexity, observe that Reingold's algorithm, given graph $G$, transforms it (implicitly) into an expander graph $G'$ and traverses every walk of length $l = O(\log n)$. The $O$-notation hides some quite large constants here. The graph $G'$ has constant degree of $d = 2^b$ for some sufficiently large $b$, meaning that there are $d^l = O(n^c)$ such walks for some rather large constant $c$. Skimming some lecture notes on the topic it would seem that $c \ge 10^9b$.


Historic Relationship between Typed Lambda Calculus and Lisp? I was having a discussion with a friend recently (who is an advocate of strongly typed languages). He made the comment:

  The inventors of Lambda Calculus always intended it to be typed.

Now we can see that Church was associated with the Simply Typed Lambda Calculus. Indeed, it seems he explained the Simply Typed Lambda Calculus in order to reduce misunderstanding about the Lambda Calculus.

Now when John McCarthy created Lisp - he based it on the Lambda Calculus. This is by his own admission when he published "Recursive functions of symbolic expressions and their computation by machine, Part I". You can read it here.

McCarthy appears not to have addressed the Simply Typed Lambda Calculus. This seems to be dominated by Robyn Milner with ML.

There is some discussion of the relationship between Lisp and Lambda Calculus here, but they don't really get to the bottom of why McCarthy chose to leave it untyped.

My question is - If McCarthy admits he knew about Lambda Calculus - why did he ignore the Typed Lambda calculus? (ie - is it truly obvious that Lambda Calculus was intended to be typed? It doesn't seem that way)

First, your friend is wrong about the history of the $\lambda$-calculus. Church created the untyped calculus first, which he intended as a foundation for mathematics. Fairly quickly, it was discovered that the logic derived from this calculus was inconsistent (because non-terminating programs existed).  Eventually Church developed the simple theory of types as well, and many other things besides, but that wasn't the original point of the system.

An excellent overview of the history is found in this paper.

Second, the simply-typed lambda calculus is a quite restrictive language. You need some form of recursive type to write any interesting kind of program in it. Certainly, it would be impossible to write the kinds of programs in McCarthy's original paper with the $\lambda$-calculi based type systems understood in 1958. Cutting-edge programming type systems at that point were the ones found in Fortran and COBOL.


Support Vector Machines What is it the relationship between the number of support vectors in an SVM and its generalization ability?  When lots of support vectors are used to classify, is the error rate minimized, but only to certain threashold?

The answer to your question is a bit tricky and here are good lecture notes to read to understand the various generalization error bounds. Let me try to summarize what's happening with SVMs and their generalization.  These PAC bounds are also found in "An Introduction to Support Vector Machines: And Other Kernel-Based Learning Methods" by
Cristianini and John Shawe-Taylor.

Assuming a linear classifier correctly classifies all training examples (separable case), one bound (Vapnik '95 (I think)) on the generalization error of a linear classifier is (ignoring log factors):
$$
\epsilon = \tilde{O}\left(\frac{1}{n}\left( \frac{R^2}{\gamma^2} \right)\right),
$$
where $R$ is a bound on the size of the vectors, $n$ is the number of samples, and $\gamma$ is the margin, which is the distance to the support.  This bound says that the margin (the only quantity the learner has control over if the number of training examples are fixed), is an important quantity to maximize in SVM.

However, there is an intuition the margin is maximized in sparse solutions, and the sparseness of a solution is measured by the number of support vectors, so there is a relationship between the generalization bound and the quantity you're interested in.

Another relevant bound for any classifier (not just the linear case) is the following "compression bound" (Littlestone and Warmuth '86), which basically says that if a classifier gets $n$ examples right but can be obtained by training it on just $m$ examples then you can bound its generalization error by
$$
\epsilon \approx \frac{m \log n}{n-m}.
$$
Here, you can think of $m$ as the number of support vectors.  This directly relates the number of support vectors to the generalization error.

These two bounds help explain the interplay between the margins, the number of support vectors, and the generalization ability of an SVM (in the separable case).  In the non-separable case where you do not classify all training examples correctly, you get slack variables, slightly messier bounds, etc.


Surveys on Network Coding I want to start learning about Network Coding:

http://en.wikipedia.org/wiki/Network_coding

Do you know any good survey (e.g. from IEEE Surveys and Tutorials) on the above subjects. I found some university courses on google but I'd like some recommendations from people who already read and know a good source.

Thanks
Vasilis

As per Suresh's request (he is the boss after all) I am making my comment above an answer.

Emina Soljanin at Alcatel-Lucent Labs works on network coding and content delivery networks. She has written survey articles on network coding. See her web page. ect.bell-labs.com/who/emina. You can also check out her papers on content delivery via network coding and other means on the ArXiv.

I also want to say that network coding is a topic of much interest to theoretical computer science - there are several papers in TCS on this topic.


Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree? Consider an connected undirected graph $G$ with $n$ vertices and maximum degree $\Delta$. Assume $G$ contains a maximum independent set of size $k$. Is there any relation between the chromatic number $\chi(G)$ and $k$? Say of the form $\chi(G)\le f(\Delta)\frac{n}{k}$ for some function $f$?

Obviously if $f(\Delta)=2\Delta$ then the bound holds.  However, I doubt this is what you meant.  Perhaps you meant $\chi(G) \leq f(\frac n k)$, in which case the answer is no, there is no such function.

Let $\alpha$ be the size of a maximum independent set in $G$.  Then it is easy to see that the fractional chromatic number satisfies the bound $\chi_f(G)\geq \frac n \alpha$.  One such example is the Kneser graph $K_{kb:b}$ for fixed integers $k$ and $b$.  This graph has fractional chromatic number $k = \frac n\alpha$, and chromatic number $(k-2)b+2$.  So for fixed $k$ and large $b$ the answer is no.

(See Section 3.1 of my thesis for more details. http://www.columbia.edu/~ak3074/papers/phdthesis-compact.pdf)


Algorithms for set packing There seems to be much work, for some NP-Hard problems, on developing fast exponential time exact algorithms (i.e., results of the form: Algorithm A solves problem $x$ in O(c^n) time, with c small). There seems to be a fair amount of work along these lines for some NP-hard problems (e.g., Measure and conquer: a simple $O(2^{0.288n})$ independent set algorithm. SODA’06) but I haven't been able to find similar work for the set packing problem. There seems to be similar work on some restrictions of the set packing problem (e.g., An $O^{*}(3.523^{k})$ Parameterized Algorithm for 3-Set Packing) but I haven't found any for the general set packing problem.

So my question is: What is the best time complexity for exactly solving the weighted set packing problem where there are $m$ sets drawn from a universe of $n$ elements?

I am also interested in the relationship between the number of sets and the size of the universe. For example, has there been algorithmic work on situations where $m$ is relatively large compared to $n$ (i.e., close to $2^n$)?

Indeed, set packing, partitioning, and covering have been studied in terms of exact algorithm running times.
 To address your last question, you can solve weighted set packing in $O(m2^n)$ time by dynamic programming across all subsets of $[n]$.
 Moreover, if your integer weights are bounded by $M$, you can solve it in $O(M2^n)$ time, even if $m$ is as large as $2^n$, see

http://dx.doi.org/10.1137/070683933

BTW, The parameterized result you list for $3$-sets is not the best known, see

http://arxiv.org/abs/1007.1161

for a state-of-the-art algorithm and a list of previous results on the problem.


VNP completeness of Permanent Can some one suggest a good source for VNP completeness of Permanent. I tried reading it from book on Algebraic complexity theory by Burgisser,clausen,shokrollahi,lickteig.
And What is the best known lower-bound on determinental complexity of $PERM_{n}$?

The place from which I had read the proof was Completeness and Reduction in Algebraic Complexity Theory by Peter Bürgisser (.ps). As for the determinental complexity of the permanent, the best lower bound known so far is $\Omega(n^2)$ by Mignon and Ressayre.


Covering a simple polygon with circles Suppose I have a simple polygon $S$ and an integer $k$.  What are some existing approaches for finding the smallest radius $r$ such that I can cover $S$ with $k$ circles of radius $r$?  How about if $r$ is fixed, and I want to minimize $k$?

Use the k-center clustering algorithm: see Section 4.2 in http://goo.gl/pLiEO.

One can get 1+eps approximation algorithm using sliding grids.

It is natural to assume the problem is NP-Hard because of the work by Feder and Greene.


Natural graph class with five excluded subgraphs? I'm interested in hereditary graph classes characterized by a small number of excluded subgraphs. There are some well-known graph classes that are characterized by three or four obstructions -- examples are threshold graphs, chain grapns and trivially perfect graphs. My question is: are there natural graph classes characterized by five obstructions? (No relation to the eponymous movie). It may be possible to obtain some by considering the P4-structure of the graph.

The "split-substitute" graphs are the graphs starting with a split graph and substituting any split graph into any node.
The forbidden induced subgraphs can be obtains from the forbidden induced subgraphs of split graphs (c4, C5, co-C4), but replacing the non-prime ones (c4 and co-c4) with their minimal prime extensions... (here primality is with respect with modular decomposition.)

So the 5 forbidden induced subgraphs are the C5, P5, co-P5, H6 and co-H6. This forms a self-complementary class which strictly contains the class of cographs.

See: http://webdocs.cs.ualberta.ca/~hayward/papers/p4comp.online.pdf

The maxibrittle graphs are the perfectly orderable graphs for which a vertex sequence defined only by the degrees will produce a perfect order (more specifically, the degree sequence defines a brittle ordering). These graphs have exactly 5 minimal forbidden induced subgraphs.


Intuition: Odd-cycle transversal in triangle-free graphs I conjecture that if $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle.

For more information, see the 1988 paper by Erdös et al., How to Make a Graph Bipartite.

Question 1: Is this conjecture true by your intuition?

Question 2: What is the complexity of counting the number of odd cycles in a graph? Is there any efficient algorithm to do that?

My intuition says it's probably true, and here's a matching lower bound (i.e. a graph of which you have to delete at least $\frac{n^2}{25}$ edges for it to become bipertite:

$G=(V_1\cup V_2\cup V_3\cup V_4\cup V_5, (V_1\times V_2) \cup (V_2\times V_3) \cup (V_3\times V_4) \cup (V_4\times V_5) \cup (V_5\times V_1))$
, $|V_1| = |V_2| = |V_3| = |V_4| = |V_5|$.

This graph is certainly triangle free, but if $x<\frac{n^2}{25}$ edges are to be deleted there will still exist a $C_5=v_1\to v_2\to v_3\to v_4\to v_5 \to v_1$  for some vertices $v_1\in V_1, v_2\in V_2, v_3\in V_3, v_4\in V_4, v_5\in V_5$.

As for the second question, it is well known that counting simple cycles of length $2k+1$ are $\#W[1]-hard$, with respect to $k$, and can't be computed in time $n^{o(k)}$ unless ETH fails.

There is, however, a possibility to approximate the number of such cycles in $O^*(2^{O(k)})$.


Generating points uniformly distributed over the SURFACE of a standard simplex I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices).

One way to efficiently generate points that are uniformly distributed over the ENTIRETY of the $k$-simplex is to generate samples of $k$ iid exponential random variables, $E_i$, $i\in \left[1,k\right]$, then normalize, and $\vec{X}=\frac{\left\langle E_1,E_2,\dots,E_k\right\rangle}{\sum_{i=1}^k E_i}$, will be uniformly distributed over the entire $k$-simplex.

My problem is that the probability that one of these points lands on the surface (i.e. at a vertex, or along a hyper-edge, or on hyper-face, etc.) is nearly $0$, so that in practice all of the points end up being in the INTERIOR of the $k$-simplex.

In an attempt to sample the SURFACE of the $k$-simplex I have considered each hyper-edge, hyper-face, etc. separately and generated uniformly distributed samples on each (since they are themselves lower dimensional simplices). However, the problem becomes computationally unfeasible as $k$ increases because the number of hyper-edges, hyper-faces, etc. blows up.

Does anyone know of a method to explicitly generate samples that are uniformly distributed over the SURFACE (or BOUNDARY) of a standard $k$-simplex?

I created an algorithm for that. for detail see
    http://www.sciencedirect.com/science/article/pii/0098300493900457

briefly speaking, you can use following recursive formula to generate:

x_1=1-R_1^{1/n-1}
x_k=(1-\sum_{i=1}^{k} x_i)(1-R_k^{1/n-k}),    k=2,…,n-1
x_n=1-\sum_{i=1}^{n-1} x_i

Best wishes


What is the standard name for the function which inflates a string by duplicating each of its characters? Given a string $s$ over some alphabet, I'd like to use the proper nomenclature/notation for the operation/function $f$ which inflates $s$ by independently duplicating each of its characters.

For instance:
$$ f(abc) = aabbcc$$
or, more generally, a second argument could be provided to specify the number of copies:
$$ f(xy,4) = xxxxyyyy$$

This should be embarassingly standard, so don't hesitate to shoot me in your response!
(on the other hand, it is always difficult to search for something you cannot name, but I wouldn't accept such a lame excuse from my students, so...)

As pointed out by Marcus Ritt, the correct name for this operation seems to be stutter.

As far as I could determine, it has mostly been used in the field of concurrency theory, where I could trace it back at least to Lamport's 1983 seminal paper on temporal logic.


Induction on all polynomial runtimes? Has there ever been a proof technique to show that a language isn't in $\mathrm{P}$, by showing inductively there isn't any $k$ for which the language is in $\mathrm{TIME}(n^k)$?

e.g.: $L\notin \mathrm{TIME}(n^0)$,

$L\notin \mathrm{TIME}(n^k)\rightarrow L\notin \mathrm{TIME}(n^{k+1})$,

$\therefore L\notin \mathrm{P}$.

Is something of the sort feasible? Has it been used?

Something like this is used in the definition of creative sets by Joseph and Young (1985). See the Wikipedia article on polynomial creativity. But their use is to concoct NP-hard sets with unusual properties (potential counterexamples to the Berman–Hartmanis conjecture rather than to say anything nontrivial about the complexity of any natural algorithmic problem.


Does diagonalization captures the essence of class separation ? I don't remember having seen a class separation not based on diagonalization and relativization results.  Diagonalization could still be used to separate remaining known classes, because non-relativizing arguments might still be used in the diagonalization conclusion, or in the diagonalized Turing machine construction.  Here are some related questions:

  Are there class separation proofs not based on diagonalization?

And if so

  Can we find a self-reference mechanism behind them ?

Further,

  does every class separation have a "canonical natural" proof (in an informal sense)?

If so, we should try to find non-relativizing arguments, rather than other proof schemes for open questions.

  Can every non-diagonal proof be rewritten into a diagonal one ?

Depends on how you formalize diagonalization. Kozen has a paper that shows any complexity class separation must be a diagonalization proof.


Concatenative binary lambda calculus/combinatory logic John Tromp defines a version of the lambda calculus that is encoded in binary:
https://tromp.github.io/cl/cl.html

a) Does there exist a concatenative version of this language (or its combinatory equivalent)?

b) Does there exist a concatenative version restricted to the primitive recursive functions (e.g. as per Combinators for the Primitive Recursive Functions)?

As per @cody's comment above, if we require only that "the concatenation of any two programs is a valid program" then I believe that Iota, Jot and Zot (semarch.linguistics.fas.nyu.edu/barker/Iota/zot.html) are examples of a).

However, IMO the more interesting question part of the question is b)...


List the $k$-faces of an $n$-dimensional simplex Suppose you are given an $n$-dimensional simplex

S = [ 0 1 ... n ]

which for the time being we think of as an ascending array of numbers from $0$ to $n$. Given $1 \leq k \leq n$, how can we enumerate the $k$-faces of S, i.e. the $k$-dimensional subsimplices? - In less geometric words, we want a complete and multiples-free list of all $k$-sized strictly ascending sequences of numbers between in $\{ 0, \dots , n \}$.

The straight-forward algorithm is to create the list of all $k$-sized tuples of numbers between $0$ and $n$, and pop out those that are not strictly ascending or contain duplicates. This can be done in space and time $O(n^3)$.

But can we do better? We do not impose restrictions on a particular ordering of the output.

See chapter 3 of Nijenhuis and Wilf, "Combinatorial Algorithms" (the entire book is available free online and despite its age contains many useful algorithms).


Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively? The standard problem 1-in-3 SAT (or XSAT or X3SAT) is:
Instance: a CNF formula with every clause containing exactly 3 literals
Question: is there a satisfying assignment setting precisely 1 literal per clause true?

The problem is NP-complete and remains hard even if no variable occurs negated. I wonder whether this problem becomes easy or remains hard if each variable is required to occur at least once positively and at least once negatively.

The usual reduction from 3SAT showing that 1-in-3 SAT is hard replaces a clause $(x\lor y \lor z)$ by clauses $(\lnot x \lor a \lor b)$, $(y\lor b\lor c)$, $(\lnot z \lor c \lor d)$ where $a,b,c,d$ are fresh for each clause. Thus, this reduction doesn't help in answering my question. I've had trouble coming up with a gadget showing hardness of this variant, since if exactly 1 literal in a clause is true, then non-symmetrically 2 literals are false. If it turns out to be easy, thinking in terms of partitions of the clause set might do it, but I can't see how.

In a comment, OP expressed interest in a reduction which generated instances with 3 distinct variables per clause. Here's a simple approach:

The reduction is from 1-in-3 SAT with 3 distinct variables per clause:

First of all, include all the clauses in the input formula as clauses in the output formula.
Second, introduce three new variables $F_1$, $F_2$, and $F_3$ and add the following three clauses to the output formula: $(\neg F_1, F_2, F_3)$, $(F_1, \neg F_2, F_3)$, and $(F_1, F_2, \neg F_3)$.
Finally, for each variable $x$ in the original formula, introduce a new variable $x'$, and add the following two clauses to the output formula: $(x, x', F_1)$ and $(\neg x, \neg x', F_1)$.

Let's verify that this reduction does what we want. The following properties are what we want:

Each clause always has three distinct variables.
Each variable occurs in some clause positively and in some clause negatively.
The input formula is equivalent to the output formula.

Property 1 is trivial to check. Property 2 is also easy to check: the variables $F_1$, $F_2$, and $F_3$ each occur both positively and negatively in the clauses added in the second bullet point, while every other variable in the formula occurs both positively and negatively in the clauses added in the third bullet point.

As for property 3, this is less trivial but still easy. You can easily argue that the only assignment for variables $F_1$, $F_2$, and $F_3$ that satisfies each clause from the second bullet point is to make all three $F_i$s false. But then assuming a value of false for $F_1$, the clauses $(x, x', F_1)$ and $(\neg x, \neg x', F_1)$ added in the third bullet point are satisfied if and only if $x' = \neg x$. Since there are no other constraints on $x'$, this means that it is always possible to extend a satisfying assignment for the input formula into a satisfying assignment for the output formula: simply set each $x'$ to be the negation of the corresponding $x$ and set each $F_i$ to false.


Ecology and evolution through the algorithmic lens The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very discrete nature (see for example SLBS00) and could benefit from a computer science perspective. Yet, I am aware of only a few serious results from TCS that try to touch on specific questions in ecology and evolution. The two directions that spring to mind are:

Livnat, A., Papadimitriou, C., Dusho, J., & Feldman, M.W. [2008] "A mixability theory for the role of sex in evolution" PNAS 105(50): 19803-19808. [pdf]

Valiant, L.G. [2009] "Evolvability" Journal of the ACM 56(1): 3.

The former applies idea from analysis of genetic algorithms to show a qualitative difference between the way sexual and asexual organisms behave in fitness landscapes, and has lead to follow ups that help justify observed modularity. The latter connects evolution and computational learning theory, to try to prove evolvability and impositibility results. It has influenced a small collection of papers, but mostly by other computer scientists.
Are there more results in these veins? Are their other deep/non-trivial applications of theoretical computer science to understanding ecology and evolution as it is studied by biologists?

Notes

I am not interested in general engineering related genetic or evolutionary algorithms results. Although this is a very interesting and exciting part of computer science, its connection to evolution as studied by biologists is often superficial. Sometimes (as in LPDF08) concrete connections are made, but most standard results are not of biological interest, and hence I am not interested in them in this post.

Bioinformatics is a nearby field, but it is also not what I am looking for. Although it can be used to reconstruct things like phylogenetic trees and thus help evolution/ecology, the theoretical CS aspects do not take centre stage. Here, the CS results seem to be mostly to perfect a tool that can be used largely as a black-box from within existing well established theories, and not to build or extend new biological theories.

I prefer results that use modern-ish and non-trivial aspects of computer science to influence biology at a theoretic (but still relevant to biologists) level. As such, I am not that interested in things like Chaitin's metabiology.

Related questions

Provable statements about genetic algorithms

Algorithmic lens in the social sciences

Sources for Algorithmic Evolutionary Game Theory

Computational complexity in quantitative finance

Hmmm. As far as evolutionary dynamics/game theory goes, my personal opinion is that the Livnat et al paper you mentioned, while very nice work, doesn't seem to fall "outside" the standard mathematical approach to evolutionary game theory (see work by e.g. Martin Nowak's group, such as the '05 paper "Evolutionary Dynamics on Graphs").

So the two claims I would make are: First, while this is some great work in Evolutionary Dynamics that happens to be done by computer scientists, I would not personally place it inside Theoretical Computer Science or as being all that closely related to TCS, except for the preexisting relationship between evolutionary and algorithmic game theory. Second, if you're inclined to disagree, then you may be surprised how much the field of Evolutionary Dynamics already shares/shared with TCS philosophically (but I'm still not sure the techniques are that similar).

In general, I would be inclined to say that there is not any work along these lines, including the reference you mentioned, that fit what you seem to be looking for, which I think is a deep connection between some core concept/technique in TCS and the study of evolution. (Of course, if anyone has a differing opinion, please say so!)

I do think that evolutionary game theory or evolutionary dynamics could benefit from more algorithic approaches, (such as Livnat et al). For a particular example, I see possible nice extensions for considering evolvable agents with (limited) computional abilities, as modeled by e.g. finite state machines. This would allow us to study the evolution of discrete agents with more complex conditional strategies such as tit-for-tat. I've looked into this a bit and heard of some preliminary work along these lines but don't have any references to cite.

But even this example is a rather straightforward application, so results of this sort probably still wouldn't answer your question.

I have much higher hopes on the other hand for learning theory, which could someday make nice connections to evolutionary dynamics as well. But, I'm not very familiar with those results so I will leave that for others to comment on.

(Edit) One potential connection that should be mentioned is the known relationship of learning (e.g. the "expert's problem") and convergence to equilibria in repeated games. Specifically, for example (see Aaron Roth's comment for details), in a repeated game, if all players are playing no-regret strategies, then the past distribution of actions converges to a coarse correlated equilibrium of the single-round game. There may be something interesting and novel to say about this as viewed through the evolutionary game theory lens; I'm not sure.


Rearranging strings to minimise storage in a trie I'm currently thinking about the following problem.

Problem

Input: a set $W$ of strings over an alphabet $\Sigma$.

Goal: permute the characters in each string so that the trie that will contain the rearranged strings has as few edges as possible.

(by "permuting" and "rearranging", I mean that any permutation of the characters is valid).

Example

Given strings $S=$"ABRACADABRA" and $T=$"BARRACUDA", storing them without rearrangement would require a trie of size 20, since they share no common prefix; however, if we are allowed to rearrange them, we can obtain the following optimal solution of size 12:

0-A-B-R-A-C-A-D-R-A-B-A (S')
                 \
                  U     (T')

(where 0 denotes the root, and $S'$ (resp. $T'$) is the rearranged $S$ (resp. $T$)).

Question(s)

Has this problem been studied before, and can you give me references? What is its complexity (for $|W|\geq 3$; the problem is easy otherwise)?

The problem I'm wondering about was tackled long ago (1977) by Douglas Comer and Ravi Sethi, in a paper entitled "The Complexity of Trie Index Construction". They show that the decision version of the above problem, as well as three other variants, are NP-complete.


Lower bounds for Nondeterministic Multiparty Communication This is a continuation of my previous question on communication lower bounds for partial boolean functions.

Can someone suggest any reference on lower bounds for nondeterministic multiparty communication? I've been surveying the papers in the field, but everybody seems to show separations of the following type: a lower bound for randomized protocol and an (smaller) upper bound for a nondeterministic protocol. See for example, David, Pitassi, and Viola 2009, Gavinsky and Sherstov 2010, Beame, David, Pitassi, and Woelfel 2010.

Specifically, I would like to know if there exists a norm (e.g. $\gamma_k$ for $k$ parties) that lower bounds nondeterministic multiparty communication in either the number-in-the-forehead or number-in-hand model.

After much reading, I've found the following paper

Troy Lee and Adi Shraibman. Disjointment is hard in the multi-party number-on-the-forehead model. In Proceedings of IEEE 23rd Annual Conference on Computational Complexity. June 22-26 2008.

The authors show that bounded error randomized communication is lower bounded by an approximate cylinder intersection norm $\mu_\alpha$ (cf. definition 5 in the paper).

  Theorem 6: Let M be a sign $k$-tensor, and $0\leq \epsilon<1/2$. Then $R_\epsilon^k(M)\geq \log(\mu^\alpha(M))-\log(\alpha_\epsilon)$ where $\alpha_\epsilon=1/(1-2\epsilon)$ and $\alpha\geq\alpha_\epsilon$.

Then, they make the following remark.

  Remark 7: It is nice to note that since a non-deterministic protocol induces a covering of the tensor with cylinder intersections, it follows that $\log\mu^\infty$ is a lower bound on non-deterministic communication complexity.

This answers my question. The problem now is when $\alpha\to\infty$ the authors show that for any given sign matrix $M$, $\mu^\infty(M)=1/Disc(M)$, where $Disc(M)$ is the discrepancy of $M$. It is a problem because the best lower bounds we can prove using discrepancy are polylogarithmic in the size of the input. For example, for disjointment with $k$ parties the lower bound is $\Omega(\log n/(k-1))$. In the same piece of work, the authors show that for randomized protocols, disjointment requires $\Omega(\frac{n^{1/(k+1)}}{2^{2^k}})$ using the $\mu^\alpha$ norm.

Is there any other norm stronger than discrepancy that can be used for lower bounds in nondeterministic multiparty communication? Or is it tight? These results are very recent, so maybe this is an open problem. The follow-up to this question is here.


Lattice-based algorithms in practice Are there any applications of lattice-based algorithms other than those in cryptography and integer programming?

Could someone state a few papers where
the primary algorithms use lattice-based LLL algorithms?

If you look at the original paper by Lenstra, Lenstra, and Lovasz, you will see the following applications:

factoring univariate polynomials over the rationals (the motivation for developing LLL basis reduction)
efficient version of Dirichlet's classical diophantine approximation theorem: for rationals $a_1, \ldots, a_n$ and $\epsilon$, find in polynomial time integers $p_1, \ldots, p_n$, and $q$ such that

$$
\forall 1 \leq i \leq n: |qa_i - p_i| < \epsilon,
$$

and $q< 2^{n(n+1)/4}\epsilon^{-n}.$ Dirichlet proved this without the $2^{n(n+1)/4}$ factor, but his proof is a pigeonhole argument (sometimes called Dirichlet's principle) and does not yield an efficient algorithm.

efficiently find integer relations between rationals: given rationals $a_1, \ldots, a_n$ find integers $m_1, \ldots, m_n$ such that $\sum{m_i a_i}$ is minimized and the $m_i$ are not too large.

You can also check out Oded Regev's lecture notes which reference more applications. This book chapter by Hanrot gives details about quite a few applications of LLL to constructive versions of results in diophantine approximation.


Is there a linear space lower bound for streaming set equality? Consider two streams. In each stream one string arrives at a time.  A query asks: Is the set of strings that has arrived so far the same in both streams?

  Is there a linear space randomized lower bound for this problem?

If the sets of strings had been given in advance we could just sort them, remove duplicates, concatenate them in each set and then compute a random fingerprint of each of the two concatenated strings which can then be compared quickly using very little space (although there is of course no benefit as we first created something of linear size).

In the streaming case, we would need an updatable fingerprint it seems to do something similar.  I suspect this is not possible to do in sublinear space but I don't see a proof yet.

There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and check-outs in the other, but that makes little difference) in my paper

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011.
(and WADS 2007).

See also:

What's the difference? Efficient set reconciliation without prior context.
D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese.
Proc. ACM SIGCOMM, Toronto, Canada, 2011.

which is more explicitly about comparing two sets.

In short: you can test whether two multisets (or sets with no repetitions) are the same using only very small space, or more generally find their symmetric difference in space roughly proportional to the size of the difference.

If you really mean sets, where repetitions are allowed, I think the problem may be much harder, though I don't know of a randomized lower bound for it.


Conditional entropy: $H(X | Y)$ large implies $H(X | Y, X \neq Y)$ large? Suppose that $X$ and $Y$ are two random variables that are defined on the same support. Furthermore, suppose that $H(X | Y) = \log n$ for some $n$. I am now interested in how much the term $H(X | Y, X \neq Y)$ may differ from $H(X | Y)$.

Suppose that $X|Y=y$ is uniformly distributed (for every y). Intuitively, as $H(X | Y) = \log n$, for a typical element $y$ in the support of $X$ and $Y$, we also have $H(X | Y=y) = \log n$. Thinking about a uniform distribution, X takes on at least n different values, and, therefore, we should expect $H(X | Y, X \neq Y) \ge \log(n-1)$ as the conditioning on $X \neq Y$ eliminates only a single potential element.

Can such a result be obtained in full generality?

Thanks very much for your answers. I am new to stackexchange so I don't know yet where and how to respond to suggested answers.

The fact that you can bound $H(X|Y) - H(X|Y, X \neq Y) \le \log(\frac{n}{n-1})$ is very interesting, as you can compute:
$\log(\frac{n}{n-1}) = \log( \frac{1}{1-\frac{1}{n}} ) = - \log(1-\frac{1}{n}) = -\Theta(\log(e^{-\frac{1}{n}})) = \Theta(\frac{1}{n})$. This result matches the intuition very well as if the entropy $H(X|Y) = \log(n)$ then knowing that $H(X|Y, X \neq Y)$ essentially eliminates only one possible choice for $X$. This is somehow quantified by the $\Theta(\frac{1}{n})$.

This might be a partial answer to your question:

Let $X$ and $Y$ be random variables with the same range. Let $Z$ be the indicator of the event $X \ne Y$. By the chain rule,
$$H(X|Y,Z) = H(X,Z|Y)-H(Z|Y).$$
Since $Z$ is determined by $X$ and $Y$, we have $H(X,Z|Y)=H(X|Y)$. Now, by the definition of conditional entropy, $$H(X|Y,Z) = \underset{z \leftarrow Z}{\mathbb{E}}[H(X|Y,Z=z)] = \mathbb{P}[X \ne Y] \cdot H(X|Y, X \ne Y) + \mathbb{P}[X = Y] \cdot H(X|Y, X = Y).$$ Clearly $H(X|Y, X = Y)=0$. Combining the above gives $$\mathbb{P}[X \ne Y] \cdot H(X|Y, X \ne Y) = H(X|Y) - H(Z|Y).$$
Now we have an equation linking the quantities we want. We have $$0 \leq H(Z|Y) \leq H(Z) = H_2(p) \leq 1,$$ where $p = \mathbb{P}[X \ne Y]$. In particular, $$p \cdot H(X|Y,X \ne Y) \leq H(X|Y) \leq p \cdot H(X|Y,X \ne Y) + H_2(p).$$


How bad can the greedy coloring (list color) for the c-chromatic number of graph be? c-chromatic number is defined in the paper Partitions of graphs into cographs. It asks for the minimum number of colors used to color vertices such that each color class is a cograph. Cograph is a P4-free graph, i.e., there is no induced path of length 3.

The paper denotes the c-chromatic number as $c(G)$ and proves that $c(G)\le \lceil \frac{1+\Delta}{2} \rceil$ in Remark 12 on page 4. The proof can be used to convert any coloring to a coloring of at most $\lceil \frac{1+\Delta}{2} \rceil$ colors, in polynomial time.

In the study of the classic graph coloring, i.e., the chromatic number $\chi(G)$, greedy coloring was discussed. The performance of greedy coloring is determined by the order of vertices. In the worst case, a graph needs $\frac{|V|}{2}$ colors while $\chi(G)=2$. This implies that the approximation ratio of greedy coloring is arbitrarily bad.

Similarly, when we are coloring graph into cographs, we can use the greedy coloring. Given a order of vertices, label each vertex with the smallest color ( assume colors are labeled as 1, 2, 3, ....) such that each color class is a cograph.

My question are :

what is the worst behavior of greedy coloring on cograph coloring?
Is it possible that the greedy coloring needs more than $\lceil \frac{1+\Delta}{2} \rceil$ colors?

nice question.
Consider the following construction: build k P3s numbered / ordered as 1-2-3 4-5-6 7-8-9, etc.
Now 1-2-3 all get colour R by the greedy scheme. Make 4,5,6 all adjacent to 3. Then 4,5,6 each get colour B. Now make vertices 7,8,9 adjacent to 3 and to 6, then they can't get colours R or B. They get Y.

Continue with 10-11-12, with 10,11,12 adjacent to 3,6,9. They cannot be coloured with R B Y, so they get G.

These 3k vertices will need k = n/3 colours. But note that c(G) is 2, since the set {3,6,9,12,etc} induce a clique, and the rest of the graph induces a perfect matching. So this shows that greedy colouring can still be arbitrarily bad for cograph colouring as well.

We can modify this construction to cut down the max degree as well... 4,5,6 are adjacent to 3, but make 7,8,9 still adjacent to 6 but now adjacent to 1 instead of 3. Then make 10,11,12 adjacent to 9, 4(instead of 6), and 3. And for future triplets, keep alternating which end-vertex of a prior P3 they join to. The resulting graph is probably not partitionable into 2 cographs anymore, but observe that 2,5,8,11,etc form an independent set and the rest is probably coverable with 2 more cographs, but I'm not quite sure. But I don't think this is important ... what is important here is that the max degree is low enough that the greedy colouring uses more than $\frac{1+\Delta}{2}$ colours (to answer your second question.)

Another interesting question to ask would be whether a "smarter" greedy colouring (such as LexBFS) would produce a constant-ratio approximation.


Gentle introduction to graph isomorphism for bounded valance graphs I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained here. But I found it too abstract. I would be thankful if anybody can suggest me some references of expository nature. I do not have strong background in group theory, so I would prefer papers which use group theory in a gentle way (my background is in CS).

The algorithm for bounded-degree graph isomorphism is so closely tied to (permutation) group theory that I doubt there is an introduction that uses groups "only gently." However, you might consult Paolo Codenotti's Ph.D. thesis for more complete background. He doesn't cover bounded-degree graph isomorphism exactly, but covers the tools needed for it (and the rest of the thesis is about bounded-rank hypergraphs, extending the best known algorithm for general graph isomorphism to the bounded-rank hypergraph case).

You may also find the book Group-Theoretic Algorithms and Graph Isomorphism useful, as it covers most of the background necessary (Chapter 2, "Basic Concepts", is 47 pages) and is a much more leisurely exposition than most of the published papers on the topic.


bin packing with overlapping objects I have $N$ bins with capacity $M$ and $k$ objects with size $s_i$. The goal is to pack these objects in the bins. Until now it is similar to the bin-packing problem. But the twist is that each object has a partial overlap with others. So while object 1 and 2 have sizes $s_1$ and $s_2$, when I put them in the same bin the filled space will be $s_1+s_2-O_{12}$ where $O_{12}\ge0$. Note that for 3 objects it is $s_1+s_2+s_3-O_{12}-O_{23}-O_{13}+O_{123}$

Is there any approximation algorithm like the ones for original bin-packing for this problem too?

Your problem is a generalization of the sharing-aware virtual machine colocation problem, and so hard to approximate.

Read this paper for more information:
Michael Sindelar, Ramesh K. Sitaraman, Prashant J. Shenoy: Sharing-aware algorithms for virtual machine colocation. SPAA 2011: 367-378


What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem? Let $X$ be the universe of elements, $F$ a collection of subsets $S \subseteq X$, each with an associated cost. The goal is to find a subcollection $C \subseteq F$ of minimum total cost which covers $X$.
GreedySetCover(X,F)
1 C ← ∅
2 U ← X
3 while U ≠ ∅
4     Find set S ∈ F \ C that minimizes α = cost(S) / |S ∩ U|
5     C ← C ∪ {S}
6     U ← U \ S
7 end while
8 return C

Let $N = |U|$ and $M = |F|$. Then, in the worst-case, all subsets $S \subseteq X$ have to be searched. In the first iteration we search $M$ sets, in the second iteration we search $M - 1$ sets and so on. The cost of computing $|S \cap U|$ is $O(N)$.
$$T(n) = N (M + (M - 1) + (M - 2) + \cdots + 2 + 1) = N M(M+1)/2 = O(N M^2)$$
I think this is correct. I am not sure how to approach the average case time complexity however.

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in this way is $O(n \log n)$.
The linear time algorithm for the unweighted case mentioned by Neal Young in a comment is basically the same thing, just using a bucket queue as the priority queue instead of a comparison-based priority queue.
As for average case, you haven't provided enough information to answer that. Average over what input distribution?