On the entropy of a sum I am looking for a bound on the entropy $H(X+Y)$ of the sum of two independent discrete random variables $X$ and $Y$. Naturally, $$H(X+Y) \leq H(X) + H(Y) ~~~~~~(*)$$ However, applied to the sum of $n$ independent Bernoulli random variables $Z_1, \ldots, Z_n$, this gives
$$ H(Z_1 + Z_2 + \cdots + Z_n) \leq n H(Z_1)  $$ In other words, the bound grows linearly with $n$ when applied repeatedly. However, $Z_1 + \cdots Z_n$ is supported on a set of size $n$, so its entropy is at most $\log n$. In fact, by the central limit theorem, I'm guessing that $H(Z_1 + \cdots + Z_n) \approx (1/2) \log n$ since it is essentially supported on a set of size $\sqrt{n}$.
In short, the bound $(*)$ overshoots by quite a bit in this situation. From perusing this blog post, I gather all sorts of bounds on $H(X+Y)$ are possible; is there a bound that gives the right asymptotics (or, at least, more reasonable asymptotics) when applied repeatedly to the sum of Bernoulli random variables?

For such questions, you often get the right intuition by thinking of "flat" random variables. That is, think of $X$ as the uniform distribution over a set $A$ of size $2^{H(X)}$ and of $Y$ as the uniform distribution over a set $B$ of size $2^{H(Y)}$.

So, the question you're asking is (roughly speaking) what can you say about the size $|A+B|$ compared to $|A|$ and $|B|$. Generically (e.g., if they were random sets) then indeed you'll have $|A+B| \sim |A|\cdot |B|$ which corresponds to $H(X+Y) \sim H(X)+H(Y)$.

There are some special cases when $|A+B| \ll |A|\cdot |B|$, most notably when $A$ and $B$ are intervals (or more generally arithmetic progressions). There are some results that say that (at least under some conditions and if $|A+B|$ is almost as small as it can be) this is the only case. The area that studies such questions is known as "additive combinatorics", and some results have the flavor that in a group $(G,+)$ if $|A+B|=O(|A|+|B|)$ then $A,B$ are approximately subgroups of $G$ (as you mention in your question, Terence Tao's blog discusses some such results, generally speaking set size results can be transferred to the entropy setting).

The case you describe roughly corresponds to the case where $A$ is an integer interval $[a..b]$ and $B$ is an integer interval of the form $[0..c]$  (in fact, if don't try to take advantage of concentration and shoot for a $(1/2)\log n$ entropy bound, one would have $c=1$ and $a=0$ and $b=k$ for $k=1,...,n-1$ as you apply this repeatedly, however actually this will be more like $a \sim k-\sqrt{k}$ , $b \sim k+ \sqrt{k}$). Obviously in this case $|A+B| \leq |A|+c$, but I'm not sure if there is a more general bound this falls from as a special case.


Computing unique subset intersections Given a set S = {si : {zj : z ∈ N} }, what is a time-efficient algorithm for computing the unique sets of intersections of all of the subsets of S?

As per @JeffE's comment below, there are edge cases of exponential output complexity, so the time-efficient measure of complexity should probably be a function of the output length as opposed to |S|. In that case the goal is low order polynomial complexity as a function of the output length and max(|si|), the latter of which affects the complexity of intersection operations.

For background, I am dealing with several versions of this problem, some larger than others. In the smallest one |S| ≈ 1,000, |si| ≈ 10,000 and the values are zip codes.

Tiny example for clarity:

Input: S = {{},{1},{2,3},{3,4,5,6,7,8,9,10}}
Output: {{},{1},{2,3},{3,4,5,6,7,8,9,10},{3}}

|S| = 4 and there are 24 = 16 subsets of S.
However, there are only five unique sets of subset intersections. The first four are the members of S themselves. The fifth is {3}. The empty set is already a member of S. All other 10 subset intersections produce empty sets also.

Let $u$ denote the size of the union of the sets in $S$, $n\leq 2^u$ denote the size of $S$, $h\geq n$ denote the size of the output, and $S_i$ the set of sets resulting of the intersection of $i$ sets from $S$ (in this sense, $S=S_1$), maintained in lexicographical order. For all $i\in[1..n]$, $|S_i|\leq h$.

$S_2$ can be computed in time $un(n-1)/2\leq uh(h-1)/2$: each binary intersection takes at most time $u$, and there are at most $n(n-1)/2$ of them. $S_4, S_8, \ldots$ can be computed in time $uh(h-1)/2$ each in a similar way. Other $S_j$ which are not power of two can be obtained by combining those results, up to $S_n$.

The total running time would be  within $O(unh^2)$?


Recent progress in permutation groups algorithms? I am interested in algorithms for finite groups as implemented in the GAP package. It seems that all known algorithms in this field deal with permutation groups/matrix groups; two fundamental ones are Schreier-Sims [1970] and Butler [1979], see e.g. 'Algorithms for Permutation groups' by Alice Niemeyer as a possible reference (?)

Hence, I was wondering whether there had been significant progress in the field in the last 50 years. I've seen that user NisaiVloot asked some questions about braid groups that may constitute an interesting extension of known results about permutation groups, though it's unclear to me what is the current state of research in this field as the mathematics/algorithmics communities seem somewhat out-of-sync nowadays.

Certainly there has been tons of progress! (And if you really meant to ask about the last 50 years, then that includes the algorithms of Schreier-Sims and Butler that you already mentioned...)

For example, see Seress's book [1], which includes many algorithms that upgrade standard tasks into $\mathsf{NC}$ and/or quasi-linear (sometimes Las Vegas) time, such as membership testing, computing the order, and even computing the entire composition series! The finite simple groups can be recognized in the black-box model [2] (more general/stronger than permutation groups or matrix groups), and permutational isomorphism of permutation groups of degree $n$ can be decided in $O(2^{n} |G|)$ time [3] (prior to that, the best known was the trivial $n! \cdot poly(n)$ algorithm). Many of these results were in the last 20 years, and the latter is even from 2012.

[1] Seress, Ákos
Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003

[2] Babai, László; Kantor, William M.; Pálfy, Péter P.; Seress, Ákos Black-box recognition of finite simple groups of Lie type by statistics of element orders. J. Group Theory 5 (2002), no. 4, 383–401.

[3] László Babai, Paolo Codenotti, Youming Qiao: Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (Extended Abstract). In: Proc. 39th Internat. Colloq. on Automata, Languages and Programming (ICALP'12), Springer LNCS 7391, 2012, pp. 51-62.


Can consume/produce be modeled in linear logic? Question is whether it is possible to model in linear logic
two modes of access to a resource. I know that two modes
of resources are possible, i.e:

$!r \vdash$      r is infinitely available
$r \vdash \quad$       r is only once available

But what if I don't want to decide whether r is infinitely or
only once available. And the query, i.e access, should
decide, so:

$*r \vdash r \quad \quad \quad \quad \quad \quad$ r is only checked (like it were !r)
$*r \vdash consume(r)$  r is consumed (like it were r alone)

Can I model a consume(r) and a normal r access in linear logic?
Similarly I would like to have produce(r) operator, which then
asserts the form *r of a resource.

With non-commutative linear logic (cf. Retoré 1997, for pomset logic), you can model the sequentiality of checking resources and avoid having the resource checking occur within the scope of whatever choice operator you want to use.
For example, you could model your query so:
$$(r; a \vee b) \multimap (c; r)$$
You might interpret this as saying: if I can take $r$ and then consume $a \vee b$, then I can provide $c$ and then free $r$.  Is that the semantics you want?
It looks, unfortunately, like you can't combine non-commutative linear logic with usual linear logic in the sequent calculus and maintain the needed proof-theoretic properties to model planning via proof search.  You can do this is the Calculus of Structures, see (Strassburger, 2003), which has been used for planning (Kahramanogullari 2009).
If you want to go the route of having a modality decorating just $t$, well that might be tricky because you essentially want to be able to look at $r$ without consuming it, and without having it available for unlimited use, which is not a propositional attitude of regular linear logic.  You can try to see if
$$((?r \otimes a) \vee (?r \otimes b)) \multimap c$$
works for you, but it probably won't, because $?r$ is cheaper than $r$ — it is a bit like having a reference ro $r$; and so does not actually ensure that you can put your hands on $r$.  $?!r$ might work better, and is the basis for the two encodings used to model classical logic in linear logic, but to have $r$ doesn't mean you can provide $?!r$.  Looking at one of the various weak exponentials for linear logic might help here.
References

Retoré 1997, Pomset logic: a non-commutative extension of classical linear logic
Strassburger 2003, Linear Logic and Noncommutativity in the Calculus of Structures
Kahramanogullari 2009, On Linear Logic Planning and Concurrency,
Information and Computation 207:1229 - 1258.


How to map random cardesian points in a 2d array I was wondering if there is any algorithm, theoretical or already implemented, or if its even possible at all, where, given N random points (x,y) we can relatively map them in a 2d array where each mapped point in the 2d-array has the property that its neighboring points (at most 8 points around it) are the closest to that point.

I would also like to add an extra restriction that no node in the 2d array is NULL meaning that if we have for example N = 1 Million elements then the 2d array would be sqrt(N) x sqrt(N) or 1000 x 1000 dimension, where each element of that array occupies a point.

In addition, we can also consider sorting, if it can help, as of x-coordinate and as of y-coordinate...

Thanks in advance!

This is impossible in general.

The reason is that the grid-distance is symmetric while being closest neighbors is not a symmetric relation.

If you have many points ($\geq 9$) close to the origin and then a point at, say, $(M,0)$ for some large $M$.

The point at $(M,0)$ has a its closest neighbors as some of the points which are closest to the origin, but these points consider it as the farthest point from them.


Upper bounds on the circut depth Suppose $f:\{0,1\}^n \to \{0,1\}$ is a function such that it can be computed by a circuit of size $n^c$ for some constant $c>0$.

  Q. Is there any nontrivial upper bound on the depth of a circuit of size quasi-polynomial or subexponential computing $f$?

[Too long for a comment, hence, an "answer".]

It seems that, for boolean circuits, only logarithmic in the size improvements of the trivial depth are known: every circuit of size $S$ can be transformed to a circuit of depth $O(S/\log S)$ Paterson and Valiant. For boolean (and arithmetic) formulas, the depth can be reduced to $O(\log S)$ (known as Spira's theorem). For arithmetic circuits, we can do much better than in the boolean case: then the resulting circuit has depth only about $(\log S)(\log d)$ and size $O(S^3)$, where $d$ is the degree of the computed polynomial: Valiant, Skyum, Berkowitz and Rackoff. Earlier, Hyafil (see the citation in the above paper) has obtained a similar upper bound on the depth, but the size increased until about $S^{\log d}$.


Maximum shortest word accepted by pushdown automata Given a fixed alphabet, consider all deterministic pushdown automata with $n$ states that accept a nonempty language. What is the maximum length of the shortest word accepted by a deterministic pushdown automaton with $n$ states (holding alphabet size constant)?

I found an example where the shortest word is $\Omega(n^2)$ and suspect that this bound is tight, but have been unable to prove it. Everything I found online talking about shortest words is talking about finite or two-way automata only, not pushdown automata.

As an example, choose two large prime numbers $p$ and $q$, and two input symbols $a$ and $b$. Create an automaton with a cycle of length $p$ that reads an $a$ and pushes onto the stack, with a transition to a cycle of length $q$ that reads a $b$ and pops from the stack.

By placing the initial and accept states at appropriate places on the first and second cycle, you force the automaton to go through the first cycle $q-1$ times and the second cycle $p-1$ times, so that the maximum stack length is the same modulo $p$ and $q$, and thus the shortest word has length $\Omega(pq)$. Since the automaton has $p+q$ states, this means the shortest word is $\Omega(n^2)$.

The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman).  And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols.  For example, a classic construction turns a grammar like

$S \rightarrow X_1 X_1$

$X_1  \rightarrow X_2 X_2$

$X_2 \rightarrow X_3 X_3$

...

$X_{n-1} \rightarrow X_n X_n$

$X_n \rightarrow a$

into a 3-state machine accepting the language $\{\,a^{2^n}\,\}$ by final state, no matter how many variables there are, or into a 1-state machine accepting by empty stack.  This gives a classic example of how the shortest string can be exponential in the description size of the PDA.


Unary parametricity vs. binary parametricity I've recently become quite interested in parametricity after seeing Bernardy and Moulin's 2012 LICS paper ( https://dl.acm.org/citation.cfm?id=2359499). In this paper, they internalize unary parametricity in a pure type system with dependent types and hint at how you can extend the construction to arbitrary arities.

I've only seen binary parametricity defined before. My question is: what is an example of an interesting theorem that can be proved using binary parametricity, but not with unary parametricity? It would also be interesting to see an example of a theorem provable with tertiary parametricity, but not with binary (although I've seen evidence that n-parametricity is equivalent for n >= 2: see http://www.sato.kuis.kyoto-u.ac.jp/~takeuti/art/par-tlca.ps.gz)

Typically, you use binary parametricity to prove program equivalences. It's unnatural to do this with a unary model, since it only talks about one program at a time.

Normally, you use a unary model if all you are interested in is a unary property. For example, see our recent draft, Superficially Substructural Types, in which we prove a type soundness result using a unary model. Since soundness talks about the behavior of one program (if $e : A$  then it either diverges or reduces to a value $v : A$), a unary model is sufficient. If we wanted to prove program equivalences in addition, we would need a binary model.

EDIT: I just realized that if you look at our paper, it just looks like a plain old logical relations/realizability model. I should say a little bit more about what makes it (and other models) parametric. Basically, a model is parametric when you can prove the identity extension lemma for it: that is, for any type expression, if all of the free type variables are bound to identity relations, then the type expression is the identity relation. We don't explicitly prove it as a lemma (I don't know why, but you rarely need to when doing operational models), but this property is essential for our language's soundness.

The definition of "relation" and "identity relation" in parametricity is actually a bit up for grabs, and this freedom is actually essential if you want to support fancy types like higher kinds or dependent types, or wish to work with fancier semantic structures. The most accessible account of this I know is in Bob Atkey's draft paper Relational Parametricity for Higher Kinds.

If you have a good appetite for category theory, this was first formulated in an abstract way by Rosolini in his paper Reflexive Graphs and Parametric Polymorphism. It has since been developed further by Dunphy and Reddy in their paper Parametric Limits, and also by Birkedal, Møgelberg, and Petersen in Domain-theoretical Models of Parametric Polymorphism.


Commutative operators in unification Say I want to find a unification for the following two sentences in first-order logic:

P(x) & Q(y)
Q(A) & P(B)

Common sense tells us that {x: B, y: A} is such a unification. However, if I apply the standard unification algorithm, then we will go through the following steps:

Attempt to match & with & (succeeds, returns {}, go to step 2)
Attempt to unify P(x) with Q(A) (go to step 3)
Attempt to match P with Q (return failure)

The algorithm returns failure because it doesn't know that & is commutative.

We could fix that by telling our unification algorithm that And and Or are commutative. But more generally we might have a user-defined relation that is commutative, for example

IsRelated(Mother(x),Father(x))
IsRelated(Father(John),Mother(John))

Again, the standard unification algorithm would return failure, even though these terms can be unified.

How is this dealt with in practice, e.g. in theorem provers, or type inference algorithms?

The keywords you want to look into are "AC Unification," "ACU Unification," and "Associative-commutative unification." People have been looking into this for a long time (see this 1987 paper, for example).


Natural relativized worlds The oracles that are used in relativized collapses or separations of complexity classes rarely represent $natural$ algorithmic problems. They are typically constructed "artificially" with techniques like diagonalization, for the sole purpose of achieving the relativized collapse or separation. A notable exception is that for any ${\bf PSPACE}$-complete set $L$ it holds that ${\bf P}^L={\bf NP}^L$. This indeed leads to "natural relativized worlds," since there are  ${\bf PSPACE}$-complete languages that correspond to  natural algorithmic tasks. Generally, I am looking for such examples, where the oracle represents a natural problem. (And, of course, it is not trivially implied by the above example).

In particular, is there any such known "natural relativized world" in which ${\bf P}$ and ${\bf NP}$ are separated?

$Note:$ A random oracle here does not count as natural, because it does not represent a natural algorithmic problem. It rather represents that a statement holds for almost all oracles, regardless to their "naturality."

It seems that there is a confusion in the question between oracles resulting in equality vs. oracles resulting in separation. It is easy to find natural oracles resulting in equality. Oracles for separation is a different matter and your question does not contain an example for them.

We don't have that many techniques for separating complexity classes and relativized separations are no different. The examples you get are expected to result from those techniques so it is unlikely that such oracles are known.

As far as I know, diagonalization is the only method we know of that can separate non-small complexity classes, so no surprise the oracles separating $\mathsf{NP}$ from $\mathsf{P}$ are such sets.


Is the convex combination of two potential games a potential game? My question: is the set of potential games closed under convex combinations?

An n player game with action set $A = A_1 \times \ldots \times A_n$ and payoff functions $u_i$ is called an exact potential game if there exists a potential function $\Phi$ such that:
$$\forall_{a\in A} \forall_{a_{i},b_{i}\in A_{i}} \Phi(b_{i},a_{-i})-\Phi(a_{i},a_{-i}) = u_{i}(b_{i},a_{-i})-u_{i}(a_{i},a_{-i})$$

A game is a general (ordinal) potential game if there exists a potential function $\Phi$ such that:
$$\forall_{a\in A} \forall_{a_{i},b_{i}\in A_{i}} sgn(\Phi(b_{i},a_{-i})-\Phi(a_{i},a_{-i})) = sgn(u_{i}(b_{i},a_{-i})-u_{i}(a_{i},a_{-i}))$$

Say that we have two games on the same action set, with utility functions $u_i$ and $u'_i$ respectively, for each player $i$. For any $0 \leq p \leq 1$, there is a convex combination of these two games, again on the same action set, where the utility function for each player $i$ is now $u^p_i(\cdot) = (1-p)u_i(\cdot) + pu'_i(\cdot)$.

Clearly, the convex combination of two exact potential games is also an exact potential game: just take the same convex combination of the two potential functions.

But is it possible to have two (general) potential games such that their convex combination is not a potential game?

NO.

The following two-player game, with e very close to 0, is a potential game:

(e,0)   (e,1)

(0,0)   (0,e)

Taking the 8 equivalent games (switching the roles of the players / rows / columns), then a convex combination of them gets you as close as you want to any game with positive utilities, like to matching pennies with a positive constant added to each utility.  But that is not a potential game.


Arranging letters to make a word in a regular language Fix a regular language $L$ on the alphabet $\{a, b\}$, and consider the following problem. I am given as input:

some number $m \in \mathbb{N}$ of copies of the letter $a$, and
some number $n \in \mathbb{N}$ of copies of the letter $b$ but each copy $1 \leq i \leq n$ comes with a constraint expressed as a pair of integers $(p_i, q_i)$ which means: "there must be at least $p_i$ $a$'s to the left of this $b$ and at least $q_i$ $a$'s to the right of this $b$".

My goal is to decide if I can construct a word of length $m + n$ with $m$ letters $a$ and $n$ letters $b$ that falls in the language $L$ and where every copy of $b$ was put at a position that satisfies its constraints. (Formally: there is an injective function $f$ from $\{1, \ldots, n\}$ to $\{1, \ldots, n+m\}$ such that, letting $A$ be the elements of $\{1, \ldots, n+m\}$ that are not in the image of $f$, for each $1 \leq i \leq n$, the set $A$ contains at least $p_i$ integers that are $< f(i)$ and at least $q_i$ integers that are $> f(i)$.) Note that the $b$'s can be put in any order (as long as their constraints are satisfied), they needn't be put in the order in which they are in the input. In other words, $f$ need not be an increasing function.

Is this problem in polynomial time for every regular language $L$, or is there a language $L$ for which the problem is NP-hard?

I have a PTIME greedy algorithm that works if $L$ has only one word of every length, e.g., it is something like $(ab)^*$. In this case, you should go over the even positions (where $b$'s must go) and at each position put a copy of $b$ which is available and which is as constrained as possible, i.e., the constraint $p_i$ is satisfied, and the constraint $q_i$ is as large as possible. It is clear that this algorithm respects the constraints if it succeeds, and that this is always the best way to place the $b$'s. However when $L$ contains multiple words of length $m+n$ then this no longer works and I can't see a dynamic algorithm to solve the problem.

(This question relates to this earlier question of mine but the main difference that the alphabet is now restricted to be $\{a, b\}$ so the previous proof does not work. The problem can also be equivalently phrased in terms of topological sorts in which case it is a rephrasing of a problem in this list.)

With an idea by Louis Jachiet, we managed to design a PTIME algorithm for this task. Long story short, it's a dynamic programming algorithm where you sort the $b$'s by decreasing "ending time" (i.e., by increasing $q_i$ above), consider the $b$'s by intervals of "starting time" (the $p_i$ above), and restrict the search to greedy schedulings that follow the idea for $(ab)^*$ given in the question. Somewhat surprisingly, the problem is in PTIME even if the target regular language is also given as part of the input (i.e., not fixed). Also, the algorithm would also work if, instead of copies of the letter $a$, we had a fixed word on some alphabet; however all the $b$'s should be the same symbol.

I'll rephrase the problem of my question to a problem where each $b$ comes with a pair $(s_i, e_i)$ saying that this $b$ must be inserted with at least $s_i$ $a$'s to the left, and strictly less than $e_i$ $a$'s to the left. This is equivalent to the original problem phrasing in the question (take $s_i := p_i$ and $e_i := m + 1 - q_i$  where $m$ is the number of $a$'s), but it is a bit easier to reason with: we can now see the constraints as defining an interval $[s_i, e_i[$ of positions where the insertion can take place. By a position $p$, I mean a position in the word of $a$, i.e., $0 \leq p \leq m$; when we insert multiple $b$'s then they do not change positions of other $b$'s in the word of $a$'s. Besides, since all $b$'s are the same symbol, it suffices to know the position where we insert them; we don't care about the relative positions of the $b$'s that are all inserted at the same position in the word of $a$'s.

I will need to talk about state pair sets of the automaton, which are just sets $S$ containing pairs $(q, q')$ of states. Given a word $w$ over $\{a, b\}$, I will write $\phi(w)$ for the state pair set that it achieves, i.e., all $(q, q')$ such that there is a path from $q$ to $q'$ labeled by $w$, which can clearly be computed in PTIME from $w$ and an automaton representation of the word. Given two state pair sets $S$ and $S'$, I define $S \odot S'$ to be the set of all state pairs $(q, q'')$ that can be obtained by combining a pair of $S$ and of $S'$, formally $S \odot S' = {(q, q'') \mid \exists q', (q, q') \in S \land (q', q'') \in S'}$. Notice that we have $\phi(w w') = (\phi(w)) \odot (\phi(w'))$ for any words $w$ and $w'$. What is more, the question of whether a word is accepted or not boils down to checking whether $\phi(w)$ contains a pair $(q_0, q_f)$ for a final state $q_f$. (What I'm redefining here is basically the transition monoid of the automaton, for those familiar with it.)

I will consider the $b$'s by decreasing ending time $e_i$, and break ties in some arbitrary but consistent way, so when I talk about the $i$-th $b$, with constraints $(s_i, e_i)$, then it is the $i$-th $b$ according to this order that I fixed.

Let me now claim that, if we can achieve a word $w$ by insertions of $b$'s into the $a$'s, then we can achieve the same word $w$ by doing insertions following a greedy strategy: when I insert the $i$-th $b$ at a position $p$ in the word of $a$'s, then all subsequent $b$'s that could also go at that position (i.e., $s_j \leq p < e_j$ for some $j$) are inserted to the left of that position, i.e., their position is $p'$ with $p' \leq p$. Let's see why we can always restrict to greedy strategies without loss of generality. Consider a stategy to do insertions to achieve $w$, and let's see that we can change it into a greedy strategy that achieves the same word. Consider a violation in the current strategy where we insert the $i$-th $b$ at position $p$ (so $p_i \leq p < e_i$) and the $j$-th $b$ (with $j > i$) could also go at that position (so $p_j \leq p < e_j$) but it was inserted to the right, i.e., $p' > p$. Let's see why the $i$-th $b$ can also be inserted at $p'$, which justifies that we can fix that violation by swapping the two insertions, and thus iteratively repair any strategy to a greedy strategy.  By definition of the order, we have $e_j \leq e_i$, so as $p' < e_j$ we have $p' < e_i$. Now, as $p_i \leq p$ and $p < p'$, we have $p_i \leq p'$. So indeed $p \in [p_i, e_i[$ and we can indeed fix the violation by inserting the $i$-th $b$ at $p'$ and the $j$-th $b$ at $p$.

Now I can explain the dynamic algorithm. We will compute, for all $0 \leq i \leq j \leq m$, for all $0 \leq s \leq s' \leq m$, for all $0 \leq k \leq n$ (with $n$ the number of intervals), the set $S(i, j, s, s', k)$ which is the union of the state pair sets over all words that can be obtained by taking the subword of $a$'s from the $i$-th $a$ (included) to the $j$-th $a$ (excluded), performing insertions of $b$'s using exactly the $b$'s with position $i \geq k$ in the order (numbering them from $0$ to $n-1$) and with starting time $s \leq s_i < s'$, and considering the word obtained in this fashion (containing $j - i$ $a$'s and some $b$'s inserted before, after, or between them).

The quantity that we wish to compute to solve our problem is $S(0, m, 0, m, 0)$, telling us what can be achieved by inserting all intervals in the whole word of $m$ $a$'s; we then simply check if there is a pair of the form $(q_0, q_f)$ in the result, with $q_0$ the initial state and $q_f$ a final state.

The base case is the $S(i, j, s, s', n)$, where we ask what can be achieved without any insertions: this is simply the effect of the $a$'s on their own, formally, it is $\phi(a^{j-i})$.

Now, for the inductive step, consider $S(i, j, s, s', k)$ with $k < n$. Consider the $k$-th copy of $b$ and its interval $[s_k, e_k[$. If we don't have $s \leq s_k < s'$, then we are not considering this $b$, so we simply have $S(i, j, s, s', k) = S(i, j, s, s', k+1)$. Otherwise, we are considering the $k$-th $b$, and we claim that:

$$S(i, j, s, s', k) = \hspace{-1cm} \bigcup_{\max(i, s_k) \leq p \leq \min(j, e_k-1)}\hspace{-1cm} S(i, p+1, s, p+1, k+1) \odot \phi(b) \odot S(p+1, j, p+1, s', k+1).$$

In particular, if the interval for the $k$-th $b$ does not overlap with $[i, j[$, then $S(i, j, s, s', k) = \emptyset$ (meaning that we cannot perform the insertions).

To see why this formula holds, observe that we must insert the $k$-th $b$ as we are considering it, and this insertion must be at a position $p$ such that $s_k \leq p < e_k$, so $s_k \leq p \leq e_k-1$, and also we are considering insertions in the subword from the $i$-th $a$ (included) and the $j$-th $a$ (excluded) so $i \leq p \leq j$ (we can insert immediately after the end of this subword of $a$). Now, all remaining $b$'s (strictly after $k$) with starting position in $[s, s'[$ are partitioned between those with starting position in $[s, p+1[$ and those with starting position in $[p+1, s'[$. Let's argue that these $b$'s must be inserted as we claim, i.e., the first ones in the subword of $a$ between $i$ included and $p+1$ excluded (so at or before $p$) and the second ones between $p+1$ included and $j$ excluded (so strictly after $p$). For the second ones, this is clear, as their starting position is $\geq p+1$ so they must be inserted at position $p+1$ or later. For the first $b$'s, either their ending time is $\leq p+1$, in which case they must necessarily be inserted strictly before position $p+1$; or their ending time is $> p+1$, but in this case, as their starting position is $< p+1$, this means that they could legally be inserted at position $p$ where we inserted the $k$-th copy of $b$; now by definition of a greedy strategy, since they come after this $k$-th $b$ in the order which we inserted at a position $p$, then they must be inserted at a position $\leq p$.

Formally, correctness can be shown by showing inductively that the $S(i, j, s, s', k)$ contains the right state pair set: one direction is because what we compute really corresponds to a way to perform the insertions; the other is because any way to perform the insertions is equivalent to a greedy strategy, and all greedy strategies are represented by the above reasoning.

This algorithm clearly establishes that the problem is in PTIME, with complexity like $O(n \times n^4 \times m \times \mathrm{Poly}(A))$ where $A$ is the automaton. We're not claiming that this is optimal. :)


Collision Attacks, Message Digests and a Possible solution I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 certificate duplicate.

From what I can tell in the case of the postscript attack, specific data was generated and embedded within the header of the postscript (which is ignored during rendering) which brought about the internal state of the md5 to a state such that the modified wording of the document would lead to a final MD equivalent to the original. The X.509 took a similar approach where by data was injected within the comment/whitespace of the certificate.

Ok so here is my question, and I can't seem to find anyone asking this question:

Why isn't the length of ONLY the data being consumed added as a final block to the MD calculation?
In the case of X.509 - Why is the whitespace and comments being taken into account as part of the MD?

Wouldn't a simple processes such as one of the following be enough to resolve the proposed collision attacks:

$MD(M + |M|) = xyz$
$MD(M + |M| + |M| * magicseed_0 +...+ |M| * magicseed_n) = xyz$

where :

M : is the message
|M| : size of the message in bits
MD : is the message digest function (eg: md5, sha, whirlpool etc)
xyz : is the pairing of the acutal message digest value for the message M and |M|. <M,|M|>
$magicseed_{i}$: Is a set of random values generated with seed based on the internal-state prior to the size being added.
'+' : is a concatentation operation A+B+C = ABC

This technqiue should work, as to date all such collision attacks rely on adding more data to the original message.

In short, the level of difficulty involved in generating a collision message such that:

It not only generates the same MD
But is also comprehensible/parsible/compliant
and is also the same size as the original message,

is immensely difficult if not near impossible. Has this approach ever been discussed? Any links to papers etc would be nice.

Further Question: What is the lower bound for collisions of messages of common length for a hash function H chosen randomly from U, where U is the set of universal hash functions ?

Is it $1/N$ (where N is $2^{|M|}$) or is it greater? If it is greater, that implies there is more than 1 message of length |M| that will map to the same MD value for a given H.

If that is the case, how practical is it to find these other messages? bruteforce would be of $O(2^N)$, is there a method of time complexity less than bruteforce?

Links:

Postscript: http://www.schneier.com/blog/archives/2005/06/more_md5_collis.html
X.509: http://www.win.tue.nl/~bdeweger/CollidingCertificates/

Note: This question is NOT as easy as it seems. Please read it very carefully and make sure you have understood exactly what is being asked. The answer will require understanding of martingales and distribution ensembles. If you are unsure what these are or how they apply to this particular problem then please do not post answers. Prior knowledge of this class of attack is required, please access the links above and the following: csse question. Please DO NOT focus on answers that relate to generating messages of length different from the original message as any such solution is invalid.

I will attempt an answer, which hopefully interpretes the question correctly and if not, will at least lead to some clarification.

Let's say the hash has an output of size $2^{N}$ and we are hashing messages only of length exactly $2^{M}$.

The last question is the best place to start: what is the probability of a collision with a randomly selected hash? A common analogy used when talking about collisions is balls and bins. The question addresses the scenario where we randomly throw (definition of the hash) $2^{M}$ balls (message space) into $2^{N}$ bins (output space).

I am not clear on the exact question: is it, what is the probability of at least one bin having more than one ball? Or is it, what is the probability that given I just threw a ball into a particular bin that another ball is thrown into the same bin?

The former is simply the birthday problem while the latter is:

$p=1-(1-\frac{1}{2^{N}})^{2^{M}-1}$

Now as the ratio $N/M$ increases, $p$ decreases. We cannot change $2^N$. Any method that lowers $2^M$ will have an effect. This includes restricting messages from any M-bit string to only M-bit strings from a language. Say there are $2^{L}$ admissible strings, $L \leq M$, then just substitute in ${L}$ for $M$ in the equation.

As for the first question of adding the length of the message as a suffix, one can still find a collision of a different length as long as the new collision ends with a suffix equivalent to it's (new) length. This makes finding collisions moderately harder but does not "solve" the collision problem by any means. It is not effective at enforcing the length remains the same, without some outside knowledge of what the length should be.

If the length is known, then this adding the length as a suffix adds redundant information and does not increase $M$ in the above equation.

Finally, I don't know anything about X.509 whitespace.


Certainty of mutual confirmation over faulty channels? This is a very theoretical question, although I am sure the problem pops up in lots of IT and automation applications. Still, I prefer to formulate it in an action-movie scenario (a bit of the Prisoner's Dilemma style).

"You" and "I" are two groups of partisans hiding in two different places in the forest. The enemy are holding some of our guys in a heavily guarded prison. We want to attack the prison and free our comrades, but this can only succeed if both our groups participate. If just one group goes ahead, it will get massacred for nothing.

So we need to be sure we're both going for it. But the only means of communication we have are signal flares, and firing one does not guarantee it will be seen (due to distance, fog, whatever).

I leave aside the issue of the enemy seeing our flares, or firing their own to confuse us - it's just my flares and yours, and my eyes and yours.

Suppose I fire a flare meaning "I'm ready, are you?".  You see my flare and you reply with another, meaning "Yes I'm ready too, let's go for it!". But I will only start if I see your flare, so you cannot start unless you are sure I have seen it. So now I need to fire another flare to confirm I have seen your reply...... and apparently this chain will never end. No matter how long we keep firing our flares, the last (and decisive) one will be unconfirmed.

Any ideas? For starters, does this problem already have a name that's recognizable in information theory?

TIA!

This is known as The Two Generals' Problem (among other, similar names).


Bibliography needed: How many "good" solutions for Knapsack? I am trying to find some related bibliography in the field. If, by chance, my question is easy enough though, a direct answer is more than welcome.

The problem is: Given that the best possible solution for our instance has value $v$, how many solutions have value at least (1 - ε)v? Of course, they should satisfy the constraint of the weight.

I face some difficulties finding the related bibliography in particular, because it seems it is quite often to consider the problem without trying to maximize an associated value but just trying to find the number of solutions in the corresponding linear Diophantine's equation.

Knapsack as in:

maximize $\sum_{i=1}^{n}u_ix_i$,

subject to $\sum_{i=1}^{n}w_ix_i \le W$, $x_i = {0, 1}$

Although, it does not really matter whether it is the 0-1, bounded or the unbounded problem.

What I have found so far and is somewhat related is:

Counting Solutions of CSPs: A Structural Approach
Upper Bounds on the Number of Solutions of Binary Integer Programs

Shooting from the hip here, but I think this might, in fact, be a simple problem to solve in pseudopolynomial time, using dynamic programming (DP). Not sure if that's acceptable, or if you need a polynomial-time algorithm?

  A brief detour: You assume that the optimal value is known, and that $\varepsilon>0$, and I don't know how hard the given counting problem is. If you made no such assumptions, however, you're basically left with (an obvious reduction from) the decision-version of 0-1-knapsack, which is, of course, NP-complete. The question, of course, is whether the additional assumptions are enough to “rescue” the problem from hardness.

My intuition comes from the fact that DP formulations in general are equivalent to path problems (such as shortest/longest path, or the number of paths) in DAGs. I think counting the number of paths from some node $s$ (representing the zero-capacity knapsack and the empty subset of items) that are “long enough,” given some threshold (in your case, $(1-\varepsilon)v$) is quite straightforward as well.

You can formulate it recursively, as follows. Let $G=(V,E)$ be your DAG, let $w(u,v)$ be the edge weight function, let $\ell_\delta(v)$ be the number of $s$-paths ending at node $v$ with a length of at least $\delta$. You then have:

\begin{equation}
\ell_\delta(v) =
\begin{cases}
0 & \text{if $v=s \land \delta > 0\,$;} \\
1 & \text{if $v=s \land \delta \leq 0\,$;} \\
\sum_{u:(u,v)\in E} \ell_{\delta-w(u,v)}(u)& \text{otherwise.}
\end{cases}
\end{equation}

I'm implicitly assuming that all nodes lie on a path from $s$, as they will in your case, but for nodes beside $s$ that don't have predecessors, the sum will simply be an empty sum, which can be assumed to be zero. To implement this, just memoize it or turn it “upside down” and fill the appropriate array.

In the knapsack case, you'd only have two predecessors $u$ to sum over, of course (i.e., the ones representing the solutions with and without the object under consideration in node $v$). The solution will simply be $\ell_{(1-\varepsilon)v}(t)$, where $t$ is the final “corner” of your matrix, with full capacity and the full set of items.


Are there local maxima in the number of moves required to solve a Rubik's Cube? Peter Shor brought up an interesting point in relation to an attempt to answer an earlier question on the complexity of solving the $n \times n \times n$ Rubiks cube. I had posted a rather naive attempt to show that it must be contained in NP. As Peter pointed out, my approach fails in some instances. One potential case of such an instance is where there exists a local maxima in the path length. By this I mean that it may take $S_A$ moves to solve the cube from configuration $A$, and either $S_A$ or $S_A - 1$ moves to solve the cube from any position which can be reached in one move from $A$. Now, this isn't necessarily such a problem if $S_A$ is maximum number of moves required to solve the cube in general (God's Number for that cube), but is definitely a problem if $S_A$ is strictly less than God's Number for that cube. So my question is do such local maxima exist? Even an answer for the $3 \times 3 \times 3$ cube would be of interest to me.

Asking Tomas Rokicki this question immediately yielded the correct answer ("yes, local maxima exist"):

  If a position exhibits total
  symmetry, it is of necessity a local
  maximum (all except the start).  A
  little thought should make it clear
  why this is the case in the QTM [quarter-turn metric].  For
  the HTM [half-turn metric] it's a bit more subtle but not
  too bad.

  ...

  Such a position is pons asinorum,
  which is distance 12 in QTM and
  distance 6 in HTM (U2D2F2B2L2R2).

I don't see why this is the case for the half-turn metric; but for
the quarter-turn metric it is clear.  In a position with total symmetry, all neighboring positions must be at the same path length (since all moves are equivalent by symmetry).  So a position with total symmetry must be either a local maximum or a strict local minimum.  But strict local minima cannot exist... there has to be some move that reduces the distance to the solved state, just by the definition of the distance.  The symmetry argument translates to the $n \times n \times n$ cube, as does the example position provided.


Applications of association schemes to complexity theory and other TCS An association scheme is defined as a pair $(V, R_0,R_1, \ldots,R_{n+1})$ of a set $V$ and relations $R_i$ on $V$ such that

$(x,y) \in R_i$ implies $(y,x) \in R_i$ for all $x, y \in V$.

$R_0 = \{ (x,x) \mid x \in V \}$

If $(x,y) \in R_k$, the number of $z \in V$ such that $(x,z) \in R_i$ and $(y,z) \in R_j$ is a constant $c_{ijk}$ depending on $i$, $j$ and $k$, but not on the choice of $x$ or $y$.

An example of the application of the theory of association schemes to complexity theory is the following result of Evdomikov from 1994:

Under the Generalized Riemann Hypothesis, the irreducible factors of a degree $n$ polynomial over an explicitly given finite field of order $q$ can be found in time $(n^{\log n} \log q)^{O(1)}$.

So... question(s):

Are there other, more recent applications of association schemes to complexity theory, or other TCS?
What is the current state of the art in factoring algorithms of polynomials over finite fields?

Thanks in advance.  I'll be offline for a day or two, I'm afraid.  If there are issues with this question, I'll address them within 72 hours.

One application that I know of is the connection between combinatorial designs (which are related to associative schemes) and coding theory. Delsarte's program in particular has lead to some interesting LP based bounds for codes. I don't know much about these but I remember that Alex Samorodnitsky has worked on these connections (for example, this, this, this and this). Perhaps some expert can shed more light on this.


$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $? While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post:

  If, for every $n$, there exists a relation of the form
  $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
  where $m = poly(n)$, and each of the $a_k$, $b_k$ and $c_k$ are $poly(n)$ in bit length, then factoring has polynomial sized circuits.

In other words, the $(2^n)!$, which has an exponential number of bits, can potentially be represented efficiently.

I have a few questions:

Could someone provide a proof of the above relation, tell me the name and/or provide any references?
If I were to give you $n$, $m$ and each of the $a_k$, $b_k$ and $c_k$, could you provide me a polynomial time algorithm to check the validity of the relation (i.e. is it in $NP$)?

I’ll comment on why a relation as in the question
$$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
(for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can.

The first observation is that a relation as above (and more generally, the existence of poly-size arithmetic circuits for $(2^n)!$) gives a poly-size circuit for computing $(2^n)!\bmod x$ for $x$ given in binary: simply evaluate the sum modulo $x$, using exponentiation by repeated squaring.

Now, if we could compute $y!\bmod x$ for arbitrary $y$, we could factor $x$: using binary search, find the smallest $y$ such that $\gcd(x,y!)\ne1$ (which we can compute using $\gcd(x,(y!\bmod x))$). Then $y$ must be the smallest prime divisor of $x$.

If we only can do powers of $2$ for $y$, we can still try to compute $\gcd(x,(2^n)!)$ for every $n\le\log x$. One of these will be a nontrivial divisor of $x$, except for the unfortunate case when there is an $n$ such that $x$ is coprime to $(2^n)!$, and divides $(2^{n+1})!$. This is equivalent to saying that $x$ is square-free, and all its prime factors have the same bit-length. I don’t know what to do in this (rather important, cf. Blum integers) case.


Implications of approximating the determinant It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space.
What would be the complexity implications of approximating the determinant of a real matrix, of norm at most $1$ ($\left\|A\right\|\leq 1$) in randomized logarithmic space, up to say, a $1/\text{poly}$ accuracy?

In this respect, what would be the "correct" approximation to ask for - multiplicative or additive?  (see one of the answers below).

With a risk of not having understood the details of the question properly: Being able to approximate the determinant within any factor requires being able to decide whether a square matrix is singular or not, which should have some consequences.

For one thing, it gives a randomized test for whether a general graph has a perfect matching (via the Tutte matrix and Schwarz-Zippel). I don't think the latter is known in randomized logspace (e.g., the Complexity Zoo lists bipartite perfect matching as hard for NL).


"All-different hypergraph coloring" - known problem? I am interested in the following problem: Given a set X and subsets X_1, ..., X_n of X, find a coloring of the elements of X with k colors such that the elements in each X_i are all differently colored. More specifically, I am looking at the case where all X_i are of size k. Is this known in the literature under some name?  I am looking for characterizations of colorable instances and results on complexity (P vs. NP-hard). For example, for k=2, colorable instances correspond to bipartite graphs, and thus the problem can be solved in polynomial time.

I believe this is known in the literature as the problem of finding a strong k-coloring for a k-uniform hypergraph.  This should be a good place to start: [PDF].


finding smallest k elements in array in O(k) This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 <= k <= n

I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!

quick notes:
-the order of the k smallest elements is not important
-the elements in the array are number , might be integers and might be not (so no radix sort)
-the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .

Preprocess the array of $n$ values in time $O(n)$:

$i\leftarrow n$
while $i>2$

Compute the median $m$ of $A[1..i]$ in time $O(i)$
partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.
$i \leftarrow \lfloor i/2 \rfloor$

The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$

Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:

$l\leftarrow \lfloor \log_2 k \rfloor$
select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$
partition $A[2^l..2^{l+1}]$ by $x$ in the same time

$A[1..k]$ contains the $k$ smallest elements.

References:

In 1999, Dor and Zwick gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.


P and NP classes explanation through lambda-calculus In the introduction and explanation P and NP complexity classes often given through Turing machine.
One of the model of computation is the lambda-calculus.
I understand, that all of models of computation are equivalent (and if we can introduce anything in terms Turing machine, we can introduce this in terms any model of computation), but I never seen explanation idea P and NP complexity classes through lambda-calculus.
Can anybody explain notions P and NP complexity classes without Turing machine and only with lambda calculus as model of computation.

Turing-machines and $\lambda$-calculus are equivalent only w.r.t. the functions $\mathbb{N} \rightarrow \mathbb{N}$ they can define.

From the point of view of computational complexity they seem to behave differently.
The main reason people use Turing machines and not $\lambda$-calculus to reason about
complexity is that using $\lambda$-calculus naively leads to unrealistic complexity measures, because you can copy terms (of arbitrary size) freely in single $\beta$-reduction steps, e.g. $(\lambda x.xxx)M \rightarrow MMM.$ In other words, single reduction steps in $\lambda$-calculus are a lousy cost model. In contrast, single Turing-machine reduction steps  work great (in the sense of being good predictors of real-world program run-time).

It is not known how fully to recover
conventional Turing-machine based complexity theory in
$\lambda$-calculus. In a recent (2014) breakthrough Accattoli and Dal Lago
managed to show  that
large classes of time-complexity such as $P$, $NP$ and $EXP$ can
be given a natural $\lambda$-calculus formulation. But smaller
classes like $O(n^2)$ or $O(n \, log\, n)$ cannot be presented
using the Accattoli / Dal Lago techniques.

How to recover conventional space   complexity using
$\lambda$-calculus is unknown.


A direct-sum theorem for the non-deterministic communication complexity of inequality? A non-deterministic protocol for the inequality function is a protocol that behaves as follows: Alice and Bob get strings $x,y\in\{0,1\}^n$ respectively, and an untrusted prover is trying to convince them that $x \ne y$ by sending them some proof string $\pi$. The protocol accepts if both Alice and Bob accept $\pi$, and rejects otherwise. The prover should succeed in making the protocol accept if and only if indeed $x \ne y$.

It is well-known that in every such protocol, the string $\pi$ must be of length at least $\log n$. The easiest way to see it is to observe that if this lower bound did not hold, then there would be a deterministic protocol for the equality function that transmits less than $n$ bits. This lower bound is tight, since the prover can choose $\pi$ to be a coordinate $i\in [n]$ suh that $x_i \ne y_i$.

My question is whether the non-deterministic complexity of solving $k$ independent instances of inequality is at least $k\cdot\log(n)$? In other words, is there a direct-sum theorem for the non-deterministic communication complexity of inequality?

Relevant work:
Feder et. al. [FKNN95] proved a general direct-sum theorem for non-deterministic communication complexity. Unfortunately, this theorem only applies to functions whose complexity is $\gg log(n)$, and therefore does not apply to the inequality function. Karchmer et. al. [KKN95] gave an alternative proof for this theorem, which suffers from the same limitation.

References:

[FKNN95] Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan, "Amortized Communication Complexity". SIAM J. Comput. 24(4): 736-750 (1995)

[KKN95] Mauricio Karchmer, Eyal Kushilevitz, Noam Nisan, "Fractional Covers and Communication Complexity". SIAM J. Discrete Math. 8(1): 76-92 (1995)

I think this can be done with $\log n \cdot\log t + t \cdot\log\log t$ bits of nondeterministic communication.

By encoding all strings with an error correcting code, we may assume that whenever we have an input pair $(x,y)$ with $x\neq y$ the two strings differ in a constant fraction of coordinates. Suppose we are given $t$ pairs $(x^j,y^j)_{j\in[t]}$ that we want to certify are all nonequal. By averaging, there is some coordinate $i\in[n]$ that witnesses $x^j_i\neq y^j_i$ for a constant fraction of $j\in[t]$. Iterating this argument we may construct a set $S\subseteq[n]$ of about $|S|=\log t$ coordinates such that for every $j$ there is some $i\in S$ such that $x^j_i\neq y^j_i$. The nondeterministic proof consists of $S$ (which is $\log t\cdot \log n$ bits) and a mapping $[t]\to S$ (which is $t\cdot\log\log t$ bits) that indicates which coordinate in $S$ to use for each of the $t$ input pairs.


Hardest problems to approximate Under some assumptions, it is hard to approximate MAX-CLIQUE within a factor $n^{1-\epsilon}$ for any $\epsilon >0$. Are there any other problems that are known to be equally hard to approximate? I'm particularly interested in unweighted problems.

A similar hardness result is known for the inapproximability of chromatic number [1]. Independent set is hard to approximate as well, since it is $\mathsf{MAX\text{-}CLIQUE}$ on the complement graph. Some problems that are easier to approximate include vertex cover, (connected) dominating set, feedback vertex set, TSP and Steiner tree.

[1] Zuckerman, David. "Linear degree extractors and the inapproximability of max clique and chromatic number." Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. ACM, 2006.


Resources for complexity results for optimization problems in restricted graph classes I am specifically interested in optimization problems in graphs (minimum coloring, maximum clique, maximum matching etc.) and I need a resource (database) which contains complexity results on different graph classes. The best resource that I know is the following:

http://graphclasses.org/

I think this web site is great because it covers all the graph classes, however the results presented (recognition, independent set, domination) in the site and my interests do not match.

I am looking for similar resources.

Thanks.

Get Spinrad's book on efficient graph representations:
http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150

Also check out Li and Vitanyai's book on Kolmogorov Complexity:
http://www.amazon.com/Efficient-Representations-Fields-Institute-Monographs/dp/0821828150

You will get an appriciation for each graph class by studying succinct data structures.  When you understand why certain classes of graphs take less storage than others you gain a great understanding of how to tailor optimization problems on to them.


Is the bitonic sort algorithm stable? I was wondering, is the bitonic sort algorithm stable? I searched the original paper, wikipedia and some tutorials, could not find it.

It seems to me that it should be, as it is composed of merge / sort steps, however was unable to find answer anywhere.

The reason why I'm asking - I was comparing this particular implementation of bitonic sort to the sort implemented in the C++ standard library, for array length 9 it requires 28 comparison / swap operations, while the standard library sort (which is unstable) requires 25. The three extra cswaps do not seem enough to make the sort stable.

No, bitonic sort is not stable.

For this post I will denote numbers as 2;0 where only the part before the ; is used for comparison and the part behind ; to mark the initial position.
Comparison-exchanges are denoted by arrows where the head points at the desired location of the greater value.

As written in the link that @JukkaSuomela posted a stable sorting network needs to avoid swaps of equal values.

When swapping equal values, the bitonic sorter for two values is already unstable:

0;0 ----- 0;1
      |
      v
0;1 ----- 0;0

Of course, this can be fixed when we don't swap equal values:

0;0 ----- 0;0
      |
      v
0;1 ----- 0;1

However, it could happen that the order of two equal elements is swapped without them being compared to each other.

This is exactly the case in this example of a bitonic sorter for 4 values:

1;0 ------ 1;0 ------ 0;2 ------ 0;2
      ^          |          |
      |          |          v
1;1 ------ 1;1 --|--- 1;1 ------ 1;1
                 ||
                 v|
0;2 ------ 0;2 ---|-- 1;0 ------ 1;0
      |           |         |
      v           v         v
2;3 ------ 2;3 ------ 2;3 ------ 2;3

Although we were careful not to swap elements that compared equal (upper left comparison), the merging pass swapped the order of 1;1 and 1;0 which cannot be corrected later on.

This counterexample proves that bitonic sort cannot be stable.


How does the BosonSampling paper avoid easy classes of complex matrices? In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the polynomial hierarchy collapses to the third level.  The motivating problem is sampling from a distribution defined by a linear-optical network; this distribution can be expressed as the permanent of a particular matrix.  In the classical case all entries of the matrix are non-negative, and so a probabilistic polynomial-time algorithm exists, as shown by Mark Jerrum, Alistair Sinclair, and Eric Vigoda (JACM 2004, doi: 10.1145/1008731.1008738).  In the quantum case the entries are complex numbers.  Note that in the general case (when the entries are not required to be non-negative) the permanent cannot be approximated even within a constant factor, by Valiant's classic 1979 result.

The paper defines a distribution $D_A$ defined by a matrix $A$, and a sampling problem

  BosonSampling
  Input: matrix $A$
  Sample: from distribution $D_A$

Using a hardness result seems to be weak evidence for a separation between the classical and quantum worlds, since it is possible that the class of matrices in the specific quantum setup will all be of special form.  They might have complex entries, but may still possess a lot of structure.  There could therefore exist an efficient sampling procedure for such matrices, even though the general problem is #P-hard.

  How does the use of BosonSampling in the paper avoid easy classes?

The paper uses a lot of background I don't have in quantum complexity.  Given all the quantum people on this site, I'd really appreciate a pointer in the right direction.  How would the arguments hold up if one were to discover that the class of complex-valued matrices seen in a specific experimental setup actually corresponded to a class of distributions that was easy to sample from?  Or is there something inherent in the quantum system that guarantees this cannot happen?

Thanks for your question!  There are two answers, depending on whether you're interested in the hardness results for exact or approximate BosonSampling.

In the exact case, we prove that given any n-by-n complex matrix A, you can construct an optical experiment that produces a particular output with probability proportional to |Per(A)|2.  This, in turn, implies that no classical polynomial-time algorithm can sample from exactly the same distribution as the optical experiment (given a description of the experiment as input), unless P#P = BPPNP.  In fact we can strengthen that, to give a single distribution Dn (depending only on the input length n) that can be sampled using an optical experiment of poly(n) size, but that can't be sampled classically in poly(n) time unless P#P = BPPNP.

In the approximate case, the situation is more complicated.  Our main result says that, if there's a classical polynomial-time algorithm that simulates the optical experiment even approximately (in the sense of sampling from a probability distribution over outputs that's 1/poly(n)-close in variation distance), then in BPPNP, you can approximate |Per(A)|2, with high probability over an n-by-n matrix A of i.i.d. Gaussians with mean 0 and variance 1.

We conjecture that the above problem is #P-hard (at the very least, not in BPPNP), and pages 57-82 of our paper are all about the evidence for that conjecture.

Of course, maybe our conjecture is false, and one can actually give a poly-time algorithm to approximate the permanents of i.i.d. Gaussian matrices.  That would be a phenomenal result!  However, the whole point of 85% of the work we did was to base everything on a hardness conjecture that was as clean, simple, and "quantum-free" as possible.  In other words, instead of the assumption

"approximating the permanents of some weird, special matrices that happen to arise in our experiment is #P-hard,"

we show that it suffices to make the assumption

"approximating the permanents of i.i.d. Gaussian matrices is #P-hard."


About the sign-rank of the Minsky-Pappert function Apologies this might be a very trivial thing I am getting confused by!

Firstly in corollary 1.1 (page 3) in this paper, https://eccc.weizmann.ac.il/report/2016/075/ the authors claim that they have given a new proof of the apparently well-known fact that the Minsky-Pappert DNF has an exponentially high sign-rank. They claim that this was previously also proven in this paper by Razborov and Sherstov, http://people.cs.uchicago.edu/~razborov/files/sign.pdf.

But in the Razborov-Sherstov paper I am unable to locate any such claim or proof.
What am I missing? Is this somehow implicit?

The high sign-rank function that Razborov-Shertov display is in their theorem $1.1$ called the "Main Result" on page $2$. This is a depth $3$ $AC^0$ function and not a depth $2$ one like Minsky-Pappert is.
Also on page $2$ a few lines below the statement of Theorem $1.1$ Razborov-Sherstov seem to say that depth $1$ and $2$ $AC^0$ function can only have polynomial sign-rank. This if I am reading correctly implies that the Minsky-Pappert function does not have an exponentially large sign-rank since it is depth $2$ $AC^0$. What is going on?
If true, could anyone kindly link to any reference which gives a pedagogic exposition of the proof that the Minsky-Pappert function has a high sign-rank?

The Razborov-Sherstov paper does use the Minsky-Pappert function as a tool in their final proof on page $16$ whereby they use its pattern matrix to create another matrix which is a submatrix of high sign-rank sitting inside the pattern matrix of their hard function from the "Main Result" quoted above. Its not clear to me if this is somehow implicitly also proving a high sign-rank for the Minsky-Pappert function itself. Is it?

There's the Minsky-Papert function, which is a depth-two formula, OR composed with AND, where the OR is of size $n^{1/3}$ and the AND is of size $n^{2/3}$. I.e., it's $OR_{n^{1/3}}\circ AND_{n^{2/3}}$.

Then there's the particular communication complexity problem studied in the papers you linked, which is now a function of 2 $n$-bit strings $x$ and $y$, where $x$ is given to Alice and $y$ to Bob. This function is $OR_{n^{1/3}}\circ AND_{n^{2/3}} \circ (x \vee y)$, maybe more clearly expressed as

  $\bigvee _{i=1}^{n^{1/3}}\circ \bigwedge_{j=1}^{n^{2/3}} \circ (x_{ij} \vee y_{ij})$

This is the communication problem for which both papers you linked to prove a sign rank lower bound. If you look at Corollary 1.1, they're talking about this function, not the Minsky-Papert DNF.

Note that any communication problem can be represented as a matrix, by having $x$ index rows and $y$ index columns. The papers prove lower bounds on the sign rank of this matrix for the above communication problem. (Rank and sign rank being measures that make sense for matrices.) What Minsky and Papert showed was a sign degree (or threshold degree) lower bound on the Minsky-Papert DNF. Degree (and sign degree) are measures of Boolean functions.


Composition theorem for randomized communication complexity I am currently organizing the literature of composition theorem, and I found the paper by https://www.research.cs.rutgers.edu/~troyjlee/Composition.pdf, in their theorem 5, I find
$$ R_{1/4} (f \circ g^{n}) = \mathcal{O}(RT_{1/4}(f)R_{1/4}(g)\log RT_{1/4}(f)) $$ coming from Nisan's paper http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.6891&rep=rep1&type=pdf, where $RT(f)$ is denoted as query complexity and $R(f)$ is the randomized communication complexity.
However, I am not sure I notice such a conclusion has ever been drawn in Nisan's paper. The closest claim I suppose is the lemma 3, where Nisan claims that

Let $G$ be a family of functions. If a function $f$ can be computed by a circuit consisting of $s$ gates from $G$ then, for all $k$, $R^{k}(f) \leq s \cdot R^{k}_{1/3s}(G)$.

My question is : is it the lemma leading to the theorem 5 of the first paper, and how? Or am I missing something here?

My understanding is that it's not following from [Nisan94], but from [BCW98] (note that there are two citations provided from Theorem 5), specifically their Theorem 2.1. while phrased for quantum, this generalizes to classical models as well.
See Theorem 69 of Troy Lee and Adi Shraibman's survey [LS09], available, e.g., at this address.

[BCW98] Buhrman, Harry; Cleve, Richard; Wigderson, Avi. Quantum vs. classical communication and computation. STOC '98 (Dallas, TX), 63--68, ACM, New York, 1999. Available at https://arxiv.org/abs/quant-ph/9802040
[LS09] Troy Lee and Adi Shraibman, Lower Bounds in Communication Complexity, Foundations and Trends® in Theoretical Computer Science: Vol. 3: No. 4, pp 263-399. 2009. http://dx.doi.org/10.1561/0400000040
[Nisan94] Nisan, N. The communication complexity of threshold gates. Combinatorics, Paul Erdős is eighty, Vol. 1, 301--315, Bolyai Soc. Math. Stud., János Bolyai Math. Soc., Budapest, 1993.


Expansion vs Sparsest cut let $G=(V,E)$ and $S\subsetneq V$ then expansion of set $S$ is

$$\alpha(S)=\frac{|E(S,\overline{S})|}{\min\{|S|,|\overline{S}|)\}}$$
where $\bar{S}=V\setminus{S}$ and $E(S,\bar{S})$ are edges between S and $\bar{S}$.
Expansion of graph G is
$$\alpha(G)=\min_{\emptyset\neq S\subsetneq {V}}\alpha(S)$$
Sparsity $\mathcal S_G$ of graph G is
$$\mathcal S_G=\min_{\emptyset\neq S\subsetneq {V}}\frac{|E(S,\overline S)|}{|S||\overline S|} $$
It is easy to see, that
$$\frac{n}{2} \mathcal{S}_G\leq \alpha(G) \leq (n-1)\mathcal{S}_G$$
where $n=|V|$.
Solution for Expansion Problem is to find set $S\subsetneq V$ such that $\alpha(S)=\alpha(G)$
Solution for Uniform Sparsest Cut Problem is to find set $S\subsetneq V$ such that
$$\frac{|E(S,\overline S)|}{|S||\overline S|}=\mathcal S_G$$.
My question is, is there a graph for which there are different solution for Expansion Problem and for Uniform Sparsest Cut Problem?
Thank you for any ideas ..

I think there may be multiple instances of such graphs. One pathological case that can be constructed is as follows

Consider three disjoint vertex sets S,T,O. S is a single vertex of degree d+1 with all of edges going into the set O, i.e. there are no edges between S and T. Let O be a very large set and let the edges inside O be such that O is a clique. Now the idea is that we will set edges such that T has smaller expansion than S but T will have greater sparsity. So essentially such that S is the smallest sparsity set and T is the smallest expansion. Set up edges such that T is a clique and every vertex in T has d edges going into O. Suppose that |O| and |T| >> d

Now clearly T is the set with smallest expansion (of expansion d) (this is not hard to see because subsets of T and O have a lot of edges going out). Once again the smallest sparsity sets would be either T or S. Sparsity of S = d+1 / |O| + |T| and Sparsity of T = d / |O| + 1 . Given our chosen set of parameters. Sparsity of T > Sparsity of S


Subset sum vs. Subset product (strong vs. weak NP hardness) I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.

Subset Sum: Given $X = \{x_1,...,x_n\}$ and $T$, does there exist a subset $X'$ such that $\sum_{i\in X'}x_i = T$.

Subset Product: Given $X = \{x_1,...,x_n\}$ and $T$, does there exist a subset $X'$ such that $\prod_{i\in X'}x_i = T$.

I always thought the two problems were equivalent -- an instance of SS could be transformed to an instance of SP via exponentiation and an instance of SP to SS via logarithms. This led me to conclude that they both belonged to the same class of NP-hard -- i.e., they were both weakly NP-hard.

Further, it appears that the same recurrence could be used to solve both problems using dynamic programming with a very small change (replacing subtraction in SS with division in SP).

That was until I read chapter 8 of "Theory of Computation" by Bernard Moret (for those without the book, it has a proof of hardness of subset product via X3C -- a strongly NP-hard problem).

I understand the reduction, but cannot figure out what was wrong with my earlier conclusion (equivalence of the two problems).

UPDATE: Turns out that subset product is only weakly NP-complete (the target product is exponential in $\Omega (n)$). Gary and Johnson published this in their NP-completeness column in 1981, but I guess it was less visible than their earlier claim in their book.

Firstly, using exponentiation to go from SS to SP works (using base 2 rather than base $e$), but blows up the size of the numbers involved. Weak NP-hardness means that if the numbers are small (or more precisely, denoted in unary), the problem is no longer hard. Hence, using exponentiation creates exponentially sized instances of SP even for the easy instances of SS, where the numbers are written in unary.

Secondly, using logarithms to go from SP to SS doesn't work, as logarithms typically generates non-integer values. SS and SP are defined using integer numbers, and logarithms often result in transcendental values, which are hard to represent or do math on.

<edit>

Let $A$ be an integer, $A > 0$, then $\log_2 A$ is rational if and only if $A$ is a power of 2, and transcendental otherwise. Firstly, if $\log_2 A = \frac{p}{q}$ for nonzero integers $p$ and $q$, then $A = 2^{\frac{p}{q}}$, $A^q = 2^p$. We therefore have that $A = 2^r$ by prime decomposition. Furthermore $A^{rq} = 2^p$, so given an $A$ we can pick $q=1$ and $p=r$ to prove $\log_2 A$ is rational.

We just need to show that $\log_2 A$ is never transcendental otherwise. This follows from the Gelfond-Schneider theorem, for an equivalent formulation (as can be found on the Wiki page) is "if $\alpha$ and $\gamma$ are nonzero algebraic numbers, and we take any non-zero logarithm of $\alpha$, then $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ is either rational or transcendental." It is also easy to verify by taking the converse of the theorem and setting $\alpha^\beta = \gamma$ and hence $\beta = \log_\alpha \gamma$.

</edit>

Lastly, consider what happens when we try the dynamic programming algorithm from SS on SP. Because we use products rather than sums, the numbers involved blow up enormously, and the arbitrary precision math required suddenly becomes a factor in the running time. This is why the algorithm cannot solve SP instances quickly even if the numbers are in unary.


Can Suffix trees be used to find all common substrings? I am trying to use suffix trees to compare string sequences. I have found implementations/theory for the longest common sub string problem using suffix trees.
However, What i am looking for is a discussion of the related problem - "all common substrings".
Specifically, I have a problem in which i need to first find the longest common substring, then find the next longest common substring that does not include the already found lcs indices, and so on until a minimum length. Is this problem solvable by constructing the Generalized suffix tree (GST) only once for the two sequences. I know it can be solved by repeatedly constructing a GST after every iteration of finding and removing the LCS. But, I am wondering if i am missing a neat trick where in the GST is constructed only once.

Yes, suffix trees can be used to find all common substrings. I would say to use a suffix array instead, but if you already have a suffix tree, building a suffix array from a suffix tree takes linear time by DFS. So the rest of my answer will assume we are working with a suffix array.

Given a text $S = s_1 , ..., s_n$, a suffix array for $S$ is an array of integers of range $0$ to $n$ specifying the lexicographic ordering of the $n+1$ suffixes of the string $S$\$

We want to couple the suffix array with the $LCPs$, the longest common prefixes. We can construct the array of $LCPs$ in linear time as mentioned in the paper by Kasai et al. Suffix arrays and their lcp arrays line up together in a way that given an index into the lcp array say $lcp[k]$ where $k$ is the index number, then $sa[k]$ will be the start of one instance of the common substring and $sa[k-1]$ will be the start index of the second instance. The length is of course the value in the lcp array.


Current parallel models for computation The 1980's gave rise to both the PRAM and the BSP models of parallel computation. It seems that both model's heyday were during the late 80s and early 90s.

Are these areas still active in terms of research for parallel algorithms? Are there newer more sophisticated models for parallel computation? Are general models still in vogue, or are researchers trying to specialize with GPGPU or Cloud based computation coming in fashion?

I apologize beforehand for the blog-post format of my answer. I couldn't help myself making a small overview of the parallel computing world.

You can categorize parallel programming models in roughly two categories: control-flow and data-flow models.

The control-flow models try to make parallelism work within the context of a explicit-control program, basically every programmable computer today.  The fundamental problem being tackled is that such a 'Von Neumann architecture' was not designed for parallel execution, but efficient sequential computations.  Parallelism in such context is obtained by duplicating parts of the basic modules (memory, control, arithmetic).

Duplicating only arithmetic gives you SIMD instructions, all ALUs share the same Program Counter (PC) and thus always execute the same operation in parallel, albeit on different data.

Duplicating ALU and the PC but keeping the instruction sequencer inside the control unit gives you Out of Order (OoO) execution that yield some pipeline-parallelism. In this category you also have the Very Long Instruction Word (VLWI) and branche-prediction techniques. You rarely see this category at a software level though.

Going a bit further is duplicating the whole 'core' but keeping the memory shared, these are the current multicore processors that give you task (or thread) parallelism.  Sharing memory in this context gives you very, very hard and subtle concurrency issues.  Parallel computations on current multicore are thus completely revolving around synchronization/concurrency problems, the careful balance of performance (no sync) and desired semantics (totally synchronized, sequential execution semantics). Examples of this is the PRAM or more popular these days the Cilk ofshoots such as fork/join (IntelTBB, Java.Utils.Concurrency). CSP and Actor models are concurrency models, but as mentioned above concurrency and parallelism become blurred in a shared-memory environment. n.b. parallelism is for performance, concurrency to maintain correct semantics.

Duplicating memory too gives you either networked computers that get programmed with MPI and its ilk or just strange non-Von Neumann architectures such as the network-on-a-chip processors (cloud processor, the Transputer, Tilera). Memory models such as UMA or NUMA try to maintain the illusion of shared memory and can exist on either software or hardware level. MPI maintains the program-level parallelism and only communicates via message passing. Message passing is also used on a hardware level for communication and concurrency (Transputer).

The second category are data-flow models. These were designed at the dawn of the computer age as a way to write down and execute parallel computations, avoiding the Von Neumann design.  These have fallen out of vogue (for parallel computing) by the '80s after sequential performance rose exponentially. However, a lot of parallel programming systems such as Google MapReduce, Microsoft's Dryad or Intel's Concurrent Collections are in fact dataflow computational models.  At some point they represent computations as a graph and use that to guide execution.

By specifying parts of the models you get different categories and semantics for the dataflow model. What do you restrict the shape of the graph to: DAG (CnC, Dryad), tree (mapreduce), digraph?  Are there strict synchronization semantics (Lustre, reactive programming]? Do you disallow recursion to be able to have a static schedule (StreaMIT) or do you provide more expressive power by having a dynamic scheduler (Intel CnC)? Is there a limit on the number of incoming or outgoing edges? Do the firing semantics allow firing the node when a subset of the incoming data is available? Are edges streams of data (stream processing) or single data tokens (static/dynamic single assignment). For related work you could start by looking at the dataflow research work of people like Arvind, K. Kavi, j. Sharp, W. Ackerman, R. Jagannathan, etc.

Edit: For the sake of completeness. I should point out there are also parallel reduction-driven and pattern-driven models. For the reduction strategies you broadly have graph-reduction and string-reduction. Haskell basically uses graph-reduction, which is a very efficient strategy on a sequential shared-memory system. String-reduction duplicates work, but has a private-memory property that makes it better suited to being implicitly parallelized. The pattern-driven models are the parallel logic languages, such as concurrent prolog. The Actor model is also a pattern-driven model, but with private memory characteristics.

PS. I use the term 'model' broadly, covering abstract machines for both formal and programming purposes.


Avarage classes for PP (probabilistic polynomial time) and PPT machines running in expected polytime i have some question concerning the class PP and PPT machines.

1) PP is defined as the class of problems $L$ for wich exist a probabilistic turing machine running in polytime with error probability < 1/2.

I would like to know if there exists a complexity class that says in the following way (or something similar). "The class of problem $L$ for wich exist a probabilistic turing machine running in expected(or avarage) polytime with error probability < 1/2."
I took a look at complexity zoo, papadimitriou and arora-barak books but nothing seems concerning this aspect.

2) Concerning Goldreich09 it seems that Expected Probabilistic Polinomial Time (EPPT) is defined regarding a strategy. Are there alternatives definition of EPPT not related to adversaries and interactive machines or EPPT is strictly linked with strategies and adversaries?

By question arises for the following reason. In Feige phd thesis there is written (page 10):

  A probabilistic Turing Machine is expected polynomial time, if for any input, its expected running time (over random flips) is polynomial.

This definition don't say anything about adversaries.

the first question then follows. can we create a complexity set of problem by using Probabilistic TM running in EPPT?

Thank in advance.

(This is a more detailed version of my comment on the question.)

As for your question 1, your class is R, the class of decidable problems.  Expected polynomial time is not a useful resource restriction when you allow unbounded error.

To prove that your class contains R, consider a language L∈R.  Let M be a Turing machine for L which halts on every input.  Then we construct a probabilistic Turing machine M′ which runs in expected polynomial time as follows:

Simulate one step of M.  If M accepts, then accept.  If M rejects, then reject.  If M has not halted, continue.
Halt and accept with probability 1/4, halt and reject with probability 1/4, and go to step 1 with probability 1/2.

It should be easy to see that if M halts after t steps, then M′ surely halts before executing step 1 more than t times, and that the probability of error is at most 1/2−1/2t < 1/2.  The expected number of times step 1 is executed is 2(1−1/2t) < 2, and therefore M′ runs in expected constant time.

To prove that your class is contained in R, first note that finite expected running time implies that the probabilistic Turing machine halts with probability 1, and therefore your requirement implies that the machine halts with the correct answer with probability greater than 1/2.  Simulate the probabilistic Turing machine, accumulating the probability of acceptance p and the probability of rejection q.  Because the machine gives the correct answer with probability greater than 1/2, either p or q exceeds 1/2 eventually, and at this point we can stop the simulation and give the correct answer.  (For more details, see this answer by Karolina Sołtys.)


Counterintuitive results for undergraduates I am looking for examples of results which go against people's intuition for a general audience talk. Results which if asked from non-experts "what does your intuition tell you?", almost all would get it wrong. Results' statement should be easily explainable to undergraduates in cs/math. I am mainly looking for results in computer science.

What are the most counterintuitive/unexpected results (of general interest) in your area?

For a general audience you have to stick to things that they can see. As soon as you start theorizing they'll start up their mobile phones.

Here are some ideas which could be worked out to complete examples:

There is a surface which has only one side.
A curve may fill an entire square.
There are constant width curves other than a circle.
It is possible to color the plane with three colors in such a way that every border point is a tri-border.

If you can rely on a bit of mathematical knowledge, you can do more:

There are as many odd numbers as there are natural numbers.
There is a continuous and nowhere differentiable function.
There is a function $f : \mathbb{R} \to \mathbb{R}$ which is discontinuous at all rational numbers and differentiable at all irrational numbers.
The Banach-Tarski "paradox".

For programmers you can try:

The impossible functionals: there is a program which takes a predicate p : stream → bool, where stream is the datatype of infinite binary sequences, and returns true if and only if p α is true for all streams α (that's uncountably many), and false otherwise.
It is possible to play poker by telephone in a trusted way which prevents cheating.
A group of people can calculate their average salary without anybody finding out any other person's salary.
There is a program which constructs a binary tree $T$ with the following properties:

the tree $T$ is infinite
there is no program that traces an infinite path in $T$


What's the complexity to check whether a matrix is Diagonalizable? Given an $n\times n$ matrix $A$ with rational entries. What's the complexity to check $A$ is diagonalizable?

I suspect that this can be done in P, but I do not know any reference. However, a more interesting question is, is there any better complexity class to capture this problem?

Any guidance/comment is welcome! Thanks.

You can do this in uniform NC, see:

G. Villard. Fast parallel algorithms for matrix reduction to canonical forms. AAECC 8:511-537, 1997. http://link.springer.com/article/10.1007%2Fs002000050089


Is there any connection between the diamond norm and the distance of the associated states? In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such as the trace distance, fidelity, etc. The Jamiołkowski isomorphism provides a duality between quantum channels and quantum states.

This is interesting, to me at least, because the diamond norm is notoriously hard to calculate, and the Jamiołkowski isomorphism would seem to imply some correlation between distance measures of quantum channels and quantum states. So, my question is this: Is there any known relation between the distance in the diamond norm and the distance between the associated states (in some measure)?

For a quantum channel $\Phi$, let us write $J(\Phi)$ to denote the associated state:
$$
J(\Phi) = \frac{1}{n} \sum_{1\leq i,j \leq n} \Phi(|i \rangle \langle j|) \otimes |i \rangle \langle j|.
$$
Here we are assuming that the channel maps $M_n(\mathbb{C})$ (i.e., $n\times n$ complex matrices) to $M_m(\mathbb{C})$ for whatever choice of positive integers $n$ and $m$ you like.  The matrix $J(\Phi)$ is sometimes called the Choi matrix or Choi-Jamiolkowski representation of $\Phi$, but it is more frequent that those terms are used when the $\frac{1}{n}$ normalization is omitted.

Now, suppose that $\Phi_0$ and $\Phi_1$ are quantum channels.  We may define the "diamond norm distance" between them as
$$
\| \Phi_0 - \Phi_1 \|_{\Diamond} =
\sup_{\rho} \: \| (\Phi_0 \otimes \operatorname{Id}_k)(\rho) - (\Phi_1 \otimes \operatorname{Id}_k)(\rho) \|_1
$$
where $\operatorname{Id}_k$ denotes the identity channel from $M_k(\mathbb{C})$ to itself, $\| \cdot \|_1$ denotes the trace norm, and the supremum is taken over all $k \geq 1$ and all density matrices $\rho$ chosen from $M_{nk}(\mathbb{C}) = M_n(\mathbb{C}) \otimes M_{k}(\mathbb{C})$.  The supremum always happens to be achieved for some choice of $k\leq n$ and some rank 1 density matrix $\rho$.

(Note that the above definition does not work for arbitrary mappings, only those of the form $\Phi = \Phi_0 - \Phi_1$ for completely positive maps $\Phi_0$ and $\Phi_1$.  For general mappings, the supremum is taken over all matrices with trace norm 1, as opposed to just density matrices.)

If you don't have any additional assumptions on the channels, you cannot say too much about how these norms relate aside from these coarse bounds:
$$
\frac{1}{n} \| \Phi_0 - \Phi_1 \|_{\Diamond} \leq
\| J(\Phi_0) - J(\Phi_1) \|_1 \leq \| \Phi_0 - \Phi_1 \|_{\Diamond}.
$$
For the second inequality, one is essentially settling for the specific choice
$$
\rho =
\frac{1}{n} \sum_{1\leq i,j \leq n} |i \rangle \langle j| \otimes |i \rangle \langle j|
$$
rather than taking the supremum over all $\rho$.  The first inequality is a bid tougher, but it would be a reasonable assignment question for a graduate course on quantum information.  (At this point I should thank you for your question, because I fully intend to use this question in the Fall offering of my quantum information theory course.)

You can achieve either inequality for an appropriate choice of channels $\Phi_0$ and $\Phi_1$, even under the additional assumption that the channels are perfectly distinguishable (meaning $\| \Phi_0 - \Phi_1 \|_{\Diamond} = 2$).


Reference request: Classical analog of quantum threshold theorem For quantum circuits, once the gate error is below a threshold, the error probability of an entire computation can be driven exponentially small with polylog costs in time and space:

http://arxiv.org/pdf/quant-ph/9611025v2.pdf

The classical version should be entirely analogous, and was presumably proven long before the quantum case.  Who proved the classical version?

The classical theory of fault tolerance was pioneered by John von Neumann. I think this is the original reference:

von Neumann, J. (1956). "Probabilistic Logics and Synthesis of Reliable Organisms from Unreliable Components", in Automata Studies, eds. C. Shannon and J. McCarthy, Princeton University Press, pp. 43–98


Why isn't the decrease key operation in a pairing heap $O(1)$ According to the paper (1986)

Decrease-key is implemented by first by removing the node from the tree $O(1)$, decreasing the key $O(1)$, then linking it with the root node $O(1)$. The paper admits this as well.

I must be missing something since this paper shows that it is $\Omega(\log \log n)$ amortized.

An operation can have higher amortized cost than actual cost if it adds too many coins (in the banker's method) or too much potential (in the physicist's method). The lower bound paper you linked to includes the line:

  Decrease-key and insertion operations are both considered to have 0 actual cost.


Notation of sequences in rate distortion theory I have been reading whatever sources I could get my hands on today, regarding this problem.
Most notes online about rate distortion theory come from the book Elements of Information Theory by Thomas M. Cover and Joy A. Thomas. The book seems well regarded so  I assume i am misunderstanding something.

I.e the following slides. I am confused by the notation - which comes from the book. If we look at slides 14 and 16 in the slides deck linked. Firstly on slide 14 they denote a sequence of random variables (i.e a sequence of bits, as far as I understand) as $X^n$
$$
X^n = (X_{1}, \ldots, X_{n}), \quad X_{n} \sim p(x)
$$
and the codeword for that sequence as $\hat{X}^n$.  Now moving on to slide 16 they seem to mix between $X^n$ and $x^n$ i.e they mention that the distortion between sequences
$$
d\left(x^{n}, \hat{x}^{n}\right)=\frac{1}{n} \sum_{i=1}^{n} d\left(x_{i}, \hat{x}_{i}\right)
$$

And distortion for a $\left(2^{n R}, n\right)$ code:
$$
D=E d\left(X^{n}, g_{n}\left(f_{n}\left(X^{n}\right)\right)\right)=\sum_{x^{n}} p\left(x^{n}\right) d\left(x^{n}, g_{n}\left(f_{n}\left(x^{n}\right)\right)\right)
$$

but as far as i can $x^n$ and $X^n$, and consequently $\hat{x}^n$ and $\hat{X}^n$ denote the same thing? What is the idea behind this, if any?  It would make more sense to me to keep the capitalization consistent unless I am missing something? This notation is consistent across all sources I could find.

In information theory notation, capital letters such as $X$ denote random variables, and lowercase letters such as $x$ mean their possible outcomes (i.e., fixed values). For example you can write the definition of expectation as $E[X] = \sum p(x) \cdot x$. Moreover, vector values are denoted using length as superscripts, for example $X^n$ means $(X_1, \ldots, X_n)$ (similarly for $x^n$). Moreover a substring $(X_i, \ldots, X_j)$ is often denoted by $X_i^j$. These slides seem to be consistent with this convention.


If you have a casual conversation with someone and it leads to a paper, what do you owe them? What if you had a casual conversation with someone, and that conversation lead to your findings?

What do you owe them?  When is it plagiarism?  I read somewhere that "first to submit, wins" - so basically the first to publish owns the idea.  Is this true?

The problem with this question is that it is way too vague. Suppose you have a casual conversation, and somebody says "I've been looking at Trudeau gadgets, and I think I can show that they all have a canonical commuting umbrella." If you then publish a paper showing that all Trudeau gadgets have a canonical commuting parasol, there is no question that this is unethical, even if you didn't hear all the details of his proof. (Things like this have happened occasionally, and sometimes the unethical author gets away with it, but I'm not sure doing this is good for your career ... people will probably hear about it).

However, suppose you are having a casual conversation about your research, and you explain to somebody what a Trudeau gadget is, and she says "That reminds me of Smith's umbrella theorem." You then look up Smith's umbrella theorem, and it is exactly what you need to prove your result. Here, it would be nice to thank her in the acknowledgments of your paper, but you certainly don't need to make her a coauthor.

So there is really no way to answer this question without knowing more details.


Is my language Turing-complete? Consider a language like Brainfuck but without the brackets. At the end of each line (i.e. when "\n" occurs), if the current cell is not 0, then the line is re-executed.

An example of an infinite loop:

+.
// OUTPUT (numbers represent the corresponding ascii characters)
1
2
3
...

Now, would this hypothetical language be Turing-complete? I'd say yes but I'm not sure, since there's no such a goto thing at all, only while-like.

Here's a proof that the language is not Turing-complete: its Halting problem can be solved for all programs in your language. This language contains only single loops in sequence, and each loop consists of a finite number of numeric changes to the tape contents. I will gloss over the fact that BF is an 8-bit language, and grant you that the tape contents are all numbers $z \in \mathbb{Z}$. Let $(\alpha_k, \beta_k) \in \mathbb{Z}^{2}$ denote the interval of the tape walked on in statement #k, and let $\nabla_k \in \mathbb{Z}$ denote the amount the tape head moves during each iteration of statement #k. For example, for statment <+>>->+\n, $(\alpha_k, \beta_k) = (-1,3)$ because it moves one item to the left and 2 to the right, plus 1 for the position on which it started, and the net position change is $\nabla_k = 2$. Now, every statement can only increase and decrease its surrounding tape with some vector $v_k \in \mathbb{Z}^{\beta_k-\alpha_k}$, so the program reduces to following simple code:

Input: Infinite tape of zeros, except for a sequence $x$ of numbers starting at position 1

p = 1; // initial tape position

for k = 1..n {

$\quad$while (Tape[p] != 0) {

$\quad\quad$Tape[$p - \alpha_k$ : $p + \beta_k-1$] += $v_k$;

$\quad\quad$p += $\nabla_k$;

$\quad$}

}

Of particular interest is $v_{k,\nabla_k}$ and $v_{k, 2\nabla_k}$ and so forth, because they are the amount the machine will change the items it will inspect next. Now it is easy to solve the Halting problem for any program in your language. Suppose we are have arrived at statement #k and have tape contents Tape, with the tape head at $p$. If $\nabla_k$ = 0, then the head does not move in this loop, and we need only check whether T[$p$] - $m \times v_{k,-\alpha_k} = 0$ for some integer m. If $\nabla_k \not= 0$, then the machine will move across the tape at constant speed. Two things can happen: Tape[$p$] can become zero before the tape head reaches the end of the thus-far written tape - which can be checked in finite time - or it moves past the end of the tape into the unwritten region, at which point it must start repeating itself, which can also be checked in finite time (note that this must be on the positive side of the tape, with $p>0$, otherwise the head has fallen off the tape. It is possible to consider a two-way infinite tape for your language, but the argument still holds). It must start repeating itself in the sense that the contents in Tape[$p - \alpha_k$ : $p + \beta_k$ - 1] must be equal to that of the pervious iteration of loop #k. This is because once arrived in the unwritten region, Tape[$p + \beta_k$] = $v_{k, \beta_k}$, and Tape[$p + \beta_k - \nabla_k] = v_{k,\beta_k} + v_{k, \beta_k - \nabla_k}$, and so forth.

Solving this problem for all statements in a program decides whether that program halts. It is an interesting language nonetheless, and I wonder whether there are programs which have worst-case running times of $\Omega(|x|^2)$, although probably not, and where in the complexity landscape lies the set of languages decided by programs in this BF variant.