Is it possible to compute whether two functions are extensional equal? If you have two functions implementing a different sorting algorithm, is it then possible to infer by source code that they both have the same external properties? Meaning that they both will have a possible unsorted sequence as their input and have a sorted sequence as their output? In what way could these external properties be determined by the source code? And how would you describe these external properties? What notation would be used?

The external properties could be made known by defining them explicitly, for example within a type system, but I am wondering whether this could be done implicitly. Or is it somehow theoretically impossible to infer this kind of semantics? I am interested in whether this is possible for arbitrary functions, not just for sorting algorithms, assuming things like functions will always halt and have no side-effects.

Should I look at denotational semantics, or is unrelated?

I'm interested in pointers to research in this area and to different terms used to describe the subject that might help my literature search.

Yes. If you can verify that they are the same, then so can a computer.

Here's a quick specification for an integer sort in Coq:

Inductive natlist : Type :=
| nil : natlist
| cons : nat → natlist → natlist.

Fixpoint is_sorted (l : natlist ) : bool :=
    match l with
    |  nil => true
    |  (cons x nil) => true
    |  (cons x (cons y r)) => if x <= y then is_sorted (cons y r) else false
    end.

...

Theorem sort_spec : forall l, is_sorted (sort_list l).

A specification can be directly encoded into the declaration of sort using dependent types.

For this particular problem, John Darlington demonstrated in the 70s that 6 families of sorting algorithms can be derived by mechanically transforming the specification of a sort into an implementation; I believe this goes under the name "semantics-based program derivation."

In the software-engineering world, finding extensionally equivalent functions is known as "semantic clone detection."

Dave Clarke also gave a good answer to this question on the CS StackExchange: https://cs.stackexchange.com/questions/2059/how-do-you-check-if-two-algorithms-return-the-same-result-for-any-input

This all falls under the umbrellas of formal methods and programming languages. Denotational semantics are one class of techniques for modeling semantics, but they've fallen out of favor for being difficult to use compared to operational semantics.

A quick answer (I admit I did not spent much time...) Rice theorem says that  for any non trivial question, it is undecidable to say wether the function computed by a program will have the property or not. Therefore the question here is undecidable


Regular languages under change of encoding Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$.
Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other encoding (say unary, or, decimal) also form a regular language ?

Formally, is it the case that the language $L' = \{w | w \in 1^*, \exists w' \in L \text{ such that the unary encoding of } w' \text{ is } w \}$ also regular?

What happens when the base is shifted to a lower number? For example can we also say anything about the following language:
$L'' = \{w | w \in \{0,1,2\}^*, \exists w' \in L \text{ such that the ternary encoding of } w' \text{ is } w \}$

The answer is no.
I'll give an example of a language $L$ which is regular in binary but not in unary:

Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.

It's easy to see that $L$ is regular while $L'$ is not even context free.

L'' also isn't regular either, by the link @Sylvain posted in his comment.

If my memory is right, the answer is yes as a consequence of the following two points:
(1) conversion between two number bases can be expressed by a FS transducer -- not sure about that one, please check;
(2) regular languages are closed under application of a FST -- this follows from the more general fact that FSTs are closed under compositions.
A possible reference for FSTs is the Sakarovitch textbook "Elements of automata theory". Hope this helps...


Minimal DFA satisfying a finite view of a language Say one has a language $L \subseteq \Sigma^*$, but one doesn't know what strings are actually part of the language. All one has is a finite view of the language: a finite set of strings $A \subseteq L$ that are known to be in the language, and a finite set of strings $B \subseteq (\Sigma^* \setminus L)$ that are known to not be in the language.

For example, let's say I have the $A = \{ab, aaab, aaaaabb\}$ and $B = \{b, aab, aaaba\}$. I might have the language $L = \{a^{2i+1}b^j~|~i, j \in \mathbb{N} \}$, since $A$ and $B$ are consistent with $L$, or I might have a completely different language.

My question is: is there a known way to create a DFA (deterministic finite automata) that accepts the strings in $A$ and rejects the strings in $B$, with a minimal or almost-minimal number of states? What's the complexity of this problem? How good is it at approximating $L$ (assuming $L$ has a fairly low descriptive complexity, and $A$ and $B$ are large)?

Original question on math.stackexchange.com. I decided to repost here after getting no answers on the original question, and having no idea where to look for them. If someone could point me toward research in this area, it would be greatly appreciated.

As you already know from the comments, finding the minimal DFA satisfying a finite set of positive and negative examples is $\mathsf{NP}$-hard. However, not all hope is lost, if you are willing to modify your learning paradigm slightly then we can get back into $\mathsf{P}$.

Assume that you are trying to learn a an unknown DFA $W$ which is minimal for some language $L_W$. If you allow the oracle membership queries and to act as a teacher by answering the following question: Given a proposed DFA $G$ does it recognize $L_W$? If not, can you provide a counter-example?

Note that if the oracle has access to $W$ it can compare $G$ to $W$ in poly-time, since testing equality between regular languages is easy. Generating a counter-example can also be done in polynomial time.

In this framework, you can learn $W$ in polynomial time using Angluin's (1987; pdf) algorithm (or Schapire's refinement of it; see section 5.4.5). For more info about this model, here are two questions on cstheory and CS.SE about it:

Lower bounds for learning in the membership query and counterexample model
Are there improvements on Dana Angluin's algorithm for learning regular sets

I think this problem may have been inexactly phrased by the questioner. The questioner apparently wants an algorithm that generalizes infinite words based on specific finite word examples, using some kind of mechanized induction, i.e. recognizing apparent patterns in the examples.

In addition to some CS theory research cited in comments, there is also some more empirical research in this area e.g. below, using ANNs to create FSMs from examples. Note one can always run a standard DFA minimization algorithm on the result. The AT&T FSM library is good for work in this area.

The questioner is not specific about his problem domain, that can help to understand the structure of examples and get more specific references. However, one example that can be seen is AI algorithms in games that use FSM algorithms. I suspect there are some cases where the FSMs are learned from examples using learning algorithms.

[1]
Learning a class of large finite state machines with a recurrent neural network
C. Lee Giles, 1, B.G. Horne, T. Lin 1995

[2] Learning FSMs with self-clustering recurrent networks  by Zeng & Smyth 1993

[3] AT&T FSM library


"The Solution Problem" - How to get credit for your work as an undergrad? I have come to a rather startling discovery in regards to a question that has been posed to me a number of times through my now almost 1 year of CS studies.

Solving this problem is of great interest to many people, and if I have indeed done so... What do I do?

I see a few options, but none seem to ensure that my work gets recognized as my own: I could stash away the notes till the time comes for my masters thesis. This would force me to share both work and credit with my supervisor, though. I could attempt to publish it... But who would want to take work from a 9 months old computer scientist?

I am at a loss - in attempting to solve a difficult problem I have only given rise to an even more difficult one!

Worrying about someone taking credit for your work is very common among amateurs and people just starting out, but in my experience is far less common with more experienced researchers. I'm not really sure exactly what the reason for this is, but I have encountered this phenomenon numerous times. I would venture that it is perhaps because those with more experience in the field know how uncommon it is for one person to essentially steal another's results. Most people are relatively good, or at worst benign, and wouldn't dream of taking credit for work they haven't contributed to. Couple that with the fact that being caught plagiarizing someone else's work would be career suicide, and you can be pretty confident that no one you talk to is likely to write up your idea and pass it off as their own.

As Suresh says, you could always upload it to the arxiv, but I would be inclined not to do this, as if it turns out that the work is not novel or there is a major error, then you cannot actually delete the paper, but rather will have to post a retraction, and the original will still be there for all to see. Even now, I still ask colleagues to check any paper I consider relatively important before uploading a manuscript.

If I were you, I would be inclined to talk to one of my lecturers in the first instance, as they can probably give you a feel for whether your solution is novel (and correct), and if it meets both of these criteria, they should be able to give you an idea of how best to proceed. Alternatively, you could just post it as a question here, asking if the result was previously known, or if anybody could point you to a good survey paper on the problem. You'd have a time stamp from the post time, so you wouldn't have to worry about that. If you got an encouraging response here (i.e. that it was not currently known), then you could consider how to proceed from there. If on the other hand, it was already known, or there was a flaw, then it wouldn't really matter.

Technically, you could also simply write it up and submit it to a journal. As Dave says, no one involved in the process will actually know your level (the first time, it's kind of a kick when you get the correspondence addressed to you as either Dr. or Professor), unless one of the reviewers happens to know you personally. However, I would not suggest doing so. You need to search the literature to make sure your idea is actually novel, and as Dave mentions, the writing of papers is an art in and of itself. You would probably need to read a lot of journal articles to even get the style right.

several other answers have mentioned submitting to arxiv which is indeed a sometimes prestigious and elite site occasionally containing some work/papers submitted by undergraduates. you appear to be affiliated with a university. fyi this is a semiofficial requirement of arxiv submissions, sometimes [apparently] judged by your ".edu" on your email address.

if you are not "university affiliated", arxiv can be harder to submit to. it requires the support of one of the [unlisted] moderators.

generally it seems [speaking from experience] their acceptance policy is rather opaque and occasionally verging on arbitrary for borderline cases. if you submit a paper and you're in, great, but if its not accepted based on the sometimes sketchy criteria [which seems not to be published or clearly articulated anywhere on the site], you wont necessarily have a clear path to fix that. in other words the structure is not at all set up to encourage/help/coax borderline cases to make it in [it is somewhat similar to stackexchange in this way, but also maybe scientific journal submissions].

so fyi, a relatively new alternative that was recently created specifically/partially in protest of arxiv's opaque and not-fully-open submission policies is vixra which seems to be stable and attracting a healthy dose of submissions. more details on their policy and contrast to arxiv can be found on the page "why vixra". quoting from that:

  Vixra is also an experiment to see what kind of scientific work is being excluded by the arXiv. But most of all it is a serious and permanent e-print archive for scientific work. Unlike arXiv.org it is truly open to scientists from all walks of life. You can support this project by submitting your articles.

as to another reasonable suggestion by JF in the other answer:

  Alternatively, you could just post it as a question here, asking if the result was previously known, or if anybody could point you to a good survey paper on the problem. You'd have a time stamp from the post time, so you wouldn't have to worry about that. If you got an encouraging response here (i.e. that it was not currently known), then you could consider how to proceed from there. If on the other hand, it was already known, or there was a flaw, then it wouldn't really matter.

again, personal experience, I tried this to some degree here with some of my own ideas & had some degree of success, but it was highly variable and unpredictable. however, dont really recommend the above in this forum (TCS.se) for several reasons. if your question is upvoted beyond a certain threshold, it is likely to stay here forever unmolested.

however in a borderline case (which frankly is the likely case here for an undergraduate attempting to accomplish a genuine research advance), the question could easily be closed and deleted, and on stackexchange, these questions are totally vaporized without trace (all comments, all answers, etc, everything is completely wiped out as if the question had never appeared in the 1st place) see why and how are some posts are deleted. surely not what you intended, so much for "a time stamp from the post time, so you dont have to worry about that"...

another less severe but still problematic case here [from the POV of the originator] are questions that end up getting heavily edited via the collaborative editing, and get pushed away/drift significantly from your original intentions/meaning. see why can people edit my posts, how does editing work.

you may have better luck starting out in cs.stackexchange. occasionally very advanced questions there get migrated to this forum.


Exact Algorithm for edge labeling problem in DAG I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.

Problem: We are given directed acyclic graph $G=(V,E)$.  Without loss of generality assume that $G$ has exactly one source vertex $s$ and exactly one sink vertex $t$; let $P$ denote the set of all directed paths from $s$ to $t$ in $G$.  We are also given a set of vertices $R \subseteq V$.  The problem is to assign non-negative integer weights to the edges of $G$, so any two paths in $P$ have the same weight if and only if they contain the same subset of vertices in $R$.  (The weight of a path is the sum of the weights of its edges.)  The range of weights of paths in $P$ should be as small as possible.

Currently my approach does not seems efficient; I am just looking for some references to literature or some good insights. Anything otherwise is also appreciated.

Edit: Is there a hardness proof for this problem? Does the compact numbering always exists?

havent heard of this problem exactly in literature [maybe someone else has] however as a "nearby problem" it seems to me the minimum spanning tree would have useful properties to solve your problem. for example maybe generating two minimum spanning trees starting from the source vertex & the sync vertex, and propagating them outward until they touch, etc. might solve the problem or give a close answer. before anyone dings me on this here plz understand I am extending the idea of the MST somewhat to be generated starting from a given vertex [normally it starts from shortest edge in the entire graph]. if it doesnt work Id be curious for the reason.


Number of reachable vertices in DAG for every vertex Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every vertex and this will take $O(|V||E|)$ time. Is there a better way to solve this problem?

The best exact algorithm will run in time O( min{mn, n^2.38} ) by using fast binary matrix multiplication. However, there is a random algorithm, which runs in time O(m+n) and estimates the number of reachable nodes from each node with a small relative error, please refer to paper "Size-Estimation Framework with Applications to Transitive Closure and Reachability" by Edith Cohen.

I am not a expert here i will a try.

1) Since it is DAG, it should have a sink vertex i.e vertex with outdegree 0. Find a sink vertex say x and add {x} as reachable vertex to Neighbor(x). remove x and repeat the process till graph becomes empty


Universal Approximation - Are ReLUs discriminatory? In Cybenko's elegant proof of the Universal Approximation Theorem (UAT) he proves that single hidden layer neural networks (with linear output layer) are universal approximators whenever their activation functions are (what he calls) discriminatory. He then shows that bounded measureable sigmoidal functions are discriminatory, completing the proof. In particular, continuous sigmoidal functions work as well.

Later Leshno et al. proves that locally bounded piecewise continuous (l.b.p.c.) activation functions yield the UAT if and only if they are nonpolynomial.

My Question(s):

What kinds of functions are discriminatory? Polynomials certainly aren't (Leshno et al.) and continuous sigmoids are (Cybenko).  Are ReLUs discriminatory?

Together, the above results imply that for l.b.p.c. functions, that discriminatory implies non-polynomial. Is the converse true?

Yes, ReLUs are discriminatory. See for example the nice, simple proof in Lemma 3.15 of these notes by Leonardo Ferreira Guilhoto:
http://math.uchicago.edu/~may/REU2018/REUPapers/Guilhoto.pdf

Regarding whether an unbounded function like a ReLU can be discriminatory, note that you can construct a bounded, continuous function as the difference of two ReLUs:

$f(x) = ReLU(W x + b_1) - ReLU(W x + b_2)$

and an appropriate choice of $b_1, b_2$ makes this difference f a sigmoidal function, as defined in Cybenko, so function f is discriminatory.

By definition a function is discriminatory if the zero measure is the only signed Borel measure $\mu$ such that:

$\int f(W x + b) d \mu (x) = 0$
for all W, b

Applying this to the difference of ReLUs above shows that both integrals over each ReLU must have measure zero if integral of f has measure zero.

I think ReLUs does not satisfy Cybenko theory requirements, i.e. are unbounded.
There is another recent paper showing UAT type theorem  for ReLU feed forward deep networks using wavelet approximation property
https://arxiv.org/abs/1509.07385


NP-hard problems on trees Several optimization problems that are known to be NP-hard on general graphs are trivially solvable in polynomial time (some even in linear time) when the input graph is a tree. Examples include minimum vertex cover, maximum independent set, subgraph isomorphism. Name some natural optimization problems that remain NP-hard on trees.

It is NP-complete to determine whether a tree can be embedded into the two-dimensional integer grid, with the tree vertices placed on distinct grid points and the tree edges placed on grid edges.

See e.g. Gregori, IPL 1989.

Is Circuit SAT on trees NPC?. Tree inner vertices are labeled as OR/AND gates. Leaves are inputs. Determine if there is a satisfying set of inputs for the circuit to evaluate to True.

At first glance it seems you can solve bottom up, but constraints get nasty as you move up the tree and OR gates suddenly need one of the other $2^k - 1$ assignments.


Is there a general theory for why certain algorithms are inefficient in high-level languages? First of all, I apologise off the bat for my mangling of CompSci language. I have no real training or background in computer science or mathematics.

I've been wondering lately whether there's a 'general' explanation for the inefficiency of high-level languages in performing certain kinds of algorithms - from simple cases like the massive performance improvement in C over, say, Python, when looping over a set, up to complex mathematical algorithms.

Is it purely a quantitative matter - C is more efficient because it's not doing weird magic behind the scenes and the programmer directly interacts with main memory? And because it's not doing things like interrupts for garbage collection and other general housekeeping like a high-level language might?

Or is there some deeper ontological explanation for this? Is there some qualitative property of a low-level procedural language (or, at times, of a functional language) that makes it possible to express and compute a problem efficiently? Or is it simply a matter of brute resource and CPU cycle efficiency?

There is no deeper reason other than quality of compilers and interpreters.

Some languages are not designed with speed of execution in mind. For example, the design goals of Python did not include speed of execution at the very top. In such cases you should not wonder where speed has gone.

Some languages are intended to run fast but it takes time for people to produce good compilers and runtime environments. Typical examples are the so-called "high-level" languages. For example, early variants of ML were memory hogs that ran sort of fast until the garbage collector kicked in. Nowadays, 25 years later, a modern variant of ML, such as Ocaml, runs with speeds comparable to those of C and C++, and in most cases you don't even notice that there is a garbage collector.

Why is it harder to compile high-level languages to fast code? Well, because they are high level. Programs written in such languages operate directly with concepts that are far removed from the underlying hardware. In contrast, low level languages such as C, C++ and java are essentially glorified assembly languages and there is very little that the compiler actually needs to do.

Also, there are languages out there whose design is essentially screwed up in such a way that efficient compiled code is hard to obtain. Typically such languages have no or little compile-time type checking or unreasonable amounts of reflection, i.e., eval <string>, and an operational semantics which relies heavily on string replacement and manipulation of source code. Bourne shell comes to mind, TeX/LaTeX as well, and maybe Python to an extent. As long as such "features" are deliberate design choices that is ok, but there also seem to be languages out there whose design was based on ignorance of programming language theory.

there is a simple answer in the case you mention, Python/C, not mentioned in answers so far. the Python interpreter is written in C but not vice versa. same with eg Ruby or Perl.

& yes as you guess, another simple answer is that modern interpreted languages use a garbage collector which simplifies the programming experience and maintenance of the code at the expense of some runtime overhead.

a useful way of picturing language implementation complexity is to visualize layers of different systems or subsystems that run concurrently or "on top" of each other. for example interpreted code runs concurrently with a garbage collector. interpreted code is built "on top" of C interpreting code. etc.; the "higher level" language is written in terms of the "lower level" language. in a sense the higher level language is compiled into the lower level language.

however the question seems to suggest an unfamiliarity with the basic theory of NP completeness which is the theoretical construct used to judge runtime complexity and in which there is indeed no substantial difference between compilers and interpreted code because it all runs within P-time factors of each other.


Can decoying provide security against traffic analysis? Eve is an intelligence agency with the capability to scan all cleartext communications and do traffic analysis against encrypted communications.

There are n Alices, who each want to communicate secretly with some of the other Alices. So, they want the content of their communication to be secret, and the fact that they are actively trying to communicate secretly to be secret.

There are also N>>n Bobs, who disagree with mass surveillance but don't want to do anything  which would give them any legal liability, such as transmitting illegal material (IE, they don't want to run TOR nodes).

So the Bobs decide to help by sending junk communications to other Bobs, which are indistinguishable from encrypted data. An individual Bob, if challenged, can show that his transmissions are junk, thus avoiding legal liability (NB -  I Am Not A Lawyer). For the purpose of the exercise Eve in not allowed to challenge 'many' Bobs.

Eve wins if she can distinguish the Alices from the Bobs, or at least, as many Alices as possible. In particular, Eve may start by knowing at least some of the Alices; we don't want the security of the other Alices to collapse if she does.

A dumb approach is as follows: For each period of time, each Bob (or masquerading Alice) chooses another Bob(Alice) to communicate with at random from a public list. The Bobs send junk, the Alices send their encrypted message. In this scheme, the Alices are indistinguishable from the Bobs, but the Alices only obtain 1/N of the bandwidth of an individual communication, which is very low since N is large, and have very high latency, since they have to wait many time periods before they happen to communicate with who they want.

Is it possible to do better?

How can Bobs prove that their transmissions are junk? Given that the transmissions can be encrypted using information theoretically secure one-time pads (OTPs), it is not possible to prove that they are not significant messages. Even if the messages from Bobs would be assumed to be encrypted with a single cipher of a good grade (AES?) it would be very hard to show that there is no key that decodes a given message into meaningful content, because, assuming such a method would exist, it would simultaneously show that the cipher (AES?) is broken. A statistical method showing that a message from a Bob cannot be an AES-encrypted message would correspond to a distinguisher for AES and that would also signal that it is a weak cipher.


Kolmogorov Complexity applications in Number Theory What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.)

One of the nice proofs i have come across is the proof of the existence of infinite number of primes, using the definition of Kolmogorov Complexity and the compression factor.

Also, what is the importance of Kolmogorov Complexity in Cryptography?

Every integer has an associated Kolmogorov complexity; the shortest program that prints that integer.

There are $\approx {x \over ln(x)}$ primes up to $x$ so primes have lower Kolmogrov complexity than composites on average; $\approx ln({x \over ln(x)})$    vs  $\approx ln(x)$.

As a side effect you have to have some large gaps between primes; otherwise you could encode every number as the previous prime plus some small number of bits.

try this reference

From Kolmogorov’s theorem on empirical distribution to number theory, Kevin Ford, also here.

  We describe some new estimates for the probabiity that an empirical distribution function stays on one side of a given line, and give applications to number theory.

sketch of another basic conceptual connection/bridge in cryptography. $K(x)$ is related to the entropy of an information source. entropy is used heavily in cryptography as a measure related to randomness, eg see Some Notions of Entropy for Cryptography by Reyzin.
however, caveat, there is no direct reference to Kolmogorov complexity there! and looking at this very long Phd thesis/survey on entropy in cryptography by Cachin/Maurer Entropy Measures and Unconditional Security in Cryptography, there is no direct reference either! so it appears to me that $K(x)$ is a more "computationally intractable" measurement of entropy and therefore doesnt show up often in cryptography analysis which needs more pragmatic metrics even though it is conceptually linked. there may be a sense in which $K(x)$ is at the same time the strictest measure of entropy and yet at the same time the most intractable, with other entropy measures at other "easier" points in this apparent strict vs. tractable tradeoff continuum.


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

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

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

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

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

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

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

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

  A tree has a 1-edge separator.

Right?

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

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

If $\mu$ is the expected value of $X$, we expect that $\{X=\mu\}$ will actually happen.


Maintaining the product of a queue of semigroup elements I have a queue $Q$ where elements can be popped from the left and added to the right in $O(1)$ time.  The elements are members of a fixed semigroup $S$ with $O(1)$ time multiplication.  Let the current state of the $Q$ be the sequence $(s_1,\ldots,s_n)$.  I am interested in the product

$$\prod Q = s_1 \cdots s_n.$$

Question: Is it possible to maintain this product in amortized constant time as elements are added and removed?

A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack.

See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )

About how to maintain on stacks:

Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one stack, we need to maintain $s_1 s_2 \ldots s_n$; for the other, we need to maintain $s_n\ldots s_2 s_1$. We only consider the first case.

Let $p_k=s_1\ldots s_k$, then $p_n$ is the answer we need.

When pop, simply delete $p_n$ and $s_n$.

When push, $p_{n+1}=p_n s_{n+1}$.

I would memoize the partial products:

{.}{..}{....}{........}{....}{..}{.}

On the incoming end you combine them as they grow to a size equal to their left neighbor. On the outgoing end you spit them in half until you get one element. Amoritized work is log(n) per update to maintain the total product.


Trees: complexity of counting the number of vertex covers Which is the complexity of counting the number of vertex covers of trees? Is it still #P-complete, as for general graphs?

The complement of a vertex cover is an independent set.  Your question is therefore equivalent to asking whether counting independent sets is #P-complete on trees.

The answer to this question is NO, it is not #P-complete: there is actually a polynomial-time algorithm to count the number of solutions.

S. D. Noble, Evaluating a Weighted Graph Polynomial for
Graphs of Bounded Tree-Width, The Electronic Journal of Combinatorics 16(1) R64, 2009. (link)

Noble actually shows much more.  Suppose the class of graphs under consideration has treewidth at most $k$.  Then the weighted graph polynomial $U$, which evaluated at a certain point yields the number of independent sets of a graph, can be evaluated in $O(a_k n^{2k+3})$ operations at any point.  Here $a_k$ depends only on $k$ and $n$ is the number of vertices in the input graph.  Hence there is a polynomial-time algorithm to count the number of vertex covers on trees (or any other class of graphs of bounded treewidth).

On the other side, it is interesting to ask: what is the smallest class that is known to be #P-complete?

  Theorem (Greenhill, 2000): counting independent sets in 3-regular graphs is #P-complete. (link).

In the comments Colin McQuillan pointed out an even stronger result:

Mingji Xia, Wenbo Zhao, #3-Regular Bipartite Planar Vertex Cover is #P-Complete, TAMC 2006, 356–364.

Note that wall graphs are 3-regular (if their corners are joined up), bipartite, and planar, but they have arbitrarily large treewidth.

Finally, a different graph polynomial $R_2$ yields the number of independent sets in a bipartite graph.  This was posed as an open question:

  Question (Ge and Štefankovič, 2010): is the exact evaluation of the $R_2$ polynomial easy for bounded tree-width graphs? (link)

Find any solution in O(N) time using the greedy algorithm (keep moving the leaves, select parent of a leaf if the leaf is not selected or covered.)
Initialize a counter vector to ones for the selected nodes. Check the selected nodes in vertex cover one by one and determine if you release that node and select any of its un-selected neighbors without violating the vertex cover. For each move increase the corresponding counter by one. Number of the vertex cover should be the product of the counter.
(Please let us know if you find any counter example.)


Are there problems for which divide-and-conquer / recursion is provably useless? When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the problem becomes much more complicated as its input grows.

My question is: are there problems for which we can prove that a divide-and-conquer approach cannot help to solve? In the following lines I try to make this more formal.

Let $P(n)$ be a certain problem whose input has size $n$ (e.g. a problem that accepts an input an array of $n$ numbers). Suppose we have a recursive algorithm for solving $P(n)$.    The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time. For example:

The recursive runtime of binary search is $O(1)$, since it uses only a comparison and two recursive calls.
The maximum element in an array can be found in recursive time $O(1)$.
The recursive runtime of merge sort is $O(n)$, because of the merging step.

The recursive time is usually smaller than the actual runtime, which reflects the fact that the recursive algorithm is simpler than a straightforward non-recursive solution to the same problem.

Now my question is:

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime asymptotically less than $f(n)$?

Some specific variants of this question are:

Is there a problem in $P$ which has no algorithm with recursive runtime $O(1)$? (Maybe sorting?)
Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

EDIT: contrary to my guess, sorting has an algorithm with recursive runtime $O(1)$. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

Yes.  Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P.  There is a tally language in E∖P by a standard diagonalization argument.

  Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime $o(f(n))$?

It may depend on the computational model, but I doubt this is known, given that the time hierarchy theorem for two-tape Turing machines is not powerful enough to distinguish, say, O(n2) time and o(n2) time even without giving the latter the constant-time access to the answers on smaller instances.

Random comments on your questions in this post:

I do not think that these questions are related to the usefulness of recursive programs, despite what the title of the post and your choice of terminology suggest.  As BVMR wrote in an answer, recursions and iterations are equivalent in a certain sense.  Instead, I think that the questions have a connection to the usefulness of the divide-and-conquer approach.
In complexity theory, a related notion to your notion of “recursive algorithms” with their “recursive runtime” is called “length-decreasing self-reductions” with their time complexity.
Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.

I am not sure if I correctly understand your notion of "recursive complexity".

Lets (reasonably) Assume a programming language that contains a schema for primitive recursion i.e. in which one can define functions $f$ from

$$
f(0,\vec x) = c(\vec x)\\
f(n+1,\vec x) = g(f(n,\vec x),n,\vec x)
$$

where $c$ and $g$ are previously defined functions. Further let us assume that the basic functions (constants, projections, successor) have $\mathcal{O}(1)$ "recursive complexity" If I understand your definition correctly, then all primitive recursive functions (and thus problems/relations) have $\mathcal{O}(1)$ "recursive runtime". This, I think, can be seen by induction on the build up of recursive functions.

If all my assumptions are met, then the example you are looking for cannot be primitive recursive.


Is {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} non-context-free? Is the language {$a^{i}b^{j}c^{k} ~|~ i \neq j, i \neq k, j \neq k$} context-free or not?

I realized that I have encountered almost all variants of this question with different conditions about the relationship between i, j, and k, but not this one.

My guess is that it is not context-free, but do you have a proof?

Ogden's lemma should work:

For a given $p$ choose $a^i b^p c^k$ and mark all the $b$'s (and nothing else).

$i$ and $k$ are chosen such that for every choice of how many $b$'s are actually pumped there is one pumping exponent such that the number of $b$'s is equal to $i$ and one where it is equal to $k$.

That is $i$ and $k$ have to be from the set $\bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in \mathbb{N}_0\rbrace$.

I am quite sure but too lazy to formally prove that this set is infinite.

If the relation between the three restrictions is "OR", then the language is CFL.
The solution uses the fact that CFLs are closed under union.
Clearly, the following are CFLs:
$L_1=\{a^ib^jc^k \mid i\ne j,\ k\ge 0\}$,
$L_2=\{a^ib^jc^k \mid i\ne k,\ j\ge 0\}$,
$L_3=\{a^ib^jc^k \mid j\ne k,\ i\ge 0\}$
(if one is not convinced, one can look on $L_i$ as concatenation of CFL and regular language. For instance, $L_1$ is $\{a^ib^j\mid i\ne j \}$ concatenated to $\{c\}^*$.

The desired language is the union of the above $L=L_1\cup L_2\cup L_3$.
So, it is CFL.


Why did Kolmogorov publish Karatsuba's algorithm? Karatsuba's algorithm for fast multiplication was first published in A. Karatsuba and Yu. Ofman (1962), "Multiplication of Many-Digital Numbers by Automatic Computers", Proceedings of the USSR Academy of Sciences 145: 293–294.

According to Karatsuba (1995, "The complexity of computations", Proc. Steklov Institute
of Mathematics 211: 169–183), this paper was actually written by Kolmogorov (and possibly Ofman) without Karatsuba's knowledge. By modern standards this seems a strange and grave breach of ethics.

Why would Kolmogorov have done this? What did he gain?

This paper, in Russian,

  Gricenko, S. A., Karatsuba, E. A., Korolyov, M. A., Rezvyakova, I. S.,
  Tolev, D. I., & Changa, M. E. (2012). Scientific contributions of A. A.
  Karatsuba / Научные достижения Анатолия Алексеевича Карацубы.
  Современные проблемы математики, 16(0), 7-30.

states the following (items 1—3).

Karatsuba presented his algorithm at a seminar led by Kolmogorov.
Kolmogorov prepared an article that had two results of his students, Karatsuba and Ofman. One of the results was Karatsuba's algorithm, the other was an unrelated result of Ofman.
The article clearly attributed the results. It stated that the multiplication algorithm is due to Karatsuba and the other result is due to Ofman.

We can only guess why Kolmogorov did that. I am afraid that the only person who could answer the question why Kolmogorov published the paper without Karatsuba's permission or knowledge was Kolmogorov himself.  Perhaps he thought that it was a good way to publish the results of his students. Note that the article correctly attributed all results. The article of Karatsuba and Ofman was published in the Proceedings of the USSR Academy of Sciences; it is my understanding that it had to be submitted/presented by a member of the USSR Academy of Sciences.

Here is the relevant quote from the paper of Gricenko et al (in Russian):

  Этот результат был доложен Анатолием Карацубой на семинаре А. Н.
  Колмогорова в МГУ в 1960 г., после чего семинар был Колмогоровым
  закрыт. Первая статья с описанием этого метода [2] была подготовлена
  самим Колмогоровым. Там он представил два разных и не связанных друг с
  другом результата двух своих учеников, и хотя в статье Колмогоров
  четко отметил, что одна теорема (не связанная с быстрым умножени- ем)
  принадлежит Ю. Офману, а другая теорема (с первым в истории быстрым
  умножением) принадлежит А. Карацубе, эта публикация под именами двух
  авторов надолго сбила с толку читателей, которые полагали, что оба
  автора внесли вклад в создание быстрого умножения, и даже называли
  этот метод двумя именами.

English translation:

  This result was presented by Anatoly Karatsuba in A. N. Kolmogorov's seminar at the Moscow State University in 1960, after which the seminar was closed by Kolmogorov. The first article with the description of this algorithm [2] was prepared by Kolmogorov himself.  In it he presented two different results from his two students that were unrelated to each other, and although Kolmogorov clearly noted in the article that one theorem (unrelated to fast multiplication) belonged to Y. Ofman, and the other theorem (with the first fast multiplication algorithm in history) belonged to A. Karatsuba, this publication on behalf of the two authors for a long time confused readers, who supposed that both authors had stake in the invention of fast multiplication, and even referred to the algorithm using both names.

It is probably cultural.  Karatsuba's discovery took place only 7 years after the death of Stalin.  I do not believe it was an environment in which subjects questioned authority, and authority did not ask permission from subjects.  As a professor and member of NAUK, Kolmogorov was definitely authority.   No complaints about Kolmogorov, he left us a lot of good stuff!


Defintion of a Data Structure? Lately I have been looking around for a formal definition of a what a data structure is. I cannot find neither a paper, nor a book with such a definition. Even the famous "The Art of Computer Programming" is missing one. Even for just a linked data structure, e.g., binary search tree, I couldn't find one.

So, is there one? Perhaps a paper that is talking about it?

By formal definition I'm thinking of something like "A data structure is a tuple (Op, El, ..) where ...".

Data structures is nothing but the ways how data of different kinds can be structured in a systematic way. The actual definition may be somewhat lengthy and descriptive which can be found on different sources. But it is all about defining structures of your data that will satisfy your need to solve any particular problem.


Alan Turing Documentaries To celebrate Alan Turing 100th birthday, I want to watch a documentary about his life.  However, there are several documentaries to choose from.
Which documentary about Alan Turing is your favorite?
Please include only one documentary per answer.

a leading one is Codebreaker with a list of reviews/publicity here [unfortunately several are behind paywalls]. here is one web review by chris harvey & with quotes by the writer warner.

this documentary originated by channel 4 seems balanced and avoids hagiography, looking at all the aspects of his complex life. has award winning writer, actors and acclaimed producer.

closely related is a highly-viewed documentary circulating on a lego turing machine built in honor of the 100th anniversary of Turings birthday, by CWI Phd student & software engr/researcher


Core algorithms deployed To demonstrate the importance of algorithms (e.g. to students and professors who don't do theory or are even from entirely different fields) it is sometimes useful to have ready at hand a list of examples where core algorithms have been deployed in commercial, governmental, or widely-used software/hardware.
I am looking for such examples that satisfy the following criteria:

The software/hardware using the algorithm should be in wide use right now.

The example should be specific.
Please give a reference to a specific system and a specific algorithm.
E.g., in "algorithm X is useful for image processing"
the term "image processing" is not specific enough;
in "Google search uses graph algorithms"
the term "graph algorithms" is not specific enough.

The algorithm should be taught in
typical undergraduate or Ph.D. classes in algorithms or data structures.
Ideally, the algorithm is covered in typical algorithms textbooks.
E.g., "well-known system X uses little-known algorithm Y" is not good.

Update:
Thanks again for the great answers and links!
Some people comment that it is hard to satisfy the criteria
because core algorithms are so pervasive that it's hard to point to a specific use.
I see the difficulty.
But I think it is worthwhile to come up with specific examples because
in my experience telling people:
"Look, algorithms are important because they are just about everywhere!" does not work.

Algorithms that are the main driver behind a system are, in my opinion, easier to find in non-algorithms courses for the same reason theorems with immediate applications are easier to find in applied mathematics rather than pure mathematics courses. It is rare for a practical problem to have the exact structure of the abstract problem in a lecture. To be argumentative, I see no reason why fashionable algorithms course material such as Strassen's multiplication, the AKS primality test, or the Moser-Tardos algorithm is relevant for low-level practical problems of implementing a video database, an optimizing compiler, an operating system, a network congestion control system or any other system. The value of these courses is learning that there are intricate ways to exploit the structure of a problem to find efficient solutions. Advanced algorithms is also where one meets simple algorithms whose analysis is non-trivial. For this reason, I would not dismiss simple randomized algorithms or PageRank.

I think you can choose any large piece of software and find basic and advanced algorithms implemented in it. As a case study, I've done this for the Linux kernel, and shown a few examples from Chromium.

Basic Data Structures and Algorithms in the Linux kernel

Links are to the source code on github.

Linked list, doubly linked list, lock-free linked list.
B+ Trees with comments telling you what you can't find in the textbooks.

  A relatively simple B+Tree implementation.  I have written it as a learning exercise to understand how B+Trees work.  Turned out to be useful as well.

  ...

  A tricks was used that is not commonly found in textbooks.  The lowest values are to the right, not to the left.  All used slots within a node are on the left, all unused slots contain NUL values.  Most operations simply loop once over all slots and terminate on the first NUL.

Priority sorted lists used for mutexes, drivers, etc.
Red-Black trees are used for scheduling, virtual memory management, to track file descriptors and directory entries,etc.
Interval trees
Radix trees, are used for memory management, NFS related lookups and networking related functionality.

  A common use of the radix tree is to store pointers to struct pages;

Priority heap, which is literally, a textbook implementation, used in the control group system.

  Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7

Hash functions, with a reference to Knuth and to a paper.

  Knuth recommends primes in approximately golden ratio to the maximum
  integer representable by a machine word for multiplicative hashing.
  Chuck Lever verified the effectiveness of this technique:

  http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf

  These primes are chosen to be bit-sparse, that is operations on
  them can use shifts and additions instead of multiplications for
  machines where multiplications are slow.

Some parts of the code, such as this driver, implement their own hash function.

  hash function using a Rotating Hash algorithm

  Knuth, D. The Art of Computer Programming,
  Volume 3: Sorting and Searching,
  Chapter 6.4.
  Addison Wesley, 1973

Hash tables used to implement inodes, file system integrity checks etc.
Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
Semaphores and spin locks
Binary search is used for interrupt handling, register cache lookup, etc.
Binary search with B-trees
Depth first search and variant used in directory configuration.

  Performs a modified depth-first walk of the namespace tree, starting
  (and ending) at the node specified by start_handle.  The callback
  function is called whenever a node that matches the type parameter is
  found. If the callback function returns a non-zero value, the search
  is terminated immediately and this value is returned to the caller.

Breadth first search is used to check correctness of locking at runtime.
Merge sort on linked lists is used for garbage collection, file system management, etc.
Bubble sort is amazingly implemented too, in a driver library.
Knuth-Morris-Pratt string matching,

  Implements a linear-time string-matching algorithm due to Knuth,
  Morris, and Pratt [1]. Their algorithm avoids the explicit
  computation of the transition function DELTA altogether. Its
  matching time is O(n), for n being length(text), using just an
  auxiliary function PI[1..m], for m being length(pattern),
  precomputed from the pattern in time O(m). The array PI allows
  the transition function DELTA to be computed efficiently
  "on the fly" as needed. Roughly speaking, for any state
  "q" = 0,1,...,m and any character "a" in SIGMA, the value
  PI["q"] contains the information that is independent of "a" and
  is needed to compute DELTA("q", "a") 2. Since the array PI
  has only m entries, whereas DELTA has O(m|SIGMA|) entries, we
  save a factor of |SIGMA| in the preprocessing time by computing
  PI rather than DELTA.

  [1] Cormen, Leiserson, Rivest, Stein
   Introdcution to Algorithms, 2nd Edition, MIT Press

  [2] See finite automation theory

Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.

  Implements Boyer-Moore string matching algorithm:

  [1] A Fast String Searching Algorithm, R.S. Boyer and Moore.
   Communications of the Association for Computing Machinery,
   20(10), 1977, pp. 762-772.
   http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf

  [2] Handbook of Exact String Matching Algorithms, Thierry Lecroq,
  2004
   http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf

  Note: Since Boyer-Moore (BM) performs searches for matchings from
  right
  to left, it's still possible that a matching could be spread over
  multiple blocks, in that case this algorithm won't find any
  coincidence.

  If you're willing to ensure that such thing won't ever happen,
  use the
  Knuth-Pratt-Morris (KMP) implementation instead. In conclusion,
  choose
  the proper string search algorithm depending on your setting.

  Say you're using the textsearch infrastructure for filtering,
  NIDS or
  any similar security focused purpose, then go KMP. Otherwise, if
  you
  really care about performance, say you're classifying packets to
  apply
  Quality of Service (QoS) policies, and you don't mind about
  possible
  matchings spread over multiple fragments, then go BM.

Data Structures and Algorithms in the Chromium Web Browser

Links are to the source code on Google code. I'm only going to list a few. I would suggest using the search feature to look up your favourite algorithm or data structure.

Splay trees.

  The tree is also parameterized by an allocation policy
  (Allocator). The policy is used for allocating lists in the C free
  store or the zone; see zone.h.
  Voronoi diagrams are used in a demo.
  Tabbing based on Bresenham's algorithm.

  There are also such data structures and algorithms in the third-party code included in the Chromium code.

Binary trees
Red-Black trees

  Conclusion of Julian Walker

  Red black trees are interesting beasts. They're believed to be
  simpler than
  AVL trees (their direct competitor), and at first glance this seems
  to be the
  case because insertion is a breeze. However, when one begins to play
  with the
  deletion algorithm, red black trees become very tricky. However, the
  counterweight to this added complexity is that both insertion and
  deletion
  can be implemented using a single pass, top-down algorithm. Such is
  not the
  case with AVL trees, where only the insertion algorithm can be
  written top-down.
  Deletion from an AVL tree requires a bottom-up algorithm.

  ...

  Red black trees are popular, as most data structures with a
  whimsical name.
  For example, in Java and C++, the library map structures are
  typically
  implemented with a red black tree. Red black trees are also
  comparable in
  speed to AVL trees. While the balance is not quite as good, the work
  it takes
  to maintain balance is usually better in a red black tree. There are
  a few
  misconceptions floating around, but for the most part the hype about
  red black
  trees is accurate.
  AVL trees
  Rabin-Karp string matching is used for compression.
  Compute the suffixes of an automaton.
  Bloom filter implemented by Apple Inc.
  Bresenham's algorithm.

  Programming Language Libraries

I think they are worth considering. The programming languages designers thought it was worth the time and effort of some engineers to implement these data structures and algorithms so others would not have to. The existence of libraries is part of the reason we can find basic data structures reimplemented in software that is written in C but less so for Java applications.

The C++ STL includes lists, stacks, queues, maps, vectors, and algorithms for sorting, searching and heap manipulation.
The Java API is very extensive and covers much more.
The Boost C++ library includes algorithms like Boyer-Moore and Knuth-Morris-Pratt string matching algorithms.

Allocation and Scheduling Algorithms

I find these interesting because even though they are called heuristics, the policy you use dictates the type of algorithm and data structure that are required, so one need to know about stacks and queues.

Least Recently Used can be implemented in multiple ways. A list-based implementation in the Linux kernel.
Other possibilities are First In First Out, Least Frequently Used, and Round Robin.
A variant of FIFO was used by the VAX/VMS system.
The Clock algorithm by Richard Carr is used for page frame replacement in Linux.
The Intel i860 processor used a random replacement policy.
Adaptive Replacement Cache is used in some IBM storage controllers, and was used in PostgreSQL though only briefly due to patent concerns.
The Buddy memory allocation algorithm, which is discussed by Knuth in TAOCP Vol. 1 is used in the Linux kernel, and the jemalloc concurrent allocator used by FreeBSD and in facebook.

 Core utils in *nix systems

grep and awk both implement the Thompson-McNaughton-Yamada construction of NFAs from regular expressions, which apparently even beats the Perl implementation.
tsort implements topological sort.
fgrep implements the Aho-Corasick string matching algorithm.
GNU grep, implements the Boyer-Moore algorithm according to the author Mike Haertel.
crypt(1) on Unix implemented a variant of the encryption algorithm in the Enigma machine.
Unix diff implemented by Doug McIllroy, based on a prototype co-written with James Hunt, performs better than the standard dynamic programming algorithm used to compute Levenshtein distances. The Linux version computes the shortest edit distance.

Cryptographic Algorithms

This could be a very long list. Cryptographic algorithms are implemented in all software that can perform secure communications or transactions.

Merkle trees, specifically the Tiger Tree Hash variant, were used in peer-to-peer applications such as GTK Gnutella and LimeWire.
MD5 is used to provide a checksum for software packages and is used for integrity checks on *nix systems (Linux implementation) and is also supported on Windows and OS X.
OpenSSL implements many cryptographic algorithms including AES, Blowfish, DES, SHA-1, SHA-2, RSA, DES, etc.

Compilers

LALR parsing is implemented by yacc and bison.
Dominator algorithms are used in most optimizing compilers based on SSA form.
lex and flex compile regular expressions into NFAs.

Compression and Image Processing

The Lempel-Ziv algorithms for the GIF image format are implemented in image manipulation programs, starting from the *nix utility convert to complex programs.
Run length encoding is used to generate PCX files (used by the original Paintbrush program), compressed BMP files and TIFF files.
Wavelet compression is the basis for JPEG 2000 so all digital cameras that produce JPEG 2000 files will be implementing this algorithm.
Reed-Solomon error correction is implemented in the Linux kernel, CD drives, barcode readers and was combined with convolution for image transmission from Voyager.

Conflict Driven Clause Learning

Since the year 2000, the running time of SAT solvers on industrial benchmarks (usually from the hardware industry, though though other sources are used too) has decreased nearly exponentially every year. A very important part of this development is the Conflict Driven Clause Learning algorithm that combines the Boolean Constraint Propagation algorithm in the original paper of Davis Logemann and Loveland with the technique of clause learning that originated in constraint programming and artificial intelligence research. For specific, industrial modelling, SAT is considered an easy problem (see this discussion). To me, this is one of the greatest success stories in recent times because it combines algorithmic advances spread over several years, clever engineering ideas, experimental evaluation, and a concerted communal effort to solve the problem. The CACM article by Malik and Zhang is a good read. This algorithm is taught in many universities (I have attended four where it was the case) but typically in a logic or formal methods class.

Applications of SAT solvers are numerous. IBM, Intel and many other companies have their own SAT solver implementations. The package manager in OpenSUSE also uses a SAT solver.

An amazingly successful (hardware) algorithm is the power-on reset.

Without a system whereby a computer is in a known state when power is applied, nothing else happens right.

Power-on reset is why anything works at all that has a CPU in it, whether considered embedded or otherwise.

Next time you're at the watering hole for programmers and computer scientists, raise your glass of cherry soda to the power-on reset.


Efficiently computable variants of Kolmogorov complexity Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features:

It corresponds to an intuition of giving strings with patters or structure a lower complexity than strings without.
It allows us to define conditional complexity $K(x|y)$, or even better $K(x|O)$ for some oracle $O$.
It is sub-additive $K(x,y) \leq K(x) + K(y)$.

However it has an awful downside: returning $K(x)$ given $x$ is undecidable.
I have wondered if there is a variant of Kolmogorov complexity $K'(x)$ using a restricted model of computation (either by using weaker languages than TMs, or using resourced bounded TM) that preserves features (1) and (2) (feature (3) is a bonus, but not a must) while being efficiently computable?
The motivation for this question is for use in simulation studies of various toy-models of evolution. Thus an answer that has been used as a 'rough approximation' for Kolmogorov complexity in numeric work before is preferred. However, the goal isn't to go completely experimental, so a relatively simple/clean description language/model-of-computation for $K'$ is preferred, so that it might be possible to prove some reasonable theorems about how drastically $K'$ differs from $K$ and on what kind of strings.
Relates questions
Kolmogorov complexity with weak description languages
Is there a sensible notion of an approximation algorithm for an undecidable problem?

Gzip.  Cilibrasi and Vitanyi have a really nice article where they use gzip as an approximation of Kolmogorov complexity to do clustering. Clustering by Compression

You're looking for resource bounded Kolmogorov complexity. You can start with this paper and branch out.


Langton's ant questions I'm a mathematician currently working on the Langton's ant conjecture, just for fun. I have some result but I don't know if they are meaningless.
So that is why I'm asking.

1)
Is there a mathematical proof that the Langton's ant will stay forever on the highway once it's enter in it ?

2)
Is there a proof that for only one initial condition the Langton's ant will always build the highway ?

There is an article on Langtons ant, published in the
SCTPLS Newsletter ( Society for Chaos Theory in Psychology & Life Sciences   Vol. 26, No. 2 February 2019 ) It introduces a first order recurrence relation for the cellular automata 'Langtons ant'   A copy can be downloaded from

http://buzwordsalad.com/lit/SCTPLS_LAWE_bw.pdf


Is there algorithmic mathematical analysis? There are algorithmic graph theory/number theory/combinatorics/information theory/game theory.

  Is there algorithmic mathematical analysis?

According to wiki, mathematical analysis includes the theories of differentiation, integration, measure, limits, infinite series, and analytic functions. It is OK to focus on real analysis (wiki) that deals with the real numbers and real-valued functions of a real variable.

"Algorithmic" means studying something from the perspectives of computability theory and complexity theory.

Googling of "algorithmic mathematical analysis" leads me to "mathematical analysis of algorithms" or "applications of analysis to algorithms", which is not what I mean.

Check out
the Computability and Complexity in Analysis network. Quote:

The topics of interest include foundational work on various models and approaches for describing computability and complexity over the real numbers. They also include complexity-theoretic investigations, both foundational and with respect to concrete problems, and new implementations of exact real arithmetic, as well as further developments of already existing software packages.

Looking at this question more than two years after it was posted and, no offense, I'm disappointed with the answers and comments.

This is what happens when CS departments all over the world mislabel their topics and mislead multiple generations of scientists and engineers.

Either the Algorithms classes in all CS departments need to be relabelled to Discrete Algorithms.
Or the current content of that class needs to be cut down to 50% or less (that 50% or less includes Data Structures) and the remaining half needs to include some assortment of topics from Numerical Analysis and Scientific Computing.

Because what is the core of Mathematical Analysis? Real Analysis and the real line. And how are real numbers represented in computers? floating point, or arbitrary precision, etc. So the next time you're working on any algorithm that deals with floating point and/or arbitrary precision as a core component (not as a content, as in sorting a bunch of floating point numbers), know that you're doing Algorithmic Mathematical Analysis (AMA)!

And don't even get me started with the massive universe of NA/Computational Science topics. It arguably dwarfs whole of TCS. When you're solving systems of multiple non-linear PDEs on a computer, you're not only utilizing the fundamentals of mathematical analysis, but cutting edge functional analysis in all its glory, complete with open research problems, etc. It can't get any more AMA than that.


Is there a stable heap? Is there a priority queue data structure that supports the following operations?

Insert(x, p): Add a new record x with priority p
StableExtractMin(): Return and delete the record with minimum priority, breaking ties by insertion order.

Thus, after Insert(a, 1), Insert(b, 2), Insert(c, 1), Insert(d,2), a sequence of StableExtractMin's would return a, then c, then b, then d.

Obviously one could use any priority queue data structure by storing the pair $(p, time)$ as the actual priority, but I'm interested in data structures that do not explicitly store the insertion times (or insertion order), by analogy to stable sorting.

Equivalently(?): Is there a stable version of heapsort that does not require $\Omega(n)$ extra space?

The Bently-Saxe method gives a fairly natural stable priority queue.

Store your data in a sequence of sorted arrays $A_0,\ldots,A_k$.  $A_i$ has size $2^i$.  Each array also maintains a counter $c_i$. The array entries $A_i[c_i],\ldots,A_i[2^i-1]$ contain data.

For each $i$, all elements in $A_i$ were added more recently than those in $A_{i+1}$ and within each $A_i$ elements are ordered by value with ties being broken by placing older elements ahead of newer elements.  Note that this means we can merge $A_i$ and $A_{i+1}$ and preserve this ordering.  (In the case of ties during the merge, take the element from $A_{i+1}$.)

To insert a value $x$, find the smallest $i$ such that $A_i$ contains 0 elements, merge $A_0,\ldots,A_{i-1}$ and $x$, store this in $A_i$ and set $c_0,\ldots,c_i$ appropriately.

To extract the min, find the largest index $i$ such that the first element in $A_i[c_i]$ is minimum over all $i$ and increment $c_i$.

By the standard argument, this gives $O(\log n)$ amortized time per operation and is stable because of the ordering described above.

For a sequence of $n$ insertions and extractions, this uses $n$ array entries (don't keep empty arrays) plus $O(\log n)$ words of bookkeeping data.  It doesn't answer Mihai's version of the question, but it shows that the stable constraint doesn't require a lot of space overhead.  In particular, it shows that there is no $\Omega(n)$ lower-bound on the extra space needed.

Update: Rolf Fagerberg points out that if we can store null (non-data) values, then this whole data structure can be packed into an array of size $n$, where $n$ is the number of insertions so far.

First, notice that we can pack the $A_k,\ldots,A_0$ into an array in that order (with $A_k$ first, followed by $A_{k-1}$ if it's non-empty, and so on).  The structure of this is completely encoded by the binary representation of $n$, the number of elements inserted so far.  If the binary representation of $n$ has a 1 at position $i$, then $A_i$ will occupy $2^i$ array location, otherwise it will occupy no array locations.

When inserting, $n$, and the length of our array, increase by 1, and we can merge $A_0,\ldots,A_i$ plus the new element using existing in-place stable merging algorithms.

Now, where we use null values is in getting rid of the counters $c_i$.  In $A_i$, we store the first value, followed by $c_i$ null values, followed by the remaining $2^i-c_i-1$ values.  During an extract-min, we can still find the value to extract in $O(\log n)$ time by examining $A_0[0],\ldots,A_k[0]$.  When we find this value in $A_i[0]$ we set $A_i[0]$ to null and then do binary search on $A_i$ to find the first non-null value $A_i[c_i]$ and swap $A_i[0]$ and $A_i[c_i]$.

The end result: The entire structure can be implemented with one array whose length is increment with each insertion and one counter, $n$, that counts the number of insertions.

I don't think that's possible

concrete case:

       x
    x    x
  x  x  1  x
1  x

min heap with all x > 1

heapifying will eventually give something a choice like so

       x
    1    1
  x  x  x  x
x  x

now which 1 to propagate to root?


Wikipedia-style explanation of Geometric Complexity Theory Can someone provide a concise explanation of Mulmuley's GCT approach understandable by non-experts? An explanation that would be suitable for a Wikipedia page on the topic (which is stub at the moment).

Motivation: I am "co-reading" Scott Aaronson's book Quantum Computing since Democritus with a friend of mine who is a researcher in string theory. In the preface of the book, Aaronson calls GCT "the string theory of computer science".
Being a string theorist, my friend got excited about this claim and asked me what GCT is. At that point I shamefully realized I didn't have a Wikipedia-ready answer for his question.

I'm not exactly sure what level is suitable for Wikipedia article (different articles seem to be aimed at different levels of expertise) or exactly what you're looking for. So here's a try, but I'm open to feedback.

Geometric complexity theory proposes to study the computational complexity of computing functions (say, polynomials) by exploiting the inherent symmetries in complexity and any additional symmetries of the functions being studied.

As with many previous approaches, the ultimate goal is to separate two complexity classes $\mathcal{C}_{easy}, \mathcal{C}_{hard}$ by showing that there is a polynomial $p$ which takes functions $f$ as inputs (say, by their coefficient vectors) such that $p$ vanishes on every function $f \in \mathcal{C}_{easy}$ but does not vanish on some function $g_{hard} \in \mathcal{C}_{hard}$.

The first key idea (cf. [GCT1, GCT2]) is to use symmetries to organize not the functions themselves, but to organize the (algebro-geometric) properties of these functions, as captured by polynomials such as $p$ above. This enables the use of representation theory in attempting to find such a $p$. Similar ideas relating representation theory and algebraic geometry had been used in algebraic geometry before, but to my knowledge never quite in this way.

The second key idea (cf. [GCT6]) is to find combinatorial (and polynomial-time) algorithms for the resulting representation-theoretic problems, and then reverse-engineer these algorithms to show that such a $p$ exists. This may be taken in the spirit of using Linear Programming (an algorithm) to prove certain purely combinatorial statements.

Indeed, [GCT6] suggests reducing the representation-theoretic problems above to Integer Programming problems, then showing that the resulting IPs are solved by their LP relaxations, and finally giving combinatorial algorithms for the resulting LPs. The conjectures in [GCT6] are themselves motivated by reverse-engineering known results for the Littlewood-Richardson coefficients, an analogous but easier problem in representation theory. In the case of LR coefficients, the Littlewood-Richardson combinatorial rule came first. Later Berenstein and Zelevinsky [BZ] and Knutson and Tao [KT] (see [KT2] for a friendly overview) gave an IP for LR coefficients. Knutson and Tao also proved the saturation conjecture, which implies that the IP is solved by its LP relaxation (cf. [GCT3,BI]).

The results of [GCT5] show that explicitly derandomizing Noether's Normalization Lemma is essentially equivalent to the notorious open problem in complexity theory of black-box derandomization of polynomial identity testing. Roughly how this fits into the larger program is that finding an explicit basis for the functions $p$ that (do not) vanish on $\mathcal{C}_{easy}$ (in this case, the class for which the determinant is complete) could be used to derive a combinatorial rule for the desired problem in representation theory, as has happened in other settings in algebraic geometry. An intermediate step here would be to find a basis for those $p$ that (do not) vanish on the normalization of $\mathcal{C}_{easy}$, which is by construction a nicer algebraic variety -- in other words, to derandomize Noether's Normalization Lemma for DET.

Examples of symmetries of complexity and functions

For example, the complexity of a function $f(x_1, \dotsc, x_n)$ - for most natural notions of complexity - is unchanged if we permute the variables $f(x_{\pi(1)}, \dotsc, x_{\pi(n)})$ by some permutation $\pi$. Thus permutations are symmetries of complexity itself. For some notions of complexity (such as in algebraic circuit complexity) all invertible linear changes of the variables are symmetries.

Individual functions may have additional symmetries. For example, the determinant $\det(X)$ has the symmetries $\det(AXB) = \det(X^{T}) = \det(X)$ for all matrices $A,B$ such that $\det(AB) = 1$. (From what little I picked up about this, I gather that this is analogous to the phenomenon of spontaneous symmetry-breaking in physics.)

Some Recent Progress [this section definitely incomplete and more technical, but a complete account would take tens of pages....I just wanted to highlight some recent progress]

Burgisser and Ikenmeyer [BI2] showed a $\frac{3}{2}n^2$ lower bound on matrix multiplication following the GCT program as far as using representations with zero vs nonzero multiplicities. Landsberg and Ottaviani [LO] gave the best known lower bound of essentially $2n^2$ on the border rank of matrix multiplication using representation theory to organize algebraic properties, but not using representation multiplicities nor combinatorial rules.

The next problem after Littlewood-Richardson coefficients is the Kronecker coefficients. These show up both in a series of problems that is suspected to eventually reach the representation-theoretic problems arising in GCT, and more directly as bounds on the multiplicities in the GCT approach to matrix multiplication and permanent versus determinant. Finding a combinatorial rule for Kronecker coefficients is a long-standing open problem in representation theory; Blasiak [B] recently gave such a combinatorial rule for Kronecker coefficients with one hook shape.

Kumar [K] showed that certain representations appear in the coordinate ring of the determinant with nonzero multiplicity, assuming the column Latin square conjecture (cf. Huang-Rota and Alon-Tarsi; this conjecture also, perhaps not coincidentally, shows up in [BI2]). Hence these representations cannot be used to separate permanent from determinant on the basis of zero vs nonzero multiplicities, though it still might be possible to use them to separate permanent from determinant by a more general inequality between multiplicities.

References
[B] J. Blasiak. Kronecker coefficients for one hook shape. arXiv:1209.2018, 2012.

[BI] P. Burgisser and C. Ikenmeyer. A max-flow algorithm for positivity of Littlewood-Richardson coefficients. FPSAC 2009.

[BI2] P. Burgisser and C. Ikenmeyer. Explicit Lower Bounds via Geometric Complexity Theory. arXiv:1210.8368, 2012.

[BZ] A. D. Berenstein and A. V. Zelevinsky. Triple multiplicities for $\mathfrak{sl}(r+1)$ and the spectrum of the exterior algebra of the adjoint representation. J. Algebraic Combin. 1 (1992), no. 1, 7–22.

[GCT1] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems. SIAM J. Comput. 31(2), 496–526, 2001.

[GCT2] K. D. Mulmuley and M. Sohoni. Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. SIAM J. Comput., 38(3), 1175–1206, 2008.

[GCT3] K. D. Mulmuley, H. Narayanan, and M. Sohoni. Geometric complexity theory III: on deciding nonvanishing of a Littlewood-Richardson coefficient. J. Algebraic Combin. 36 (2012), no. 1, 103–110.

[GCT5] K. D. Mulmuley. Geometric Complexity Theory V: Equivalence between blackbox derandomization of polynomial identity testing and derandomization of Noether's Normalization Lemma. FOCS 2012, also arXiv:1209.5993.

[GCT6] K. D. Mulmuley. Geometric Complexity Theory VI: the flip via positivity., Technical Report, Computer Science department, The University of Chicago, January 2011.

[K] S. Kumar. A Study of the representations supported by the orbit closure of the determinant. arXiv:1109.5996, 2011.

[LO] J. M. Landsberg and G. Ottaviani. New lower bounds for the border rank of matrix multiplication. arXiv:1112.6007, 2011.

[KT] A. Knutson and T. Tao. The honeycomb model of $\text{GL}_n(\mathbb{C})$ tensor products. I. Proof of the saturation conjecture. J. Amer. Math. Soc. 12 (1999), no. 4, 1055–1090.

[KT2] A. Knutson and T. Tao. Honeycombs and sums of Hermitian matrices. Notices Amer. Math. Soc. 48 (2001), no. 2, 175–186.

GCT is a research program for proving complexity theory bounds and in a way defies a wikipedia-style abstract/summary due to its heavy abstraction, but for the TCS crowd good surveys are available.[2][3][4] (and surely Wikipedia is the best place for wikipedia entries). it was formulated in the early 2000s by Mulmuley and is both relatively new in complexity theory and very advanced, using and applying advanced mathematics (algebraic geometry) that did not originate in TCS/complexity theory.

the approach is considered promising by some but possibly too complex by other authorities ie it is not proven and therefore controversial whether it could overcome standard known "barriers". (in this sense it does exhibit some signs of a so-called Kuhnian "paradigm shift".) even Mulmuley proposes that it realistically might not succeed (in proving major complexity class separations) after decades of further development. here is a skeptical opinion by Fortnow, a leading authority in the field of complexity theory:[1]

  Consider a huge mountain and you want to reach the mountaintop. Ketan comes along and says he'll teach you how to create the tools needed to climb the mountain. It will take a hard month of study and actually these tools aren't good enough to climb the mountain. They need to be improved and these improvements won't happen in your lifetime. But don't you want to learn how others will climb the mountain centuries from now?

[1] How to prove NP different than P Fortnow blog

[2] Understanding the Mulmuley-Sohoni Approach to P vs. NP Regan

[3] On P vs. NP and Geometric Complexity Theory Mulmuley

[4] The GCT program towards the P vs. NP problem Mulmuley


Convergence theorem for Genetic Programming? Genetic Programming (GP) is stochastic algorithm, there has been early attempts to explain its convergence with the Schmea Theorem (Holland 1975) for Genetic Algorithm adapted for GP such as (Koza 1992) (O'Reilly 1994) (Altenberg 1994) (Rosca 1997), but I was wondering if someone could point me to the generally agreed theorem that proves GP's covergence? Does it exist?

References:

[Altenberg 1994]: Altenberg, Lee. "Emergent phenomena in genetic programming." Evolutionary Programming—
Proceedings of the Third Annual Conference. World Scientific Publishing, 1994.
[Goldberg 1989]: Goldberg, David. “Genetic Algorithms in Search, Optimization and Machine Learning.” Addison-
Wesley Professional, Reading, MA 1989.
[Koza 1992]: Koza, John R. Genetic programming: on the programming of computers by means of natural selection.
[O'reilly 1994]: O'Reilly, Una-May, and Franz Oppacher. Using Building Block Functions to Investigate a Building Block Hypothesis for Genetic. No. 94-04-020. 1994.
Vol. 1. MIT press, 1992.
[Rosca 1997]: Rosca, Justinian P. "Analysis of complexity drift in genetic programming." Genetic Programming
(1997): 286-294.

I am not sure that there is one Theorem to point to. Anyhow, you will probably be interested in the following reference, which summarizes many more recent results than those you mention in the question, e.g., for the (1+1)-EA with linear functions, quadratic functions, and monotone polynomials as objective functions (I know these are probably much simpler functions than you care about). Anyway the citations within should give you good pointers, via Google Scholar, to even newer results.

Stefan Droste, Thomas Jansen, Günter Rudolph, Hans-Paul Schwefel, Karsten Tinnefeld, and Ingo Wegener (2002): Theory of evolutionary algorithms and genetic programming.  In H.-P. Schwefel, I. Wegener, and K. Weinert (Eds.): Advances in Computational Intelligence Theory and Practice. Springer, Berlin, Germany, pages 107-144.

You have an endofunction:

genetic :: Population -> Population

What are the idempotents? What are the indexes and periods?

Convergence means that under iteration most Populations hit upon a high fitness Population, i.e. high fitness Populations form a near dominating set over the rest of the population space if you make a graph that has edges f^i -> f.


Curious about computer-assisted NP-completeness proofs In the paper "THE COMPLEXITY OF SATISFIABILITY PROBLEMS" by Thomas J. Schaefer, the author has mentioned that

This raises the intriguing possibility of computer-assisted NP-completeness proofs. Once the researcher has established the basic framework for simulating conjunctions of clauses, the relational complexity could be explored with the help of a computer. The computer would be instructed to randomly generate various input configurations and test whether the defined relation was non-affine, non-bijunctive, etc.

Of course, this is a limitation:

The fruitfulness of such an approach remains to be proved: the enumeration of the elements of a relation on lO or 15 variables is Surely not a light computational task.

I am curious that

  Are there follow-up researches in developing this idea of "computer-assisted NP-completeness proofs"? What is the state-of-the-art (may be specific to $\textsf{3SAT}$ or $\textsf{3-Partition}$)?
  Since Schaefer has proposed the idea of "computer-assisted" NP-Completeness proof (at least for reductions from $\textsf{SAT}$), does this mean there are some general principles/structures underlying these reductions (for the ones from $\textsf{3SAT}$ or $\text{3-Partition}$)? If so, what are they?
  Does anyone have experience in proving NP-completeness with a computer-assistant? Or can anyone make up an artificial example?

As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant.

Erickson and  Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-complete. They gave a polynomial time reduction from planar 3-SAT to tatami domino covering. A SAT-solver (Minisat) was used to automate gadgets discovery in the reduction. No other $NP$-completeness proof is known for it.

Ruepp and Holzer proved that pencil puzzle Kakuro is $NP$-complete. Some parts of the $NP$-completeness proof were generated automatically using a SAT-solver ( again Minisat).

the questioner has indicated he is ok with a more broad interpretation of the Schaefer statement in an answer. coincidentally have been collecting links for a blog on a nearby topic & will write some up here.
the original statement (sec 7 p225) is clear in its intentions as illustrated with example of a NP complete reduction from 2 colorable perfect matching thm 7.1 using the "dichotomy thm" 2.1.
so his stated idea is that one has some algorithm $F(x)$ that generates SAT clauses, and one a priori does not know the overall structure of these clauses, and that one can generate sample formulas and examine their clause structure to see how they relate to the dichotomy thm. the idea is a sketch and omits some details because obviously even if all finite set of samples adhere to some rule it is not a proof. ie its not automated but "computer assisted." (human analysis/ interpretation is required).
Schaefer also refers to randomly generating various input configurations ie examining samples $F(x)$ over random $x$.
taking a broad pov these general ideas can be seen to have grown & been explored in many areas of research since these 1978 musings/ "seed ideas" leading to entire large branches and research programs, still ongoing, none of which existed in almost any form at the time of writing of Schaefers paper. 1st one general idea is empirical analysis of NP completeness properties via instance generators/ solvers/ analyzers.

the largest research area spawned here is into random SAT instances and looking at SAT solver performance on them which led to discovery of the transition point in the mid 1990s, later shown to have deep connections to statistical physics and an apparently ubiquitious/ intrinsic/ fundamental aspect/ characteristic of all NP complete problems. there are very many papers in this area & now a few books. see eg Information, physics, and Computation Mezard / Montanari

Decomposing satisfiability problems
or Using graphs to get a better insight into satisfiability problems, Herwig 2006 (83pp). this is a somewhat novel approach wrt other published research that looks at the variable-clause graph structure of generated SAT instances and analyzes their structure/ metrics to find correlations with hardness.

one can take conjectured-hard problems and encode them as SAT instances & then examine their structure or run SAT solvers on them & observe the dynamic behavior of the SAT solvers. its not easy to figure out when this was 1st done but an early case is with factoring, probably in the mid 1990s or so, and these instances showed up in the DIMACS SAT solver contests. unfortunately this was not necessarily considered separately publishable research results at the time. there are allusions in a few SAT papers.
see eg Satisfy This: An Attempt at Solving Prime Factorization using Satisfiability Solvers by Stefan Schoenmackers, Anna Cavender and also cs.se question reducing integer factorization problem to NP complete problem & (there are some other related/ scattered (T)CS stackexchange questions on this).

2nd another modern general idea/ seed inherent in Schaefers old statement is attacking hard algorithmic or mathematical problems in general by converting them to SAT instances, and using off-the-shelf (but state-of-the-art) SAT solvers (ie SAT solving can be regarded broadly as literally one of the earliest cases in logic/ math of computer automated theorem proving where SAT formula solutions are like "theorems", although admittedly the modern pov on that may have shifted somewhat) and there are some notable recent successes on this front.

the Erdos Discrepancy problem related to bounds on random walks is very hard and progress was limited with analytic approaches, and a novel/ unprecedented, empirical approach with SAT was recently taken to achieve some key results on a related open problem, celebrated by many as a veritable breakthrough. a SAT attack on the Erdos discrepancy conjecture Konev, Lisitsa

research on optimal sorting networks goes back decades and there are natural hard open problems on minimal sizes of networks to sort a given number of elements. within last few years there has been major recent progress in converting these to SAT instances & running standard solvers on them. New Bounds on Optimal Sorting Networks Ehlers, Müller, also cites other recent work.


Applicability of Church-Turing thesis to interactive models of computation Paul Wegner and Dina Goldin have for over a decade been publishing papers and books arguing primarily that the Church-Turing thesis is often misrepresented in the CS Theory community and elsewhere.  That is, it is presented as encompassing all computation when in fact it applies only to computation of functions, which is a very small subset of all computation.  Instead they suggest we should seek to model interactive computation, where communication with the outside world happens during the computation.

The only critique I have seen of this work is in the Lambda the Ultimate forum, where somebody lamented these authors for continually publishing what is obviously known.  My question then is, is there any more critique into this line of thinking, and in particular their Persistent Turing Machines.  And if not, why then is it seemingly studied very little (I could be mistaken).  Lastly, how does the notion of universality translate to an interactive domain.

Here's my favorite analogy.  Suppose I spent a decade publishing books and papers arguing that, contrary to theoretical computer science's dogma, the Church-Turing Thesis fails to capture all of computation, because Turing machines can't toast bread.  Therefore, you need my revolutionary new model, the Toaster-Enhanced Turing Machine (TETM), which allows bread as a possible input and includes toasting it as a primitive operation.

You might say: sure, I have a "point", but it's a totally uninteresting one.  No one ever claimed that a Turing machine could handle every possible interaction with the external world, without first hooking it up to suitable peripherals.  If you want a TM to toast bread, you need to connect it to a toaster; then the TM can easily handle the toaster's internal logic (unless this particular toaster requires solving the halting problem or something like that to determine how brown the bread should be!).  In exactly the same way, if you want a TM to handle interactive communication, then you need to hook it up to suitable communication devices, as Neel discussed in his answer.  In neither case are we saying anything that wouldn't have been obvious to Turing himself.

So, I'd say the reason why there's been no "followup" to Wegner and Goldin's diatribes is that TCS has known how to model interactivity whenever needed, and has happily done so, since the very beginning of the field.

Update (8/30): A related point is as follows.  Does it ever give the critics pause that, here inside the Elite Church-Turing Ivory Tower (the ECTIT), the major research themes for the past two decades have included interactive proofs, multiparty cryptographic protocols, codes for interactive communication, asynchronous protocols for routing, consensus, rumor-spreading, leader-election, etc., and the price of anarchy in economic networks? If putting Turing's notion of computation at the center of the field makes it so hard to discuss interaction, how is it that so few of us have noticed?

Another Update: To the people who keep banging the drum about higher-level formalisms being vastly more intuitive than TMs, and no one thinking in terms of TMs as a practical matter, let me ask an extremely simple question.  What is it that lets all those high-level languages exist in the first place, that ensures they can always be compiled down to machine code?  Could it be ... err ... THE CHURCH-TURING THESIS, the very same one you've been ragging on?  To clarify, the Church-Turing Thesis is not the claim that "TURING MACHINEZ RULE!!"  Rather, it's the claim that any reasonable programming language will be equivalent in expressive power to Turing machines -- and as a consequence, that you might as well think in terms of the higher-level languages if it's more convenient to do so.  This, of course, was a radical new insight 60-75 years ago.

Final Update: I've created a blog post for further discussion of this answer.

skimming Wegner's paper, its clear he's being a bit melodramatic and contrarian, but he has a point. the future of computing is arguably much more significantly centered in robotics, AI, or datamining (of vast real world "big data") which he doesnt seem to mention very much by name, but which he is clearly alluding to with his model. and these areas very much largely focus on the universe outside of a TMs inputs and outputs.

historically it also went by the name cybernetics as invented/formulated by Weiner. the point of robotics is that inputs and outputs are not merely digital and without meaning, which one might conclude looking at a TM; they are, but they have real world implications/effects/causes etc., and the machine forms a feedback loop with the environment.

so I would argue that TMs and robotics form a very natural synergy or symbiotic relationship so to speak. but this is not a radical assertion and what Wegner announces with great fanfare is, phrased in different terms, not very controversial or novel. in other words, Wegner seems to be setting himself up as an intellectual or academic iconoclast in his style on purpose... and so who is the TCS community to deny him that melodramatic framing? nevertheless see [2] for a serious rebuttal.

Wegner's example of driving a car is very relevant & other key recent breakthoughs in TCS can be cited:

the DARPA road race challenge and also Google's closing in on the technology of a driving car.[3]
the case of the Big Blue AI chess victory over Kasparov
the recent Deep Blue Jeopardy Challenge victory
the increasingly autonomous Mars rover
a recent announced breakthrough in unsupervised object recognition by Google.[4]
commercialized speech recognition

but it is true, what started out decades ago as mere theory with TMs is now a very real-world phenomenon and segments of the ivory tower TCS community might be in some resistance or even denial of that fact and the associated, fundamental [near Kuhnian] transformation and shift "currently in play". this somewhat ironic because Turing was very applied in many of his perspectives & studies such as his interest in an operational AI test (the Turing test), chemical dynamics, chess solving computation, etc [5].

you can even see this in a microcosm on this site in clashes over how to define the scope, and heated arguments over whether a specific seemingly innocuous tag called application-of-theory is legitimate.[7]

and lets note that TCS is in fact studying many interactive models of computation and much key research is going on in that area... particularly interactive proof systems of which all the important computing classes can be defined in terms of.[6]

[1] The Church-Turing thesis-- breaking the myth by Goldin & Wegner

[2] Are there new models of computation? a reply to Goldin & Wegner by Cockshott & Michaelson

[3] Googles self-driving cars-- 300K miles logged, not a single accident under computer control, the Atlantic

[4] Google unsupervised object recognition of Youtube images

[5] Alan Turings contributions to CS

[6] Landscape of interactive proof systems

[7] On modifying our scope-- a proposal


EXPSPACE-complete problems I am currently trying to find EXPSPACE-complete problems
(mainly to find inspiration for a reduction), and
I am surprised by the small number of results coming up.

So far, I found these, and I have trouble expanding the list:

universality (or other properties) of regular expressions with exponentiation.
problems related to vector addition systems
unobservable games (see for instance this blog)
some fragment of FO-LTL, in On the Computational Complexity of Decidable Fragments of First-Order-Linear Temporal Logics

Do you know other contexts when EXPSPACE-completeness appears naturally?

Extending the example pointed out by Emil Jerabek in the comments, $\mathsf{EXPSPACE}$-complete problems arise naturally all over algebraic geometry. This started (I think) with the Ideal Membership Problem (Mayr–Meyer and Mayr) and hence the computation of Gröbner bases. This was then extended to the computation of syzygies (Bayer and Stillman). Many natural problems in computational algebraic geometry end up being equivalent to one of these problems. Also see the Bayer–Mumford survey "What can be computed in algebraic geometry?"

an example & proof is given in Introduction to Automata Theory, Languages, and Computation Hopcroft/ Ullman Thm13.16 that any nondeterministic algorithm for the first-order theory of reals with addition is NExpTime-hard. therefore it is presumably also NExpSpace-hard unless some theoretical breakthrough proves it can be solved "in tighter space" but of course that question is similar (nearly identical?) to L=?P. (in other words all the known NExpTime-hard problems are also basic candidates for NExpSpace-hard, and if any provably arent, it would likely mean a breakthrough resolution of a long-open complexity class separation.) the proof comes from Fischer, Rabin 1974, "Super-exponential complexity of Presburger arithmetic," Complexity of Computation (R. Karp ed.). Proceedings of SIAM-AMS Symposium in Applied Mathematics.