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.


What are the theoretical limits of the Stratego Programming Language?

I'll have a go at the answer, though I do not have a concrete program for you to try. In one Eelco Visser blog entry you can see a screen shot containing essentially the lambda calculus encoded in Stratego (I'm sure this code is available elsewhere). He presents an interpreter for the lambda calculus in Stratego. Presumably, this is sufficient to show that Stratego is Turing-complete.

If you are interested in a more specific notion of expressiveness, then I suggest that you rephrase your question.

In terms of practical usage, I found Stratego's main limitation that it operated over only one data structure, namely, the tree being transformed. Using other data structures such as a table of symbols was unnatural (at least in Stratego from 5+ years ago). Even though Stratego is ideal for transformations on a single tree, performing operations on two trees simultaneously is not easy.


$\mathsf{NL} \neq \mathsf{coNL}$. Prior to the result that these two were equal, I think it was widely believed that they were distinct, by analogy with the belief that $\mathsf{NP} \neq \mathsf{coNP}$ (i.e. the general principle that "nondeterministism and co-nondeterminism are different"; this turned out to be false under space complexity bounds that were at least logarithmic).


Does anyone know of online video courses (in english) on randomness in theoretical computer science?

leading expert on the topic Wigderson at IAS has recently been lecturing/researching/survey/overviewing this important/emerging/crosscutting area.

Avi Wigderson -- "Randomness" youtube
Professor Avi Wigderson on a computational theory of randomness youtube/ETH Zurich

written notes similar to/overlapping these lectures:

Tao notes on Widgerson power/weakness of randomness in computation Terence Tao blog
COMPUTATIONAL INTRACTABILITY AND PSEUDORANDOMNESS essay by Wigderson


On the size of P4-transversals of graphs

Let H be any graph on N vertices and requires T vertices in a P4-transversal (so its ratio is T/N).
Construct G like in the previous examples: G is a P4 but substitute an H in for each vertex. Then the total number of vertices of G is n = 4N and the transversal size is N + 3T.

This gives a ratio of (N+3T)/4N = (1/4) + (3/4)T/N

So, the last example I gave in the comment of Peng Zhang's answer used H = $P_4$ with T/N = 1/4 and the ratio was 1/4 + 3/16 = 7/16.

Now use that 7/16 graph in for H and construct G. This uses 64 vertices, and the transversal size is 16 + 3(7) = 37. We get a ratio of (1/4) + (3/4)(7/16) = 16/64 + 21/64 = 37/64 which is already over 50%.

This seems correct to me (in that I don't see what is wrong with it) but it is troublesome, because repeating this process will get to a fixed point x = (1/4) + (3/4)x , which is x=1.0 (?)

Thoughts...?


Would a purely topological computational model be useful in decision problems in topology?

Avishy Carmi and Daniel Moskovich have been developing tangle machines very recently, which is a topological model to describe information. There are two papers on the arXiv, as well as three introductory posts on the blog "Low Dimensional Topology" :

http://ldtopology.wordpress.com/2014/05/04/low-dimensional-topology-of-information/


Relationship between context-free/decidable languages and NP

Basic Facts:

CYK-algorithm parses inputs of length $n$ for any CFG in Chomsky normal form in time in $\mathcal{O}(n^3)$
Every CFL is generated by a CFG in Chomsky normal form
Every regular language is (also) context-free.

That answers immediately all those questions:

  What is the relationship between NP and context-free/regular languages? Are there context-free languages in NP? Are there regular languages in NP?

$\{a^nb^nc^n \mid n \geq 0\}$ is not context-free (by pumping lemma). It can obviously be decided by a (D)TM in quadratic time. That answers:

  Are there languages in NP that are not
  context-free? Are there languages in
  NP that are not regular?

And as for

  Are there also decision problems that
  are decidable but not in NP?

Yes, see Problems that cannot be verified in polynomial time


Is there an online-algorithm to keep track of components in a changing undirected graph?

There are several data structures that support edge insertions, edge deletions, and connectivity queries (Are these two vertices in the same connected component?) in polylogarithmic time.

Monika R. Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  Journal of the ACM 46(4):502—516, 1999.
Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM 48(4):723—760, 2001.
Mikkel Thorup.  Near-optimal fully-dynamic graph connectivity.  Proc. 32nd STOC 343—350, 2000.


Implications of the rule of cumulativity in the Calculus of Constructions

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

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


Is this multiprocessor scheduling problem with overlaps NP-Hard?

Reduce Garey & Johnson problem [SS8], Multiprocessor Scheduling, to your problem.  This is NP-complete, even if $m=2$.  In this problem there are no overlaps, and a deadline is specified.  Your problem is therefore NP-hard, even in the case of zero overlaps.

If you require non-zero overlaps, then it is still possible to reduce Multiprocessor Scheduling to your problem, by increasing the length of each task by 1, and specifying all overlaps to be exactly 1.


Efficient encoding of integers with constant digit sum

Just omit the last digit.

(Extra text to get over the 30-chaacter minimum.)


Concepts in theoretical CS that would be approachable ages 8-14

Computer Science Unplugged addresses kids (and teachers) in primary school.


How to come up with an non-trivial idea in theoretical computer science?

Almost certainly there are lists of open problems in your particular subfield.  Find them and read them.  Although it's rather unlikely you will be able to solve these problems --- at least right away ---, use them as a starting point.  Can you solve some particular cases?  Can you solve a less general problem?  Can you show a more general problem is computationally difficult?
Read what other people are doing.  This means making a list of the conferences and journals in your area, and devoting at least an hour a day to reading papers in them.  There is no need to understand everything at once.  Try to familiarize yourself with the general themes, then pick one or two papers that seem interesting or fundamental and immerse yourself in them.  Study the
techniques and proofs.  Can you apply them to similar or related problems?  Work out specific examples in detail, to the extent possible.
When reading any result, ask yourself:  are all the hypotheses necessary?  What if the hypotheses are weakened or strengthened?  Are the bounds really optimal?  If only an upper bound is proved, can you prove a matching lower bound?


Do buyers bidding for sellers and sellers bidding for buyers produce equivalent outcomes?

Generally speaking, auctions can go both ways in a dual manner: you can sell something via an auction among buyers or you can buy something via a procurement auction among possible providers (sellers).  The asymmetry usually comes from where the competition lies: the auctioneer holds a "monopoly" while the bidders compete with each other.

In the example of ad auctions we usually view the advertisers as having unlimited demand for "impressions" and thus there is no effective competition between websites which each can be viewed as having a monopoly over the impressions it delivers.  More realistic models may take into account some limits on the demand of advertisers for impressions (e.g max impressions or budget limits) in which case taking competing websites into account too would take us out of the usual auction model and into a two-sided market scenario.

Generally speaking there is no reason for the prices of a buyer-led auction to be equal to those from a seller-led one.  Consider even the case of one buyer and one seller: certainly the side running the "auction" (which in this case is just setting a transaction price for the other to take or leave) can set it at the others' value in order to optimize for himself.  A related example would be the stable-marriage problem where a "men-propose algorithm" produces a man-optimal matching, while a "women-propose algorithm" produce a women-optimal one.


Fast classical simulation of quantum algorithms

Your question was inspired by the recent quantum-inspired classical advance in recommendation algorithm. Note that it is not the firs time such a thing happens. In 2015, similar developments happened with approximate MAX3LIN: a quanutm algorithm outperforming all previous known classical algorithms motivated a succesfull search for a better classical algorithm. However, as far as I know, in both these cases, the classical algorithms do not look like classical simulation of a quantum evolution.

I know of one paper describing a classical simulation of a quantum system allowing to outperform previously known algorithms
(Full disclosure: the authors are friends of mine):

  A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices, by
  L. Chakhmakhchyan, N. J. Cerf, R. Garcia-Patron,
  arXiv:1609.02416 /
  Phys. Rev. A 96, 022329

This is based on the connection between the permanent and quantum optics, shown by boson sampling. In opposition to the usual approach, they look at states who are well known to be easy to simulate (thermal states), and use this simulation to perform a Monte-Carlo computation of the permanent of Hermitian positive semidefinite matrices. For some classes of matrices, this algorithm gives a better approximation than the best previously known algorithm (Gurvits algorithm).


Maximal munch rule issue for lexers: is detection decidable?

To answer in the large, the fact that the syntax of programming languages is not context-free is not news (see e.g. Floyd, 1962).

To answer more precisely, in a context of scannerless parsing like yours, a way to implement maximal munch is to employ so-called follow restrictions (van den Brand et al., 2002) by forbidding some language to follow a given rule.  In your example, you could write a restriction X -/- a forbidding an $a$ after the token $X$.  Provided your forbidden languages are regular, these restrictions can be compiled back into the grammar (however in van den Brand et al.'s formalism, the forbidden language can be context-free and $X$ can be any nonterminal, and this clearly leads to an undecidable emptiness problem).

Another formalism for scannerless parsing is that of parsing expression grammars (Ford, 2004), which has a greedy, maximal-munch type semantics, and an undecidable emptiness problem.

Now, it doesn't look like your specific maximal munch semantics would allow you to reduce from these undecidable problems.  For a start, it seems to me that, rather than emptiness of the generated language, a tool should more broadly warn the user about any case where a token might "eat" a (non-empty) prefix of its follow language, i.e. whenever $(L_T\cdot\mathrm{Pref}_+(L_R))\cap L_T\neq\emptyset$, regardless of whether this prefix is mandatory of not.  This would capture your $aba^\ast b^\ast ab$ example if I understand correctly how you would tokenize it.

To conclude, here is an attempt to formalize your notion of maximal-munch-caused emptiness: let $\langle N,T,P,S\rangle$ be a context-free grammar with nonterminal alphabet $N$, terminal alphabet $T$, production set $P$ and axiom $S$.  Each terminal symbol $X\in T$ is associated with a regular language $L_X\subseteq\Sigma^\ast$ used for its tokenization.  For every occurrence of a terminal symbol $X$ in some production $A\to \alpha X\beta$ of your grammar where $\alpha,\beta$ are sequences of mixed terminals and nonterminals, construct the follow language $L_{\beta,A}$ of this particular occurrence (this is a context-free language) and consider the residual language of the token $L^{\text{max-munch}}_X=(L_X^{-1}\cdot L_X)\cap\Sigma^+$, which is a regular language of strings that will be "eaten up" by the maximal munch semantics.  In fact the language $L^{\text{max-munch}}_X$ is the language one would put in the follow restriction for $X$.  Then, if $$L_{\beta,A}\subseteq L^{\text{max-munch}}_X\cdot\Sigma^\ast\;,$$ or equivalently $L_{\beta,A}\cap (\Sigma^\ast\backslash(L^{\text{max-munch}}_X\cdot\Sigma^\ast))=\emptyset$, any string allowed to follow this occurrence of $X$ will be "eaten", and the language of the rule $A\to\alpha X\beta$ is empty.  Using the classical algorithm for emptiness checking with this extra twist for handling terminal symbols might solve your emptiness problem.


Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

Of course the equalities and inclusions claimed in the question hold only for uniform $\mathsf{NC}^k$. The class $\mathsf{AALTSP}(\log^k n, \log n)$ is the same as uniform $\mathsf{AC}^k$, so the question is the same as whether $\mathsf{NC}^k = \mathsf{AC}^k$.

In particular the case $k=1$ implies that $\mathsf{L}$ is equal to $\mathsf{NL}$ and even $\mathsf{LogCFL}$, since $\mathsf{NC}^1 \subseteq \mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{LogCFL} \subseteq \mathsf{AC}^1$.


What is the best way to find an induced cycle basis of a graph?

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

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

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

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

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


What is the space complexity of CTL model checking?

In general, CTL model checking is P-complete. Since we think that $L\neq P$ (and moreover $NL\neq P$), it is unlikely that an algorithm with logarithmic space exists. It is also unlikely that a sub-polynomial space algorithm exists, for similar reasons of common belief.

I don't know of exact space-optimizations for the problem, but in general - yes, you need to mark each state with a formula, so naively you need the size you suggest. It may be the case that you can reduce the formula by encoding it more succinctly, but it hasn't attracted attention in research.

You can start from this survey for citations.


On the status of learnability inside $\mathsf{TC}^0$

The main thing missing from your list is the beautiful 2006 paper of Klivans and Sherstov.  They show there that PAC-learning even depth-2 threshold circuits is as hard as solving the approximate shortest vector problem.


Early history of certain results on space-time tradeoffs?

I do not know if it is the first occurrence or not, but the construction appears in the proof of Lemma 1 of Borodin [Bor77] about the space complexity of evaluating a Boolean circuit.  (It contains slightly more than just the idea of recursive evaluation to reduce the space complexity further from O(D log S) bits to O(D + log S) bits, where D is the depth of the circuit and S is the size of the circuit.)

[Bor77] Allan Borodin.  On relating time and space to size and depth.  SIAM Journal on Computing, 6(4):733–744, Dec. 1977.  DOI: 10.1137/0206054.


Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

EDIT: I was wrong about the implication to arithmetic circuits.

I think it is possible. It uses ideas in parallel evaluation of arithmetic expressions and tree contraction.

Consider the arithmetic formula, it is an arithmetic circuit that forms a directed tree. Consider each gate as a function of the form $f(x,y) = a(x\square y)+b$ for constant $a,b$ and operation $\square$. So, a $\square$ gate is $1(x\square y)+0$.
We call $a$ the linear part, and $b$ the constant part.
One can evaluate the formula by a "tree contraction" operation. It takes 3 vertices $u,v,w$ and returns one new vertex in this tree. Here $u,v$ are children of $w$, and $u$ is a leaf.
That is, we can delete node $u$, contract $w$ and $v$ into to a new vertex $w'$, and the gate for $w'$ is a function of the form $a(x\square y)+b$ for some constants $a$ and $b$, and we have the tree evaluates to the same value.

Here is an example:

Let $\ell(v)$ be the labels of $v$, defined as all the input used to compute the linear and constant part of the gate $v$.

Facts:

One can apply tree contraction to a constant fraction of vertices in
parallel. Let such parallel operation be called a single iteration.
At any moment of the computation, $\{\ell(v) | v\in V_t\}$ forms a partition of the input, where $V_t$ is the vertices of the formula after the $t$th contraction.
The coefficient of the linear term and constant term on each node can be expressed as a single-use expression (i.e. each variable in the input is used at most once). It implies if $y$ is the constant part or linear part of the vertex $v$, then $|y| \leq \sum_{x\in \ell(v)} |x|$. Note this fact is only used to bound the size of the coefficient. The computation of the coefficient itself is not related to the single-use expression.

Consider an algorithm that does $O(\log(n))$ iterations of tree contraction in parallel, and get a constant size tree. We evaluate the final tree directly. In each iteration, the running time is bounded by the sum of the size of the labels for each node, which is $O(m)$ due to disjointness of the label sets over the vertices.

Together the running time is $O(m\log n)=O(m\log n)$.


from a search, here is a paper with some research & findings for graduate level research but (caveat) no references. it has some heuristics, estimates, empirical results & commentary on the problem and some ideas on proving its (approximation) complexity etc.

Identification of Most Frequent Subsequences
CSE 549 Computational Biology Project Final Report
Mikhail Bautin 2006

(while there are some standard subsequence problems that are somewhat similar & studied eg in the Elzinga et al paper, is it possible this particular subsequence problem has not been studied too much?)


What are the root difficulties in going from graphs to hypergraphs?

In this question I understand "difficulty" refers not to "difficult to compute," but to "difficult to study."

Graph problems are easier (at least for me) to study since some concepts happen to be equivalent.  In other words, if you want to generalize questions for graphs to those for hypergraphs, you need to pay attention to the "right" generalization so that the desired consequence can be obtained.

For example, consider a tree.  For graphs, a graph is a tree if it is connected and contains no cycle.  This is equivalent to being connected and having n-1 edges (where n is the number of vertices), and also equivalent to containing no cycle and having n-1 edges.  However, for 3-uniform hypergraphs, let's say a 3-uniform hypergraph is a tree if it is connected and contains no cycle.  But, this is not equivalent to being connected and having n-1 hyperedges, nor to containing no cycle and having n-1 hyperedges.

I've heard a main difficulty to prove the regularity lemma for uniform hypergraphs was to come up with the right definitions of regularity and related concepts.

When you want to consider "spectral hypergraph theory," you may try to look into tensors, or into homology if you see a k-uniform hypergraph as a (k-1)-dimensional simplicial complex, from which linear algebra naturally arises.  I don't know which is the "right" generalization for your purpose, or it's possible that neither is right.


When can we say that two programs are different?

Q1: There are many notions of program equivalence (trace equivalence, contextual equivalence, observational equivalence, bisimilarity) which may or may not take into account things such as time, resource usage, nondeterminism, termination. A lot of work has been done on finding usable notions of program equivalence. For example: Operationally-Based Theories of Program Equivalence by Andy Pitts. But this barely scratches the surface. This should be useful even if you are interested in when two programs are not equivalent. One can even reason about non-halting programs (using bisimulation and coinduction).

Q2: One possible answer to part of this question is that interactive programs are not algorithms (assuming that one considers an algorithm to take all of its input at once, but this narrow definition excludes online algorithms). A program could be a collection of interacting processes that also interact with their environment. This certainly doesn't match with the Turing-machine/Recursion theory notion of algorithm.


An edge partitioning problem on cubic graphs

Here is a suggestion for how to show it's NP hard. I don't know if this works or not. First, consider the same problem on multigraphs. NP hardness may be easier to prove there. Try reducing from cubic MAX CUT which is NP hard even to approximate (Berman and Karpinski "On Some Tighter Inapproximability Results"). Divide each edge into two and at each of the new degree-2 vertices attach a vertex with self-loop. Does your maximum partition correspond to a maximum cut?

--

Here is a bit more explanation.

(1)
The problem of maximizing (number of sources+number of sinks) over all orientations of a cubic graph is related to MAXCUT by some linear function. This requires showing some corersspondence between maximal cuts and sources-and-sinks-maximal orientations. In one direction, in a maximum cut (U,V), we can orient all edge from U to V. The internal edges E(U) form a matching, so these can be oriented arbitrarily and similarly for E(V), and the total number of sources and sinks is some linear function of the size of the cut. In the other direction, given a sources-and-sinks-maximal orientation, the partition U=vertices of in-degree 0 or 1, V=vertices of in-degree 2 or 3 gives a cut.

(2)
In the edge-bisecting transformation I described above, in an optimal configuration each loop is coloured the same as the edge next to it, and w.l.o.g that edge is coloured the same as the some other (non-loop) edge next to that. So each bisected edge has one colour coming from its attached loop and one other colour. This corresponds to an orientation and (1) applies.


dependent types and higher-order logic applied in the realm of DSLs

It's time for you to meet Edwin Brady:

http://edwinb.wordpress.com/publications/

His earliest papers are about designing DSLs to solve very concrete problems. Lately, he has also been working on optimizing their performance (using type theoretic tools!).

To explore this design space, I would recommend playing with Agda or Idris.


A more intuitive proof of the Zone theorem ?

This is not cleaner, but it is a good preparation for more advanced stuff, and it is a good example of abstraction...

One can use Davenport-Schinzel sequences argument. Consider the region above your zone line. Every line becomes a ray, and in fact two rays, as we consider the left side and right side as being different. Scan the boundary of this zone from left to right, writing down which rays you encounter. This is a sequence defined over 2n symbols, and the pattern abab is illegal. As such, the length of the sequence is at most 2(2n)-1 = 4n-1. Applying it to the zone below the line, implies a bound of the form 8n.

Now, proving that a sequence of symbols without ...a..b..a..b... as a subsequence of n symbols has length 2n-1 is easy. indeed, consider two consecutive appearances of the same character that are closest to each other in this sequence. Clearly, in between these two characters, each character that appears must be unique. Consider such a character, and observe that if it appears anywhere else in the string, then we will get the forbidden subsequence. As such, this character appears exactly once in the string. Remove it, and remove an extra character if needed if you created two consecutive identical characters. Namely, removing a character from the string shorten it by 2, as such, the maximum length of the string is 2n-1.


Emil Jeřábek's construction [Gill 1977, Simon 1975] works indeed. Assume the formula $A$ has the propositional variables $x = \langle x_1,..,x_n \rangle$ and $y$ is some fresh variable. We can then construct $B$ as a formula $(y \rightarrow A) \wedge (\neg y \rightarrow C)$ whereby the formula $C$ needs to be further specified.
For the formula $C$ we assume the threshold given binary as $s = \langle s_1,..,s_n \rangle$. We can encode the arithmetic comparison $s \leq x$ in binary form, which is the lexicographic order union equality: $\langle s_j,..,s_n \rangle \leq \langle x_j,..,x_n \rangle  := (\neg s_j \wedge x_j) \vee ((s_j \leftrightarrow x_j) \wedge \langle s_{j+1},..,s_n \rangle \leq \langle x_{j+1},..,x_n \rangle)$ for $j<n$ and $(s_n \leq x_n) := (s_n \rightarrow x_n)$ otherwise.
So the formula $C$ will be just $s \leq x$. Now we have for the count of $B$:
$$|B| = |A| + |C| = |A| + 2^n-s$$
And therefore for the majority of $B$:
$$|B| \geq 2^n  \Leftrightarrow |A| \geq s$$
Since $\langle 0,..,0 \rangle \leq \langle x_j,..,x_n \rangle$ is trivially true, we can even construct $C$ gradually via binary search, and thus determine $|A| = s$ by calling $n$-times the majority oracle.


Recursively presenting or even enumerating all P-hard languages

After some further thought, partly triggered by writing a long question, it seems clear that the set of P-hard languages is not countable, and therefore not recursively presentable either.

To see why, consider languages $L$ that satisfy $w\in 2SAT$ iff $ww\in L$. 2SAT can be log-space reduced to any such language by definition. However, there are countably many words that do not have the form $ww$, and the languages might differ on their membership status. Hence we obtain uncountably many P-hard languages of this form.

Moreover, it does not seem possible to recursively present all decidable P-hard languages either, since there is no effective enumeration of all Turing machines that are guaranteed to halt (this seems to be the minimal requirement for applying Schöning's construction).


Grover's algorithm, M out of N, when M is large

When $M=N/2$, you don't need a quantum algorithm; a classical algorithm can find a matching entry in $O(1)$ iterations on average (expected running time), just by randomly guessing an item and checking if it matches.  Grover's algorithm is also randomized, so the quantum computer offers no advantage in asymptotic running time for that case.


Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information

The new SDP that you obtain by replacing minimize by maximize is not necessarily closely related to the first one. Right now the value is infinity, and if you replaced 0 by $Q_a$ on the right side of the constraint, the value is always going to be 0 or infinity (if it's not 0, you can just multiply any solution with positive value by an arbitrary constant, and increase the value).

The way I went about this general issue when solving these SDPs was just implementing the partial trace, and then coding the dual and primal problem separately. The implementation of the partial trace is at https://cs.uwaterloo.ca/~amolinap/prtrace.m, hope it is useful!


NP-complete problems related to Minimizing Variance

The problem should be solved in polynomial time since it can be reduced to the integral convex quadratic minimum-cost flow problem.

The essential part of the objective function is $\sum_{v \in V}m(v)^2$ since $\sum_{v \in V}m(v)$ does not change by a choice of mates.

Given a graph $G=(V,E)$ we construct the following network. The vertex set is $V_+ \cup V_- \cup \{s,t\}$, where $V_+ = \{v_+ \mid v \in V\}$ and $V_- = \{v_- \mid v \in V\}$ are copies of $V$, and $s,t \not\in V_+\cup V_-$.  The vertex $s$ is a source, and $t$ is a sink. The arcs are constructed as follows.

There is an arc from $s$ to each vertex in $V_+$.  The capacity is $k$, and the cost is $0$.
There is an arc from each vertex in $V_-$ to $t$.  The capacity is $+\infty$, and the cost is the square of flow on the arc.
There is an arc from $u_+ \in V_+$ to $v_- \in V_-$ if and only if there is an edge $\{u,v\} \in E$ in $G$.  The capacity is $1$, and the cost is $0$.

Now, we inject the $k|V|$ unit of flow to the network from $s$ toward $t$.  Then, a feasible integral flow corresponds to a mate assignment, and the total cost is $\sum_{v \in V} m(v)^2$.


Complexity of 3SAT where each pair of 3-clauses share at most one variable

The central insight is that you can use two $2$-variable clauses to make sure two variables have the same value. Let me abbreviate $(x \vee \neg y) \wedge (y \vee \neg x)$ with $x=y$.
This allows the following reduction from 3SAT.

Given a 3SAT formula, copy the clauses to your reduction one by one. If you encounter a clause with a variable $x$ you've already seen twice, write the clause with a new variable $y$ instead of $x$ and add two $2$-variable clauses for $x=y$. Call the resulting formula $\phi$.

Formula $\phi$ satisfies requirements 1) and 2). Next, employ the same technique
to ensure requirement 3). Walk through each pair of $3$-variable clauses of $\phi$ and for each pair which shares two variables $x$ and $y$, keep $x$ in one clause and in the other clause, change $x$ to $z$, and add $x=z$. An example:

$(x\vee y\vee h) \wedge (\neg x \vee \neg y \vee h) \mapsto (x\vee y\vee h) \wedge (\neg x \vee \neg z \vee h) \wedge (y=z)$

The resulting formula has as many $3$-variable clauses as the original and two $2$-variable clauses for each third or later repetition of a variable and then some more to satisfy requirement 3). Because the $2$-variable clauses ensure that $x=y$ so that your substitutions work, the resulting formula is satisfiable exactly when the original 3SAT formula was satisfiable. Its length is at most quadratic in the number of clauses of the original formula, so your problem is NP-Complete.

EDIT: I notice I interpreted your question to mean, a variable cannot appear in more than two $3$-variable clauses. The way it is formulated now, requirements 2) and 3) are equivalent. I hope you're not mad.


Lower bound for finding repeated elements in sorted array

Any algorithm would need $\Omega(\log n)$ queries.

To see this, define $f(k)$ to be the number of queries needed for deciding whether an element $x$ appears at least $a$ times in a sorted array $A$. We assume that $x$ appears in $A[m],A[m+1],\dots,A[M]$, and that $k\triangleq\min\{a, m-1, n-M\}$.

Notice that in these notations we are looking to bound $f(\lfloor n/2 \rfloor)$.

Claim: $f(k)\ge \log k$.

Proof:

Consider the first query made by the algorithm.

If it was done within radius $k/2$ of the interval (i.e. somewhere in $[m-k/2,\ldots,M+k/2]$), and found the median at the spot, then we still need at least $f(k/2)$ queries to decide the problem.

If it was done outside that radius, consider the case where the queried cell did not contain the median. Once again, this leaves us with at least $f(k/2)$ queries to be made.

Continue with induction and you get the $\Omega(\log n)$ bound.


What are the advantages and limitations of the various approaches?

Pros of deep embeddings : You can prove and define things by induction on formulas' structure. Examples of interests are the size of a formula.
Cons of deep embeddings: You have do deal explicitly with binding of variables. That's usually very laborious.

  Are there any guidelines available for determining which to use ?

Shallow embeddings are very useful to import result proved in the object logic. For instance, if you have prove something in a small logic (e.g. separation logic) shallow
embeddings can be a tool of choice to import your result in Coq.

On the other side, deep embedding are almost mandatory when you want to prove
meta-theorems about the object logic (like cut-elimination for instance).

  Is it possible to switch between the two representations in any systematic fashion?

The idea behind the shallow embedding is really to work directly in a model of the object formulas. Usually people will maps an object formula P directly (using notations or by doing the translation by hand) to an inhabitant of Prop. Of course, there are inhabitants of Prop which cannot be obtained by embedding a formula of the object logic. Therefore you lose some kind of completeness.

So it is possible to send every result obtained in a deep embedding setting through an interpretation function.

Here is a little coq example:

Inductive formula : Set :=
    Ftrue : formula
  | Ffalse : formula
  | Fand : formula -> formula -> formula
  | For : formula -> formula -> formula.

Fixpoint interpret (F : formula) : Prop := match F with
    Ftrue => True
  | Ffalse => False
  | Fand a b => (interpret a) /\ (interpret b)
  | For a b => (interpret a) \/ (interpret b)
 end.

Inductive derivable : formula -> Prop :=
    deep_axiom : derivable Ftrue
  | deep_and : forall a b, derivable a -> derivable b -> derivable (Fand a b)
  | deep_or1 : forall a b, derivable a -> derivable (For a b)
  | deep_or2 : forall a b, derivable b -> derivable (For a b).

Inductive sderivable : Prop -> Prop :=
    shallow_axiom : sderivable True
  | shallow_and : forall a b, sderivable a -> sderivable b -> sderivable (a /\ b)
  | shallow_or1 : forall a b, sderivable a -> sderivable (a \/ b)
  | shallow_or2 : forall a b, sderivable b -> sderivable (a \/ b).

(* You can prove the following lemma: *)
Lemma shallow_deep :
   forall F, derivable F -> sderivable (interpret F).

(* You can NOT prove the following lemma :*)
Lemma t :
   forall P, sderivable P -> exists F, interpret F = P.


Fast high-dimensional K-nearest neighbors

For high-dimensional exact nearest neighbor search the theoretical guarantees are pretty dismal: the best algorithms are based on fast matrix multiplication and have running time of the form $O(N^2D^\alpha)$ for some $\alpha < 1$.

On the other hand you can do better if you are ok with approximation. Locality sensitive hashing can be used to achieve subquadratic in $N$ running times while reporting points which are not much further than the nearest neighbors.

For subsets of Euclidean space with doubling dimension $d$ (which captures the lower-dimensional manifold situation), Indyk and Naor show that there is an embedding into $O(d)$ dimensions (in fact a random projection in the style of the Johnson-Lindenstrauss lemma) which approximately preserves nearest neighbors. If $d$ is small enough you could first apply the embedding, then use a nearest neighbor data structure for low dimension.

You could also try the random projection trees (RP-trees) of Dasgupta and Freund. They are a natural variant of kd-trees in which the cut in each level is done in a random direction, rather than a coordinate direction. I don't think there are any known provable guarantee for how well RP-trees do on nearest neighbor problems, but the paper I have linked does prove that the trees adapt nicely to doubling dimension, so there is hope. The guarantee they give is that, if a point set inside a cell has doubling dimension $d$, then the descendants of the cell $O(d\log d)$ levels down the tree have diameter at most half that of the cell.


Context weakening as an explicit rule for languages of the the lambda cube?

If you intend to formalize meta-theorems in a proof assistant, then it's probably better to avoid the general weakening rule because it will pollute all your inductive arguments. Every single induction on the derivation will contain the case "but what if the context got larger using weakening?" and that's going to be super annoying. I would recommend instead a sane variable rule and no weakening. You can always show that weaking is admissible.
As far as sane variable rules go, the one you quoted works well when variables are symbols and contexts are maps taking symbols to their types. If you indent to use de Bruijn indices, then you should use different variable rules (note that contexts are just lists of types because variable names are just natural numbers):
$$
\frac{ }{\Gamma, A \vdash \mathtt{var}_0 : A}
\qquad
\frac{\Gamma \vdash \mathtt{var}_k : B}{\Gamma, A \vdash \mathtt{var}_{\mathtt{succ}(k)} : B}$$


Objective function for stochastic optimization

First, notice that the first objective is a minimization problem, who's solution is a vector $x$, while the second is merely a number.

The objective $\min_{x} E\left( \parallel Ax-b \parallel_2^2 \right)$ asks for the vector $x$ which best explains the data.

If $A$ is stochastic, it still looks for the best $x$ which, on average, is the best one.

The lower objective asks for "What's the expected error of the best $x$, in hindsight ", i.e. after we fix $A$, take the minimum over all $x$'s, and ask what's the error.
(more formally, for different $A$ values there are different "best" $x$s, so the each time take the best one for computing the error).

Since we are usually interested in finding the feature vector $x$ which explains the data, and not the expected error of the best $x$ after $A$ is fixed, the first stochastic objective makes more sense. The only reason I can think of as why would someone be interested in the second is for competitive-analysis like proofs (i.e. what's the gap between the best $x$ prior to knowing $A$ and the best one afterwards).


To what extent is it possible to use genetic algorithms to make wind mill turbine blades more efficient?

Short answer, yes you could build a GA that worked on a 3D model of a turbine with the correct viscosity, and (probably) yes, it would still find good designs. Exactly what those designs would be is somewhat unpredictable -- they might be very conventional blade arrangements or they might be completely novel and weird.

However, that's also true of many other search algorithms. GAs are, at heart, just one of a class of hundreds of stochastic search algorithms. All you need for a GA to work is three things: (1) a way of describing what a possible solution looks like, (2) a way of trying to combine good solutions to get more good solutions, and (3) a way of determining when one solution is better than another. The former can be as simple as just a vector of numbers ([number of blades, distance between blades, angle of attack, ...]) or may be arbitrarily complex, allowing for each blade to have an independent length and position, etc. For number three, you need a model that tells you how good a turbine is. This is where you need to get the viscosity of air correct, embed the right equations governing the electrical outputs, etc.

That just leaves the genetic operators -- how do you take good designs and produce more or better ones? Again, this can be very complex, but it can also be quite simple. For instance, you have a design with three blades, each five meters long. OK, make a small random change to that. Try blades that are 5.2 meters long. If the model tells you this is better, keep it. If not, throw it away and keep the original five meter blades. It's in this stage where domain knowledge is often invaluable. Having someone who can say, "the number of blades is really important -- taking a good five blade design and removing a blade isn't going to work unless you also change lots of other aspects of the design" allows you to simply say, "OK, my algorithm will avoid making that type of change in favor of making changes that are more likely to help.

Like I said, GAs are just search algorithms. They tend to often perform a "broader" search, which can sometimes make them more likely to find these off-the-wall solutions than some other methods. On the flip side, they typically take much longer to find good solutions than some other methods. That's also an approximation; sometimes a GA works great, sometimes it works very poorly. Understanding which cases will be which is one of the great unsolved problems for people working in optimization.

Finally, would companies adopt them if better designs were found? As you say, that's a more complex question. It isn't even just a matter of "too complicated". Suppose you find a 5% better turbine design that's completely feasible. You'll still likely have to redesign manufacturing equipment and processes, perhaps find new suppliers, etc. In the real world, "good enough" is often just that. However, there are numerous examples of real-world problems where methods like GAs or other random search methods have found solutions that were adopted. A lot of them are tucked behind corporate walls, but there have been notable successes in things like antenna design and aircraft design, as well as non engineering optimization problems like vehicle routing problems, scheduling problems, etc.


Start by putting $A$ into Jordan normal form, i.e., write $A=PJP^{-1}$ where $J$ is the Jordan normal form and $P$ is a suitably chosen invertible matrix.  Then $A^k = PJ^k P^{-1}$, so without loss of generality I only need to consider possibilities for $A$ that are already in Jordan normal form.

For $2\times 2$ matrices, there are only three interesting cases:

Repeated eigenvalues: Suppose
$$A = \begin{pmatrix} \lambda &1\\ 0 &\lambda \end{pmatrix}$$
where $\lambda \ne 0$.  A simple induction shows that
$$A^k = \begin{pmatrix} \lambda^k &k\lambda^{k-1}\\ 0 &\lambda^k \end{pmatrix}.$$
Therefore in this case, the problem is easy: $k = \lambda \times (k \lambda^{k-1})  / \lambda^k = A_{1,1} \times B_{1,2} /B_{1,1}$.
A zero eigenvalue: Suppose
$$A = \begin{pmatrix} \lambda &0\\ 0 &0 \end{pmatrix}$$
where $\lambda$ is a generator modulo $p$ (i.e., it has order $p-1$ in the multiplicative group).
Then this problem is exactly as hard as the discrete log problem to base $\lambda$ modulo $p$, i.e., it is unlikely to have a poly-time solution.  This is because
$$A^k = \begin{pmatrix} \lambda^k &0\\ 0 &0 \end{pmatrix},$$
so we have exactly an instance of the discrete log problem modulo $p$ hiding in there.
If $\lambda$ is not a generator, the problem is exactly as hard as the discrete
log to the base $\lambda$.

Note that this case is not in $GL(2,p)$, so strictly speaking it could be excluded from the case analysis, but I thought I'd show how to handle it.
Diagonal matrix: Suppose
$$A = \begin{pmatrix} a &0\\ 0 &b \end{pmatrix}.$$
Then this problem is hard in general.  For instance, if $a$ is a generator of $GF(p)$ and $b=1$, this problem is exactly as hard as the discrete log problem modulo $p$ (so most likely there is no polytime algorithm for it).  If $a,b$ are both generators, then I believe the problem remains hard (see, e.g., this question), though I'm not aware of any reduction from the discrete log problem modulo $p$.  If either $a$ or $b$ is such that the discrete log to base $a$ or $b$ is easy, then this problem is easy, though the chances of this happening by blind chance (if $a$ and $b$ are randomly chosen) is very low.

When we generalize to $n\times n$ matrices, I think the story remains approximately the same.    If there is any Jordan block of size $>1$, then the discrete log problem is easy ($A^k$ contains the values $\lambda^k$ and $k \lambda^{k-1}$, so the same trick works).  If $A$ is diagonal, then this is just an instance of this question; when the diagonal elements are chosen randomly, we can expect this to be hard (except with negligible probability).


The relationship between completeness and strength of reductions

If I understand correctly your questions are answered in

Agrawal-Allender-Impagliazzo-Pitassi-Rudich-2001: Reducing the Complexity of Reductions

Gap Theorem - Any set that is NP-complete under $AC^0$ reductions is NP-complete under $NC^0$ reductions.
Stop Gap Theorem - There is a set that is NP-complete under $AC^0[\!\!\mod 2]$
reductions, but not under $AC^0$ reductions.


My answer only applies to Japan, I don't know about other countries. There is a special position termed "Research Student". I did that for 6 months before my masters .

I know that in general any student (foreigner or japanese) can do this. However, it is very common for foreigners to do this before starting the masters or phd program. It gives you adaptation time, and you also start studying the basics of your future research. Most student also start preparing for admissions.

During my time as a research student, I worked as a research assistant for my current advisor in different projects. I also took the time to really study quantum computing, which at that time I had 0 intuition for quantum mechanics. That was perfect for me, before doing any serious stuff.

EDIT:

Q: Are research student positions elusively research positions (i.e. no mandatory coursework)?

A: There is no mandatory coursework for research students. However, there are a lot of things you can do. In my case, I started directly doing research (mostly learning the basics), prepared myself for admissions, and colaborated in some projects. I also attended group seminars, school seminars, etc. You gain access to all activities in the university. You can also attend classes if you want, but that doesn't count for coursework in the graduate course. Another example is when you come from another university (from anywhere in the world) and you want to learn the tools of the trade in some field. So you talk with a professor, and if he agrees you can spend some time in his group as a research student.

Q: Also, are you expected to then stay for a Masters/PhD at the institute where you held the research student position?

A: No, you can change universities if you want. I have a friend that did exactly that. This is a position that doesn't give you a degree nor a diploma or anything, besides the experience.

It is very important also to note Okamoto-sensei's comment below. Specially, note that you don't get paid for doing this, unless 1) you have a good scholarship, like MEXT's scholarship; or 2) you get some funds from a company or a professor looking for phd students.

To give you and idea, I post a couple of links explaining the requirements to be a research student. The first link is from my own university, and the second is from the university of Tokyo:

1) http://www.naist.jp/en/international_students/prospective_students/admission_information/research_student_applications/index.html

2) http://www.s.u-tokyo.ac.jp/en/admission/research-students.html

You can also find more information here

http://www.studyjapan.go.jp/en/index.html


Say that two pairs $p_1=(a_1,b_1)$ and $p_2=(a_2,b_2)$ are no-swap compatible if they can be placed in either order in the sorted list without swapping either one.  This is true if either $(a_1 \le a_2 \wedge b_1 \ge b_2)$ or $(a_2 \le a_1 \wedge b_2 \ge b_1)$.  Note that $p_1$ and $p_2$ are no-swap compatible if and only if they are two-swap compatible (since the partial order defined satisfies $p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$, where $*$ denotes the swap operation).  Finally, $p_1$ and $p_2$ are one-swap compatible if they can be placed in either order in the sorted list with exactly one of them swapped.  This is true if $p_1^{*}$ and $p_2$ are no-swap compatible.  In the remaining cases, $p_1$ and $p_2$ are simply incompatible: they cannot satisfy the order condition regardless of their swap state.

The problem can now be solved as follows.  Test every pair of pairs.  If any pair is incompatible, there is no solution, and we can throw an exception.  Otherwise, consider the graph with nodes corresponding to the original pairs, and edges between those pairs of nodes that are not one-swap compatible.  Each such pair of nodes must have the same swap state in any properly sorted list, and therefore all nodes in each connected component of the graph must have the same swap state.  We need to determine if these component-wide swap states can be consistently assigned.  Test all pairs of nodes within each connected component.  If any pair is not no-swap compatible, there is no solution, and we can throw an exception.  Now test all pairs of connected components (i.e., for components $C_1$ and $C_2$, test all pairs of nodes $p_1 \in C_1$ and $p_2 \in C_2$).  We know that each pair of components is at least one-swap compatible, but some pairs may also be no-swap compatible (because each pair of nodes not connected by an edge is at least one-swap compatible, and may also be no-swap compatible).  Consider a reduced graph with nodes corresponding to the connected components, and an edge between two nodes if the corresponding components are not no-swap compatible.  There is a solution to the original problem if and only if this graph is $2$-colorable.  If there is no $2$-coloring, there is no solution, and we can throw an exception.  If there is one, then swap all nodes in all components of a single color.  We are now guaranteed that any two nodes are no-swap compatible, and so we can properly sort the list of pairs using the defined partial order.

Each step in the algorithm, and hence the entire algorithm, can be performed in $O(N^2)$ time.

UPDATE: A much more elegant construction is the following.  If a pair of pairs is not no-swap compatible, connect the corresponding nodes with an edge (forcing them to be different colors in any 2-coloring).  If a pair of pairs is not one-swap compatible, connect the corresponding nodes with a chain of length 2 (forcing them to be the same color in any 2-coloring).  There is a solution if and only if the resulting graph is 2-colorable.  To construct a solution from a blue-red coloring of the graph, swap just those pairs whose corresponding nodes are blue, then sort the resulting list.


Counterexample to max-flow algorithms with irrational weights?

The answer is that for every irrational number $r$, there exists a network

with $n=6$ vertices and $m=8$ arcs,
in which seven arcs have integer capacity,
in which one arc has capacity $r$,
and on which Ford-Fulkerson may fail to terminate.

This has been proved in the paper

  Toshihiko Takahashi:
  "The Simplest and Smallest Network on Which the Ford-Fulkerson Maximum Flow Procedure May Fail to Terminate"
  Journal of Information Processing 24, pp 390-394, 2016.
  Link: https://www.jstage.jst.go.jp/article/ipsjjip/24/2/24_390/_article


Foundational textbook(s) for Complexity and Computability on Real Numbers

There are some good books -
 1. Computable Analysis - Pour-El and Richards (an older reference)
 2. Computable Analysis - Weihrauch

There's also the Blum-Shub-Smale Model, which is the model explored in "Complexity and Real Computation".

The complexity theory of computability of reals is explored in
 1. Computational Complexity of real functions  - Ker-I Ko

A regular conference which explores this area is "Computability and Complexity in Analysis", held annually.


Formal Semantics of Programming Languages

Looking at the operational semantics course at my University gives the following three:

Andrew Pitts's lecture notes
Gordon Plotkin's Aarhus notes on structural operational semantics
Matthew Hennessey's The Semantics of Programming Languages

Ohad.


complexity of games with just doors and keys

If I understand your question correctly, by path you mean that we build up a tree starting from s by always taking an edge adjacent to our current tree. This problem is NP-complete, the reduction is from SAT.

The main part of the graph will consist of n cycles of length four attached to each other at vertices s=v0, v1, v2, .., vn. So from s we have two paths of length two to v1, from v1 two paths to v2 and so on. From vn there will be a path of length N+1 to t.
We will have only enough weights to use one of each pair of paths and depending on which path we use, the value of the variable xi will be true or false. The weight in s is N+2n, where N is some big number.

Each clause is represented by an additional vertex that is connected by a path of length N to the center vertex of the path that corresponds to its literals and it has value N+epsilon (I know we need integers, but we can multiply up and replace each edge by 1/epsilon edges), where 1/epsilon is the number of clauses. So we have to visit every clause-vertex to get to t.


Can one-way alternating automata with one-counter recognize some unary non-regular languages?

Yes.
Consider the language $L = \{ a^n \mid n = 2^s, s \geq 0 \}$ and construct a one-way alternating one-counter automaton recognizing $L$ in the following way. First, the automaton starts increasing the value of the counter and guesses when to stop, that is, guesses some value $m$. Then it branches universally: the first branch checks that the length of the input is precisely $2 m$, and the second branch moves $m$ cells forward on the input and checks that the remainder is in $L$, by going to the initial control state. Now add a base case: let the device accept if the input tape is exactly of length $1$, by making a nondeterministic guess at the initial state. That completes the construction.

In a similar fashion, one can get products of the form $n = k_1^{s_1} \ldots k_r^{s_r}$, with $k_1, \ldots, k_r$ fixed and $s_1, \ldots, s_r$ arbitrary.


Adherence of languages and the Dyck language

For each $n \geq 0$, the word $aaba^nb^{n+1}$ is in $D$, therefore $aaba^\omega$ is in $Adh(D)$.


First, you should write up your result so it's comprehensible as you can make it, and send it to a journal. If your write-up looks like it is a real research paper, your paper should be sent out for review and possible publication. How to choose a journal? Look for other papers which are on roughly the same subject matter and around the same quality as yours, and see where they got published.

Don't publish in a fourth-tier journal; if you do, it will never be read; these seem to exist only for the purpose of increasing the number of researcher's publications, and are not subscribed to by many academic libraries. To make sure you're not choosing one of these, check the online databases of a few good academic libraries, and make sure most of them subscribe to the journal you have picked.


Papers every complexity theorist should read

Ryan William's Non-uniform ACC Circuit Lower Bounds and all the results cited therein.

Not only is this a recent important result, it is a very well-written paper. Furthermore, the results the paper uses and cites cover a pretty good range of seminal complexity results. So if you trace through the references and read those as well - get to a point where you understand every part of the ACC lower bound from first principles - I would think that would be an excellent start to a graduate complexity education.


Semantic equivalence using a model of computation of two languages

Let me clarify the setting, which has nothing to do with $\pi$-calculus or bisimulation.

The first thing you have to realise that it does not make much sense to talk about a programming language without reference to the notion of program equivalence you intend to impose on the language. That's because

We usually identify certain programs (e.g. f(x:int) = { x+1 } is considered the same as  f(y:int) = { y+1 }).
The notion of program equivalence to be used depends highly on what you are doing with these languages, e.g. sometimes we care about program time- or space complexity, sometimes we don't.

So the general setup you are interested in is this: you are given 3 language $(A, \cong_A)$, $(B, \cong_B)$ and $(T, \cong_T)$, each comprising of a set of programs ($A$, $B$ and $T$)  with associated notions of program equivalence ($\cong_A$, ...). In addition, you have two mappings:

$trans_A : A \rightarrow T$.
$trans_B : B \rightarrow T$.

They map ("compile") from source languages $A$ and $B$ to target $T$. Typically you want these two translation functions to be at least sound. That means that for all $A$-programs $P, Q$, we have: $trans_A(P) \cong_T trans_A(Q) \Rightarrow P \cong_A Q$, and likewise for $trans_B$.

Now you want to argue that $(A, \cong_A)$ and $(B, \cong_B)$ are equivalent as languages. That's what you use the target $(T, \cong_T)$ for. There are many ways that this can be done, details depend on what concept of language equivalence you are interested in. One approach could be to say

For each $A$-program $P_A$ there is a $B$-program $P_B$ such that $trans_A(P_A) \cong_T trans_B(P_B)$.
Vice versa.

None of the above is $\pi$-calculus specific, but you
 can instantiate $T$ with $\pi$-calculus and $\cong_T$ with any chosen notion of equivalence on $\pi$-calculus such as strong or weak bisimulation, maximum consistent theory, reduction congruence, or whatever else makes sense for your application.

I said that there are many alternative ways of doing this. You could for example impose constraints on $trans_A$ and $trans_B$ so the translation preserves chosen constraints (e.g. termination, or compositionality).


I use Mendeley, which allows you to tag your papers, find them by topic, author, export bibtex files, and so on.


Other norms for Lattice reduction techniques (LLL, PSLQ)?

Following the specific reference provided by Steve Huntsman in his MO answer leads to the paper

Oded Regev and Ricky Rosen. Lattice problems and norm embeddings, STOC 2006.  doi: 10.1145/1132516.1132581 (full preprint version)

This paper presents randomized reductions from the approximation versions of lattice problems in the $\ell_2$ norm to any norm $\ell_p$ where $1 \le p \le \infty$.  The reductions don't quite preserve the approximation ratio, but the loss can be bounded by a factor of $(1+\epsilon)$.  So the $\ell_2$ norm yields in some sense the "easiest" versions of lattice problems.  It is enough to prove hardness of approximation using the $\ell_2$ norm, and hardness of approximation for any other $\ell_p$ norm follows with only a $(1+\epsilon)$ larger approximation factor.

Regev and Rosen then go on to use this to strengthen some existing hardness results.

On the other hand, Chris Peikert showed that lattice problems posed using $\ell_p$ norms are not substantially harder than problems posed in the $\ell_2$ norm.

Chris Peikert, Limits on the hardness of lattice problems in $\ell_p$ norms, Computational Complexity 17 300–351, 2008.  doi: 10.1007/s00037-008-0251-3 (full preprint version)

So yes, the question is sensible, and it has also essentially been answered.

(Thanks to @user834 for the preprint links.)


MSOL optimization problems on graphs of bounded cliquewidth, with cardinality predicates

After asking around some more, it seems that the answers to 1) and 2) are both YES. Optimizing the cardinality of a set is possible in LinEMSOL (as mentioned by Martin Lackner); as I have been told, the existence of the cardinality predicates is no problem since they can be efficiently handled by finite-state tree automatons, which should follow (more explicitly than in the originally referenced paper) from On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width.


Generalization and instantiation of types in Hindley-Milner type inference

However, I fail to see what this accomplishes and when you want to do this, and would be very grateful if someone can point me in the right direction.

When you define the function x -> x and first apply it to an integer you don't want the type of that identity function to be specialized to int -> int. That's why you generalize it. Note that this is done at let bindings.


Predecessor versions of this paper have been around for more than 15 years. I remember that there were counter-examples to the first versions, then first revisions, counter-examples to the first revisions, second revisions, new counter-examples, further revisions, further counter-examples, and so on.

It would be much better, if the authors were able to provide a mathematical proof that the given LP formulation indeed yields a full description of the TSP.
From the scientific point of view, it is certainly not enough to just state an LP formulation and to claim that it is correct, as long as nobody is able to explicitly construct a counter-example.

All in all, I would say that it is safe to ignore this paper as long as the authors do not provide supporting arguments for their claims.


What is the running time of taking a limit?

I don't have time to go into detail now, but here's a quick sketch of how to solve it. Let's assume that all of your polynomials look like $x^k-1$. What you have to do is use the identity $x^k-1 = (x-1)(1+x+x^2+\ldots + x^{k-1})$. You are starting with the function $\frac{\Pi_{i=1}^n (x^{k_i}-1)}{\Pi_{i=1}^m (x^{\ell_i}-1)}$. Now, factor out all the $(x-1)$ terms and take the limit. If $n >m$, you get $0$. If $n \lt m$, you get $\infty$. Otherwise, the $x-1$ terms cancel out, and what you're left with is $\frac{\Pi_{i=1}^nk_i}{\Pi_{i=1}^n\ell_i}$.


Interesting algorithms in the formalization of the Feit-Thompson theorem?

(Turning a comment into an answer, and expanding on it)

From talking to someone who worked on this: no. He invented all sorts of clever refinements to many proofs, and restructured many theory developments, both of which are extremely valuable, but the algorithms involved are not interesting -- in fact, many of them are dumb brute force, the very opposite of interesting.

Basically what was sought was as direct a line to the proof of Feit Thompson, without worrying about 'computational content' along the way (and even not overly worrying about reusability of some of the modules).  This was already extremely ambitious given the timelines.  Luckily, several of the people involved in the project have gone on to refactor many parts of the proofs to be

more reusable for a wider set of applications
more computationally meaningful


complexity of finding a cycle with total weight k in a graph when you know no hamiltonian cycle in graph satisfies the given weight k

I don't know about knapsack problem, but it isn't too hard to reduce from Hamiltonian Cycle to this problem (assuming you mean a simple cycle). We start with an arbitrary graph $G$ with $n$ nodes for which we want to find a Hamiltonian cycle. Then we construct $G'$, which is $G$ with the addition of a single node $v$, a single edge from $v$ to an arbitrary node in $G$ with arbitrary weight, and every other edge has weight 1. We then ask if there is a cycle with weight $n$ in $G'$.

If we have a Hamiltonian cycle in $G$, this corresponds to a cycle in $G'$ with weight $n$. This is not a Hamiltonian cycle in $G'$, since it doesn't go through our added vertex $v$. If we have a (simple) cycle with weight $n$ in $G'$, then it must include exactly n nodes. It can't include $v$ since it has degree 1, and can't be part of a cycle. Therefore, this goes through all the nodes in $G$, and thus is a Hamiltonian Cycle in $G$.

Therefore this problem is $\mathcal{NP}$-Complete, unless I misinterpreted your question.


Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?

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

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

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

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

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

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

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


Hierarchical sorting strategies for pattern-avoiding permutations?

Another approach is enumerative encoding. Consider for example $231$-avoiding permutations, of which there are $C_n$. The number of $231$-avoiding permutations with $\pi^{-1}(n) = i$ is $C_{i-1} C_{n-i}$, and this gives a recursive algorithm for encoding $231$-avoiding permutations: divide the interval $[0,C_n)$ into $n$ intervals $I_1,\ldots,I_n$ of lengths $C_i C_{n-i-1}$ for $i=1,\ldots,n$ arbitrarily. Given a permutation with $\pi^{-1}(n) = i$, notice that $\pi|_{1,\ldots,i-1}$ is a $231$-avoiding permutation of $\{1,\ldots,i-1\}$, and $\pi|_{i+1,\ldots,n}$ is a $231$-avoiding permutation of $\{i+1,\ldots,n\}$. Recursively encode the first part in $[0,C_{i-1})$ and the second part in $[0,C_{n-i})$, and put both encodings together to encode $\pi$ in $I_i$.

For any other $\tau \in S_3$, $\tau$-avoiding permutations are bijectively related to $231$-avoiding permutations, through taking the inverse, complementing the elements, reversing, or the Simion–Schmidt bijection between $132$- and $123$-avoiding permutations. So this encoding applies to all patterns of length $3$.


Is it $NP$-complete to decompose bridgeless cubic bipartite graph into edge-disjoint paths of length 3?

As pointed out by David Eppstein when I asked a related question a while ago: you can do that in polynomial time.

The idea is to find a perfect matching $M$ (which exists and can be found in polynomial time since your graph is cubic and bridgeless), and then to use the edges of $M$ as middle edges of the $P_4$'s.

To complete the construction, remove the edges of $M$ and orient the remaining cycles arbitrarily. Then attach to each edge $\{u, v\}$ of $M$ the arcs going out from $u$ and $v$, and you are done.


Testing whether a set of n points in the plane form a convex n polygon in o(nlogn) time

Thats seems unlikely, at least in the comparison/algebraic tree models. Definition first:

A point set $P$ is in convex position if no point of $P$ can be written as a convex combination of the remaining points of $P$.

Now, deciding if a set of $n$ numbers are all distinct takes $\Omega(n \log n)$ time (this is known as UNIQUENESS). Given such a set of $n$ numbers $X$, map them to the set of points
$$
P = \{ (x, x^2) | x \in X\}.
$$
If there is no repeated number, then the points are in convex position.

If there is a repeated number, then this repeated number corresponds to a point that can be written as a convex combination of the remaining points. Namely, the points are not in convex position.

Namely, deciding if a point set is in convex position is as hard as UNIQUENESS.


Word length using entropy : Maximum entropy criteria

Disclaimer: This is based on generic information theory knowledge only. Too long for a comment.

Summary: The pointwise product of your two plots should go to some limit, as the relevant blocklengths and sequence lengths increase.

I don't know if this applies to DNA but in theory if your sequence is ergodic (stationary, and time averages are the same as ensemble averages, for long enough sequences) then the two entropies are related intimately.

The whole point is, if you obtain a "block" entropy $H(X_1,\ldots,X_n)$ for a block of length $n,$ then
$$
\lim_{n\rightarrow\infty} \frac{H(X_1,\ldots,X_n)}{n}=H_0
$$
which is the entropy per symbol, i.e., the entropy rate, what you call shannon entropy as opposed to block entropy.

Now, the question of estimating these is a different question. In fact your program does this by a sliding window technique, which then means that it is averaging overlapping thus dependent samples.

Define the shorthand $X_i^j=(X_i,X_{i+1},\ldots,X_{j})$ where $j\geq i.$ I am sure that under suitable conditions an estimator of the form
$$
\frac{\sum_{k=1}^{n-\ell+1}\hat{H}(X_k^{k+\ell-1})}{n-\ell+1}
$$
where $\hat{H}(X_k^{k+\ell-1})$ is a suitable estimator for block entropy, will converge to a multiple of the entropy rate, i.e., to $\ell \times f$ where $f$ is a correction factor. However, one may need to let $\ell$ grow with $n.$


I have found the newest one that gives 7-wise independence using MR code, also two others based on BCH and EH code with 3-wise independence. They are tested to be good enough for AMS sketch in this paper


Both Coq and Isabelle can do this.

[Coq]
Here is a paper discussing how to encode ZFC in CIC, on which Coq is based.

Benjamin Werner: Sets in Types, Types in Sets (1997).
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.1709

[Isabelle]
There is a library for ZF.

http://www.cl.cam.ac.uk/research/hvg/Isabelle/dist/library/ZF/index.html


Examples where the uniqueness of the solution makes it easier to find

3-SAT may be one such problem.  Currently the best upper bound for Unique 3-SAT is exponentially faster than for general 3-SAT.  (The speedup is exponential, although the reduction in the exponent is tiny.)  The record-holder for the unique case is this paper by Timon Hertli.

Hertli's algorithm builds upon the important PPSZ algorithm of Paturi, Pudlák, Saks, and Zane for $k$-SAT, which I believe is still the fastest for $k \geq 5$ (see also this encyclopedia article).  The original analysis showed better bounds for Unique $k$-SAT than for general $k$-SAT when $k = 3, 4$; subsequently, however, Hertli showed in a different paper that you could get the same bounds for (a slightly tweaked) PPSZ algorithm, without assuming uniqueness.  So, maybe uniqueness helps, and it can definitely simplify the analysis of some algorithms, but our understanding of the role of uniqueness for $k$-SAT is still growing.

There is evidence that Unique $k$-SAT is not too much easier than general $k$-SAT. The Strong Exponential Time Hypothesis (SETH) asserts there is no $\delta < 1$ such that $n$-variable $k$-SAT is solvable in $O^*(2^{\delta n})$ time for each constant $k \geq 3$. It was shown in a paper of Calabro, Impagliazzo, Kabanets, and Paturi that, if SETH holds, then the same statement is true for Unique $k$-SAT.  Also, if general $k$-SAT  requires exponential time, i.e. there is some $k \geq 3, \epsilon > 0$ such that general $k$-SAT cannot be solved in time $O^*(2^{\epsilon n})$, then the same must be true for Unique 3-SAT.  See the paper for the most general statement.

(Note: the $O^*$ notation suppresses polynomial factors in the input length.)


While Per Vognsen's comment works well for labeled trees, your question uses the word "unique" (which should probably be "distinct") to describe the shape of the tree.  This makes me think you mean "How many isomorphism classes of unlabeled binary trees are there?"

To compute this exactly, you will probably want to use Brendan McKay's "Isomorph-free exhaustive generation" which he uses in his program geng to list each isomorphism class of simple graphs on a given number of vertices and edges, and do it quickly.

To summarize his process, he uses a depth-first search on graphs, where each deepening step adds a vertex.  To make sure no isomorphism class is repeated (which would happen a lot if this was done naïvely) the vertex-added graph decides if this was the "canonical" subgraph to use in the search.  The algorithm essentially picks a vertex in the graph to be deleted using a canonical labeling of the graph and tests if this was the vertex that was added.  A canonical labeling can be found by McKay's nauty library.

In your binary tree example, you would add a leaf somewhere in the tree.  You can fix the root, but the other vertices may permute based on the automorphism group.  Hence, you only need to test adding a leaf to each orbit of vertices that has fewer than two children.  After adding the leaf, compute the canonical labeling of the tree and find the lexicographically-least leaf.  If this leaf is in the same orbit as the leaf you added, then the search can deepen; otherwise try a new leaf.  When $n$ vertices are reached, increment your counter.


Constructivity in Natural Proof and Geometric Complexity

No, the unavoidability of constructivity definitely still leaves GCT open as a viable plan of attack on lower bound problems such as $NP$ vs. $P/poly$.

First, it is worth mentioning that Ryan's result on constructivity is very similar in flavor to the so-called "Flip Theorems" by Mulmuley, which say, for example, that if permanent does not have poly-size arithmetic circuits, then there is a randomized poly-time constructible set of (polynomially many) matrices $\{M_1, \dotsc, M_{p(n)}\}$ such that every small circuit differs from the permanent on one of these matrices. See  Explicit Proofs and The Flip, Technical Report, Computer Science Department, The University of Chicago, September 2010 by Mulmuley.

Second, the centrality of symmetry-characterization (mentioned already by siuman) in GCT has become more apparent since Regan's survey. If symmetry-characterization turns out to be as crucial to GCT as it seems like it is going to, then this already gets around the largeness condition. For the definition of symmetry-characterzation, see this answer to a closely related previous question.

For a proof that symmetry-characterization violates largeness, see Section 3.4.3 "Symmetry-characterization avoids the Razborov–Rudich barrier" in my thesis (shameless self plugs, but I don't know anywhere else where this is written down so completely). I suspect it also violates constructivity, but left that as an open question there. (Earlier in Chapter 3 there's also an overview of the flip theorems in GCT and how they relate to symmetry-characterization.)

(I find it interesting that symmetry-characterization - the very property we suspect will be used in GCT that gets around Razborov--Rudich - is used to prove the flip theorems, which essentially say that constructivity is necessary.)

Finally, it is worth mentioning that although in the long run GCT aims to address $NP$ versus $P/poly$ and other Boolean problems, at the moment most work in GCT is focused on algebraic analogs of these, such as over the complex numbers, and there is as yet no algebraic analog of Razborov--Rudich (that I know of).


Does a pair of disjoint homotopic cycles in the dual separate the graph?

Yes.  Let me write $\Sigma$ for the surface on which $G$ and $G^*$ are embedded.

Because the cycles $C_1$ and $C_2$ are homotopic, they are also in the same $\mathbb{Z}_2$-homology class.  So by definition, the symmetric difference $C_1\oplus C_2$ is the boundary of the union of some subset of faces of $G^*$; call this union of faces $U$.  (In fact, either $U$ or its complement $\Sigma\setminus U$ must be an annulus, but this isn't important.)

Because $C_1$ and $C_2$ are disjoint, the symmetric difference $C_1\oplus C_2$ is equal to the union $C_1\cup C_2$.  In particular, we have $C_1\oplus C_2\ne \varnothing$, which implies that both $U$ and its complement $\Sigma\setminus U$ are non-empty.  In other words, the subsurface $\Sigma \setminus (C_1\cup C_2)$ is disconnected.

Any path in $G$ can be viewed as a path in $\Sigma$ that avoids the vertices of $G^*$, and vice versa (up to homotopy).  Thus, the (graph) components of $G\setminus (E_1\cup E_2)$ correspond bijectively to the (surface) components of $\Sigma \setminus (C_1\cup C_2)$.  We conclude that $G\setminus (E_1\cup E_2)$ is disconnected.

The assumption that $\Sigma$ is orientable is never used.


How do the state-of-the-art pathfinding algorithms for changing graphs (D*, D*-Lite, LPA*, etc) differ?

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

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

Simple recalculations

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

Any-angle movement

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

Moving Target Points

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

Fast/Sub-optimal

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

Other/Unknown

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

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


Define the properties of a grammar that is the fastest to parse

Your question is unclear. When you write "parse", do you actually mean
to produce a parse structure (one, or all possible ones). How do you define
it ? For example, some grammars have a parse tree that differs from the
derivation tree. Or did you mean that the language must be fasted to
recognize?  Regular grammars give you languages that are recognized
in linear time. What qualifies as a grammar? Actually, if you are just
interested in recognition, you are looking for properties of languages
rather than properties of grammar (though they can be related).

You can certainly build hierarchies of grammars according to
complexity criteria if you clarify the above.

For example in the case of Context-Free grammar, the is nearly a well
defined concept of parsing (up to specifying whether you want one
parse tree or all possible parse trees).

The complexity is at worst $O(n^3)$ for parsing and $O(n^{2.373})$ (due to valiant, with a looser bound at the time) for
recognition (wich is only asymptotic, and not the fastest in any
realistic situation). There are CF grammar that will parse in linear
time (notably deterministic grammars), others  will parse in $O(n^2)$
time, and others are believed to require more (though the exact
complexity bound is not known), even for simple recognition.

I do not really know if these complexity hierarchies have been
identified precisely.

The usual hierarchies studied for context-free grammars are often more
related to the applicability of techniques that can be used to build
parsers for these grammars.

As the question is stated, I guess there is one language that is faster than any other to recognize. That is the Babel language invented (nearly) by Jorge Luis Borges and containing all possible string (Borges was unfortunately limited to a finite size due to paper shortage, which would invalidate what I am saying). With all strings of any size, recognition is easy. You start in an accepting state and terminate in 0 steps.
The empty language is recognized as fast. I believe these are the only ones recognized in 0 steps (for a given alphabet). This establishes that, if the alphabet is fixed, the class of languages recognizable in 0 time is closed under complementation.

This is of course in jest, but you can see from it that one can define languagesn and corresponding grammars, that can be recognized in constant time, by putting constraints only on a finite prefix of strings. They are not much more interesting. The problem is in the statement of the question.

I guess the fasted interesting class of CF grammars is the class parsable in linear-time. Deterministic CF grammars are clearly member of that class, so that is a sufficient property. However many non-deterministic languages, having no deterministic grammars, can also be parsed in linear time.


Should we consider $\mathsf{P} \neq \mathsf{NP}$ a law of nature?

Strassen's statement needs to be put into context. This was an address to an audience of mathematicians in 1986, a time when many mathematicians did not have a high opinion of theoretical computer science. The complete statement is

  For some of you it may seem that the theories discussed here rest on weak foundations. They do not. The evidence in favor of Cook's and Valiant's hypotheses is so overwhelming, and the consequences of their failure is so grotesque, that their status may perhaps be compared to that of physical laws rather than that of ordinary mathematical conjectures.

I am sure that Strassen had had conversations with pure mathematicians who said something along the lines of

  "You're basing the whole of complexity theory on a house of cards. What if P=NP? Then all your theorems will be meaningless. Why don't you just put forth a little effort and prove that P$\neq$NP, rather than keep building a theory on such weak foundations."

In 2013, when P$\neq$NP has been a Clay prize problem for a dozen years, it may seem difficult to believe that any mathematicians actually had such attitudes; however, I can personally vouch that some did.

Strassen continues by saying that we should not give up looking for a proof of P$\neq$NP (thus indirectly implying that it is indeed a mathematical conjecture):

  Nevertheless, a traditional proof would be of great interest, and it seems to me that Valiant's hypothesis may be easier to confirm than Cook's...

so maybe I would label it as a "working hypothesis" rather than a "physical law".

Let me finally note that mathematicians also use such working hypotheses. There are a large number of mathematics papers proving theorems whose statements run "Assuming the Riemann hypothesis is true, then ...".


Efficient synchronization of two instances of an ordered list

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

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

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

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

Again, credit to Michael Heyeck.


Lower bound on independence number in terms of clique number and order of graph

Where it says

then any maximal independent set has size at least $n^{1/k}$,

it should say

then any maximal independent set has size at least the floor of $n^{1/k}$,

(Then this sentence is true for the complete graph $K_k$.)

They are being a bit sloppy, but I imagine that they just need the result for "large enough $n$".


Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

This is Assignment 3, Question 5 in Richard Cleve's ongoing intro to quantum computing course. (Seems like this assignment was due today.)

While we're not supposed to answer homework questions on CSTheory, fortunately the assignment answers all your questions. It also takes you through the construction of the quantum algorithm. I strongly recommend reading it.


Confusion with the proof of constraints for a particular adiabatic quantum evolution

The norms are the usual norms of a ket vector, i.e. $|||a\rangle||^2 = \langle a|a\rangle$.

What did we do on the bottom of page 3? It is really running the argument from the An Analog Analogue paper backwards.

Imagine we start from the state $|g_x\rangle$ (a particular ground state of the final Hamiltonian $H_{P}$, related to $|x\rangle$), and evolve backwards with an inverse algorithm. Similarly to AAA, we are looking at whether evolving backwards with no purpose (without knowledge of $x$) makes the evolution any different from evolving with a Hamiltonian that involves $x$. We show that for a successful algorithm, it is necessary that the quantity $S(0)$ must be large enough. However, running back in time from $T$ to $0$, this $S(t)$ doesn't change much, which allows us to show that $T$ must be large.


Type, operation and function, and their limits

Depends on your definition of "fundamental". As Martin said, you can do pretty much anything with the few primitives in lambda calculus, for instance, or simply anything that is Turing complete. However, would that be useful in your problem domain?

I don't know the specifics of your language, but you should have some use in mind for it. Depending on its intended use, you may want to have certain operations as builtins. For instance, MATLAB is specialised to work with matrices, so it has a lot of built-in operations for them.

In summary: decide what is your language supposed to be good for, and tweak your types and operations to that effect.

There are two kinds of operations that I'd make into built-ins:

those that can't be implemented by the user of your language without breaking the intended abstraction (i.e. accessing implementation details). For instance, I'd need something to increment an integer variable by 1.
the operations that are commonly used and that can be made much more efficient and/or convenient by taking advantage of implementation details. I could use a loop to increment something by 5, but it'd normally be much more efficient to do it in one go.


Is there some mathematical closed form (or somewhat tight asymptotic one) for "Google Eggs Puzzle"?

With m eggs and k measurements the most floors that can be checked is exactly $$n(m,k)={k \choose 0} + {k \choose 1} + \ldots + {k \choose m},$$ (maybe $\pm 1$ depending on the exact def). Proof is trivial by induction. This expression has no closed form inverse but gives good asymptotic.


Ternary (and beyond) computation and quantum computing?

Actually the usual RAM model is just this approach taken into extreme: each "storage unit" has as many as $\textrm{poly}(n)$ possible states (instead of just 2 states). We assume that each memory word can store $O(\log n)$ bits and word-operations have unit cost.

Cf. this question.


Maximum Treewidth of a Graphs with $m$ Edges

There are bounded degree (in fact even cubic i.e. 3-regular) expanders on $m$ vertices with treewidth at least $\epsilon \cdot m$, for some constant $\epsilon > 0$. See Section 2 in:

Martin Grohe, Dániel Marx:
On tree width, bramble size, and expansion. J. Comb. Theory, Ser. B 99(1): 218-228 (2009)

Basically, they prove something much stronger: large vertex expansion is the only reason on why the treewidth can be as much as linear (in the number of vertices, but bounded degree graphs have linear number of edges).


What is the run-time of the bin packing approximation algorithm?

According to the definition of polynomial (from Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.):

An algorithm is said to be of polynomial time if its running time is
upper bounded by a polynomial expression in the size of the input for
the algorithm, i.e., T(n) = O(n^k) for some positive constant k.

In their Theorem 1.2 they say "The algorithm is randomized and the expected running time is polynomial". So their are meaning that the algorithm proposed is randomized (non deterministic), but its running time is polynomial, since is within a sum over the bins.


Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?

The distance should be upper semicomputable. For instance the Hamming distance or Euclidean distance as such is not. One has to turn them into a version that satisfies the requirement above. Read the paper closer.