randomness extraction of real valued sequences of numbers I have a sequence of numbers $x_1, x_2, \dots, x_n, \dots \in \mathbb{R}$ I would like to extract fair bits from that sequence.

My first thought was to use the Von Neumann extractor.  For a sequence of 0 and 1,

divide sequence into pairs
eliminate all occurrences of 00 and 11
apply transformation 01 → 1 and 10 → 0

This produces a sequence of fair bits from biased bits *even if you do not know the bias $p = \mathbb{P}[x_i = 1]$ as long as your sequence is

a Bernoulli trial
independently distributed
identially distributed

The sequence of numbers I have is the hourly readings from a sensor, so it exhibits cyclic behavior every 24 hours + every week.  If I compute the expected value over time, it may be possible to subtract out the daily and weekly cycles leaving sequence of loosely self-correlated real numbers.

How can I extract randomness from here in a simple way?

First, it depends how the quantization of the real values is performed.
Using 8 bits can be really different from using 16 for example.

Assuming that a fixed number of bits is chosen, hash functions are a good and simple way to extract randomness.

Universal Hash Functions are families of hash functions that can be securely used in this context (not all hash functions are suitable for this).


parallelizable fast matrix in-place transposition what is the current state of the art in fast and parallel matrix in-place transposition?

I would be very happy, if I could be given some pseudocode for this problem. As far as I could find papers, they do not include very detailed descriptions.

Thanks!

PS:
Of course, we do not restrict to square matrices, but rather arbitrary rectangular matrices. Their memory layout is usually a linear sequence of entries in the memory (say, as in C) and it is a highly non-trivial task to convert this data block in-place/in-situ to the sequence that corresponds to the transposed matrix.

Some information can be found in this wikipedia article, whose references I did not find to be very helpful though: Wikipedia Entry.

Sorry, no pseudocode, but a recent paper with a fast parallel algorithm, to appear in ACM Transactions on Mathematical Software:

@Article{Gustavson:2011:PCE,
  author =       "Fred Gustavson and Lars Karlsson and Bo K{\aa}gstr{\"o}m",
  title =        "Parallel and Cache-Efficient In-Place Matrix Storage Format
                  Conversion",
  journal =      "{ACM} Transactions on Mathematical Software",
  accepted =     "8 July 2010",
  upcoming =     "true",
  abstract =     "
                  Techniques and algorithms for efficient in-place
                  conversion to and from standard and blocked matrix
                  storage formats are described. Such functionality is
                  required by numerical libraries that use different
                  data layouts internally. Parallel algorithms and a
                  software package for in-place matrix storage format
                  conversion based on in-place matrix transposition are
                  presented and evaluated. A new algorithm for in-place
                  transposition which efficiently determines the structure
                  of the transposition permutation a priori is one of the
                  key ingredients. It enables effective load balancing in
                  a parallel environment.",
}

Here is the journal page, and here is a pdf version of the paper.
I hope this can be useful.

Load two blocks that fit in cache then write them back out transposed? Depends on how they are stored if you want a parallelization.


Uses of $\infty$-categories in TCS I'm not a theoretical computer scientist. I'm a stable homotopy theorist using $\infty$-categories. I've seen applications of category theory and topos theory to theoretical computer science, and I was wondering if there was any way one could use $\infty$-categories (and preferably for me, stable homotopy theory) in theoretical computer science. I think HoTT mught be one such application, but I may very well be wrong because I know close to nothing about HoTT. (So I also don't know how HoTT is used in TCS.)

Applying higher homotopy-theoretic ideas to CS is still a very nascent field! My understanding is that it's not even that old as a mathematical field.

Certainly HoTT is the central impetus for such ideas. Even there though, there only have been few applications of category theory of "dimension" higher than 2.

One nice "computer science-y" one is Homotopical Patch Theory by Anguili et al. They show that some common operations and properties inherent git like version control systems can be best understood using homotopy type theory.

Another rather unrelated train of thought is some interesting work on the relationship between (2-)Homology theory and confluence of term rewrite systems (or more complex structures such as higher algebras). Some examples are

Y. Guiraud Confluence of linear rewriting and homology of algebras .

Y. Lafont & A. Proute Church-Rosser property and homology of monoids.

this attempts to sketch out more general connections. some of this program can be considered a very recent & more elaborate extension of the old Curry-Howard correspondence noted between proofs and programs. there is also a close connection with automated theorem proving (aka proof assistants). many techniques used in automated theorem proving proofs are not on entirely solid mathematical ground and homotopy theory adds firmer grounding.

this proposal by a sizeable team captures/ surveys much of the currently known connections with CS: Homotopy Type Theory:
Unified Foundations of Mathematics and Computation (MURI Proposal)

Licata from that team is esp interested in computer scientific applications of homotopy theory. some of his talks, and one by Voevodsky founder of the standout Univalence axiom:

Mathematical and Computational Applications of Homotopy Type Theory. Colloquium at University of Iowa. November, 2013. [slides]
Computer-Checked Proofs in the Logic of Homotopy Theory. Invited Talk at the Association for Symbolic Logic North American Meeting. May, 2013. [slides]
Programming and Proving in Homotopy Type Theory. Colloquium at Wesleyan, Princeton, and Cornell. Spring, 2013. [slides]
Computer Science and Homotopy Theory, 10m video lecture by Voevodsky / IAS


One Stack, Two Queues background

Several years ago, when I was an undergraduate, we were given a homework on amortized analysis. I was unable to solve one of the problems. I had asked it in comp.theory, but no satisfactory result came up. I remember the course TA insisted on something he couldn't prove, and said he forgot the proof, and ... [you know what].

Today, I recalled the problem. I was still eager to know, so here it is...

The Question

  Is it possible to implement a stack using two queues, so that both PUSH
  and POP operations run in amortized time O(1)? If yes, could you tell
  me how?

Note: The situation is quite easy if we want to implement a queue with two stacks (with corresponding operations ENQUEUE & DEQUEUE). Please observe the difference.

PS: The above problem is not the homework itself. The homework did not require any lower bounds; just an implementation and the running time analysis.

I don't have an actual answer, but here's some evidence that the problem is open:

It's not mentioned in Ming Li, Luc Longpré and Paul M. B. Vitányi, "The power of the queue", Structures 1986, which considers several other closely related simulations
It's not mentioned in Martin Hühne, "On the power of several queues", Theor. Comp. Sci. 1993, a follow-on paper.
It's not mentioned in Holger Petersen, "Stacks versus Deques", COCOON 2001.
Burton Rosenberg, "Fast nondeterministic recognition of context-free languages using two queues", Inform. Proc. Lett. 1998, gives an O(n log n) two-queue algorithm for recognizing any CFL using two queues. But a nondeterministic pushdown automaton can recognize CFLs in linear time. So if there were a simulation of a stack with two queues faster than O(log n) per operation, Rosenberg and his referees should have known about it.

A stack may be implemented using two queues by using the second queue as a b
uffer.
When items are pushed onto the stack they are added onto the end of the queue. Each
time an item is popped, the
n
–
1 elements of the first queue must be moved to the
second, while the remaining item is returned.
public
class
QueueStack
implemen
ts
IStack
{
private
IQueue q1 =
new
Queue();
private
IQueue q2 =
new
Queue();
public
void push( E e )
{
q1.enqueue( e )
//
O
(
1
)
}
public
E pop( E e )
{
while
( 1 < q1.size() )
//
O
(
n
)
{
q2.enqueue( q1.dequeue() );
}
sw
apQueues();
return
q2.dequeue();
}
p
rivate
void swapQueues()
{
IQueue Q = q2;
q2 = q1;
q1 = Q;
}
}


Difference between self-information and entropy I get a bit confused about different definitions of entropy and/or self-information.

Entropy?

$$ H(X) = - \sum_{x \in X} P_X(x) \cdot \log{\left(P_X(x)\right)} $$

Self-information?

$$ I(x) = - \log{P_X(x)} $$
$$ I(X) = - \sum_{x \in X} \log{\left(P_X(x)\right)} $$

When do I use which formulate to calculate what? Generally, I am interested in the average information content of a text. Here I would calculate the frequency of each word, the probability, sum up the negative logarithm of this probability and average it by the number of words.

What am I missing here?

The entropy refers to a set of symbols (a text in your case, or the set of words in a language). The self-information refers to a symbol in a set (a word in your case).

The information content of a text depends on how common the words in the text are wrt the global usage of those words.

E.g. "Next saturday morning" should have less self-information (as a named entity) than "Large Hadron Collider", each of the words should have less self information (except for large, maybe). However the entropy may be higher in the first case, there are not many Large Hadron "things".

Maybe Markov chains or some model that is better suited for probability in natural language would give you better (more significant and useful) results.

Two mistakes from Post169:

Post169 wrote : "....Let's say we have a random number generator that gives you an integer between 0 and 4. Half the time it gives you a 0 ....."

Random means equal probabilities. There is no random number generator, that gives you half the times 0. This is a bias generator.

The equation that Post169 wrote is wrong. The result with this wrong equation is -2 (and not 2). The write equation is −[1/2×(-1) + 1/8×(-3) + 1/8×(-3) + 1/8×(-3) + 1/8×(-3)] =2 bits.

log(base2)0.5= -1, and log(base2)0.125= -3


Why economists should care about computational complexity When trying to convince economists of the relevance of complexity theory in print, is there a standard reference to cite? I am familiar with Noam Nisan's blog post, Tim Roughgarden's survey, and chapter 11 of Scott Aaronson's essay. These posts are accessible for computer scientists, but do not use the language of economists and are not published in venues typically read by them. Are there good arguments for the importance of the complexity of equilibiria, etc. targeted at economists? Is there a good historic overview of how economists have responded to pressure from computer scientists?
It could be argued that neoclassical economics is simply closed off and hence such papers can't exist, but there are slightly heterodox fields such as evolutionary economics and complexity (in the SFI sense) economics that justify themselves in language familiar to economists. These fields also make similar critiques as the computational complexity approach (such as moving away from assumptions of equilibria), but don't justify them as rigorously as CS does.

Related questions

Algorithmic lens in the social sciences

Computational complexity in quantitative finance

I see two separate directions to take your question. One is How has a computer science philosophy and computational thinking impacted the field of economics, and why should economists care about the computer science approach? This is a really cool but really broad question that I'll avoid attempting to address.

The second is more specific: Now that computer scientists know that many problems in game theory are hard, how do we convince economists that these are important issues with or objections to their work? This may not be what you had in mind, but it seems to be an interpretation of what you wrote, so I want to address it because I think it's a bit problematic and I think there are reasons not to write an essay arguing this point (which might explain any lack of answers).

First, micro-economists are often theorists and they may be more interested in understanding the problem in their model than in ours. There is no a priori reason one approach is better than the other. As an analogy, many theoretical computer scientists are happy to design algorithms that work over real numbers even though this may require undecidable operations. Similarly, to an economist, complexity may be a detail that clouds one's understanding of what's important in their model rather than a key consideration. This seems more a matter of preference or philosophy than right or wrong.

Second, it's not clear that computer science is yet in a position to argue convincingly that our models fit the real world better than theirs, until we have experimental data to back this up. (After all, it might be for example that markets often find equilibria quickly in practice, so hardness of computing is irrelevant to real-world applications.) Without data, the disagreement is philosophical and it's hard to claim there is a right or wrong side. I don't know that we have enough data yet to make any specific claims.

Third, I think many economists to whom these issues are relevant have been taking notice. In areas like matching, for example (subject of last year's Nobel!), a computational complexity and algorithmic approach is important as they attempt to implement solutions at large scale. So if an economist claims that complexity isn't relevant to her interests, she might be right; but there are others who do take notice.

So in sum, while it seems like a worthwhile goal to help make economists aware of the results regarding complexity in economics (especially as some do take interest), I am not sure that we are in a position to argue that they should take much notice or change their approach; and I think a strong scientific argument would require more data rather than just philosophy.

this is clearly a very emerging area so surveys and established literature would be difficult to come by. also complexity theory may be a little more abstract for this. however a compelling/natural area on the rise/intersection between CS/econ: try recent research into auctions which is especially significant given google Adsense advertising largely funding the rise of the company over the last decade and also their singular auction-based IPO. also note the large-scale economy price fluctuations and buyer/seller dynamics can be modelled somewhat as an auction-like system.

another somewhat similar area where some very advanced/substantial CS is applied is high-speed trading, a complex/advancing science but unfortunately it is not openly published research due to its heavy secrecy.

[1] Auctions and bidding: A guide for computer
scientists by Parsons

[2] Computer science tackles 30-year-old economics problem -
MIT researchers generalize Nobel winner’s work on single-item auctions to auctions involving multiple items.

[3] Menu size complexity of auctions Sergiu Hart, Noam Nisan


About the position of side conditions in an inference rule Sometimes I see people put side conditions above the inference line as if they were premises of an inference rule.  This feels strange.  My understanding (which may be wrong) is that a side condition belongs to the meta-theory, not to the object-theory: an object-proof of a side condition should not be required and may even not be possible.  So what is the motivation of doing this?  For saving space or for some other deeper reason?

$Update$:

I am no longer quite sure whether a side condition belongs to the meta-theory.  But at least it is outside the object-theory the inference rules describe,that is, the truth of a side condition cannot be derived using the inference rules.

$Update^2$:

Take as an example the rule for typing variables from the simply-typed $\lambda$-calculus.  $(x : T) \in \Gamma$ is a side condition that tests whether the variable $x$ of type $T$ is in the typing context $\Gamma$.  In some presentations, the side condition is put aside, leaving the premises empty to indicate that it is an axiom, though conditional:

$$\frac{}{\Gamma \vdash x : T} (x : T) \in \Gamma$$

while in others, it is put above as if it were a premise:

$$\frac{(x : T) \in \Gamma}{\Gamma \vdash x : T}$$

An inference rule is a symbolic representation of an entire family of closure rules. A side condition cuts down such a family to a subfamily. It is perhaps best to show an example.

We consider the following toy variant of the propositional calculus. The language of expressions is built from primitive constants $\top$ and $\bot$, and a binary connective $\land$. Let $\mathscr{E}$ be the set of all expressions we can build in this language (they correspond to binary trees whose leaves are labeled with $\bot$ and $\top$).

There is only one judgement form $\vdash A$ and only two judgement rules
$$
\frac{ }{\vdash \top}
\qquad
\frac{\vdash A \qquad \vdash B}{\vdash A \land B}
$$
It should be clear that $\vdash A$ is derivable if, and only if, $A$ is an expression which contains no $\bot$'s. Now, how precisely do we read the above inference rules? Bare with me while I describe closure rules and closure operators. These provide an order-theoretic explanation of what rules of inference are and what derivability is about.

Each rule determines a family of closure rules. A closure rule is a pair $(S, A)$ where $S \subseteq \mathscr{E}$ and $A \in \mathscr{E}$. In our case we get the following family of closure rules $\mathscr{C}$:
$$\mathscr{C} = \{(\emptyset, \top)\} \cup \{(\{A,B\},A \land B) \mid A, B \in \mathscr{E}\}$$
Such a family then induces a closure operator $F_\mathscr{C} : P(\mathscr{E})
\to P(\mathscr{E})$ on the powerset of expressions, defined by
$$F_\mathscr{C}(X) = \{A \mid \exists S \subseteq X . (S, A) \in \mathscr{C}\}.$$
The set of all derivable judgements is precisely the least fixed point of $F_\mathscr{C}$. The least fixed point exists by Tarski's theorem because $F_\mathscr{C}$ is a monotone operator on a complete lattice.

Suppose we place a side condition $\phi$ on the second rule:
$$
\frac{ }{\vdash \top}
\qquad
\frac{\vdash A \qquad \vdash B}{\vdash A \land B} \ \text{if $\phi(A,B)$}
$$
Here $\phi$ can be any condition on the expressions. For instance, it could be $A \neq B$ (but in that case there will be a better way of writing the rule without a side condition), or perhaps it says that $A$ has fewer occurrences of $\bot$ than $B$, or whatever. The side condition limits the family of closure rules determined by the rule:
$$\mathscr{C} = \{(\emptyset, \top)\} \cup \{(\{A,B\},A \land B) \mid A, B \in \mathscr{E} \ \text{and}\ \phi(A,B)\}.$$
Thus we see that the side-condition lives at the "meta-level", because it does not appear inside the closure rules, but instead gives an additional condition on the closure rules themselves.

In the example of the variable rule that you mention,
$$\frac{ }{\Gamma \vdash x : T} \ \text{if $(x:T) \in \Gamma$},$$
we clearly have a side-condition.

It is called a side-condition because it is written on the side. And it is so written for a reason, namely to make it clear that it is not a premise of the rule. This is especially important when the object-language described by the rule uses the same symbols as the meta-level language and confusion could ensue. However, it has become fashionable in certain circles to write side-conditions above the line. I am not sure it is a good idea to write side-conditions above the line, as it confuses students and newcomers, but it is stylistically a bit more pleasing.

This is a rather interesting matter and the question has long been left unanswered, so I'll attempt an answer myself.

As the comment points out, the difference among the two formats proposed in the second update seems to just be syntactic sugar. However I find the second one, if possible, even more misleading: indeed, it places in the premise the symbol $\in$, that is most certainly not included in the language we are considering, nor in the deduction system.

Note that there is a very simple way to express this rule without the need of any side condition:
$$ \frac{}{\Gamma, x: T \vdash x : T} $$
I personally find this more satisfactory.

The matter can get more sophisticated: consider the $\forall$-left rule of Gentzen's sequent calculus LK
$$ \frac{\Gamma \vdash \varphi}{\Gamma \vdash \forall x.\varphi} (x \text{ not free in }\Gamma)$$
Here the condition plays a more important role, and indeed the rule is stated like this in most expositions (it is the famous eigenvariable condition).
Even here one has the opportunity to not mention an external condition by means of extra care, if one creates a new environment to keep track of the eigenvariables and make sure that they dont leak into $\Gamma$:
$$ \frac{\Xi,x;\Gamma \vdash \varphi}{\Xi;\Gamma \vdash \forall x.\varphi}$$
In this subtler case one might argue that we are expressing a precise philosophical stance: that is, there is no such thing as a free variable, but rather one should specify an "interface" to a proof/program, that allows it to interact with external specifications.


Are there incompressible strings $S$ such that $K(SS) \lt K(S)$? This question was inspired by Sune Jakobsen's question and Tsuyoshi's answer. In Kolmogorov-complexity, a string is incompressible if $K(S) \ge |S|$.

Is there incompressible string $S$ such that $K(SS) \lt K(S)$? Is there an infinite set of such strings? What is the theoretical consequence if such infinite set of strings does exist?

A rough argument that there should be infinitely many such strings is as follows.

Consider a machine $M$ that first left-pads its input with zeroes out to some known length $2f(|T|)$ (we will specify $f$ below), then repeatedly performs some length-preserving and random-looking operation on it, halting only when it has produced (essentially by accident) a string consisting of two copies of the same string.  It is not required to halt for every input.  When it does, the output it produces from input $T$ will have complexity satisfying $K(SS) \approx K(T) + K_M$ for some $K_M$, as long as $f(|T|)$ is large enough, and $S$ will have length $f(|T|)$.  The string $S$, moreover, will have complexity $K(S) \approx K(SS) + K_C$ for some $K_C$.  The key final step is to choose the right $f(|T|)$.  It must be large enough to ensure that $SS$ is best described as "the output of $M$ applied to $T$", but small enough to ensure that the description of $S$ as "half the output of $M$ applied to $T$" is not less than $|S| = f(|T|)$.  Taking $f(|T|)=|T|+K_M+K_C-1$ should work.  We conclude that arbitrarily long incompressible inputs $T$, if they halt, will typically produce outputs $SS$ such that $K(SS) < K(S)$ and such that $S$ is incompressible.  The machine $M$ could do any number of things; for instance, the machine $M$ that squares its input and then discards every other bit of the result would probably work.

This is not an answer, it contains some "practical" thoughts on the question :-).
I did some investigations using Java as "target" language and defining $K(s)$ as the length of a function in the form:

String s(){<return a STRING_EXPR>}

and such that s() == $s$

Obviously we can build:

String s(){return"$s$";}

So, for every string $s$, $K(s) <= |s| + 21$ (assuming that no special character is in the string)

I'm trying to figure out an incompressible string $s$ (i.e. $K(s)>=|s|$) for which $K(ss) < K(s)$

... but didn't find it ... any ideas?

I've made some tries with small strings, for example $r = a^{28} = aaaaaaaaaaaaaaaaaaaaaaaaaaaa$

String r(){return"aaaaaaaaaaaaaaaaaaaaaaaaaaaa"}
String r(){String x="aaaaaaa";return x+x+x+x;}   // << K(r)=46
aaaaaaaaaaaaaaaaaaaaaaaaaaaa // << |r|=28

$r$ is incompressible ( $K(r)>|r|$ ) ... but didn't find a way to make $K(rr)<K(r)$

Furthermore if such string exist, then $K(r) - K(rr)$ cannot be "too large", indeed we can build:

CODE_FOR_R: function r(){return<SOME_SHORT_EXPR_FOR_RR>.substring($N$);}

where $N$ is half the length of $rr$


The motivation for using Karp-reductions in the theory of $\mathcal{NP}$-completeness The notion of polynomial time reductions (Cook reductions) is an abstraction of a very intuitive concept: efficiently solving a problem by using an algorithm for a different problem.

However, in the theory of $\mathcal{NP}$-completeness, the notion of $\mathcal{NP}$-hardness is captured via mapping reductions (Karp reductions). This concept of "restricted" reductions is much-less intuitive (at least to me). It even seems a bit contrived, as it creates a somewhat less intuitive notion of hardness; by that I'm referring to the fact that $\mathcal{NP}$ does not trivially contains $co-\mathcal{NP}$. Although in complexity theory we are very used to the concept that being able to solve a problem such as $\mathsf{SAT}$ does not imply that we can solve $\overline{\mathsf{SAT}}$, in natural settings (which are captured by Cook reductions), assuming we have an algorithm for solving $\mathsf{SAT}$, we can solve $\overline{\mathsf{SAT}}$ just by running the algorithm for $\mathsf{SAT}$ and returning the opposite.

My question is why should we use Karp reductions for the theory of $\mathcal{NP}$-completeness? What intuitive notion does it capture? How does it relates to the way we understand "hardness of computation" in the real world?

Like Turing reductions, many-one reductions came into complexity theory from computability/recursion theory literature. Cook and Karp reductions are natural complexity theoretic versions of similar existing reductions in computability.

There is a intuitive way of explaining many-one reductions: it is a restriction of Turing reductions where we can ask only a single question from the oracle and the oracle's answer will be our answer.

Now the question is why would we need to study this (and any other kind of reductions like truth-table, weak-truth-table, etc.)?

These reductions give a finer picture than Turing reductions. Turing reductions are too powerful to distinguish between many concepts. A very large portion of computability theory is devoted to the study of c.e./r.e. degrees. The notion of an c.e. set is central. We can have TM machine that can enumerate an infinite set, we may not be able to enumerate its complement. If you want to study c.e. sets then Turing reduction is too strong since c.e. sets are not closed under it. So many-one reductions are a (and maybe the) natural way of defining reductions for this purpose.

Other types of reductions are defined for similar reasons. If you are interested I would suggest checking Piergiorgio Odifreddi's "Classical Recursion Theory". It has a quite comprehensive chapter on different reductions and their relations.

Now for complexity theory the argument is similar. If you accept that $\mathsf{NP}$ is a extremely natural class of problems and you want to study $\mathsf{NP}$, then Cook reductions are too strong. The natural choice is a weaker reduction such that $\mathsf{NP}$ is closed under it and we can prove existence of a complete problem w.r.t. to those reduction for $\mathsf{NP}$. Karp reductions are the natural choice for this purpose.

there are several questions on this site related to Cook vs Karp reductions. have not seen a very clear description of this for the neophyte because its somewhat inherently subtle in many ways and its an active/open area of research. here are some refs that may be helpful to address it. as wikipedia summarizes, "Many-one reductions are valuable because most well-studied complexity classes are closed under some type of many-one reducibility, including P, NP, L, NL, co-NP, PSPACE, EXP, and many others. These classes are not closed under arbitrary many-one reductions, however."

it seems fair to say that even advanced theorists are actively pondering the exact distinction and differences as in below refs and the full story wont be available unless important open complexity class separations are resolved, ie these questions seem to cut to the center of the known vs unknown.

[1] Cook versus Karp-Levin: Separating Completeness Notions If NP Is Not Small (1992) Lutz, Mayordomo

[2] Are Cook and Karp Ever the Same? Beigel and Fortnow

[3] More NP-Complete Problems (PPT) see slides 9-14 on history & Cook vs Karp reduction distinctions


Is there a hash function for a collection (i.e., multi-set) of integers that has good theoretical guarantees? I'm curious whether there is a way to store a hash of a multi-set of integers that has the following properties, ideally:

It uses O(1) space
It can be updated to reflect an insertion or deletion in O(1) time
Two identical collections (i.e., collections that have the same elements with the same multiplicities) should always hash to the same value, and two distinct collections should hash to different values with high probability (i.e., the function is independent or pairwise independent)

One initial attempt at this would be to store the product modulo a random prime of the hashes of the individual elements. This satisfies 1 and 2 but it's not clear whether it, or a close variation, would satisfy 3.

I originally posted this on StackOverflow.

*Properties 1 and 2 could be relaxed a little to, say, O(log n), or a small sublinear polynomial. The point is to see whether we can identify multi-sets and reliably test equality without storing the elements themselves.

If you think of sets as living in universe $[u]$, it is quite easy to solve your problem with $O(\lg u)$ update time. All you need is a fast hash function for a vector of $u$ numbers, with fast "local updates".

Wikipedia/Universal hashing suggests $h(\vec{x}) = \big(\sum_{i=1}^{u} x_i a^i \big) \bmod{p}$, where $p$ is a large enough prime and $a$ is uniformly drawn from $[p]$. When you add or remove element $i$, you have to add/subtract $a^i$ from the hash code, which takes $O(\lg i)$ time using divide and conquer for the exponentiation. Since a polynomial of degree $u$ can only have $u$ roots, the probability of collision for two distinct sets is $O(u/p)$. This can be made very small by taking $p$ to be large enough (for instance, $p=u^2$ and you work in "double precision"). If the sets are much smaller than $[u]$, you can of course begin by hashing the universe down to a smaller universe.

Does anybody know a solution with $O(1/p)$ collision probability when hashing to range $[p]$? This ought to be possible.

A = 0x4F1BBCDD
B = 0x314EFB75
A*B = 1
N = size of set before addition/removal<P>
Add X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U+X)&M)<<16) + ((V^X)&M)
H *= A
H += N+1

Remove X
H = (H-N)*B
U = H >> 16
V = H & 0xFFFF
H = (((U-X)&M)<<16) + ((V^X)&M)
H *= A
H += N-1

the sum allows us to have multiple occurrences of the same value
 the xor allows us to have sets that sum to the same amount


Computing the Mobius function The Mobius function $\mu(n)$ is defined as $\mu(1)=1$, $\mu(n)=0$ if $n$ has a squared prime factor, and $\mu(p_1 \dots p_k)= (-1)^k$ if all the primes $p_1,\dots,p_k$ are different. Is it possible to compute $\mu(n)$ without computing the prime factorization of $n$?

One non-answer to your question is that SQUARE-FREE (is a number square free) is itself not known to be in P, and computing the Möbius function would solve this problem (since a square free number has $\mu(n) \neq 0$).

Let $n=p_1 \dots p_k$, where $p_j$ are distinct primes. Then $$\mu(n)=\mu(p_1 \dots p_k)=\mu(p_1)\dots \mu(p_k).$$ Then to compute $\mu(n)$, it is necessary to compute $\mu(p_j)$ for each $p_j$. This implicitly requires recognizing that $p_1 \dots p_k$ is the prime factorization of $n$.

Here's an analogy: In order to know whether there are an odd or even number of jelly beans in a jar, one must count the jelly beans. This is why you must compute the prime factorization of a number to compute its Mobius function, when it is not divisible by a square. But in order to know that there is more than one jelly bean in a jar, one does not need to examine any of the jelly beans in the jar. One can just shake the jar and hear that there is more than one jelly bean. This is why you don't have to factor a number to know it is composite. Algorithms like Fermat's Little Theorem allow one to "shake the number up" to know it is composite.

When $n$ is divisible by a square, you don't have to compute the prime factorization of $n$. But you do have to find a nontrivial factor of $n$: If $n$ is square, in order to determine that it is square, you have to take its square root, in which you find a nontirival factor of $n$. A fortiori, if $n$ is not a square but is still not squarefree, in order to determine that $\mu(n)=0$, it is necessary to find a nontrivial factor of $n$.


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

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

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

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

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

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

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

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

Lattices are one abstraction for eventually consistent distributed computations. https://www.cs.indiana.edu/~lkuper/papers/lvars-fhpc13.pdf

How you would usefully apply LLL in this context would take some category theory foo to abstract it.


What is the Volume of Information? This question was asked to Jeannette Wing after her PCAST presentation on computer science.

  “From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge question for the theoretical computer science community since I think it begs the question “What is information?”)

Beyond "What is information?" one should also figure out what "volume" means in this context? Perhaps maximum density of information is a better measure.

Lance, there is in fact a theorem which gives bounds on this. The Margolus-Levitin theorem bounds the rate of computation in terms of energy density. There is a nice trick which can then be played: If the local energy density exceeds a certain limit, a black hole will form causing an event horizon which will essentially prevent you from getting an answer by causally disconnecting that region of space-time from the rest of the universe. Seth Lloyd has a nice paper using this trick to estimate the computational power of the universe (Phys. Rev. Lett. 88, 237901 (2002), arXiv).

You can of course use similar reasoning on any finite region of space-time.

This is an interesting and somewhat amusing question but it's poorly formulated in its current form.

I'll take another stab/risk at an answer hoping that scoring will take the original difficulty and basic/inherent "soft" ambiguity of the question in mind and that based on current literature knowledge there are several possible avenues but arguably no "correct answer".

The main query seems to be  "physics analogies in computer science" of which volume is one of them.
Therefore it's highly related to this other question
Physics results in TCS?

To answer this question I'll take a few different approaches which I think all have merit.

first, one approach sometimes used in physics and engineering fields is "dimensional analysis".

In this case strictly interpreted, volume is in the unit "space" or "length cubed". (Although note in physics sometimes the term "space" is measured in either terms length or length cubed.)

Therefore one could argue that in algorithmics the study of the space hierarchy is analogous to the study of "volume". A $O(n^3)$ space algorithm seems also to have the units "length cubed" where length is expressed in terms of input size.

The problem with this is that in algorithmics a $O(n^3)$ algorithm is merely a contrived limit, in a sense TCS has considered the "multidimensional space continuum" since its inception seen in the space hierarchy theorem.

Carrying this over to physics, it might seem absurd to consider anything other than 3-d space, but of course advanced physics takes into consideration all kinds of higher dimensional space realms all the time, via c-dimensional Hilbert [vector] spaces. So it would seem that in some sense an $O(n^c)$ space algorithm can be construed to operate in a c-dimensional hilbert space. Seems like mulmuleys GCT program would be a premiere example of this.

Another approach to a volume analogy (and other physics quantities) in TCS is as follows, as discussed in the other question. It is known that SAT has a transition point extremely analogous to the transition point in physics/thermodynamics, Which happens eg with ideal gases under compression from one phase to another eg gas to liquid. This happens under a decrease in volume (say of the container of the gas). Now in SAT with random inputs the main two parameters on input size are clauses and variables. (Another parameter is number of variables in clauses, although that is often fixed at 3 for 3-SAT.)

Adjusting either the clauses or variables while keeping the other fixed pushes the problem difficulty through the easy-hard-easy transition point. Therefore it seems that these parameters are somehow analogous to Volume although I haven't seen the specifics mapped out. Digging into some of the deep papers on the statistical physics of SAT may turn up the analog of Volume. See [5] for a basic mapping of SAT onto statistical physics terminology.

[5] Analytic and Algorithmic
Solution of Random
Satisﬁability Problems by Mezard, Parisi, Zechina
http://dynamics.org/Altenberg/UH_ICS/EC_REFS/K-SAT/Mezard.Science.297_812.pdf

The other approach might be related to the prior responses talking about high density information processing in physical space leading to black holes. It would use the Planck limit which has units of time, space, mass etcetera. There is a Planck Length unit $l_p$ defined on that Wikipedia page. See units in this table.

I don't know the exact physical interpretation of the Planck length (it's arguably an active area of physics research), but I believe it can be interpreted in some sense as "smallest possible length of space". In other words $l_p^3$ might be the size of a smallest possible physical bit. It is interesting and perhaps a discontinuity of the analogy that in physics a smallest bit apparently must actually have volume (ie units length cubed) in contrast to computer science in which bits seem to have a dimension of unit "length" only.


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

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

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

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

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

(Mirror)

The Base Rate Fallacy and its implications for the Difficulty of Intrusion Detection

Stefan Axelsson, "The Base-Rate Fallacy and its Implications for the Difficulty Of Intrusion", 1999

For those poor saps stuck waiting for IDS alerts, this shows that even if you're signature is 99% accurate, if it's a packet based IDS then you will still be overrun with false positives.

Comment - More generally an understanding of how Bayes rule applies to probabilistic inference, and how probabilistic graphical models are used illuminates many fallacies that arise in working with statistical data.


The origin of the terms "efficient" and "feasible" computation/algorithm I would like to know about the history of these two terms: "efficient", "feasible".

Who used them about computation/algorithms the first time? (in modern sense of these terms, i.e. 20th century).
How did they become mainstream?
How did these two terms start to be used as synonyms?

I know that Cobham used the term "feasible" in the statement of his thesis which associated with polynomial time computability. But is there an earlier reference? There doesn't seem to be an explicit reference to these terms in Godel's letter to von Neumann. I was not able to find any related article predating 1960 (using Google Scholar).

Another interesting point is that the title of Cobham's paper from 1965 is "The intrinsic computational difficulty of functions". When did "computational complexity" replace "computational difficulty"?

I don't know about the terms "efficient" and "feasible."  Since these terms even today have no precise technical meaning, I suspect that the history of their usage will turn out to be murky, just as the history of most words in most languages is murky.

"Computational complexity" is a more interesting term.  With the help of MathSciNet, I find that Juris Hartmanis seems to have been the first to popularize it.  The famous 1965 paper by Hartmanis and Stearns uses the term in the title, but even before that, Hartmanis's Mathematical Review of Michael Rabin's paper "Real time computation" (Israel J. Math. 1 (1963), 203–211) says:

  This result is very instructive and contributes new techniques to the emerging theory of computational complexity of recursive sequences and functions. This theory is mainly concerned with the classification of computable problems by their degree of computational difficulty, the study of the properties of these complexity classes, their relation to each other and their dependence on the (abstract) computing devices.

Note that Rabin himself does not use the term "computational complexity" in this paper.

MathSciNet also turns up a couple of earlier reviews that use the term "computational complexity," but these seem to be spontaneous and sporadic occurrences.

Edit: Answer re-written

How it got mainstream? probably by spreading the idea of comparing new research with older one in terms of performance, with the supposition that creating new ideas is more difficult.


Is there a P-complete problem on diophantine equations? In general deciding whether a diophantine equation has any integer solutions is equivalent to the halting problem.  I believe that deciding if a quadratic diophantine equation has any solution is NP-complete. Does there exist a further restriction on the equations involved that yields a P-complete problem?

No , as far as i know diaphantine problem in general is undecidable thus equivalent to halting problem , if the equations are restricted to be quadratic then it is np-complete , and linear diaphantine equation can be reduced to integer programming problem and For linear Diophantine equation equations, integral solutions exist if and only if, the GCD of coefficients of the two variables divides the constant term perfectly.


Mathematical implications of complexity theory conjectures outside TCS Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)?

I would prefer answers where:

the complexity theory conjecture is as general and standard as possible; I am ok with consequences of the hardness of specific problems too, but it would be nice if the problems are widely believed to be hard (or at least have been studied in more than a couple of papers)
the implication is a statement that is not known to be true unconditionally, or other known proofs are considerably more difficult
the more surprising the connection the better; in particular, the implication should not be a statement explicitly about algorithms

"If pigs could fly, horses would sing" type of connections are ok, too, as long as the flying pigs come from complexity theory, and the singing horses from some field of math outside of computer science.

This question is in some sense "the converse" of a question we had about surprising uses of mathematics in computer science. Dick Lipton had a blog post exactly along these lines: he writes about consequences of the conjecture that factoring has large circuit complexity. The consequences are that certain diophantine equations have no solutions, a kind of statement that can very hard to prove unconditionally. The post is based on work with Dan Boneh, but I cannot locate a paper.

EDIT: As Josh Grochow notes in the comments, his question about applications of TCS to classical math is closely related. My question is, on one hand, more permissive, because I do not insist on the "classical math" restriction. I think the more important difference is that I insist on a proven implication from a complexity conjecture to a statement in a field of math outside TCS. Most of the answers to Josh's question are not of this type, but instead give techniques and concepts useful in classical math that were developed or inspired by TCS. Nevertheless, at least one answer to Josh's question is a perfect answer to my question: Michael Freedman's paper which is motivated by a question identical to mine, and proves a theorem in knot theory, conditional on $\mathsf{P}^{\#P} \ne \mathsf{NP}$. He argues the theorem seems out of reach of current techniques in knot theory. By Toda's theorem, if $\mathsf{P}^{\#P} = \mathsf{NP}$ then the polynomial hierarchy collapses, so the assumption is quite plausible. I am interested in other similar results.

Here's another example from graph theory. The graph minor theorem tells us that, for every class $\mathcal{G}$ of undirected graphs that is closed under minors, there is a finite obstruction set $\mathcal{Obs(G)}$ such that a graph is in $\mathcal{G}$ if and only if it does not contain a graph in $\mathcal{Obs(G)}$ as a minor. However, the graph minor theorem is inherently nonconstructive and does not tell us anything about how big these obstruction sets are, i.e., how many graphs it contains for a particular choice of $\mathcal{G}$.

In Too Many Minor Order Obstructions, Michael J. Dinneen showed that under a plausible complexity-theoretic conjecture, the sizes of several of such obstruction sets can be shown to be large. For example, consider the parameterized class $\mathcal{G}_k$ of graphs of genus at most $k$. As $k$ increases, we can expect the obstruction sets $\mathcal{Obs}(\mathcal{G}_k)$ to become more and more complicated, but how much so? Dinneen showed that if the polynomial hierarchy does not collapse to its third level then there is no polynomial $p$ such that the number of obstructions in $\mathcal{Obs}(\mathcal{G}_k)$ is bounded by $p(k)$. Since the number of minor obstructions for having genus zero (i.e. being planar) is just two ($\mathcal{Obs}(\mathcal{G}_0) = \{K_5, K_{3,3}\}$), this superpolynomial growth is not immediately obvious (although I believe it can be proven unconditionally). The nice thing about Dinneen's result is that it applies to the sizes of obstruction sets corresponding to any parameterized set of minor ideals $\mathcal{G}_k$ for which deciding the smallest $k$ for which $G \in \mathcal{G}_k$ is NP-hard; in all of such parameterized minor ideals the obstruction set sizes must grow superpolynomially.

it appears that many TCS complexity class separation questions have major implications in mathematics. the P=?NP question in particular seems to have very deep connections across many fields and this includes mathematics. some notable cases in this area:

Hilberts Nullstellensatz problem formulated in the early 20th century has been shown to have a tractability closely relating to the P vs NP complexity eg in ON THE INTRACTABILITY OF HILBERT’S NULLSTELLENSATZ AND AN ALGEBRAIC VERSION OF “NP ̸= P?” by Shub/Smale. this is a continuing area of study eg in Computer Algebra, Combinatorics, and Complexity: Hilbert’s Nullstellensatz and NP-complete Problems by Margulies.
Fagins theorem (wikipedia):

  Fagin's theorem is a result in descriptive complexity theory that states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP. It is remarkable since it is a characterization of the class NP that does not invoke a model of computation such as a Turing machine.

the major/surprising implication of P=NP here would mean that all second-order logic assertions could be efficiently computed.
another case is that there are various NP complete problems stated mostly only in mathematical terms (eg no reference to TCS concepts like TMs, nondeterminism etc). this list could be very large if graph theory is (quite reasonably) regarded as mathematical. however even narrow interpretations of "mathematical" lead to cases, for example in number theory.

  As proved by Manders and Adleman, the following problem is NP-complete: given natural numbers $a,b,c$, determine whether there exists a natural number $x\le c$ such that $x^2\equiv a\pmod b$.

Is there a natural problem on the naturals that is NP-complete? tcs.se
number theory and NP complete mathoverflow


Complexity of applying a permutation in-place To my surprise, I was not able to find papers about this - probably searched the wrong keywords.

So, we've got an array of anything, and a function $f$ on its indices; $f$ is a permutation.

How do we reorder the array according to $f$ with memory and runtime as close to $O(1)$ and $O(n)$ as possible?

Are there any additional conditions when this task becomes easier? E.g. when we explicitly know a function $g$ is the inverse of $f$?

I know of an algorithm that follows cycles and traverses a cycle for each index to check if it's the least in its cycle, but again, it has worst-case $O(n^2)$ run time, though on average it seems to behave better...

Option 0: Permuting In Place (1995) by Faith E. Fich , J. Ian Munro , Patricio V. Poblete $O(n \log n)$ time $O( \log^{2} n )$ space.

Option 1: Cheat by compressing your permutation to a succinct data structure, see Munro  http://www.itu.dk/people/ssrao/icalp03-a.pdf .

Option 2:  Use a prime cycle decomposition to store the perm succinctly and use that extra space to cheat http://oeis.org/A186202

Option 3: Keep track of the largest index of each cycle manipulated. For each iteration use the largest unseen index to move everything in its cycle by one. If it hits a seen index undo all that work because the cycle has already been manipulated. $O(n^2)$ time, $O(\#\text{cycles} * \log n)$ space.

Option 4: Keep track of the largest index of each cycle manipulated, but only do them in batches of distinct cycle lengths. For each iteration use the largest unseen index to move everything in it's cycle by one. If it hits a seen index undo all that work because thae cycle has already been manipulated. $O(n^2 * \text{distinct}\_\text{cycle}\_\text{lengths})$ time, $O((\#\text{cycles}\_\text{with}\_\text{same}\_\text{size}) * \log n)$ space.

Option 5: From same paper by Munro as Option 0, For $i = 1 .. n$ rotate the cycle of $p(i)$ if $i$ is the largest index in that cycle. $O(n^2)$ time and $O(\log  n)$ space.

Any permutation of N items can be converted to any other permutation using N-1 or fewer exchanges. Worst case for this method can require O(n^2) calls to the your oracle, F(). Start from the least position. Let x be the position we are currently swapping.

If F(x) >= x then swap positions x and F(x). Else, we must find where the item that was in position F(x) is currently in the list. We can do this with the following iteration. Let y=F(x). Do until y>=x: y=F(y): End Do. Now exchange positions x and y.


Transposition of any characters in Damerau–Levenshtein edit distance computation Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters?

Maybe some heuristic would help?

update

I will identify the application.

I have two sequences of characters. An "Old" one and a "New" one. I need to compute editorial prescription (is it a correct English term?) as a series of actions that could be applied to an "Old" sequence to make it equal to a "New" one.

There are not more than 10-20 characters in a sequence in most cases, thus O(n) is not so important.

The important part is... characters in that "Old" sequence have some metadata assigned to each other. That's why transposition is more welcome than remove/insert when it's possible.

My goal is to make an "Old" sequence equal to a "New" one preserving that metadata as much as possible.

Thanks for updating the question - here goes an answer tailored to your application:

Since we are dealing with realatively small instances we could define an optimal algorithm based on a backtracking branch and bound schema (Presentation on B&B - easy, Something more thorough with common application) by constructing a "path" of permutations with following assuptions:

We want to promote swaps to preserve metadata - cost = 1
We want to penilize other operations but allow them if nessesary - cost = 2
Dissalow "stupid" moves ex. Inserting a letter that's not in the target sequence
Innitial Upper Bound = Levensthein (plain version not the Damerau extension) x 2 (because of the costs)
Lower Bound current path cost + how many letters (disregard positions) do not match in current and target sequences Example:
i have ABCCDD
i want CCWGZDD

the cost added to current path is (1 (W) + 1 (G) + 1 (Z) + 2 (D)) = 5
(probably there is room for a better Lower Bound but it's usually non-trivial to come up with one)

Each time you get to target sequence and path cost is lower than Upper Bound - update it and backtrack.
Each time your Lower Bound exeeds Upper Bound - backtrack

Please google backtracking algorithms and branch and bound for more information. Should you like the solution but have no idea how to go about implementing it please let me know (PW) I'll try to cook-up some pseudocode for you.

The algorithm in worst case is exponential but on real istances should perform very well.

I agree to user834 comment - this seems like exacly this kind of problem. It is not simplified because after each swap we can perform another and another ... so in each step of the algorithm we have O(n^2) possible swaps.

It would be helpful if you could identify the application of this question - perhaps the question itself is ill-posed.

I would also appreciate if you could elaborate on the cost-metric you would like to use for swaps other than adjectant - would it still be = 1?

If you a sure that this is exactly what you want I could propose a following metaheuristic based on local search (An accessible publication about local search and other metaheurestics):

Define following:

neighbourhood (possible move) | size:

swap | O(n^2)
letter change | O(n*alphabethSize)
delete        | O(n)
insert        | O(n*alphabethSize)

Steps:

Try each move and evaluate the D-L distance of the new sequence to target sequence.
Chose best move.
Go back to 1.

Stop if you have the target sequence or there are no more moves that get you closer to it (local minimum).

Possible execution optimisations:

don't consider letters that are not in target seqence
candidate moves (see the .pdf)
you could use the greedy version of local search - choose the first move that betters the distance to target sequence (much faster but more likely to produce worse results). Also remember to evaluate the moves in random order in this version.

Optimality guarantee: none this is a heurestic.

Guys please justify downvoting if you can.


What is the smallest Turing machine where it is unknown if it halts or not? I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest one where nobody has a proof whether it halts or not?

The largest Turing machines for which the halting problem is decidable are:

$TM(2,3), TM(2,2), TM(3,2)$ (where $TM(k,l)$ is the set of Turing machines with $k$ states and $l$ symbols).

The decidability of $TM(2,4)$ and $TM(3,3)$ is on the boundary and it is difficult to settle because it depends on the Collatz conjecture which is an open problem.

See also my answer on cstheory about Collatz-like Turing machines and "Small Turing machines and generalized busy beaver competition" by P. Michel (2004) (in which it is conjectured that $TM(4,2)$ is also decidable).

Kaveh's comment and Mohammad's answer are correct, so for a formal definition of the standard/non-standard Turing machines used in this kind of results see Turlough Neary and Damien Woods works on small universal Turing machines, e.g. The complexity of small universal Turing machines: a survey (Rule 110 TMs are weakly universal).

an inexactly phrased but reasonable general question that can be studied in several particular technical ways. there are many "small" machines measured by states/symbols where halting is unknown but no "smallest" machine is possible unless one comes up with some justifiable/quantifiable metric of the complexity of a TM that takes into account both states and symbols (apparently nobody has proposed one so far).

actually research into this problem related to Busy Beavers suggests that there are are many such "small" machines lying on a hyperbolic curve where $x \times y$, $x$ states and $y$ symbols, is small. in fact it appears to be a general phase transition/boundary between decidable and undecidable problems.

this new paper Problems in number theory from busy beaver competition 2013 by Michel a leading authority exhibits many such cases for low $x,y$ and shows the connection to general number theoretic sequences similar to the Collatz conjecture.


Could there be an extremely large hidden subset of Polynomially solvable problems within NP-Complete problems? Suppose P != NP.

We know that we can make easy instances of 3-SAT at any time. We can also generate what we believe to be hard instances (because our algorithms can't solve them quickly). Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?

For any hard 3-SAT instance, we would have to add the set of all 3-SAT instances it reduces to via looping through the NP-Completeness reduction cycle, but I don't foresee this adding to the number of hard instances very much.

In this world, we could construct an algorithm that polynomially solves all NP complete problems, except an exceptional few.

Edit:
A softer variant of the question: even if we showed P!=NP, how could we know whether a given method to generate size n 3-SAT problems actually generated hard one with some requisite probability?  If there's no way to know from P!=NP alone, what is required to show that we can generate a hard NP-complete problem?

1) Depending on exactly what was meant, the conclusion in Kaveh's observation can be strengthened from $\mathsf{NP} \subseteq \mathsf{P/poly}$ to $\mathsf{P} = \mathsf{NP}$, essentially using Mahaney's Theorem. That is, if there is an algorithm which solves SAT and runs in time $\leq p(n)$ on all instances of length $n$ except for possibly $q(n)$ such instances, where $p$ and $q$ are both polynomials, then in fact $\mathsf{P} = \mathsf{NP}$. See, e.g. Meyer and Paterson and references therein, or Schoning's monograph "Complexity and Structure". So if this captures your notion of "hard instances" then there must be more than $poly(n)$ many hard instances for each $n$, assuming $\mathsf{P} \neq \mathsf{NP}$.

FYI, such algorithms are sometimes referred to as "apt" or "APT" algorithms, for "almost polynomial time" (not to be confused with the more modern complexity class $\mathsf{almostP}$, which happens to equal $\mathsf{BPP}$).

2) The above can be strengthened even further, as follows. Assume $\mathsf{P} \neq \mathsf{NP}$. Then the above says that for any algorithm solving SAT and any polynomial $p$, there is a set of instances of super-polynomial size on which the algorithm takes more than $p(n)$ time. But the set can depend on the algorithm.

The stronger result switches the quantifiers, and concludes: there is a super-polynomial size set H (for "hard") such that for any algorithm A solving SAT and any polynomial p, A takes more than $p(n)$ time on all but finitely many elements of H. Such an H is called a complexity core (the size assumption is not part of the definition of complexity core). The definition and existence of complexity cores was given by Lynch. The result I just quoted is proved by Orponen and Schoning.

another angle on this question (outside of the ref to Mahaney's theorem). the "transition point" in SAT is a study of this phenomena of easy vs hard instance distribution esp around a "critical point" where probability of hard instances is maximized. the literature on the subject is long and complex. it has both empirical and analytical approaches. it has deep ties to physics/thermodynamics.[3] unfortunately there is currently no Wikipedia entry on this very significant and fundamental complexity theory topic. also, there do not seem to be many overall or "standard" surveys on the subject. here is one recent ref to start on SAT[1] and TCS phase transitions in general.[4] your question also falls into a category of "a really good answer would basically be nearly a P$\stackrel{?}{=}$NP proof."

  Is there anything preventing the set of hard instances, from being arbitrarily small, so long as for any given instance size (n) there are only Poly(n) (or even constant) instances of size Poly(n) or smaller?

again Mahaney's theorem (phrased in a slightly different way) answers this directly. another way of looking at this is that attempts to narrow the distribution of instances in some key/characteristic way leads to NP-complete functions. an example of this from monotone circuit complexity is "slice functions".[2]

[1] Predicting Satisfiability at the Phase Transition Lin Xu, Holger H. Hoos, Kevin Leyton-Brown

[2] Paul E. S. Dunne: The Complexity of Central Slice Functions. Theor. Comput. Sci. 44: 247-257 (1986)

[3] Analytic and Algorithmic
Solution of Random
Satisfiability Problems
M. Mezard,
G. Parisi,
R. Zecchina

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


How to constrain a finite automaton (NFA and DFA) to a tree? I have a finite automaton by the standard model Hopcroft & Ullman define:
$$
M = (Q, \Sigma, \delta, q_0, F)
$$

Where $\delta$ is the transition function mapping $Q \times \Sigma \mapsto Q$, such that $\delta(q, a)$ is a state for each state $q \in Q$, the set of all states, and input symbol $a \in \Sigma$, the alphabet. That allows for $\delta$ to map to any element of $Q$. So that's a graph, although it's not described using the usual $G = (V, E)$ notation.

Without specifying any particular definition for $\delta$, I'd like to be able to write the constraint that $\delta$ may only define transitions which form a tree. How can that be expressed?

My thought is that I might say that $\delta$ must be recursive somehow (to give a tree shape), but I'm not sure how to go about that.

Thank you,

I think the easiest way of enforcing tree shape is the set of conditions

$q_0$ is not in the image of $\delta$,
$\delta$ is injective, and
$M$ is connected (to avoid isolated cycles). Note that this one is global, not local, which may be unavoidable.

Then we can prove (by induction) that for any state $q$ there is a unique path from $q_0$ to $q$.

With much help from @unautre (quelqun_dautre on freenode's ##cs):

  There exists a total order relation on Q, where $q_0$
  (initial state of the automata) is the minimum, and
  for all x, y in Q, a in sigma, y = delta(x, a) => x < y
  ($\implies$ is implication)

Where $y = \delta(x,a)$ would be for a DFA, but would be $y \in \delta(x,a)$ for an NFA, since $\delta$ would produce a set of states for any given symbol.

In maths notation:
$$
\forall x, y \in Q, \forall a \in \Sigma, y \in \delta(x, a) \implies x
< y
$$

I would possibly write $q_1$ and $q_2$ for $x$ and $y$, except I think that might be confusing with respect to $q_0$, the start state.


what is a model of computation, mathematically? Where can I find a mathematical definition for "model of computation"? https://en.m.wikipedia.org/wiki/Model_of_computation doesn't provide a precise definition for "model of computation"--it doesn't treat it as a maths object, it states it in English. Contrast this to clear maths definition for formal language: subset of finite set of symbols together with Kleene star

I think that different mathematical models of computation capture different aspects of physical reality. Similar to models of solid state physics (say), these mathematical models may be largely incomparable. Think of analog computers, where the model may not even be described with discrete math. When it comes to automata and formal languages (of finite words over a finite alphabet), an early attempt of an overarching mathematical definition was the abstract family of acceptors, which encompasses Turing machines, finite automata,  stack automata,  pushdown automata and similar notions: Ginsburg, Seymour; Greibach, Sheila (1967). "Abstract Families of Languages". Conference Record of 1967 Eighth Annual Symposium on Switching and Automata Theory, 18–20 October 1967, Austin, Texas, USA. IEEE. pp. 128–139. Needless to say, that notion does not describe L-systems, nonuniform circuit families, quantum devices, probabilistic models, membrane computing etc.

https://www.staff.science.uu.nl/~ooste110/talks/NMC53.pdf

this reference says MoC’s are structured in a category (in fact, a 2-category).


Probabilistic (randomized) algorithms before "modern" computer science appeared Edit: I choice the answer with highest score by December 06, 2012.

This is a soft question.

The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?

In this wiki entry, Rabin's algorithm for the closest pair problem in computational geometry was given as the first randomized algorithm (year???). Lipton introduced Rabin's algorithm as the start of the modern era of random algorithms here, but not as the first one. I also know many algorithms for probabilistic finite automata (a very simple computational model) discovered during 1960s.

Do you know any probabilistic/randomized algorithms (or method) even before 1960s?

or

Which finding can be seen as the first probabilistic/randomized algorithm?

This is discussed a bit in my paper with H. C. Williams, "Factoring Integers before Computers"

In a 1917 paper, H. C. Pocklington discussed an algorithm for finding sqrt(a), modulo p, which depended on choosing elements at random to get a nonresidue of a certain form.  In it, he said, "We have to do this [find the nonresidue] by trial, using the Law of Quadratic Reciprocity, which is a defect in the method.  But as for each value of u half the values of t are suitable, there should be no difficulty in finding one."

So this is one of the first explicit mentions of a randomized algorithm.

JS mentions number theory. Fermat is credited with the Fermat primality test, a probabilistic algorithm which dates to the 1600s and serves as a precursor to more modern primality tests such as Solovay-Strassen and Miller-Rabin. [it would take a historian specializing in math & number theory to try to pinpoint exactly what Fermat knew about it versus modern knowledge which is much more complete about the structure of its pseudoprimes (false positives) etc.]


How to Create Mission Critical Software? I am self learning formal methods. I heard that formal methods is used (and usually only used) to create mission critical software (such as nuclear reactor controller, aircraft flight controller, space probe controller). That's why I am interested to learn it :p

However, after learning formal methods (especially LTL, CTL and their siblings), I feel that they can only be used to verify the correctness of the specification (safety, liveness, fairness, etc).

But then how to verify that the software (not only the specification) is indeed correct?

Disclaimer: I am a 90% idiot when it comes to theoretical computer science. So please be merciful while answering.

The question is rather broad.  To answer it in a reasonable space I will make many oversimplifications.

Let us agree on terminology.  A program is correct when it implies its specification.  This vague statement is made precise in many ways, by pinning down what exactly is a program and what exactly is a specification.  For example, in model checking the program is a Kripke structure and the specification is often an LTL formula.  Or, the program could be a list of PowerPC instructions and the specification could be a set of Hoare-Floyd assertions written in, say, first-order logic.  There are very many possible variations.  It is tempting to conclude that in one case (Kripke structure) we do not verify an actual program, while in the second case (list of PowerPC instructions) we do.  However, it is important to realize we really are looking at mathematical models in both cases, and this is perfectly fine.  (The situation is quite similar to physics where, for example, classical mechanics is a mathematical model of reality.)

Most formalizations distinguish between the syntax and the semantics of a program; that is, how it is represented and what does it mean.  The semantics of a program is what counts from the point of view of program verification.  But, it is of course important to have a clear way of assigning meanings to (syntactical representations of) programs.  Two popular ways are the following:

(small step) operational semantics: This is very much like defining a programming language by writing an interpreter for it. For this you need to say what is the state, and it is affected by each statement in the language.  (You may wonder in which language you write the interpreter, but I'll pretend you aren't.)
axiomatic semantics: Here each statement type comes with an axiom schema. So, roughly, whenever a particular statement of that type is used, it translates in being able to use certain axioms.  For example, the assignment ${\bf x}:={\bf e}$ comes with the schema $\{P[{\bf x}/{\bf e}]\}\,{\bf x}:={\bf e}\,\{P\}$; the particular assignment $x:=x+1$ comes with the axiom $\{x+1=1\}\,x:=x+1\,\{x=1\}$ if we instantiate the schema with $P=(x=1)$.

(There are others.  I feel particularly bad for omitting denotational semantics, but this answer is already long.)  Machine code plus operational semantics is pretty close to what most people would call a ‘real program’.  Here is a seminal paper, which happens to use operational semantics for a subset of the DEC Alpha machine code:

Necula, Lee, Proof-Carrying Code, 1996

Why would you ever use some higher-level semantics, like the axiomatic ones?  When you do not want your proof of correctness to depend on the hardware on which you run.  The approach then is to prove correctness of an algorithm with respect to some convenient high-level semantics, and then prove that semantics sound with respect to lower-level semantics that are closer to actual machines.

In summary, I could think of three reasons that led to your question:

You saw only high-level semantics that don't look like what you are used to call a program, and you wonder if there are low-level ones.  The answer is yes.
You wonder how you prove that a model corresponds to reality.  Like in physics, you don't.  You simply come up with better models and check them against reality.
You have not seen the distinction between syntax and semantics, and various ways to assign meanings to programs.  Two previous questions list some books.

This answer is merely trying to identify three different ways in which I understood the question.  Going deep in any of these points would require a lot of space.

But then how to verify that the software (not only the specification) is indeed correct?

Unit testing? Write a test for every single requirement in the spec, and then test every single method in your implementation to see that its output/input conforms to said spec. This can be automated so that these tests are run continuously to ensure no change ever breaks previously working features.

Theoretically speaking, if your unit tests have 100% code coverage (i.e. every single method in your code is tested) your software should be correct, provided the tests themselves are accurate and realistic.


Different definitions of complexity I'm a math student and have encountered the concept of (mainly time) complexity of algorithms in several courses so far (Analysis of Algorithms, Cryptography, Numerical Analysis). However what strikes me as odd is that the definitions I have encountered so far seem to differ greatly. In particular, the differences that I have noted are

Difference between the uniform and logarithmic cost models: this can, for example, make a difference, when evaluating the time complexity of something like
for i = 1, 2, ..., n do c(i),
where c(i) is an instruction such that the number of bits involved depends on i.  When dealing with, say, sorting algorithms, all references I have ever come across adopt the uniform cost model, while in Cryptography, the time complexity of algorithms is always calculated in terms of bit operations.
Another difference is the definition of the size of an input: again, in sorting algorithms, the size of the input is simply the length of the vector that has to be sorted (as in graph searching algorithms, the number of nodes and edges). In Cryptography and Computational Number Theory, instead, the size of the input is always the number of bits involved. I don't know if this distinction is considered part of 1. , but it certainly makes a huge difference, since an algorithm that is linear using the first criterion, becomes exponential when adopting the second. Factorizing integers would be linear (actually, $O(\log{n} \sqrt{n})$) if we considered the input size of $n$ to be $n$.

One could justify these discrepancies with arguments such as "well, in Number Theory we are dealing with large integers, so adopting a more realistic model makes more sense". But this defies the whole purpose of evaluating asymptotic expressions for the complexity of algorithms! If, in certain contexts, we knew that all inputs were smaller then a fixed quantity, then everything would be $O(1)$. Also, how can it be possible to define, without ambiguity, complexity classes and other rigorous Computer Science concepts, when the definition of complexity varies from field to field?

The definition of, e.g., class P is unambiguous.

However, what is ambiguous is something like "the running time is $O(n)$". As you have observed, there are two sources of ambiguity:

What is a single time step? This depends on the model of computation.
What is $n$? This depends on the problem.

To make it completely unambiguous, you would state something like "the running time in the RAM model is $O(n)$, where $n$ is the number nodes."

Usually, we can afford to be a bit sloppy. The model is often clear from the context; in the case of algorithms, it is usually the RAM model unless otherwise specified. Moreover, there are various conventions regarding the definition of $n$. For example, in the context of graph algorithms, $n$ almost always denotes the number of nodes (and $m$ is the number of edges) – these are just conventions that you have to learn.

If you are really interested in logarithmic factors, then you have to be careful with these details. The same algorithm might be $\Theta(n)$ or $\Theta(n \log n)$ or $\Theta(n/\log n)$ if you slightly vary your model of computation or your definition of $n$.

However, if something like "polynomial time" is good enough for you, then you can ignore most of these details. Typical models of computation can simulate each other with a polynomial overhead (time $x$ in one is at most time $\mathrm{poly}(x)$ in the other), and typically an input can be encoded in $\mathrm{poly}(n)$ bits, no matter what happened to be your precise definition of $n$. For example, an $n$-node graph can be encoded as a string of $n^2$ bits. Hence you can usually say "runs in polynomial time" without worrying too much about the details ("polynomial in what?", "polynomial number of what?").

Ill take a stab at answering part of this [where I think you have a valid point] although I think parts of the question relates to a basic misunderstanding of Big-Oh notation which others are helping address in the comments.

lets focus on sorting. the lower bound on sorting operations is proven to be $O(n \lg(n))$ where $n$ is the number of elements in the list eg see this wiki page, lower bound on sort comparisons. now technically you are correct, if we then say the algorithm runs in the same time, this does not seem to count time to compare each element or apparently assumes $O(1)$ comparison time for all comparisons ie the uniform cost model.

so then lets take into account the real time it takes to compare each element. this might seem counterintuitive but think about it like this. now determine runtime by the logarithmic cost model that you mention, ie cost per each memory unit access (ie where comparing two longer elements takes time proportional to their size).

consider the total size of the input (elements times size of each element) as $m$ and the "width" of each element as $w$ in terms of "memory units" (say chars, digits, bytes, turing tape squares etc). then simply $n \cdot w = m$.

consider in best case a pairwise comparison between two elements does not need to examine all $w$ units of each element, but in worse case (exercise-- devise inputs that force this) each comparison will compare close to $w$ units. so then the algorithm takes comparisons times steps per comparison $n \lg(n) \cdot w$ total steps in worst case. but look at that! by simple algebra thats equal to

$m \lg(m/ w)$ total steps.

but note that expression is simply $O(m \lg(m))$! so we have proven that in either case even when we take into account time per comparison, we get the same answer! this is because theres an inherent "hidden" tradeoff between max number of comparisons and size of each element. this invisible tradeoff is so common in all problems that its almost never explicitly stated or accounted.

ps I dont think Ive seen the above argument in any textbook but I formulated it when I was a CS beginner pondering over the apparent/seeming gaps, handwaving, or inconsistencies in the theory like you are (and by the way, still think they may exist, but not in this case).


Are there decidable problems for which for no algorithm we can give time bounds? Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance?

I arrived at this question because I was thinking about the following:

Assume we
have a recursively enumerable, but undecidable problem. Assume further that I is
a "yes"-instance of the problem. Then for no algorithm which identifies the
"yes"-instances of the problem we can give a time bound in terms of the size n
of I. For if we could give such a time bound, we could decide the problem, as we
could simply conclude that I is a "no"-instance when the time bound is exceeded.

Since we cannot give a time bound for recursively enumerable, undecidable
problems (for the computation time for "yes"-instances), I was wondering if there are decidable problems as well for which we
cannot give a time bound.

For every algorithm $A$ that terminates on a class of inputs $\mathsf{In}$, we can define the function of its running times:
$$
f(n)=\max_{i\in \mathsf{In(n)}}~~ \mathsf{time}(A(i)),
$$
where $\mathsf{In}(n)$ is the class of inputs of length $n$ and $\mathsf{time}(A(i))$ is the time algorithm $A$ requires to terminate on $i$. Of course, this definition is unsatisfying as it relates to the algorithm, but it shows the existence of such a function.
The question that remains is whether there exists a concise representation (and I believe that this was what you were asking for).

If we use simple algebraic terms (without recursion of any sort) as definition of concise, then I think the answer is no: There are problems which can be decided but whose complexity is nonelementary. That is, there does not exist a stack of the form $2^{2^{2^{2^{\dots^n}}}}$ that bounds the execution time of an algorithm for a problem of size n.

I hope I understood your question in the right way.

as others have stated the question is not stated in a way that avoids a trivial answer however there are some concepts in TCS & number theory that are related/similar.

1) in the space and time hierarchy theorems the concept of "time constructible" and "space constructible" functions are required. non time constructible and non space constructible functions exist and lead to unusual properties found in the Blum theorems such as the "gap, speedup" theorems. most (all?) std complexity classes are defined in terms of space and time constructible functions.

2) the ackerman function is total recursive but not primitive recursive and this has implications for its time bound. the primitive recursive functions in some sense represent the "basic" mathematical operations.

3) there are thms about number theory sequences uncomputable in peano arithmetic that can be interpreted as creating not-computable-in-a-sense time bounds such as the goodstein sequence or
paris-harrington thms


Optimality of Greedy algorithm for minimization Knapsack Problem Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized.

The greedy algorithm simply sorts items based on ratio $\frac{p_i}{w_i}$. It scans and sum up the sorted items in increasing order, until $\sum{w_i}\geq{W}$. Then outputs $\sum{p_i}$.

If the distribution of $p_i$ is known (say, following zipf distribution) and $w_i$ is randomly distributed, and independently with value of $p_i$, then what is the average optimality ratio which is ratio of $\sum_{i\in{I}}{p_i}$ to the optimal results.

Note: in worst case, this greedy algorithm can be arbitrarily bad, according to
following book. P412, Knapsack Problems, By Hans Kellerer, Ulrich Pferschy, David Pisinger.

I didn't understand the question very well, but I think you're asking about the ratio of the greedy solution to the optimal solution when the problem instances are taken out of a certain probability distribution. I don't have a theoretic solution to this problem, but if you need the answer for practical reasons, then I think a Monte-Carlo simulation would give reliable results.  You can approximate knapsack to the desired precision using the well-known dynamic programming algorithm to obtain an approximate value of the optimal solution and then compare it to the greedy algorithm. You generate a number of random instances, and see where the ratio usually falls.
In order to have more reliable estimates, you can establish confidence intervals for the fraction of instances whose greedy/optimal ratio falls within a given interval, etc.


Space-approximation Trade-off In their paper Approximate Distance Oracles, Thorup and Zwick showed that for any weighted undirected graph, it is possible to construct a data structure of size $O(k n^{1+1/k})$ that can return a $(2k-1)$-approximate distance between any pair of  vertices in the graph.

At a fundamental level, this construction achieves a space-approximation trade-off --- one can reduce the space requirements at the cost of a lower "quality" of the solution.

  What other graph problems exhibit such a trade-off between space and approximation?

I am interested in the case of both static and dynamic, weighted and unweighted, undirected and directed graphs.

Thanks.

this research appears to be active in a more applied sense than the theoretical one you mention (ie oracles etc) with "data streaming" algorithms which attempt to work with very large data through "sliding windows", with many graph algorithms considered, but it is indeed relatively new/recent, fitting in with "big data" research directions.

Tradeoff Algorithms in Streaming Models, Andrea Ribichini, p7:

  We have devised several algorithms for fundamental graph problems in the
  W-Stream model, including connected components, minimum spanning tree,
  biconnected components and single-source shortest paths. To the best of
  our knowledge, our algorithms are the first to allow effective space/passes
  tradeoffs for such problems in a data streaming setting.

this ref includes other refs/surveys which might be helpful.

  Despite the heavy restrictions imposed by the [classical streaming] model, major success has
  been achieved for several data sketching and statistics problems, for which
  a constant number of passes and polylogarithmic working memory have
  been proven enough to find approximate solutions (see [4, 16, 17] and the
  extensive bibliographies in [7, 29]).

also:

Trading off space for passes in graph streaming problems
Camil Demetrescu,
Irene Finocchi,
Andrea Ribichini


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

So what I have is:

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

and what I want is:

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

Thanks for you help so far.

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

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

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

What are you specifying with benchmark? I too, is working on TSP problem using ACO. We can collaborate if you wish for.


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

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

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

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

Notes

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

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

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

Related questions

Provable statements about genetic algorithms

Algorithmic lens in the social sciences

Sources for Algorithmic Evolutionary Game Theory

Computational complexity in quantitative finance

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

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

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

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

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

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

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

alas there seems to be a massive gap here in scientific interest/significance vs actual scientific research as also evidenced in high votes on this question vs low votes on answers (& not expecting to defy that pattern here). it appears to be a very important study/research program at the heart of scientific theory in its early infancy. we now have the tools to do computational experiments that can subject evolution theory to falsifiability constraints at least in the sense that if evolutionary theory is accurate, then it should it be possible to model/simulate it at least roughly on a computer; but there seem to be very few attempting the project (which is, surely, extremely ambitious to say the least).

for example, is there some simulation that matches known evolutionary changes in the phylogenetic tree over billions of years? the challenge is interdisciplinary and crosscutting and does not seem to fit neatly/exactly into existing scientific fields/boundaries. remarkably there does not even seem to be any major scientists or biologists explicitly proposing such a research program.

here are a few other refs turned up which surely will not fit strictly into the narrow criteria outlined in the question but may be roughly close:

in the field of "artificial life" there is some interest in attempting to simulate the conditions that led to "chemical soup" self-organizing into some kind of quasi-life forms that show basic aspects of replication etcetera. eg: THE EVOGRID:
An Approach to Computational Origins of Life Endeavours Damer

  The quest to understand the mechanisms of the origin of life on Earth could be enhanced by computer simulations of plausible stages in the emergence of life from non-life at the molecular level. This class of simulation could then support testing and validation through parallel laboratory chemical experiments. This combination of a computational, or “cyber” component and a parallel effort investigation in chemical abiogenesis could be termed a cyberbiogenesis approach. The central technological challenge to cyberbiogenesis endeavours is to design computer simulation models permitting de novo emergence of prebiotic and biological virtual molecular structures and processes through multiple thresholds of complexity. This thesis takes on the challenge of designing, implementing and analyzing one such simulation model. This model can be described concisely as: distributed processing and global optimization through the method of search coupled with stochastic hill climbing supporting emergent phenomena within small volume, short time frame molecular dynamics simulations.

A GROUP SELECTION MODEL OF TERRITORIAL WAR, XENOPHOBIA AND ALTRUISM IN HUMANS
AND OTHER PRIMATES Agner Fog

  Abstract: A theoretical model of wars over group territories shows that behavioural traits like cooperative warfare, justice, altruism and outsider exclusion may have coevolved in higher primates and prehistoric man. The conditions for territorial war to be an effective mechanism of group selection are discussed. These conditions may have been present in tribal societies in prehistoric times but not in modern times. The geographic evolution of territories is illustrated with computer simulations.

remarkably the question appears to be very similar to: computer simulation of the evolution process on earth dating to 2008 on stack overflow with some misc refs.