Is it NP-hard to play international draughts correctly? Is the following problem NP-hard?

  Given a board configuration for $n\times n$ international draughts, find a single legal move.

The corresponding problem for $n\times n$ American checkers (aka English draughts) is trivially solvable in polynomial time.  There are three major differences between these two games.

The first and most significant difference is the “flying king” rule.  In checkers, a king may jump over an adjacent opponent's piece into an empty square two steps away in any diagonal direction.  In international draughts, a king may jump over an opponent's piece an arbitrary distance away by moving an arbitrary distance along a diagonal.

As in checkers, the same piece can be used to capture a series of pieces in a single turn.  However, unlike checkers, captured pieces in international draughts are not removed until the entire sequence is over.  The capturing piece may jump over or land in the same empty square multiple times, but it may not jump over an opponent's piece more than once.

Finally, both checkers and international draughts have a forced capture rule: If you can capture an opponent's piece, you must.  However, the rules rules disagree when there are several options for multiple.  In checkers, you may choose any maximal sequence of captures; in other words, you can choose any capture sequence that ends when the capturing piece cannot capture any more.  In international draughts, you must choose the longest sequence of captures.  Thus, my problem is equivalent to the following:

  Given a board configuration for $n\times n$ international draughts, find a move that captures the maximum number of opposing pieces.

It would suffice to prove that the following problem is NP-complete.  (It's obviously in NP.)

  Given a board configuration for $n\times n$ international draughts involving only kings, can (and therefore must) one player capture all her opponent's pieces in a single turn?

The corresponding checkers problem can be answered in polynomial time; this is an entertaining homework exercise.  The problem looks more similar to Demaine, Demaine, and Eppstein's analysis of Phutball endgames; a solution to the entertaining homework exercise appears at the end of their paper.  A solution also appears in the FOCS 1978 paper by Frankel et al. that proves that playing checkers optimally is PSPACE-hard; see also Robson's 1984 proof that checkers is actually EXPTIME-complete.

OK, here's the reduction. Turns out you don't need planarity after all. Also, for "find a legal move", I take the decision question as "is move X legal?".

First, let's work instead with a game where pieces move orthogonally instead of diagonally. This game is equivalent (just look at the draughts board rotated 45 degrees) except for edge properties, which we will not use. We use two gadgets: merge / split and crossover. See http://www.hearn.to/draughts.pdf. We assume there is a single White king on the board to move. (No other piece will be able to capture any significant number of pieces.) It will move through the indicated corridors, capturing black pieces along the way.

First, merge: if the king enters on any of the N paths A (via capturing a black piece, not shown), it can exit at B. Likewise, if we reverse the gadget and it enters at B, capturing the shown piece, it can exit along any path A (again, capturing an external black piece). This is a single-use gadget (because the exit black piece can be captured only once).

Second, crossover. If the king enters via A (C), it can exit at B (D). It can't stop in the middle and change routes, because that would be a non-capturing move segment.

Now, given a directed graph, construct a corresponding game configuration as follows. For each vertex, construct a merge which feeds into a split. Route the split outputs to the merge inputs of the vertex gadgets (merge + split) corresponding to the vertices the exiting edges connect to, using crossovers as necessary. Start the king on an extra input to any vertex (with a black piece to capture to let it enter the vertex).

Finally, equalize all of the "edge lengths" by adding extra black pieces along the output / input pathways as needed. If there are V vertices, and k black pieces along each edge, then the king can capture 2V + kV + 1 pieces if and only if there  is a Hamiltonian circuit of the corresponding graph. If the king has an alternative move available, capturing a simple chain of 2V + kV pieces, then determining whether that alternative move is legal is NP-complete.


Ant colony optimization for traveling salesman problem with changing graph-nodes/vertices Are there any publications focusing on solving TSP with ant colony optimization that consider small changes in the graph's nodes or vertices?

So what I have is:

a traveling salesman problem (TSP)
and a single solution for the TSP
a slight change in the graph afterwards (extra/removed node for example)

and what I want is:

An ant algorithm to solve the new TSP (on a subset-basis) using the original solution
And a benchmark

Thanks for you help so far.

Yes, there are several papers on this topic, and related ones, in the context of ant colony optimization algorithms for routing on ad hoc or mobile area networks (MANETs).  In a MANET, the nodes in the network graph are mobile, and if they move too far away from their neighbors, they fall out of range, hence the communication link is broken (i.e., the edge disappears from the network graph).  The routing problem essentially is: how do I keep all the vertices connected, and maintain efficient pathways between nodes, when links can disappear and reappear?  Of course, if a node moves out of range from all other nodes, it is the same as if the node were deleted from the network graph.

The paper An ant colony optimization routing based on robustness for ad hoc networks with GPSs  by Kadono et al. contains a "related work" section you will probably find interesting.  In this paper I've linked, there is an assumption of the availability of some GPS information, which probably does not apply to you; I chose it mainly for its discussion of other papers.  However, all these approaches assume something about how nodes can be deleted (or suddenly appear), in order to construct an efficient algorithm.  You'll have to decide what formal assumptions hold for the problem you are trying to solve.

Search phrases like "ant colony optimization MANET" or "ant colony optimization self-stabilization" may turn up other papers of interest to you.


Quantum Computation - Postulates of QM I have just started (independent) learning about quantum computation in general from Nielsen-Chuang book.

I wanted to ask if anyone could try finding time to help me with whats going on with the measurement postulate of quantum mechanics. I mean, I am not trying to question the postulate; its just that I do not get how the value of the state  of the system after measurement comes out to $M_m/\sqrt{ <\psi|M_m^+ M_m|\psi> }$.

Even though its just what the postulate seems to say, I find it really awkward that why is it this expression. I do not know if what I ask here makes sense, but this is proving to be something which for some reason seems to block me from reading any further,

I don't know if this is an "explanation", but hopefully it is a useful "description".

More generally than projective measurements, one always measures an operator. (A projector is a special case of this.) So what does it mean to "measure an operator"?

Well, operators often correspond to 'observable' physical quantities. The most important in quantum mechanics, for instance, is energy; but one can also (sometimes indirectly) measure other quantities, such as angular momentum, z-components of magnetic fields, etc. What is being measured always gives real-valued results --- in principle, some definite result (e.g. an electron is in the  'spin +1/2' state as opposed to 'spin −1/2', or in the first excited energy level as opposed to the ground-state in a hydrogen atom, etc.), albeit each a priori possible result is realized with some probability.

We assign each of the real-valued outcomes of a measurement to a subspace. The way we do this is to describe a Hermitian operator --- i.e. an operator which associates a real eigenvalue to different subspaces, with the subspaces summing up to the whole Hilbert space. A projector is such an operator, where the real values are 0 and 1; i.e. describing that a vector belongs to a designated subspace (yielding a value of 1), or its orthocomplement (yielding a value of 0). These Hermitian operators are observables, and the eigenspaces are those for which the observable has a "definite" value.

But what about those vectors which are not eigenvectors, and do not have "definite" values for these observables? Here is the non-explaining part of the description: we project them into one of the eigenspaces, to obtain an eigenvector with a well-defined value. Which projection we apply is determined at random. The probability distribution is given by the familiar Born rule:

$$ \Pr\limits_{|\psi\rangle}\bigl( E = c \bigr) \;=\; \langle \psi | \Pi_c | \psi \rangle \;, $$

where $\Pi_c$ is the projector onto the c-eigenspace of an 'observable quantity' E (represented by a Hermitian operator $A = \sum_c \; c \cdot \Pi_c$). The post-measured state is some projection of the state $|\psi\rangle$ onto some eigenspace of the observable A. And so if $| \psi_0 \rangle$ is the pre-measurement state, $| \psi_1 \rangle$ is the post-measurement state, and $\Pi_c$ is the 'actual result' measured (i.e. the eigenspace onto which the pre-measurement state was actually projected), we have the proportionality result

$$ | \psi_1 \rangle \;\propto\; \Pi_c | \psi_0 \rangle $$

by the projection rule just described. This is why there is the projector in your formula.

In general, the vector $| \psi'_1 \rangle = \Pi_c | \psi_0 \rangle$ is not a unit vector; because we wish to describe the post-measurement state by another unit vector, we must rescale it by

$$ \|\;|\psi'_1\rangle\;\| = \sqrt{\langle \psi'_1 | \psi'_1 \rangle} = \sqrt{\langle \psi_0 | \Pi_c | \psi_0 \rangle} \;,$$

which is the square-root of the probability with which the result would occur a priori. And so, we recover the formula in your question,

$$ | \psi_1 \rangle \;=\; \frac{\Pi_c | \psi_0 \rangle}{ \sqrt{ \langle \psi_0 | \Pi_c | \psi_0 \rangle }} \;.$$

(If this formula seems slightly clumsy, take heart that it looks and feels a little bit better if you represent quantum states by density operators.)

Edited to add: the above should not be construed as a description of POVMs. A "positive operator valued measurement" is better seen as describing the expectation value of various measurable observables Ec in a collection { Ec }c ∈ C .


Find all pairs of values that are close under Hamming distance I have a few million 32-bit values. For each value, I want to find all other values within a hamming distance of 5. In the naive approach, this requires $O(N^2)$ comparisons, which I want to avoid.

I realized that if I just treated these 32-bit values as integers and sorted the list once, then values which differed only in the least significant bits ended up very close together. This allows me to have a shorter "window" or range of numbers within which I can perform actual pair-wise comparisons for the exact hamming distance. However, when 2 values vary only in the higher order bits, then they end up outside this "window" and appear in opposite ends of the sorted list. E.g.

11010010101001110001111001010110

01010010101001110001111001010110

would be very far apart, even though their hamming distance is 1. Since, the hamming distance between 2 values are preserved when both are rotated, I figured that by doing 32 left rotations and then sorting the list every time, it's likely that 2 values will end up close enough in the sorted list in at least one of them.

Although this approach is giving me good results, I'm struggling to formally establish the correctness of this approach.
Given that I'm looking for matching values having hamming distance $k$ or less, do I really need to do all 32 bit rotations? For e.g. if $k=1$ and my window size is 1000, I need to do at max 24 bit rotations because even if the stray bit appeared in any of the 8 lower order bits, the resulting numbers won't differ by more than 1000.

As stated, your approach is problematic, because if 2 bitmaps have evenly spaced differences then in any rotation, there will be differences on some high order bits.

You can generalized your approach by permuting the bit position in a more complex fashion. Indeed, if you select a random permutation of bits, then all differences between 2 bitmaps with distance $5$ will appear in the 16 low-order bits with probability better than $1/50$. So repeating a few hundred times you should find a very large proportion of your bitmap pairs. For each trial, the number of pairs to test (with the same 16 high bits) is close to $64\cdot N$ (for $N\approx 2^{22}$).

However, I would also try the following approach. Built a list of your bitmaps modified in at most 2 bit positions and sort this list. If there are collisions within this list, you have two bitmaps within distance $4$. Then enumerate all values of your initial bitmaps modified three positions and search them in the list to find pairs of bitmaps at distance $5$.
The memory cost of this approach requires storing $529\cdot N$ elements and the number of elements to search in the second phase is $4960\cdot N$.

Additional information:

The probability that $5$ differences are located in the $16$ low
order bit after a random permutation of the $32$ bit-positions is
just a quotient of two binomials:
$$ \frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217
$$
Construction of the lists, for each element in the original list, put in the augmented list: the element itself, all elements differing in one position and all elements differing in two positions (keeping the information about the original element). The number of copies for each element is $1+32+\binom{32}{2}=529.$ Any collision within this list (detected after sort) corresponds to two original element at distance at most $4$. Note that each pair can be detected several times so you will need to remove duplicates (but this was already the case with your initial algorithm).
For the final pass, it is preferable to prune the augmented list of elements to keep only those at exact distance $2$ from their original element. Then, for each original element, create the $\binom{32}{3}=4960$ elements at distance $3$ and search them within the augmented list. Once again, you need to remove duplicates since each pair is going to be detected $\binom{5}{3}=10$ times. [With extra care, you can probably anticipate/avoid most duplicates but I am not sure whether it is worth the effort.]


Quantum complexity of maximum inner product search Given two matrices $X \in \mathbb{R}^{m \times k}$, $Y \in \mathbb{R}^{n \times k}$, maximum inner product search (MIPS) asks for the largest $l$ entries of $X Y^T$.  Typically $k \ll m, n$ (many small dot products).  In the approximate version, we ask for entries within a factor $\alpha < 1$ of the true largest.

Unfortunately, Ahle et al. show that an approximate solution to MIPS in subquadratic time $O(k^{O(1)} (mn)^{1-\epsilon})$ for $\epsilon > 0$ would contradict the strong exponential time hypothesis.  Terminology note: Ahle et al. calls it inner product similarity join (IPS) instead of MIPS.

Ahle et al. consider only classical complexity.  However, it is easy to beat the subquadratic limit using a quantum computer: applying Grover to the $m \times n$ search space gives $\tilde{O}(k \sqrt{m n})$ for $l = 1$.

Question: Is $\tilde{O}(k \sqrt{m n})$ the right quantum complexity for $l = 1$?  What about for larger $l \ll m, n$?

I think the quantum complexity is right for $l=1$, if a quantum oracle $O$ that can compute the inner product of any two row vectors from $X$ and $Y$, namely, $O: |i\rangle|j\rangle|0\rangle \rightarrow |i\rangle|j\rangle|X_i\cdot X_j\rangle$, is provided. Computing the inner product of two $k$-length vectors requires time $\mathcal{O}(k)$. Based on this oracle, we can use the quantum algorithm for finding minimun to find maximum and the oracle complexity will scales as $\mathcal{O}(\sqrt{mn})$. Then the total time complexity will be $\mathcal{O}(k\sqrt{mn})$.

The above algorithm can be utilized to find $l$ largest entries of $XY^{T}$ in a successive manner. For example, finding the second largest entry is equivalent to finding the largest entry of the rest entries when we 'take' the true largest one away. Therefore, i think the quantum complexity for finding $l$ largest entries will be $\mathcal{O}(lk\sqrt{mn})$.


Formalizing Homotopy Type theory in Idris Looking at the homotopy type theory blog one can easily find a lot of library formalizing most of Homotopy Type Theory in Agda and Coq.

Is there anyone aware if there is any similar attempt to formalize HoTT in Idris?

Here is a small, incomplete, and inconsistent formalization of HoTT in Idris. It shows that you can derive a contradiction in Idris just by postulating univalence. There are two barriers to formalizing HoTT in Idris at the moment.

Barrier 1:
Idris has heterogeneous equality and heterogeneous equality rewriting. From the HoTT perspective this means we have access to the following rewriting principle, which is inconsistent with univalence:
$$
 \prod_{P \,:\, X \to \mathsf{Type}}\ \prod_{x\,:\,X}\ \prod_{p \,:\, x = x}\ \prod_{a,\,b \,:\, P\, x} (\mathsf{transport}\ P\ p\ a = b) \to (a = b)
$$
With this principle, we can easily prove True = False.

Barrier 2:
The pattern matching in Idris is too strong for HoTT, as Neel Krishnaswami suspected in a comment above. We can derive Streicher's K. This leads to uniqueness of identity proofs, and is therefore incompatible with univalence. We can once again show True = False.


Approximate 1d TSP with linear comparisons? The one-dimensional traveling salesperson path problem is, obviously, the same thing as sorting, and so can be solved exactly by comparisons in $O(n\log n)$ time, but it is formulated in such a way that approximation as well as exact solution makes sense. In a model of computation in which the inputs are real numbers, and rounding to integers is possible, it's easy to approximate to within a $1+O(n^{-c})$ factor, for any constant $c$, in time $O(n)$: find the min and max, round everything to a number within distance $(\max-\min)n^{-(c+1)}$ of its original value, and then use radix sort. But models with rounding have problematic complexity theory and this led me to wonder, what about weaker models of computation?

So, how accurately can the one-dimensional TSP be approximated, in a linear comparison tree model of computation (each comparison node tests the sign of a linear function of the input values), by an algorithm whose time complexity is $o(n\log n)$? The same rounding method allows any approximation ratio of the form $n^{1-o(1)}$ to be achieved (by using binary searches to do the rounding, and rounding much more coarsely to make it fast enough). But is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$?

EDIT (UPDATE): The lower bound in my answer below was proven (by a different proof) in "On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees", by Das et al; Algorithmica 19:447-460 (1997).

  is it possible to achieve even an approximation ratio like $O(n^{1-\epsilon})$ for some $\epsilon>0$ in $o(n\log n)$ time using a comparison-based algorithm?

No. Here's a lower bound.

Claim. For any $\epsilon>0$, every comparison-based
$n^{1-\epsilon}$-approximation algorithm
requires $\Omega(\epsilon n\log n)$ comparisons in the worst case.

By "comparison-based" I mean any algorithm that
only queries the input with binary (True/False) queries.

Here's an attempt at a proof. Hopefully there are no mistakes.
FWIW the lower bound seems likely to extend to randomized algorithms.

Fix any $n$ and any arbitrarily small but constant $\epsilon>0$.

Consider just the $n!$ "permutation" input instances
$(x_1,x_2,\ldots,x_n)$
that are permutations of $[n]$.
The optimum solution for any such instance has cost $n-1$.

Define the cost of a permutation $\pi$
to be $c(\pi) = \sum_i |\pi(i+1) - \pi(i)|$.
Model the algorithm as taking as input a permutation $\pi$,
outputting a permutation $\pi'$,
and paying cost $d(\pi,\pi') = c(\pi'\circ \pi)$.

Define $C$ to be the minimum number of comparisons
for any comparison-based algorithm to achieve
competitive ratio $n^{1-\epsilon}$ on these instances.
Since opt is $n-1$, the algorithm must guarantee cost at most $n^{2-\epsilon}$.

We will show $C\ge \Omega(\epsilon n\log n)$.

Define $P$ to be, for any possible output $\pi'$,
the fraction of possible inputs for which output $\pi'$
would achieve cost at most $n^{2-\epsilon}$.
This fraction is independent of $\pi'$.

$P$ also equals the probability that, for a random permutation $\pi$,
its cost $c(\pi)$ is at most $n^{2-\epsilon}$.
(To see why, take $\pi'$ to be the identity permutation $I$.
Then $P$ is the fraction of inputs for which
$d(\pi,I)$ at most $n^{2-\epsilon}$,
but $d(\pi,I) = c(\pi)$.)

Lemma 1. $C \ge \log_2 1/P$.

Proof. Fix any algorithm that always uses less than $\log_2 1/P$ comparisons.
The decision tree for the algorithm has depth less than $\log_2 1/P$,
so there are at less than $1/P$ leaves, and, for some output
permutation $\pi'$,  the algorithm gives $\pi'$ as output
for more than a $P$ fraction of the inputs.  By definition of $P$,
for at least one such input, the output $\pi'$ gives cost more than $n^{2-\epsilon}$.
QED

Lemma 2. $P \le \exp(-\Omega(\epsilon n\log n))$.

Before we give the proof of Lemma 2, note that the two lemmas together
give the claim:
$$C
~\ge~ \log_2 \frac{1}{P}
~=~ \log_2 \exp(\Omega(\epsilon n\log n))
~=~ \Omega(\epsilon n\log n).$$

Proof of Lemma 2.
Let $\pi$ be a random permutation.
Recall that $P$ equals the probability that
its cost $c(\pi)$ is at most $n^{2-\epsilon}$.
Say that any pair $(i,i+1)$ is an edge
with cost $|\pi(i+1)-\pi(i)|$,
so $c(\pi)$ is the sum of the edge costs.

Suppose $c(\pi) \le n^{2-\epsilon}$.

Then, for any $q>0$, at most $n^{2-\epsilon}/q$ of the edges have cost $q$ or more.
Say that edges of cost less than $q$ are cheap.

Fix $q=n^{1-\epsilon/2}$.  Substituting and simplifying, at most $n^{1-\epsilon/2}$ of the
edges are not cheap.

Thus, at least $n - n^{1-\epsilon/2} \ge n/2$ of the edges are cheap.
Thus, there is a set $S$ containing $n/2$ cheap edges.

Claim. For any given set $S$ of $n/2$ edges,
the probability that all edges in $S$ are cheap
is at most $\exp(-\Omega(\epsilon n \log n))$.

Before we prove the claim, note that it implies the lemma as follows.
By the claim, and the naive union bound,
the probability that any there exists such a set $S$
is at most
$${n\choose n/2} \exp(-\Omega(\epsilon n \log n))
~\le~ 2^n \exp(-\Omega(\epsilon n \log n))$$
$$~\le~ \exp(O(n) -\Omega(\epsilon n \log n))
~\le~ \exp(-\Omega(\epsilon n \log n)).$$

Proof of Claim.
Choose $\pi$ by the following process.
Choose $\pi(1)$ uniformly from $[n]$,
then choose $\pi(2)$ uniformly from $[n] - \{\pi(1)\}$,
then choose $\pi(3)$ uniformly from $[n]-\{\pi(1),\pi(2)\}$, etc.

Consider any edge $(i,i+1)$ in $S$.
Consider the time just after $\pi(i)$ has been chosen,
when $\pi(i+1)$ is about to be chosen.
Regardless of the first $i$ choices (for $\pi(j)$ for $j\le i$),
there are at least $n-i$ choices for $\pi(i+1)$,
and at most $2n^{1-\epsilon/2}$ of those choices will give the edge $(i,i+1)$
cost less than $n^{1-\epsilon/2}$ (making it cheap).

Thus, conditioned on the first $i$ choices,
the probability that the edge is cheap
is at most $\frac{2n^{1-\epsilon/2}}{n-i}$.
Thus, the probability that all $n/2$
edges in $S$ are cheap is at most
$$\prod_{(i,i+1)\in S} \frac{2n^{1-\epsilon/2}}{n-i}.$$
Since $|S|\ge n/2$, there are at least $n/4$ edges in $S$
with $n-i\ge n/4$. Thus, this product is at most
$$\big(\frac{2n^{1-\epsilon/2}}{n/4}\big)^{n/4}
~\le~(8n^{-\epsilon/2})^{n/4}
~=~\exp(O(n)-\Omega(\epsilon n \log n))
~=~\exp(-\Omega(\epsilon n \log n)).$$

QED


Composition of $FP$ and $\#P$ functions Let $f_i \in FP$ and $g_i \in \#P$ for $i \in \mathbb{N}$.
It is known that: $f_1(f_2(x)) \in FP$ and that $g_1(f_1(x)) \in \#P$.
Is it known whether or not $f_1(g_1(x)) \in \#P$ or maybe $f_1(g_1(x)) \in GapP$?

On Closure Properties of #P in the Context of PF ∘ #P

Note that FP and PF are the same complexity class. It is stated in proposition 2.1 on page 3 that FP ∘ #P = FP $^{\# P{ [1]}}$


Projective Plane of Order 12 Objective: Settle the conjecture that there is no projective plane of order 12.

In 1989, using computer search on a Cray, Lam proved that no projective plane of order 10 exists.  Now that God's Number for Rubik's Cube has been determined after just a few weeks of massive brute force search (plus clever math of symmetry), it seems to me that this longstanding open problem might be within reach.  (Plus maybe we could use such techniques to solve something mathematically fundamental.)  I'm hoping this question can serve as a sanity check.

The Cube was solved by reducing the total problem size to "only" 2,217,093,120 distinct tests, which could be run in parallel.

Questions:

There have been several special cases of nonexistence shown.  Does anyone know, if we remove those and exhaustively search the rest, if the problem size is on the order of the Cube search?  (Maybe to much to hope for that someone knows this....)
Any partial information in this vein?

Edited to add: I asked this question on MathOverflow here.  So far it seems as though no search space reduction is achieved from the known partial results.  I still don't know the size of the total search space.

(More a comment than answer:)

Finite projective planes exist for values of n which are powers of a prime, and there are infinitely many values of n which are ruled out by a theorem of R.H. Bruck and H. Ryser, which was generalized to block designs by Chowla:

http://en.wikipedia.org/wiki/Bruck%E2%80%93Chowla%E2%80%93Ryser_theorem

n = 10, as was stated, was solved (no plane exists) by a computer search so the first value of n not ruled out by Bruck-Ryser is n = 12. However, the computer work did not seem to give new insights as to whether or not there are only the prime power planes. What seems to be needed are new mathematical methods for insight into the commonly made conjecture that only the prime power planes exist.


Hardness jumps in computational complexity? Minimum bandwidth problem is to a find an ordering of graph nodes on integer line that minimizes the largest distance between any two adjacent nodes. A $k$-caterpillar is a tree formed from main path by growing edge-disjoint paths of length at most $k$ from its nodes ($k$ is called the hair length). Minimum Bandwidth problem is in $P$ for 2-caterpillars but it is $NP$-complete for 3-caterpillars.

Here is a very interesting fact, Minimum bandwidth problem is solvable in polynomial time for 1-caterpillars (hair length at most one) but it is $NP$-complete for cyclic 1-caterpillars (in cyclic caterpillar, one edge is added to connect the endpoints of the main path). So, the addition of exactly one edge makes the problem $NP$-complete.

  What is the most striking example of problem hardness jump where a small variation of input instance causes a complexity jump from polynomial-time solvability to $NP$-completeness?

One of the more interesting applied examples of hardness jumps can be observed in the following problem:

Consider a soccer league championship with $n$ teams: The problem of deciding whether a given team can (still) win the league is in $P$ if in a match, the winning team is awarded 2 points, the losing one 0 and each team is awarded 1 point in a draw match. But if we change the rules so that the winning team gets 3 points, the same problem becomes $NP$-hard.

The result can be generalized for any $(0, 1, k)$-point rule for every $k > 2$ and even for only three remaining rounds.

Source: “Complexity Theory” by Ingo Wegener (http://portal.acm.org/citation.cfm?id=1076319)


Why is $\{0,1\}^n$ referred to as the Boolean hypercube? I used to view it just as a set of bit strings of length $n$. What does it mean for it to be the Boolean hypercube? Does viewing it from the hypercube perspective give a useful insight in a certain context?

Strictly speaking, the "Boolean hypercube" is not the same as the set $\{0,1\}^n$. The Boolean hypercube is the graph whose vertices are the set $\{0,1\}^n$, and whose edges are defined as follows: two strings are adjacent if and only if they differ on exactly one bit.

I guess that usually, people refer to $\{0,1\}^n$ as the Boolean hypercube when they really want to think of it as a graph and not as a set of strings.


Approximating non-trivial graph automorphism? Graph automorphism is a permutation of graph nodes that induces a bijection on the edge set $E$. Formally, It is a permutation $f$ of nodes such  $(u,v)\in E$ iff $(f(u),f(v))\in E$

Define an violated edge for some permutation as an edge that is mapped to non-edge or an edge whose preimage is non-edge.

Input: A non-rigid graph $G(V, E)$

Problem: Find a (non-identity) permutation that minimizes the numbers of violated edges.

  What is the complexity of finding a (non-identity) permutation with minimum number of violated edges? Is the problem hard for graphs with bounded maximum degree $k$ (under some complexity assumption)? For instance, Is it hard for cubic graphs?

Motivation: The problem is a relaxation of graph automorphism problem (GA). The input graph may have non-trivial automorphism (e.g. non-rigid graph). How difficult is it to find an approximate automorphism (closet permutation)?

Edit April 22

A rigid (asymmetric) graph has only trivial automorphism. A non-rigid graph has some (limited) symmetry and I'd like to understand the complexity of approximating its symmetry.

I don't understand the motivation very well. However, let me provide an answer to a related question. In the property testing framework, you are given two graphs $G$ ad $H$ and wish to distinguish two cases based on parameter $\epsilon$:

$G$ and $H$ are isomorphic
Any bijection from $G$ to $H$ causes error on at least $\epsilon \binom{n}{2}$ edges.

The complexity metric is the number of probes to the adjacency matrices, and the goal is to distinguish the two cases with high probability using a sublinear number of probes.

Eldar Fischer and Arie Matsliah (thanks, arnab) have a paper in SODA 2006 on precisely this problem. While it doesn't directly connect to your problem, it may be a way to a possible problem formulation, and might even provide useful techniques for you.


Best SAT upper bounds based on number of clauses What's the best upper bounds based on number of clauses? In this question shown fastest algorithms for SAT, but there bounds depends from number of variables ( $O(const^n)$ where n is number of variables).

I know that variables bounds can be converted to clauses bounds. If k-SAT formula contains $m$ clauses then $n \leq \frac{k * m}{2}$, consequently if algorithm bounded by $O(const^n)$, it also bounded by $O(const^ \frac{k * m}{2}) = O((const^ \frac{k}{2})^m)$. In that way PPSZ for 3-SAT can be bounded by $O(1.496^m)$. But I'm interested in algorithms which bounds "natively" depends from number of clauses.

It's of the order 2^{0.30897m}, see http://logic.pdmi.ras.ru/~hirsch/abstracts/sodafull.html

(I am not aware of improvements for the number of clauses.)


Is there a local variant of TSP? I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take.

It's likely NP-hard, I was just wondering if there's a name for this or similar variants on TSP.

EDIT

Here's a clarification of the problem:

Let $S$ be a clique with weighted edges that one could put onto a plane (Euclidian distances, etc.) and $k$ be a positive real number.
A solution $G$ is a subgraph of $S$ that is a simple path such that $\Sigma_{e \in E(G)} e < k$ and $|V(G)|$ is maximized.

Or, in terms of geometry:

Let $S$ be a set of points on the plane
A solution is a path through some of the points of length less than $k$ that maximizes the number of points hit.

This is an "Orienteering problem" and is NP-hard [1]. If the starting vertex is given the problem is rooted; your variant is unrooted. Some authors call it the "selective travelling salesman" [2].

[1] B. L. Golden, L. Levy, and R. Vohra. "The orienteering problem". In: Naval Research Logistics 34.3 (1987), pp. 307-318.

[2] M. Gendreau, G. Laporte, and F. Semet. "A tabu search heuristic for the undirected selective travelling salesman problem". In: European Journal of Operational Research (1998), pp. 539-545.


A converse to Fano's inequality ? Fano's inequality can be stated in many forms, and one particularly useful one is due (with a minor modification) to Oded Regev:

  Let $X$ be a random variable, and let $Y = g(X)$ where $g(\cdot)$ is a random process. Assume the existence of a procedure $f$ that given $y = g(x)$ can reconstruct $x$ with probability $p$. Then
  $$ I(X; Y) \ge pH(X) − H(p)$$

In other words, if I can reconstruct, there's a lot of mutual information in the system.

Is there a "converse" to Fano's inequality: something of the form

  "Given a channel with sufficient mutual information, there is a procedure to reconstruct input from output with error that depends on the mutual information"

It would be too much to expect that this procedure would also be efficient, but it would also be interesting to see (natural) examples where the reconstruction exists but must be inefficient.

Consider the following reconstruction procedure $P(y)$: given $y$, output $x$ such that $\Pr[X = x \mid Y = y]$ is maximized. The probability that this procedure succeeds is $\max_x \Pr[x \mid Y = y]$. This is also $2^{-H_\infty(X | Y = y)}$, where $H_\infty(X \mid Y = y)$ is the min-entropy of the random variable $X$ conditioned on $Y = y$. We know that $H_\infty(X) \leq H_1(X)$, where $H_1(X)$ is the standard Shannon entropy of the random variable $X$. Now we just have to upper bound $H_\infty(X|Y = y)$ in terms of the mutual information $I(X:Y)$.

Write $I(X:Y) = H(X) - H(X|Y) = H(X) - \mathbb{E}_y[H(X \mid Y = y)]$. Using the inequality mentioned above, $I(X:Y) \leq H(X) - \mathbb{E}_y[H_\infty(X \mid Y = y)]$, or $\mathbb{E}_y[H_\infty(X \mid Y = y)] \leq H(X) - I(X:Y)$.

The probability that the procedure succeeds where $X$ and $Y$ are chosen randomly is $\mathbb{E}_y [2^{-H_\infty(X\mid Y = y)}]$, which by concavity is at least $2^{-\mathbb{E}_y[H_\infty(X \mid Y = y)]}$. Thus the probability the procedure succeeds is at least $2^{I(X:Y) - H(X)}$.

This procedure is optimal: given any randomness procedure $P$, the probability of success is $\mathbb{E}_y [ \sum_{x} \Pr(X = x \mid Y = y) \Pr(P(y) = x) ]$, which is maximized point-wise when $P(y)$ deterministically outputs the most likely $x$.


What is the best way to find an induced cycle basis of a graph? My question is essentially what comes in the subject line: what is the best way to find an induced cycle basis of a graph (i.e., a cycle basis of the graph in which each cycle is an induced subgraph of the original graph)?

I can think of the following naive approach:
Let $T$ be any spanning forest of $G$. Now repeat operation (a) until there are no two edges $e_1 = (u_1, v_1)$ and $e_2 = (u_2, v_2)$ so that $e_1, e_2 \in E(G) \setminus E(T)$ and the path in $T$ from $u_1$ to $v_1$ contains the path in $T$ from $u_2$ to $v_2$. Operation (a) adds edge $e_2$ to $T$ and removes one of the other edges in the path from $u_2$ to $v_2$ in $T$. Finally, construct the cycle basis of $G$ according to the resulting $T$.

Now, there are several things that I am interested in:

I believe the correctness of the algorithm above is intuitive but I might be wrong. Have I missed something?
Even if correct, the above algorithm is obviously very inefficient. Is there an efficient way to implement that idea?
Are there other efficient methods of finding an induced cycle basis of a graph?
Among different algorithms for doing that, are there any time/space trade-off that I should consider? I am willing to spend a little more on computation if it means smaller memory footprint.
The above algorithm only works for undirected graphs. What about directed ones?

Did you try searching Google scholar for "induced cycle basis"? There is not much, but the following reference seems to be relevant. It characterizes the graphs for which the set of all induced cycles forms a cycle basis, which I think is more restrictive than your question (you are allowing a proper subset of these cycles in your basis).

McKee, Terry A. (2000), Induced cycle structure and outerplanarity, Discrete Math. 223 (1–3): 387–392.

In any case I believe the following approach will work for your problem. Separately, within each biconnected component, do the following steps:

Start with an induced cycle
Repeatedly find an "ear" in an ear decomposition: a simple path that starts and ends in previously chosen cycles, and with each interior vertex not belonging to previous cycles. Choose the ear to be as short as possible (breaking ties by the distance between the path endpoints among edges in previous cycles) so that there is no shortcut edge from an interior vertex back to the set of previous cycles.
Connect the endpoints of the ear by a shortest path through the edges used in previous cycles, and add the resulting cycle to the decomposition.

By using shortest paths to choose each ear and to complete each ear to a cycle, the resulting cycles are all necessarily induced. They form a weakly fundamental set of cycles (each uses an edge not part of previous cycles) so they are independent, and they have the correct number of cycles to span the cycle space of the graph, so they are a cycle basis.
But unlike your approach (?) they are not a fundamental cycle basis: they do not come from a spanning tree of the graph.


Efficient synchronization of two instances of an ordered list What data structure or algorithm can be used to efficiently synchronize two nearly identical ordered lists? Two offline systems start with the same ordered list and each edit, insert, delete and move items in the list. Occasionally they will be online to synchronize the list. The algorithm should minimize the amount of changed items or "diffs" that need to be communicated.

For an unordered list we would simply use a modification timestamp and UUID for each item to detect edits respectively inserts/deletions. But what data structure can we use for an ordered list? Using an integer rank would require renumbering all successors after an insert, and thus result in many "diffs" when comparing items in both lists. Using a floating-point rank (having the average of the predecessor and successor ranks) would have accuracy problems after inserting many new items.

Using a doubly linked list (i.e. referencing the UUID of the predecessor and successor item) would result in two changed items and one new item for each insert, thus 3 "diffs" when comparing items in both lists.

Any suggestions, pointers to literature or Google search terms about this subject?

For synchronizing from a master list to a slave list, it looks like a fellow named Michael Heyeck has a good, O(n) solution to this problem. Check out that blog post for an explanation and some code. Perhaps this is a good starting point to generalize to a two-way sync.

Essentially, the solution tracks both the master and slave lists in a single pass, tracking indices into each. Two data structures are then managed: a list of insertions to be replayed on the slave list, and a list of deletions.

It looks straightforward and also has the benefit of a proof of minimalism, which Heyeck followed up with in a subsequent post. The code snippet in this post is more compact, as well:

def sync_ordered_list(a, b):
x = 0; y = 0; i = []; d = []
while (x < len(a)) or (y < len(b)):
    if y >= len(b): d.append(x); x += 1
    elif x >= len(a): i.append((y, b[y])); y += 1
    elif a[x] < b[y]: d.append(x); x += 1
    elif a[x] > b[y]: i.append((y, b[y])); y += 1
    else: x += 1; y += 1
return (i,d)

Again, credit to Michael Heyeck.


Space-time tradeoff and the best algorithm Consider some language $L$ such that:

$L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$

and so that

$L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$

In other words, the fastest machine $M$ computes $L$ in time $O(f(n))$ and the most space efficient machine $M'$ computes $L$ while using space $O(g(n))$.

What can be said about the space efficiency of M or the time efficiency of M'? Or more precisely, if $\mathbb{M}_T$ is the set of all machines that compute $L$ in $O(f(n))$ then what can we say about the most space efficient machine in $\mathbb{M}_T$? What about the same thing for the obvious space version: $\mathbb{M}_S$.

Alternatively, can $f(n)$ and $g(n)$ be used to define some good space-time tradeoffs? Under what conditions is $TS \in o(f(n)g(n))$ or more generally for some space-time tradeoff $h(T,S)$ under what conditions is $h(T,S) \in h(o(f(n)),o(g(n)))$.

The prototypical f and g here would probably be poly-time and polylog space.  The interesting problem here is connectivity (in directed graphs) which can be solved in polynomial time (using linear space) or in polylog space (using super-polynomial time).  It is a famous open problem whether it can be solved in TIME-SPACE(poly,polylog), a class known as SC.

I.e. your question is a well-known open problem.  I don't think that anything non-trivial is known here.


Nondeterminism is on average useless for circuits? Savický and Woods (The Number of Boolean Functions Computed by Formulas of a Given Size) prove the following result.

  Theorem[SW98]: For every constant $k>1$, almost all boolean functions with formula
  complexity at most $n^k$ have circuit complexity at least $n^k/k$.

The proof consists of deriving a lower bound on $B(n,n^k)$, the number of boolean functions on $n$ inputs computed by formulas of size $n^k$. By comparing $B(n,n^k)$ to the number of circuits of size $C = n^k/k$, which is at most $C^{C}e^{C+4n}$, it can be realized that for large $n$, $C^{C}e^{C+4n} << B(n,n^k)$, and the result follows.

It looks to me that the result could be strengthened by noting that the number of nondeterministic circuits of size $n^k$ with $m$ nondeterministic inputs is not much larger than the number of deterministic circuits of size $n^k$ (for $m$ not too large, say $m=n$). Hence, I think the following corollary holds:

  Corollary: For every constant $k>1$, almost all boolean functions with formula
  complexity at most $n^k$ have nondeterministic circuit complexity at least $n^k/k$ (for nondeterministic circuits with $n$ nondeterministic inputs).

(Recall that a nondeterministic circuit has, in addition to the ordinary inputs $x = (x_1,\dots,x_n)$, a set of "nondeterministic" inputs $y=(y_1,\dots,y_m)$. A nondeterministic circuit $C$ accepts input $x$ if there exists $y$ such that the circuit output $1$ on $(x,y)$).

Obviously, the lower bound on $B(n,n^k)$ is also a lower bound on the number of boolean functions on $n$ inputs computed by circuits of size $n^k$, hence "formula complexity at most $n^k$" can be replaced by "circuit complexity at most $n^k$" in the corollary. The corollary can also be stated as: for functions with polynomial circuit complexity, switching to nondeterministic circuits cannot, on average, decrease the complexity by more than a constant factor.

  Questions:

  (1) Are there any interesting implications/consequences of the corollary above?

  (2) Are there any other results in the same direction? For example, what is known about the following proposition? For problems in P, switching from TMs to NTMs cannot, on average, decrease the complexity by more than a constant factor.

(Gil Kalai also has a  question  somewhat related to this one.)

1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once you fix the model, you can only compute $2^k$ functions that have a $k$ bit description.

2) For uniform classes like P this is more challenging, as there is no clear definition of "average function in P" and the counting arguments no longer work so cleanly. It's consistent with current knowledge that everything in P can be solved in nondeterministic linear time.


Proofs in $S_{2}^{1}$ In a talk by Razborov, a curious little statement is posted.

  If FACTORING is hard, then Fermat’s little theorem is not provable in $S_{2}^{1}$.

What is $S_{2}^{1}$ and why are current proofs not in $S_{2}^{1}$?

$S^1_2$ is a theory of bounded arithmetic, that is, a weak axiomatic theory obtained by severely restricting the schema of induction of Peano arithmetic. It is one of the theories defined by Sam Buss in his thesis, other general references include Chapter V of Hájek and Pudlák’s Metamathematics of first-order arithmetic, Krajíček’s “Bounded arithmetic, propositional logic, and complexity theory”, Buss’s Chapter II of the Handbook of proof theory, and Cook and Nguyen’s Logical foundations of proof complexity.

You can think of $S^1_2$ as a theory of arithmetic which has induction only for polynomial-time predicates. In particular, the theory does not prove that exponentiation is a total function, the theory can prove to exist only objects of polynomial size (loosely speaking).

All known proofs of the Fermat Little Theorem utilize either exponential-size objects, or they rely on exact counting of sizes of bounded sets (which is probably not definable by a bounded formula, i.e., in the polynomial hierarchy, because of Toda’s theorem).

The result on FLT, $S^1_2$, and factoring stems from Krajíček and Pudlák’s paper Some consequences of cryptographical conjectures for $S^1_2$ and EF, and in my opinion it is fairly misleading. What Krajíček and Pudlák prove is that if factoring (actually, IIRC they state it for RSA instead of factoring, but it’s known that a similar argument works for factoring too) is hard for randomized polynomial time, then $S^1_2$ cannot prove the statement that every number $a$ coprime to a prime number $p$ has finite exponent modulo $p$, that is, there exists $k$ such that $a^k\equiv1\pmod p$.

It’s true that this is a consequence of FLT, but in fact it is a much, much weaker statement than FLT. In particular, this statement follows from the weak pigeonhole principle, which is known to be provable in a subsystem of bounded arithmetic (albeit a stronger one than $S^1_2$). Thus, Krajíček and Pudlák’s argument shows that $S^1_2$ does not prove the weak pigeonhole principle unless factoring is easy, and as such provides a conditional separation of $S^1_2$ from another level of the bounded arithmetical hierarchy, say $T^2_2$.

In contrast, the actual FLT does not even seem to be provable in full bounded arithmetic $S_2=T_2$, but this is not related to cryptography. You can find some relevant discussion in my paper Abelian groups and quadratic residues in weak arithmetic.


Implications of the rule of cumulativity in the Calculus of Constructions Please help me understand some type theory research.

As suggested in "Type Checking with Universes" by Robert Harper and Robert Pollack, we can add the following rule to our otherwise standard COC or PTS type inference rules.

$$
\frac{\Gamma \vdash M : \text{Type}_{i}}{\Gamma \vdash M : \text{Type}_{i+1}} \text{(Cumulativity)}
$$

Doesn't that mean that if I declare Boolean : Type₀ that Boolean is implicitly of type Type₁, Type₂, and so on? And doesn't that mean that Typeᵢ ≡ Type₍ᵢ₊₁₎ and furthmore that ∀ i, j . Typeᵢ ≡ Typeⱼ by equational reasoning?

How does this differ from a predicative type theory where Type : Type?

Furthermore, this allows us to have dependent types even if our Π-formation rule is written as follows

$$
\frac{\Gamma \vdash \alpha : s \hspace{3em} \Gamma,x :a \vdash \beta : s}{\Gamma \vdash (\Pi x : \alpha . \beta) : s} \text{(}\Pi\text{-formation)}
$$

where the types of α, β and the resulting formation are (implicitely) required to be equivalent, right?

Just because you can always embed a lower-order type into the higher-order universe doesn't imply that the reverse is true.

The higher-order universe is always strictly larger than the lower-order one, so there is no problem with respect to predicativity.


Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix? I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix.

If any one knows if this problem is of a different complexity class, that would be just as helpful.

EDIT: I've tagged this question with Linear Programming, because I have a strong suspicion that if such a solution existed, it would be a kind of linear programming algorithm. The reason I believe this is because the extreme points of the Birkhoff polytope are precisely the permutation matrices. If you could then find an objective function which is either maximized or minimized only on the vertices of the Birkhoff polytope, you could constrain your function to the intersection of the polytope and your vector subspace, then maximize it in polynomial time. If this value were a permutation matrix, you'd know the set contained a permutation. Those are my thoughts on the subject.

EDIT 2: After some more thought, it seems to me that the permutation matrices are precisely the elements of the Birkhoff Polytope with Euclidean norm $\sqrt{n}$, the we consider the Birkhoff polytope to be the convex hull of the $n \times n$ permutation matrices. Perhaps that could also be significant.

EDIT 3: I added the semidefinite programming tag, because after my previous comment, I'm beginning to think that a semidefinite programming solution may be possible since it is now a linearly constrained quadratic optimization algorithm.

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum.

Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op.

Here is the intuition.  The problem in the post is

Is there a permutation matrix in the span of a given set of matrices?

This is essentially the same as

Is there a permutation matrix that (thinking of the matrix as a vector) satisfies some given linear constraints?

This in turn is the same as

Is there a perfect matching (in a complete bipartite graph) whose incidence vector satisfies some given linear constraints?

Reducing Subset-Sum to the latter problem is a standard exercise.

Here is the detailed proof.

Define the following intermediate problem:

  Matching-Sum:

  input: Complete, bipartite graph $G=(U,V,E)$ with non-negative
  integer edge weights, and non-negative integer target $T$.

  output: Does $G$ contain a perfect matching of weight exactly $T$?

  Lemma 1. Subset-Sum poly-time reduces to Matching-Sum.

Proving this is a standard homework exercise.  The proof is at the end.

  Lemma 2. Matching-Sum poly-time reduces to the problem in the post.

Proof of Lemma 2. Fix a Matching-Sum input: a complete bipartite graph $G=(U,V,E)$ with non-negative integer edge weights $w:U\times V\rightarrow \mathbb{N}_+$, and target $T\in \mathbb{N}_+$, where $U=\{u_1,\ldots,u_n\}$ and $V=\{v_1, \ldots, v_n\}$. For each $i,j\in\{1,2,\ldots,n\}$, define $M^{(ij)}$ to be the matrix in $\mathbb{R}^{(n+1)\times (n+1)}$ where $M^{(ij)}_{ij} = T$, and $M^{(ij)}_{n+1,n+1}=w(u_i, v_j)$, and all other entries are zero.  The reduction outputs the following set of matrices:
$$\big\{M^{(ij)} : i,j\in\{1,\ldots,n\}\big\}.$$
This defines the reduction.

Claim. The span of this set of matrices consists of
those matrices $M \in\mathbb{R}^{(n+1)\times(n+1)}$ satisfying
the linear constraints $M_{h,n+1} = M_{n+1,h} = 0$ for all $h\le n$ and
the linear constraint $$\textstyle\sum_{i=1}^n\sum_{j=1}^n M_{ij}\,w(u_i, v_j) = T\, M_{n+1,n+1}.$$

(Proof of claim. By inspection each matrix $M^{(ij)}$ in the set satisfies these constraints, so every linear combination of those matrices does.  Conversely, if $M\in\mathbb{R}^{(n+1) \times (n+1)}$ satisfies the constraints, then $M$ equals the linear combination $M'=\sum_{i=1}^n \sum_{j=1}^n \alpha_{ij} M^{(ij)}$ of the matrices, where $\alpha_{ij} = M_{ij}/M^{(ij)}_{ij} = M_{ij}/T$.  Note in particular that, by the various definitions and the linear constraints,
$$\textstyle M'_{n+1,n+1} = \sum_{ij} \alpha_{ij} w(u_i, v_j)
= \sum_{ij} M_{ij} w(u_i, v_j)/T
= (T\, M_{n+1,n+1})/T = M_{n+1,n+1}.
$$
This proves the claim.)

Now we show the reduction is correct.  That is, the given graph $G$ has a weight-$T$ matching if and only if the set of matrices spans a permutation matrix.

(Only if.) First suppose the given graph $G$ has a weight-$T$ perfect matching $M'$.  Let $M\in\{0,1\}^{(n+1)\times (n+1)}$ be the corresponding $n\times n$ permutation matrix, with an extra row and column added such that $M_{n+1,n+1} = 1$ and $M_{h,n+1}=M_{n+1,h}=0$ for all $h\le n$.
Then $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$ is the weight of $M'$, that is, $T$, and $M_{n+1,n+1}=1$, so the linear constraints in the claim hold, and the span of the given set of matrices contains the permutation matrix $M$.

(If.) Conversely, suppose the span contains any permutation matrix $M$.  By the claim, the only non-zero entry in row $n+1$ or column $n+1$ is $M_{n+1,n+1}$, so (as $M$ is a permutation matrix) it must be that $M_{n+1,n+1} = 1$.  So deleting the last row and column gives an $n\times n$ permutation matrix. Let $M'$ be the perfect matching of $G$ corresponding to that $n\times n$ permutation matrix.  The weight of $M'$ is $\sum_{i=1}^n\sum_{j=1}^n M_{ij} w(u_i, v_j)$, which (by the claim) is $T M_{n+1,n+1} = T$. So the given graph has a weight-$T$ matching, proving Lemma 2.$~~\Box$

Here's the delayed proof of Lemma 1:

Proof of Lemma 1. Given Subset-Sum instance $(w,T)\in\mathbb{N}^n_+ \times \mathbb{N}_+$, the reduction outputs the Matching-Sum instance $(G=(U,V,E), T)$ where $U=\{u_1, u_2, \ldots, u_{2n}\}$, $V=\{v_1, v_2, \ldots, v_{2n}\}$, for each $i\in\{1,\ldots,n\}$, edge $(u_i, v_i)$ has weight $w_i$, and all remaining edges have weight zero.

For any perfect matching with edge weights summing to $T$, the set $S=\{i : (u_i, v_i)\in M, i\le n\}$ is a solution to the given Subset-Sum instance (as these are the only non-zero weight edges in $M$).

Conversely, given any solution to the Subset-Sum instance, say $S\subseteq\{1,\ldots,n\}$ with $\sum_{i\in S} w_i = T$, the set of edges $\{(u_i, v_i) : i \in S\}$ is a partial matching with weight $T$, and it extends easily to a weight-$T$ perfect matching by adding, for example, the following set of (zero-weight) edges:

$$\{(u_{i+n}, v_{i+n}) : i\in S\} \cup \bigcup_{i\in\{1,\ldots,n\}\setminus S}\{(u_i, v_{i+n}), (u_{i+n}, v_{i})\}.$$

This proves Lemma 1. The theorem follows from Lemmas 1 and 2. $~~~\Box$

p.s. As an aside, according to this answer, the restriction of Matching-Sum to instances with polynomially-bounded edge weights is in P.  But I'm sure that the restriction of the problem in the post to matrices with polynomially-bounded (integer) entries remains NP hard.


Number of distinct enclosing circles for N points Several enclosing circles are possible for a given set of N 2D points. I am only talking about  enclosing circles having 3 or more points on the circumference. What is the asymptotic limit of the total number of distinct enclosing circles having 3 or more points on the circumference. The naive bound is $O(n^3)$ but tighter bound  should exist.

And also how to generate all such enclosing circles?

An enclosing circle (by your definition) corresponds to a triangular face of the farthest point Delaunay triangulation, which is a triangulation of the convex hull of the input. For points in general position it always has exactly $h-2$ faces where $h$ is the number of convex hull vertices. Therefore the number of enclosing circles is also $h-2$.

They can be generated by constructing the farthest point Delaunay triangulation, in $O(n\log n)$ time.


Deterministic Randomness Extractors I have read in several papers it is well known that deterministically extracting even one bit from a weak source is impossible. Could someone explain why?

Intuitively, the situation is you'd like some deterministic extractor $E: \{0,1\}^n \rightarrow \{0,1\}$ that can take in $n$ bits sampled from a weak source and output one bit with probability close to $1/2$, say it outputs 0 with probability $1/2 \pm \epsilon$ and 1 with $1/2\pm\epsilon$.

Here's a weak argument that at the very least, such extractors $E$ can't exist if we don't put any restrictions on the input distribution other than it has 'enough' min-entropy. Suppose $E$ is such a potential extractor. By flipping the output if necessary, we may assume without loss of generality that $|E^{-1}(0)|\ge|E^{-1}(1)|$; that is, $E^{-1}(0)$ is a set of $n$-bit strings of size at least $2^{n}/2$. Thus a random variable that samples uniformly from $E^{-1}(0)$ will have min-entropy at least $n - 1$, but the extractor will never give you any 'random' output other than 0.

Of course, if we tighten the restrictions on the input distribution (say, we assume all $n$ bits are IID) then we do have deterministic extractors that work. But as problem 6.6 in Salil Vadhan's survey of pseudorandomness shows, even weakening the IID assumption a little bit will cause deterministic extractors to fail, by a slight generalization of the same argument as I made above.


What is conjunctive truth table reduction? What are conjunctive/disjunctive truth table reductions and how do they compare with other reductions?

In the binary case they are two of the seven truth-table reducibilities
$$m, btt(1), c, d, p, \ell, tt$$
based on polynomial clones.
See Figure 1 in Culver's paper
https://link.springer.com/article/10.1007/s00153-013-0351-x
for the classic diagram of the seven.

In the ternary case there are uncountably many such reducibilities instead of 7, as Culver demonstrates using a prior result about clones from universal algebra.


What are the obstructions to extending $L=SL$ to $L=NL$? Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an expander graph from the original graph, and then do the walk in the expander graph. The expander graph is made by squaring the original graph logarithmically many times. In the expander graph, the diameter is only logarithmic, so a DFS search of logarithmic depth suffices.

Extending the result to $L=NL$ would imply the existence of a logspace algorithm for DSTCON -- the same, but for Directed graphs. (Sometimes just STCON.) My question, maybe slightly soft, is what are the primary obstructions to extending Reingold's proof to that?

It feels slightly like there should be a sort of "directed expander" graph. A similar sort of construction, where you add in edges corresponding to medium-length directed paths, and then some corresponding to long ones; and then you can traverse the graph with logarithmic depth by moving across short paths to get to a long one; then back to short paths at the end.

Is there a major flaw in this concept? Or is it that there aren't any good constructions of such expanders? Or does it somehow require more memory than the undirected version?

I unfortunately cannot find much at all on directed expander graphs. In fact essentially all I could find was https://math.stackexchange.com/questions/2628930/how-can-one-construct-a-directed-expander-graph-with-varying-degree-distribution (which is unanswered) and https://repository.upenn.edu/cgi/viewcontent.cgi?article=1202&context=cis_papers . Is there a different term I should be searching under?

The central problem is that, on directed graphs, even a truly random walk doesn't hit all the vertices in expected polynomial time, let alone a pseudorandom walk.  The standard counterexample here is a directed graph with $n$ vertices ordered from left to right, where each vertex has an edge leading to the vertex to its right (except for the rightmost vertex, $t$), and each vertex also has an edge leading all the way back to the leftmost vertex, $s$.  To get from $s$ to $t$ by a random walk then takes ~$2^n$ time.  So, what is the small-space randomized algorithm for directed connectivity that we're hoping to derandomize, analogous to what Reingold did for $USTCON$?  (To put it another way, how do we show $RL=NL$, let alone $L=NL$?)  For directed connectivity, of course there's Savitch's algorithm, but that takes $O(\log^2 n)$ space, and for general graphs no one has managed to improve it for half a century, with or without the use of randomness.


"Steve's class": origin of SC We "know" that $\mathsf{SC}$ is named for Steve Cook and $\mathsf{NC}$ is named for Nick Pippenger. If I'm not mistaken, Steve Cook named NC in honor of Nick Pippenger, and I was told that the reverse is true as well. However, I wasn't able to find any evidence of this latter fact in either Steve Cook's paper on DCFLs or Nisan's proof that $\mathsf{RL} \subseteq \mathsf{SC}$.

Is there any documented evidence of the latter claim, or is this merely "in the air" ?

p.s I'm asking because I was browsing examples of Stigler's Law of Eponymy, and was wondering about what I'll call "Stigler Reciprocity": where something invented by A is named after B and vice versa. An example of this is Cartan Matrices and Killing forms.

The following is according to Nick Pippenger:

The relevant references are as follows.  Steve described NC as Nick's Class in his paper "Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space" (ACM STOC, 11 (1979) 338-345)  on SC, and I described SC as Steve's Class in my paper "Simultaneous Resource Bounds'' (IEEE FOCS, 20 (1979) 307-311)  on NC.  But the names originated about a year-and-a-half earlier, when I visited the University of Toronto CS Department (January through June, 1978).  That's when the study of the two classes began, with Steve defining SC and me defining NC, and various people in the department (I think Allan Borodin was the first) using the two names.  The following fall, Steve submitted the paper cited above. I was on the program committee for that STOC, and not allowed to submit papers to it, so my paper appeared in the following FOCS conference.
Best wishes,
Nick


Is the complexity of this path problem known? Instance: An undirected graph $G$ with two distinguished vertices $s\neq t$, and an integer $k\geq 0$.

Question: Does there exist an $s-t$ path in $G$, such that the path intersects at most $k$ triangles? (For this problem a path is said to intersect a triangle if the path contains at least one edge from the triangle.)

Assume there are no self-edges in $G$.

For each edge between node $v_i$ and $v_j$ in $G$, let $E[i,j]=1$, and $E[i,j]=0$ if there is no edge. Compute $n\times n$ matrix $C[i,j]=\sum_{k=1}^n E[i,k]\cdot E[k,j]$, which gives the number of two-hop paths between each pair of nodes $v_i$ and $v_j$. Then for edge between $v_i$ and $v_j$ in $G$ compute $D[i,j]=E[i,j]\cdot C[i,j]$ otherwise set $D[i,j]=\infty$, which gives the number of triangles the edge is part of (or infinity if there is no edge). The matrix multiplication needed to compute $C$ costs $O(n^3)$ (could be computed faster depending on sparsity of $G$).

Now compute $n\times n$ matrix $A$, such that $A[i,j]=\min(D[i,j],\min_k(D[i,k]+D[k,j]-E[i,j]))$. $A$ is all shortest-paths in $D$ of length up to two augmented to account for paths that go along two edges of some triangle.

Now just compute the shortest path between $v_i$ and $v_j$ in $G$ on a new graph of which $A$ is the (weighted) adjacency matrix using Dijkstra (since all edge-weights are positive) i.e. and determine if $A^*[i,j]\leq k$, where $A^*$ is the closure over the tropical semiring (which gives the distance matrix).


Flood fill vs depth first search Is the flood fill algorithm the same as depth first search?

If not, how do they differ in complexity?

The Flood Fill algorithm is a particular case of the Depth First Seach algorithm, on regular mesh graphs:

Wikipedia indicates that they do not work on the same kind of data:

The Flood Fill algorithm is "an algorithm that determines the area connected to a given node in a multi-dimensional array."
The Depth First Seach algorithm is "an algorithm for traversing or searching tree or graph data structures".

A multi-dimensional array (and the kind of neighborhood considered in the flood fill algorithm) is a particular case of graph, extremely regular.

In any case, the complexity is clearly within $O(n)$ where $n$ is the number of nodes being colored (for both problems).


Minimum BoundingBox on n-dimensional case I need to develop an algorithm to define the minimum bounding box on an N-dimensional space.

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

Every reference to this problem that I'm able to find is related to computer graphics (so, only 2 or 3 dimensions). Where can I find some references on the generalised version of this problem?

See chapter 18 here http://goo.gl/pLiEO. If the dimension is really high then bounding box is the wrong creature to work with. A better choice is the ellipsoid. See chapter 16 about John's ellipsoid - it can be computed efficiently using quadratic programming in some cases.


How hard is to compute $\Delta_{|V|}$? Let $G=(V,E)$ be a graph. Let $\Delta_k$ be the quantity defined in this question. Let $\mathcal{C}$ be the set of vertex covers of $G$. The following holds:

$$
|\mathcal{C}| = 2^{|V|} - \sum_{k = 2}^{|V|} \Delta_k \cdot 2^{|V|-k}
$$

Let us focus on $\Delta_{|V|}$.

Question

How hard is to compute $\Delta_{|V|}$?

Motivation

The quantity
$$\Delta_{|V|}\ \ mod\ \ 2$$
is the parity of the number of vertex covers of $G$. If such quantity is $0$ then $|\mathcal{C}|$ is even, otherwise $|\mathcal{C}|$ is odd.

Therefore (forgive me if I'm wrong):

Being able to compute $\Delta_{|V|}$ in polynomial time implies $\mathbin{\oplus}$P = P.
$\Delta_{|V|}$ being $\#$P-hard to compute implies $\mathbin{\oplus}$P = PP.

It seems that in both cases we would get an important result. Clearly there is a third option: computing $\Delta_{|V|}$ may be of intermediate counting complexity, strictly harder than FP but strictly easier than $\#$P-hard.

Update 08/01/2013 21:50

After reading again and more carefully T. Williams' answer to this question, my understanding is that such answer precisely proves that computing $\Delta_{|V|}$ is $\#$P-hard (because the constraint $[0,1,1,1]$ forces every node of $G$ to be present).

However, my second conclusion above does not hold: to conclude $\mathbin{\oplus}$P = PP, computing $\Delta_{|V|}\ \ mod\ \ 2$ should be $\#$P-hard. But the $\#$P-hardness of computing $\Delta_{|V|}$ is not known to imply that computing $\Delta_{|V|}\ \ mod\ \ 2$ is $\#$P-hard as well.

Only a more vague and harmless conclusion can be drawn, more or less along these lines: something which appear to be false from a practical point of view (i.e. Graph Isomorphism $\not\in$ P) would imply something already formally known to be true (i.e. computing $\Delta_{|V|}$ is $\#$P-hard).

As the OP pointed out in an update above, the second question about computing $\Delta_{|V|}$ is answered in this question.

The first question is about computing the parity of the number of vertex covers. This problem is $\bigoplus$P-hard even for planar 3-regular graphs.  See Section 4.1 of this paper (particularly Corollary 4.2).

First, the notation for the corresponding Holant problem is Pl-$\bigoplus$Holant$([0,1,1]|[1,0,0,1])$.  Since there is a 1-to-1 correspondence between vertex covers and independent sets, sometimes people also refer to the Holant expression for independent set (in this case, $\bigoplus$Holant$([1,1,0]|[1,0,0,1])$) as though it were the vertex cover problem.

Second, I don't know why they called this problem $\bigoplus$3/2-Bip-VC (that is, why "3/2-Bip").  As I said above, this Holant expression is for the counting of vertex covers (equivalently, independent sets) in 3-regular graphs.


Who coined the term "empirical entropy"? I know of Shannon's work with entropy, but lately I have worked on succinct data structures in which empirical entropy is often used as part of the storage analysis.

Shannon defined the entropy of the information produced by a discrete information source as $-\sum_{i=1}^k p_i \log{p_i}$, where $p_i$ is the probability of event $i$ occurring, e.g. a specific character generated, and there are $k$ possible events.

As pointed out by MCH in the comments, the empirical entropy is the entropy of the empirical distribution of these events, and is thus given by $-\sum_{i=1}^k \frac{n_{i}}{n} \log{\frac{n_{i}}{n}}$ where $n_{i}$ is the number of observed occurrences of event $i$ and $n$ is the total number of events observed. This is called zero-th order empirical entropy. Shannon's notion of conditional entropy has a similar higher order empirical version.

Shannon did not use the term empirical entropy, though he surely deserves some of the credit for this concept. Who did first used this idea and who first used the (very logical) name empirical entropy to describe it?

I am interested in "empirical entropy" like you and the earliest paper I find was that from Kosaraju like the user "Marzio De Biasi" told in his comment.

But in my opinion the real definitions of "empirical entropy" are made later by generalizing the former concepts:

"Large Alphabets and Incompressibility" by Travis Gagie (2008)
"Emprical entropy" by Paul M. B. Vitányi (2011)

Gagie rephrase the definition of $k$th order empirical entropy to:

$H_{k}(w)=\frac{1}{|w|}\min\limits_{Q}\left\{\log\large\frac{1}{P(Q=w)}\right\}$

where $Q$ is a $k$th order Markov process. He also showed that this definition is equivalent to the previous one.
The next step from Vitányi was a generalization to arbitrary classes of processes (not only Markov-processes):

$H(w|\mathcal{X})=\min\limits_{X}\left\{K(X)+H(X):\;\left|H(X)-\log\large\frac{1}{P(X=w)}\right|\normalsize\;is\;minimal!\right\}$

where $\mathcal{X}$ is the class of allowed processes and $K(X)$ is the Kolmogorov complexity.
If we choose $\mathcal{X}$ to be the class of $k$th order Markov processes producing  a sequence of $|w|$ random variables and ignoring the Kolmogorov complexity, than this also leads to the definition of Gagie (multiplied with $|w|$).


Can quantum algorithms with exponential speed-up be rederived using span-programs? The general adversary lower-bound is now known to characterize quantum query complexity
due to breakthrough work by Reichardt et al. The same line of work also establishes connections
to the span program framework to design quantum algorithms.

Many interesting quantum algorithms, including ones with exponential speed-up like
Simon's algorithm and Shor's algorithm for period finding can be expressed in the
quantum query model.

Is there any work showing lower-bounds for these algorithms in the general adversary model?
Is there any work re-deriving Simon's or Shor's algorithms in the span-program framework?

Apparently, only quantum algorithms with polynomial speed-up, like Grover's , have been re-derived using span programs (or Belov's learning graph) framework.

There is work by Korian et al. showing lower-bounds for Simon using the polynomial method, but there is apparently no known way to translate polynomial-method lower-bounds to general adversary lower bounds.

I guess there are at least 3 questions in your question. I don't have a satisfactory answer to all of them, so this isn't a complete answer. Hopefully there will be more answers that answer all your questions.

The question in the title: Can quantum algorithms with exponential speed-up be rederived using span-programs?

As you noted, the general adversary bound characterizes the quantum query complexity of all decision problems, including promise problems for which we have exponential speedups. So, in principle, there is a span program that solves the Abelian hidden subgroup problem, which is the query problem used in Simon's and Shor's algorithms. But whether there is an explicit span program for this is your next question.

Is there any work re-deriving Simon's or Shor's algorithms in the span-program framework?

I haven't heard of any such results. I don't know of a span program for Simon's problem or any other AHSP.

Is there a way to translate polynomial-method lower-bounds to general adversary lower bounds?

Yes, I believe there is. I can't seem to find the paper that has this result, but I can give you a link to a talk given by Jérémie Roland. In the abstract of the talk, he says the following:

  ... More precisely, we will show that the multiplicative adversary method, a variation of the original adversary method, generalizes not only the generalized adversary method, but also the polynomial method, so that it essentially encompasses all known lower bound methods. Therefore, this provides a constructive approach to cast polynomial lower bounds into the adversary method framework.

Update: The paper is now available online:
Explicit relation between all lower bound techniques for quantum query complexity by Loïck Magnin and Jérémie Roland


What is the most efficient algorithm to sample graphs with trivial automorphism groups ? Let us call a graph "asymmetric" if it has no nontrivial automorphism group. http://en.wikipedia.org/wiki/Asymmetric_graph

I'm looking for an efficient way to compute a random asymmetric graph on a given number of nodes.

Almost all graphs have trivial automorphism group. So all you need to do is generate a graph uniformly at random (see e.g. http://en.wikipedia.org/wiki/Random_graph), then compute its automorphism group (or just determine its order). Repeat until you find a graph with trivial automorphism group (also called a rigid graph).


An edge orientation procedure to generate all acyclic orientations of a graph Consider the following scheme for enumerating acyclic digraphs (DAGs) by orienting the edges in an undirected graph $G$ with $n = ||V||$ vertices:

(1) Generate all $n!$ possible permutations $p_i$ of the $n$ vertices in $G$.

(2) For each permutation $p_i = (v_a, v_b, ..., v_n)$, direct any unoriented edges adjacent to $v_a$ away from $v_a$, then direct any oriented edges adjacent to $v_b$ away from $v_b$ (if edges were previously oriented, and perhaps pointing towards $v_b$, leave those oriented edges unperturbed), and so on for all successive vertices in the permutation up to $v_n$.

(3) Check if the resulting acyclic digraph generated in step (2) is an existing element of some (initially empty) list $L$.  If not, add it to the list.

Now my question is --- will $L$ contain all possible acyclic orientations of the initially undirected graph $G$, or might we miss some?  If the latter is possible, can we say anything in particular about the nature of these missed acyclic digraphs?

(Just to be clear, by no means am I suggesting that the above procedure is an efficient way to generate sets of acyclic digraphs!)

The procedure maps each permutation of the vertices to some orientation of the graph whose topological ordering of the vertices is consistent with the permutation.

Every acyclic orientation of the graph induces at least one topological ordering of the vertices.

Every topological ordering of the vertices induces exactly one orientation of the graph (since if two distinct orientations were compatible with the ordering, they would differ in the orientation of at least one edge $(u,v)$ and hence $u$ would come both before and after $v$ in the permutation, which is a contradiction).

So the procedure generates all the acyclic orientations of the graph.


Maximum flow for all edges in an undirected graph I was wondering if the following problem has been studied in the past, and what are some of the best ways people can come up with to solve it:

Let $G=(V,E)$ be an undirected graph, which we use as a flow network with edge capacities $c(e)=1$ for all $e \in E$.
For all edges $e = \{u,v\} \in E$, we would like to calculate the maximum flow between $u,v$.

Let $t_{mstf}$ be the time it takes to calculate a maximum s-t flow and $t_{mf}$ be the time it takes to calculate a maximum flow.
We can solve the problem above naively in $\mathcal{O}(|E| \cdot t_{mstf})$ time.
We can also do it by building a Gomory-Hu tree in $\mathcal{O}(|V| \cdot t_{mf})$ time and then an additional $\mathcal{O}(|E||V|)$ steps to get shortest paths along the tree.

Can we do any better?

There is a randomized algorithm for computing Gomory-Hu tree in $\tilde{O}(|E||V|)$ time when all edges have capacity 1.
Once you have the Gomory-Hu tree, you can process it so you can answer maximum flow queries between two vertices in constant time.


The decision procedure of theory of closed real field is in NP-hard? The decision procedure of theory of closed real field  refers to https://en.wikipedia.org/wiki/Decidability_of_first-order_theories_of_the_real_numbers

Yes, even in the purely existential case. See https://en.wikipedia.org/wiki/Existential_theory_of_the_reals


What papers should everyone read? This question is (inspired by)/(shamefully stolen from) a similar question at MathOverflow, but I expect the answers here will be quite different.

We all have favorite papers in our own respective areas of theory. Every once in a while, one finds a paper so astounding (e.g., important, compelling, deceptively simple, etc.) that one wants to share it with everyone. So list these papers here! They don't have to be from theoretical computer science -- anything that you think might appeal to the community is a fine answer.

You can give as many answers as you want; please put one paper per answer! Also, notice this is community wiki, so vote on everything you like!

(Note there has been a previous question about papers in recursion-theoretic complexity but that is quite specialized.)

"A mathematical theory of communication" by Claude Shannon, classics of information theory. Very readable.

(Mirror)


Why is the multi-step reduction of semantics reflexive? I was reading Programming Languages and Lambda Calculi, which defines the multi-step reduction to be the reflexive-transitive closure of the one-step reduction. (Page 15, $\twoheadrightarrow_r$ is the reflexive-transitive closure of $\rightarrow_r$)

A quick search shows that this idea is widely accepted, for example by courses from Princeton, UPenn, CU, etc. However, I think the transtivity should be enough to capture the intuition of many steps. So why is reflexivity needed?

The practical reason is that it is very convenient to include also the case "zero steps" in the definition of "many steps" (millennia of mathematical experience have taught us that it is usually a good thing to have a 0 around in our set of natural numbers).

One possible technical exemplification of this (but there are probably dozens more, perhaps more interesting than this one) is that $\to^+$, the transitive closure of reduction, does not satisfy the diamond property  (a.k.a. confluence), whereas $\to^\ast$ satisfies it.  For example, if $I:=\lambda x.x$, there is no way to close the following critical pair by means of $\to^+$:

$$I \leftarrow (\lambda x.I)(II) \to (\lambda x.I)I$$

To close the span, you need to consider the empty reduction $I\to^\ast I$.


Is there a polynomial time algorithm for creating a set of vectors in general position? It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis.

For example, in $\mathbb{R}^3$, here is such a set with 21 vectors:

$$
\left\{
  [1,2,3], [2,3,1], [3,1,2], \\
  [1,4,5], [4,5,1], [5,1,4], \\
  [1,6,8], [6,8,1], [8,1,6], \\
  [1,8,12], [8,12,1], [12,1,8], \\
  [1,10,17], [10,17,1], [17,1,10], \\
  [1,12,23], [12,23,1], [23,1,12], \\
  [1,14,30], [14,30,1], [30,1,14]
\right\}
$$

Any combination of 3 of these vectors is linearly independent.

Is it possible to create a set satisfying this property with arbitrarily many vectors? I think so, but the specific pattern used in the set above breaks down around 50 vectors; I think some more complicated pattern should work.

Is it possible to create this set in time polynomial in the number of vectors in the set?

Let me give some details for the Cauchy matrix construction, which is simple. Let $x = (x_1, \ldots, x_n)$, $y = (y_1, \ldots, y_m)$ be sequences of pairwise distinct numbers. The corresponding Cauchy matrix is
$$
C = \begin{pmatrix}
\frac{1}{x_1 - y_1} & \frac{1}{x_1 - y_2} & \ldots & \frac{1}{x_1 - y_m}\\
\frac{1}{x_2 - y_1} & \frac{1}{x_2 - y_2} & \ldots & \frac{1}{x_2 - y_m}\\
\vdots & \vdots & \ddots & \vdots\\
\frac{1}{x_n - y_1} & \frac{1}{x_n - y_2} & \ldots & \frac{1}{x_n - y_m}\\
\end{pmatrix}
$$

Then any square submatrix of $C$ is an invertible square Cauchy matrix. In particular, the $n\times n$ submatrix $C_J$ with columns indexed by $J = \{j_1, \ldots, j_n\}$, $j_1 \leq \ldots \leq j_n$, has determinant
$$
\det C_J = \frac{\prod_{i = 2}^n\prod_{k = 1}^{i-1}{(x_i - x_k)(y_{j_i} - y_{j_k})}}{\prod_{i = 1}^n\prod_{k = 1}^n{(x_i - y_{j_k})}}.
$$

Because $x$ and $y$ are sequences of distinct numbers, the determinant is nonzero, and $C_J$ is invertible.

If you prefer something even more concrete, you can take the Hilbert matrix: the Cauchy matrix with $x = (1, \ldots, n)$ and $y = (0, -1, -2, \ldots, -m)$. With $n = 3$ you get the points $(1, 1/2, 1/3),\ (1/2, 1/3, 1/4),\ (1/3, 1/4, 1/5),\ (1/4, 1/5, 1/6)$ and so on.


How to generate a permutation uniformly by repeating using an one-bit uniform random generator? If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.

I have a solution:  run the one-bit random generator n*n times to decide if each pair of elements will be exchanged.

The complexity is O(n*n).

I want to know if there more efficiency solution? What is the lower bound for this problem?

Your solution does not work (or I don't understand it): the resulting permutation would not be uniformly random.

To Sasho Nikolov, this is a research topic and is actually the topic (among others) of a paper I have recently submitted, where I provide an optimal algorithm. I can give you an idea of the lower bound. Indeed, you would have to distinguish between n! different permutations, so theoretically you would need at least log2(n!) bits exactly. But Knuth and Yao show in their seminal paper ("The complexity of nonuniform random number"), that because of "rounding errors" (to simplify), the actually random-bit complexity is between log2(n!) and log2(n!) + 2, that those are the best bounds, and in addition they provide an exact expression in terms of entropy of the distribution (in this case the uniform distribution).

It can (and has) been shown that the exact complexity involves fluctuations periodic in log2(n), much like the average complexity of divide-and-conquer algorithms such as QuickSort. (Such details are routinely hidden by the traditional sledge-hammer approach known as the "Master theorem" :-).

Now, supposing you have your random number X, the bijection between the number and the corresponding permutation is a subproblem of what is more largely referred to as "unranking". Martinez and Molinero have devised a nice general framework based on a popular random generation framework introduced by Wilf and Nijenhuis and formalized by Flajolet et al.. But for permutations it is a much simpler problem: you consider the factorial-base expansion of X to get the random integers needed for the Fisher-Yates algorithm. See the following for more info:

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

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

EDIT: added the image which shows the optimal number of expected random bits needed to distinguish between N choices.


Number of distinct nodes in a random walk Commute time in a connected graph $G=(V,E)$ is defined as the expected number of steps in a random walk starting at $i$, before node $j$ is visited and then node $i$ is reached again. It is basically the sum of the two hitting times $H(i,j)$ and $H(j,i)$.

Is there anything similar to the commute time (not exactly the same) but defined in terms of nodes? In other words, what is the expected number of distinct nodes a random walk starting at $i$ and returning at $i$ will visit?

Update (Sept 30, 2012): There is a number of related work on the number of distinct sites visited by a random walker on a lattice (i.e., $\mathbb{Z}^n$). For instance, see: http://jmp.aip.org/resource/1/jmapaq/v4/i9/p1191_s1?isAuthorized=no

Anybody has ever read something on this?

A comment:  I recently attended a talk by Bruce Reed with the title Catching a Drunk Miscreant, which was joint work with Natasha Komorov and Peter Winkler.  If you can get a hold of the results from this work, maybe that might help you in some direction.

In general, they prove an upper bound on the number of steps a cop need in a general graph to be able to catch a robber, when we know the robber moves at random along the edges.


Generating a Diffie Hellman tuple without "being able to know" one of the discrete logs involved Is it (believed to be) possible, in the various standard examples of groups in which discrete log/Diffie Hellman are hard (including multiplicative groups in modular arithmetic and elliptic curves, and including cases in which Decisional Diffie Hellman is easy) to generate tuples of the form $(g, g^a, g^b, g^{ab})$ without in a sense "knowing" either a or b?

More formally, if there is a polynomial-time Turing machine $T(G, c)$ such that $T$ maps any input into such a tuple in the group described by $G$ ($G$ could just be a modulus if this is a modular multiplicative group, and $c$ could be thought of as random bits), must there exist a polynomial-time $T'$ such that $T'$, with the same input as $T$, outputs $(g, g^a, g^b, g^{ab}, a)$ or $(g, g^a, g^b, g^{ab}, b)$?

Clearly, the answer to this question is not known since there is always such a $T'$ if discrete log is easy and there is is a $T$ without such a $T'$ if Diffie Hellman is easy and discrete log is hard.  I'm particular interested in whether there is some existence result that says there must be a $T$ with no such $T'$ (under an assumption like hardness of discrete log), or whether there is a general conjecture that such a $T'$ always exists (or better yet, that this is implied by some other, widely believed, conjecture).

For further context, I'm essentially curious about whether the assumption that such a $T'$ always exists would be considered reasonable in an analysis of a cryptographic protocol.

Now cross-posted on mathoverflow: https://mathoverflow.net/questions/76302/is-it-believed-to-be-possible-to-algorithmically-generate-diffie-hellman-tuples

It looks as though the case with a fixed $g$ has shown up under the name "knowledge of exponent assumption(s)"--Googling this phrase will turn up a few papers which discuss/use it. In particular I notice "Statistically Hiding Sets" by Prabhakaran and Xue claims to show the assumption holds in the generic group model. There may be more recent information out there, but that should serve as a starting point at least. Long story short, as far as I can tell: It's a nonstandard assumption, but it's not obviously false and some people have built things with it.


Where does the information in a fractal come from? When I view a fractal such as the Mandelbrot, my first thought is, where did this interesting picture come from. For a picture of this complexity, the information that generated this picture must be stored somewhere. Then I found that the Mandelbrot is generated by computational processes based upon mathematics in the area of complex numbers.

However, my question still holds, where did the information come from? The nice picture wasn't input when the program was written, where did the information for this picture come from?

To a large extent, the answer will depend on exactly what you mean by "information". The fractal has very low Kolmogorov complexity, as there is a very simple rule describing how you generate it. So in one sense, it contains very little information. On the other hand, a picture of such a fractal appears very complicated, even though there is a simple rule underlying it. This is not at all uncommon. Many times very simple rules give rise to very complex behavior. Examples of this range from cellular automata and Conway's game of life to things like the apparent complexity in the digits of $\pi$. The fact is that this new representation doesn't contain anything fundamentally new, but is rather a less efficient expression of the same object.


What are graph grammars? I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview of the basic uses of them?

This paper opens with an introductory survey on graph grammars and then advances two new applications. It’s dated (1992) but explains the concepts well enough that it seems like the kind of thing you’re interested in.


Average performance of universal computation This post is related to my previous question but takes a different angle

There are several related questions in here

Consider an input-less algorithm $A$ generated randomly using a prefix-free universal Turing machine, like in the definition of Chaitin's constant. Consider $T$ the conditional expectation value of $A$'s execution time, the condition being "$A$ halts"

  Is T finite?

Consider $U$ an algorithm accepting input-less halting algorithms as input and producing their output as ouput. $U$ is essentially a universal Turing machine or perhaps a "universal algorithm" since we're assuming all algorithms run on the same "hardware". Consider $T(U)$ the conditional expectation value of the execution time of $U(A)$, the condition still being "$A$ halts"

  Is $T(U)$ finite for some $U$?

Obviously, the answer to the 2nd question is "yes" if the answer to the 1st question is "yes". If the answer to the 2nd question is "no", the following questions become trivial

Consider $T_{min} = \inf_{U} T(U)$

  Is there $U_{opt}$ s.t. $T(U_{opt}) = T_{min}$?

Consider infinite sequences $U_1, U_2...$ s.t. $\lim_{i \to \infty}T(U_i)=T_{min}$

  Is there an algorithm $V$ that takes a natural number $i$ for input and outputs $U_i$ as above?

Obviously, "yes" for the 3rd question implies "yes" for the 4th

By $T(A)$ I will mean the runtime of $A$ on the empty input, and will define $T(A) = \infty$ if $A$ doesn't halt. By $|A|$ I mean the length of $A$ in bits.

What you are trying to calculate in part (1) is:

$$T = \sum_{A | T(A) < \infty} \frac{1}{2^{|A|}}T(A)$$

Where the fraction is the Chaitin probability of generating program $A$. For each length $n$ there is (at least) one machine $A_n$ such that for all halting $A$ with $|A| = n$ we have $T(A) \leq T(A_n) = BB(n)$. Here $BB$ is the relevant busy-beaver function, which grows faster than any computable function, in particular $BB(n) > 2^n$. From this we have:

$$T \geq  \sum_{n = 1}^{\infty} \frac{1}{2^n}BB(n) > \sum_{n = 1}^{\infty} 1$$

Thus your sum does not converge, and $T$ is not finite. I guess that answers the rest of your questions, too. If you want to achieve your goal, then you need to pick a better density function on programs, maybe something where probability of $A$ is proportional to say $\frac{1}{2^{BB(|A|)}}$. However, for learning more about this I recommend CS.SE.


Would an optimal sorting network ever have to swap two numbers the "wrong" way Intuitively it seems like an optimal (either minimum depth or minimum gates) sorting network should never have to compare-swap two numbers the "wrong" way (such that the larger one goes into the smaller-indexed position and vice versa).

Is this true?

If so, how do you prove it?

How do you decide what the "wrong way" is?

Take the first wrong-way swap gate, and interchange the two wires going out of it (including all their associated gates) so that it's correct. This doesn't change the fundamental circuit. It may introduce more wrong-way swap gates, but they're all later in the circuit.

Now, you can keep doing this until you've gotten rid of all the wrong-way swap gates. At this point, you may have permuted the order of the output wires, but you will have a circuit which always outputs a fixed permutation of the sorted order. But since if you input the numbers in sorted order, the right-way swap gates never change the order, this fixed permutation must be sorted order.

So for any sorting network, there's an equivalent one with the same number of gates and the same depth which has no wrong-way gates.


On the proof of Meyer's Theorem Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} $.  A proof outline is as follows:

Let $L \in EXP $ and let $M$ be a one tape TM deciding $L$ in time $2^{n^{C}}$.  Consider the computation tableau for $M$, and assume each position $(i,t)$ encodes as a string $z_{i,t}$ the content all cell at time $t$, whether the head of the tape scanning cell $i$ at time $t$, and if it is, records the internal state $q$ of the TM.

Now consider the language about computational historical tableau of $M$.
Let $L_{M} = \{ \langle x,i,t,z\rangle | \text{on input } x \text{  we have  } z_{i,t} = z \text{  for  } M  \}.$

By simulation $M$ we have $L_{M} \in EXP \subseteq P/poly$. If using polynomial size circuits for $L_{M}$ we can construct a polynomial-size multi-output circuit $C$ such that $C(\langle x,i,t\rangle)=z$ then we get a characterization with two quantifiers $L_{M} = \exists C \in \{0,1\}^{poly(n)},\forall i ,t\in  \{0,1\}^{poly(n)},C(\langle x,i,t\rangle)$ follow from  $C(\langle x,i-1,t-1\rangle),C(\langle x,i,t-1\rangle),C(\langle x,i-1,t-1\rangle) \wedge C(\langle x,1,2^{n^{C}}\rangle) $ is the accepting state by the transition function of the TM.

Question:

  In this proof, I am not sure about the construction of multi-output circuit. Can anyone  give a concrete way of doing this construction?

I am not sure I understand your question. Let $L_M(k)=\{(x,i,t)$ for which on input $x$ we have that the $k$-th bit of $z_{i,t}$ is $1$. This language is in EXP, thus also in P/poly. Putting together these circuits for different values of $k$, we get the multi-output circuit.


On the coloring number of small graphs with small cliques Given a parameter $k$, and a graph $G$ with $O(k^2)$ vertices that has a maximum clique with $\le k$ vertices, I want to investigate the maximum number of colors $C(k)$ needed to properly color $G$, i.e $\chi(G)\le C(k)$.

Using Mycielski's graphs, one can show that this number should be at least $k+\log k$.

It is known that for any integer $c$ there is a triangle-free graph that has chromatic number $c$. However in all these constructions, as far as I know, the size of these graphs is a rapidly increasing function of $c$.

I conjecture that $C(k)=\Theta(k)$ and I would be really grateful for any helpful references related to this question.

Uniformly random $k^2$-vertex graphs have clique size $O(\log k)$, well under $k$, and independent set size also $O(\log k)$, implying that their chromatic number is $\Omega(k^2/\log k)$.

As for $k^2$-vertex triangle-free graphs, their chromatic number can be $\Theta(k/\sqrt{\log k})$ (and not higher); see Kim, Jeong Han (1995),
"The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$", Random Structures & Algorithms 7 (3): 173–207, doi:10.1002/rsa.3240070302

If by "size" you mean edges rather than vertices, then the maximum chromatic number of triangle-free $k^2$-edge graphs is $\Theta((k/\log k)^{2/3})$. See Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", Discrete Mathematics 211(1–3): 261–262, doi:10.1016/S0012-365X(99)00109-0.