This answer combines some of my comments to the question and expand them.

The subrange operation on red-black trees can be performed in worst-case O(log n) time, where n is the number of elements in the original tree.  Since the resulting tree will share some nodes with the original tree, this approach is suitable only if trees are immutable (or trees are mutable but the original tree is no longer needed).

First notice that the subrange operation can be implemented by two split operations.  Here the split operation takes a red-black tree T and a key x and produces two trees L and R such that L consists of all the elements of T less than x and R the elements of T greater than x.  Therefore, our goal now is to implement the split operation on red-black trees in worst-case O(log n) time.

How do we perform the split operation on red-black trees in O(log n) time?  Well, it turned out that there was a well-known method.  (I did not know it, but I am no expert of data structures.)  Consider the join operation, which takes two trees L and R such that every value in L is less than every value in R and produces a tree consisting of all the values in L and R.  The join operation can be implemented in worst-case time O(|rL−rR|+1), where rL and rR are the ranks of L and R, respectively (that is, the number of black nodes on the path from the root to each leaf).  The split operation can be implemented by using the join operation O(log n) times, and the total worst-case time is still O(log n) by considering a telescoping sum.

Sections 4.1 and 4.2 of a book [Tar83] by Tarjan describe how to implement the join and the split operations on red-black trees in worst-case time O(log n).  These implementations destroy original trees, but it is easy to convert them to immutable, functional implementations by copying nodes instead of modifying them.

As a side note, the Set and the Map modules of Objective Caml provide the split operation as well as other standard operations on (immutable) balanced binary search trees.  Although they do not use red-black trees (they use balanced binary search trees with the constraint that the left height and the right height differ by at most 2), looking at their implementations might be useful, too.  Here is the implementation of the Set module.

References

[Tar83] Robert Endre Tarjan.  Data Structures and Network Algorithms.  Volume 44 of CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, 1983.


What is the reason for using a "Lines-Oracle" in the PCP Theorem?

The lines oracle is used to decrease the query complexity of the test from $d+1$ to $2$, at the expense of using a larger alphabet.

If you don't mind making $d+1$ queries, then the lines oracle is indeed unnecessary. However, it is usually better to make two queries over a large alphabet than $d+1$ queries over a small alphabet.

One reason is that, very roughly speaking, we have a technique, called PCP composition, which can be used to reduce the alphabet size of PCPs, but cannot be used to reduce the query complexity. Hence, it is preferable to have small query complexity and large alphabet size rather than the other way around.

A second reason, which is very related to the first one, is that many hardness-of-approximation results are proved based on $2$-query PCPs, but can not be proved using based on a PCP with more queries.

It should be mentioned that there are also generic techniques for reducing the query complexity at the expense of the alphabet size, so one could avoid the lines oracle and apply those techniques instead. However, using the lines oracle gives a more direct proof.


Will quantum computing pave the way for native, true RNGs?

Actually, today's computers can generate truly random data on their own, and many in fact do. The random data is produced as a byproduct of the physics of the components, not as the product of a given algorithm, so it necessarily has to be implemented in hardware. But the hardware is readily available.

The popular TPM chip, for example, typically has an embedded TRNG, as do many security-oriented peripherals, such as some authentication tokens.

The actual mechanism used to harvest sources of entropy varies by component, but a simple-to-understand mechanism is the analysis of noise generated at the avalanche breakdown of a P-N junction of a diode or transistor. The noise from such a cascade is actually the amplification of the random movement of electrons at the junction - essentially amplifying the randomness of quantum mechanics to the level where it can be read by traditional electronics.

Obviously this isn't the only mechanism you can use to harvest randomness in today's computers, but it's an easy one to understand. In fact it's worth pointing out that the Intel's recent Ivy Bridge architecture introduced a new instruction: RDRAND, which yields the output of an on-chip TRNG. IEEE Spectrum has a detailed write-up of how it works.


What is the most powerful kind of parser?

A grammar is usually defined as a Context Free grammar - a precise definition is given on the Wikipedia page, but it works the same as it does in PLY, which is based on Bison, which is in turn based on yacc.

It says here that PLY uses a LALR parser. This is essentially an LR parser where the lookup tables are condensed, possibly introducing parsing conflicts, reducing some of the expressiveness of an LR grammar (ie, a context free grammar that an LR parser can parse). If you want to know about the limitations of this particular branch of parsers and those of other parsers, an overview of all kinds of parsing techniques (LL, LR and others) is given here.

To answer your question: there exist parsing algorithms capable of parsing any context-free language, even if the language is ambiguous (ie, there is more than one way to interpret the input):

The first such algorithm was the CYK algorithm, which unfortunately has a running time of $O(n^3 |G|)$, where $n$ is the length of the input string and $|G|$ is the size of the grammar and is therefore impractical for parsing languages.

The second algorithm is the Earley algorithm. This algorithm is also capable of parsing any context free grammar. Although the algorithm needs $O(n^3)$ time to parse an ambiguous language, it only needs $O(n^2)$ time to parse an unambiguous language. In addition, it apparently works in linear time for most LR grammars and works particularly well on left-recursive grammars.

Here you can find a paper discussing a practical implementation of (an adaptation of) the Earley algorithm. They conclude: "Given the generality of Earley parsing compared to LALR(1) parsing ((which is roughly what PLY does)), and considering that even PEP’s ((their implementation of Earley's algorithm)) worst time would not be noticeable by a user, this is an excellent result".

The last type of parser is the GLR parser. This is a generalised version of LR parsing, capable of parsing any context-free language.

A mature implementation of GLR is ASF+SDF. Bison can also generate a GLR parser, though its implementations is slightly different from the 'standard' GLR algorithm. The Elkhound Algorithm is a GLR/LALR hybrid algorithm. It uses LALR when possible and GLR when needed, in order to be both fast and capable of parsing any grammar.

Beyond context free grammars there are context sensitive grammars, but these are in general hard to parse and don't add that much expressiveness: you can do more with them, but for most applications the extra uses are not relevant, unless you're parsing a natural language.

As the final step there are unrestricted grammars. At this point the grammar is Turing-complete, so there is no bound one can give on how long it will take to parse a particular language, which is undesirable for most parsing applications. The extra power is almost never needed. If you do want to use all that power, there is the language machine available.

Lastly, implementing your own parser-generator is not a trivial affair, in particular to get it to be fast. I've personally just finished making my own version of flex (the lexer generator), and while this seemed like an exercise in relatively simple algorithmic problems, it became quite complex to get right, in particular when I tried to support Unicode. Consider using an already existing implementation instead of writing your own.


How are proofs verified probabilistically in interactive proof systems?

Your interpretation isn't using randomness in the right way in an MA protocol.

Every MA problem can be reduced to a polynomial-size circuit of AND-OR-NOT gates, with some input variables designated for Merlin and the rest designated for Arthur. First Merlin tells Arthur the TRUE-FALSE values of Merlin's variables. Then Arthur flips coins to choose the TRUE-FALSE values for Arthur's variables. That's all the randomness Arthur needs so he can now throw his coin away.

Now we have a logical circuit with no free variables. Arthur deterministically verifies that the circuit outputs true.


Finding vertex separator such that the induced subgraph has minimal number of edges

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996)
217–222, as cited by Guantao Chen and Xingxing Yu, "A note on fragile graphs", Discrete Math. 2002, https://doi.org/10.1016/S0012-365X(01)00226-6]. So your problem is hard even in the special case of zero edges.


${\Sigma_2^P}^{NP}$ is the set of language decided by an alternating turing machine in existential, and then universal state, with an oracle in NP. Both the universal and the existantial part can querye NP.

Hence, in this case you decided to write this as $(NP^{NP})^{A}$ then the way you should think of it is as  $(NP^{NP^A\cup A})$ (by $\cup$ I mean an oracle either to $A$ or to an $NP^A$ language).

Hence ${\Sigma_2^P}^{NP}$ is equal to $(NP^{(NP^{NP})})^{NP}$ which is certainly equal to $(NP^{NP^{NP}})$ since every query you could make to the $NP$ oracle, you could make it to the $NP^{NP}$ oracle.


Is there a name for this property of a term rewriting system?

I'm not sure there is a name for this specific property, though I would say "All right-hand sides are in head-normal form".

To be honest, this seems like a very strange property to request, especially since an inner reduction may provoke a head reduction, like so:

$$ {\cal R} = \{a \rightarrow b, f(b)\rightarrow f(a)\}$$
(I'm using letters for function symbols instead of numbers, as is traditional). In this case $f(a)$, the right hand side of the second rule, does not match any rule at it's head, but it may match the second rule if you apply the $a\rightarrow b$ reduction inside.


I don't know if it has been studied before, but after a quick look I think it should be PSPACE complete.

We can build a reduction using the Nondeterministic Constraint Logic model of computation (NCL).

I quick idea is the following (I assume you're familiar with the NCL model): given an NCL graph $G$, you can replace red and blue directed edges with a suitable gadget (with undirected edges) that "marks" the direction of the edge.

Then build the $A_i \to B_i$ subgraphs in such a way that if $A_i$ is a  subgraph of $G$ that represents an NCL  node with valid incoming/outgoing edge constraints, then it can be replaced with $B_i$ which represents a valid flip of one of those edges.

The $A_i / B_i$s should be isomorphic; but this is not a problem for the OR gadget: just add 2 dum nodes "D" so that every node $u$ of the NCL, in the resulting graph has degree 5 with 3 incoming (blue) edges and 2 outgoing (red) edges.

The AND gadget is a little bit more complex, but you can use a "circle" (green edges in the figure) that forces the correct correspondence between the flip of the 2 red edges and the flip of the blue edge (on the opposite side).

If I have enough time I'll give more details about the proof.


On our regular 666 research seminar we came up with the following proof.

We start with some definitions. Let P be our poset. For simplicity, suppose that none of the weights sum up to zero.
Denote the weight of a vertex by w(x) and the sum of the weights of a set by w(X).
We say that a set X is Y-up (closed) if it is contained in Y and every element of Y that is bigger than an element of X is also in X.
Similarly, say that a set X is Y-down if it is contained in Y and every element of Y that is smaller than an element of X is also in X.
In this language the set of marked elements must be always P-down.

We prove by contradiction. Take the shortest mark/unmark sequence that marks every element. We call such sequences full. At any given point, consider the set of elements that were marked before but are now unmarked. Denote this set by U.

Claim: w(U)>0.

Proof: We prove that the weight of any U-up set, X, is positive. The proof is by induction on the size of X.
If there is an X-down set, Y, such that w(Y)>0, then since by induction we know that w(X\Y)>0 (since it is X-up), we also have w(X)>0.
If for every X-down set, Y, we have w(Y)<0, then by deleting up to this point all the markings and unmarkings of the elements of X from our sequence, we get a shorter full sequence. We are done with the proof of the claim.

Now suppose that we have a full sequence where w(U)>0 at any point for the set U of currently unmarked elements. Take the sequence that we obtain from this by taking the first marking of every element and never unmarking anything. It is clear that this will also be a full sequence satisfying that the set of marked elements is always P-down. Moreover, the sum of the weights will be always at least as much as in the original sequence since at any given time the difference is w(U). We are done.

With this method one can even prove that if instead of marking the whole of P, we only want to mark a subset of P, then it can be done with a sequence of markings followed by a sequence of unmarkings. The proof is the same except that at the end some elements, U, stay unmarked but these can be moved to the end of the sequence as the weight of any U-up set is positive.


Here is a "canned" answer that might be useful, but has no cryptographic depth (hopefully we get answers with depth as well).

What makes for a good candidate OWF? The naive answer tends to boil down to "something that looks hard to invert to me", but the expert's response is usually more like "something that many smart people have tried to invert but failed" (or something whose invertability would imply that of such a function). From this perspective, it is worse for the problem to be more obscure (fewer have tried it), and it may be worse that the function is more complicated (this obfuscates whether it is truly difficult or you just cannot see the solution yourself).

To put the intuition another way, a common "bad intuition" is that if a problem looks more complicated or difficult to define/understand, then it is more likely to be computationally difficult to solve. Theoretical crypto does not accept this premise. The primary evidence we have for computational hardness is a history of failed attempts, which means good candidates should be simple, well-known functions with long histories.


Packing $n$ objects into $m$ bins whose size is variable

One simple "bad" input that needs to be considered for worst-case analysis of this problem is as follows.

Let $c=(\sqrt{17}-1)/2 \approx 1.56$.
There are three objects of size $c$, $1$, and $1$.
There are two bins of size $2$ and $c$.
Initially $a=1$.
Some heuristics will place the largest object into the big bin, necessitating $a$ increasing from 1 to at least $(c+1)/2 = 2/c > 1.2807$.
An optimal packing leaves $a=1$, placing the two small objects into the big bin and the big object into the smaller bin, with no waste.
Hence such heuristics will have a worst-case actual-to-optimal ratio of more than 1.2807.

Notwithstanding this worst-case analysis, a heuristic like the one described in the edited question is likely to work well for practical examples, even if its worst-case performance is at least 28% worse than optimal.
Similar heuristics are often used in practice, sometimes with adjustments like "instead of the general criterion, prefer a bin that is only a tiny bit larger than the object to be placed, if one such exists".
Most implemented heuristics I'm familiar with are a big mess of such case analysis, but work extremely well in practice.
However, it is often quite hard to come up with badly behaved inputs for such complex algorithms, and it is even harder to prove that they are the worst possible.


What bounds can be put on counting reachable nodes in a dag?

The transitive closure of a directed graph with $m$ edges and $n$ vertices can be computed
slightly faster than $O(mn)$ time, but not by much. An $O(n^2 + mn/\log n)$ time algorithm is mentioned in a footnote of Chan's 2005 WADS paper on APSP (journal version in Algorithmica 2008). A slight improvement to $O(n^2 + mn \log(n^2/m)/\log^2 n)$ can be found in the ICALP'08 paper "A New Combinatorial Approach for Sparse Graph Problems " by Blelloch, Vassilevska and Williams.
That being said, I don't know whether counting descendents is easier than actually finding them


Finding an injective mapping between two sets that maximizes a similarity function

The simplest counter-example is something like an "anti-multiplication table": for $A=B=\left\{1,2,\ldots,n\right\}$ let's define the cost function as $cost(a, b) = n^2 - ab$. The greedy algorithm will fail for $n \ge 2$.

The problem you are solving is called the assignment problem and it's well studied. It can be solved in polynomial time by the Hungarian algorithm, for example.


Is any chordal graph an incomparability graph?

I believe the answer to your question, and to most questions like this, is to be found on http://graphclasses.org/

There's also a book that has much of this (including an appendix at the back with some of the main subset relations between graph classes): Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.

The answer to your specific question is no. The graph shown in http://commons.wikimedia.org/wiki/File:SubdividedTriangle.png (a central triangle with three more triangle attached to its edges) is chordal, but its complement http://en.wikipedia.org/wiki/File:Forbidden_interval_subgraph.svg is not a comparability graph.


Fast Algorithm to Check if a Set of Sets forms an Anti-chain

This problem is SETH-hard at time $n^2$ (Williams 04). There is is no $n^{2-\epsilon}$ algorithm for any $\epsilon > 0$ if the universe has size $\omega(\log n)$.

For small universe size ($c \log n$ for some $c$), there is an algorithm with time $n^{2-1/O(\log c)}$ (Abboud, Williams, Yu 15)


Is there any online lecture series that covers "Computational Complexity: A Modern Approach"?

These courses by Prof. Ryan O'Donnell are excellent:
https://www.youtube.com/watch?v=pRnnEOAQZF8&list=PLm3J0oaFux3b8Gg1DdaJOzYNsaXYLAOKH
https://www.youtube.com/watch?v=RxhpiYKFQd8&list=PLm3J0oaFux3YL5vLXpzOyJiLtqLp6dCW2
They cover most relevant material.


Data structures for embedded simplicial complexes

First you can read the CGAL documentation that can help you to understand combinatorial and generalized maps, since it provide several examples. You can also read the book "Combinatorial Maps: Efficient Data Structures for Computer Graphics and Image Processing".

Now some answers:

1) I don't think. In a combinatorial map, in 2D, a triangle is described by 3 darts. In 3D, a tetrahedron is described by 4 triangles, thus 12 darts. Etc...

Given a dart $d$, each permutation, except $\beta_n$, stay in the same n-simplex. A dart corresponds to a n+1-tuple (vertex, edge, face, ..., n-simplex), and each $\beta_i$ (except $\beta_1$) can be seen as a switch for the $i^{th}$ element of the tuple (each switch also switches vertices).

2) Condition 4 ensures that when two n-simplices are glued along one of their (n-1)-face, all the darts of the two (n-1)-faces are correctly identified two by two (cf. the following example).

3) Only quasi-manifold. For example in 3D, you cannot represent two tetrahedra that share only a common vertex, since this is not a quasi-manifold.

4)  A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells (cf. this section).

5) Let us consider one simple example in 2D. Take a square with four edges a,b,c,d. Now you can identify edges a and c to form either an orientable strip or a Mobius strip. Thus you need two different type of identification. This is not possible with combinatorial maps but this is possible with generalized maps since one edge in 2D is described by two darts, allowing to choose which pair of darts are identified (cf. the example here).

Hope this helps, and welcome into the fabulous world of combinatorial maps !


Efficiently modeling Turing machines in Peano Arithmetic

I am not sure I understand the question, specially the informal part. If by it you mean essentially how we generally argue for correctness of things, I woke interpret it as day proofs in ZFC or something like that.

In any case we can express provability of a statement in a computably axiomatizable system in PA (and in fact in weaker systems). Now you are asking if this can be expressed as efficiently in PA as in the stronger system. The answer is yes, just express that the Turing machine that search for a string is a ZFC proof of the formula halts. The size of the description of such a machine is polynomial in the size of the ZFC formula.

The answer to the second question is no. Just consider a computable function that grows so fast that PA cannot prove its totality but ZFC van prove its totality.

The key idea really is that the language of ZFC itself is very easy to capture. We can express that string $\pi$ is a ZFC-proof of $\varphi$ in much simpler systems that ZFC (e.g. Cook's $V^0$ which captures computation in $AC^0%).

If we can express that, then we can express anything ZFC can express. That is there is polynomial-time computable function $t$ that maps any well-formed formula in the language of ZFC to a formula in the language of PA such that the formula is provable in ZFC iff there is a string that PA proves it is a ZFC proof of the the translation with: just encode the ZFC proof, PA can verify syntactically that it is a valid ZFC proof, and if there is such a string that PA proves is a ZFC proof of the formula, then it is actually a ZFC proof of the formula.

It is key here that I didn't quantify for the existence of the ZFC proof in the PA translation. The reason is that PA might not be able to prove the existence generally. E.g. let $f$ be computable function whose totality is provable in ZFC but not in PA. Then the formula $\forall x \exists y f(x)=y$ is probable in ZFC but not in PA (with any resonable encoding). The reason is that if we can prove it then we prove the totality.

This is generally related to what is called interpretability and interpretation in logic. Essentially we have L1 and L2 and they have their own semantics, and we ask if everything in L1 can be faithfully expressed in L2. Think of the formulas as capturing the subsets of the standard models of those languages. E.g. for ZFC this would be the standard model $\mathbb{V}$ while for PA this would be standard natural numbers $\mathbb{N}$. Before thinking about expressing things, you need to think about how subsets of these two structure map to each other. What does it mean to map a set in ZFC to a set in PA. We can restrict our interest to subsets of $\omega$ in ZFC. Then the question becomes. We can restrict ourselves to arithmetic subsets of $\omega$. Then these subsets are expressible in PA clearly. For any such set we have a PA formula.

For size we really need to talk about families of formulas. If the family is uniform, that is it is obtained by sectioning another arithmetic formula, then the size relation is still polynomial: let the formulas in ZFC be $\varphi_n(x) := \varphi(n,x)$. To obtain the translation in PA, translate $\varphi$ and then plugin $n$: $[[\varphi_n(x)]] := [[\varphi(x,y)]]_{y/n}$. The only part that changes is $n$, the rest remain the same.

For provability the story is not about standard models but also non-standard models that satisfy the axioms. Is it the case that every function over natural numbers that is total in every model of ZFC is total in every model of PA? The answer is no.


Integer multiplication when one integer is fixed

While it won't always be the most efficient algorithm, this question has a very close relationship with addition chains; any algorithm for computing $A$ quickly by addition chains translates into an algorithm for computing $f(B) = AB$ by repeated addition (each addition, of course, being an $O(n)$ operation).  Contrariwise, a quick algorithm for computing $AB$ for any $B$ leads to a quick algorithm for computing $A$, but of course this algorithm doesn't necessarily have to have the form of an addition chain; still, that seems like an excellent place to start.  Have a look at http://en.wikipedia.org/wiki/Addition_chain or check out vol. 2 of The Art Of Computer Programming for more details.


While I can't give you a name, I can provide evidence that the problem is $\mathbf{NP}$-hard to approximate to any factor, and thus is likely to be unstudied in full generality in the literature (hinting that it may remain unnamed).

Indeed, consider the $\mathbf{NP}$-hard instance of the problem you have in mind, with source $s$ and destination $t$. Via standard arguments, there is a corresponding $\mathbf{NP}$-hard decision problem, of the form "is it possible to route at least $k$ units of flow from $s$ to $t$"? I'll assume here that $k$ is polynomial, since that seems to be the case for most reductions I can think of (such as the one through Max-3D-matching). We begin with this problem to construct our inapproximable example.

Let $u$ denote the maximum (unrestricted) flow routable from $s$ to $t$, which is an upper bound for the solution to your problem. Further, let $t'$ be a new vertex you tack onto the graph. For every possible value in the set $Q = \left(\{k, k+1, k+2, k+3, \cdots, 2k-1\} \cup \{2k, 4k, 8k, 16k, \cdots \}\right)$ no larger than $u$, add a parallel edge with that capacity from $t$ to $t'$. While this transforms your graph into a multigraph (we will fix this later), the number of parallel edges we added here is at most polynomial.

If the original problem had a solution with value $\geq k$, then there is some amount of flow routable from $s$ to $t'$. Indeed, route that flow to $t$, decompose the amount of flow at $t$ into a sum of values in $Q$, and then route it along the corresponding edges. Otherwise, it is impossible to route any flow between $t$ and $t'$, and thus the maximum flow routable (in your set up) from $s$ to $t'$ is $0$.

Since the dependency on parallel edges can be removed by subdividing each edge with a vertex, we conclude that it's impossible to distinguish cases where the optimal solution has value $0$ from that  where it's at least some $k > 0$, and thus there is no multiplicative approximation. Standard modifications to this argument rule out additive (polynomial) approximations as well.

As a side note, this approach is pretty thematic in proving such hardness results, and in general problems that can encode an all-or-nothing "all solutions must be of size at least X" constraint for arbitrary X tend to be very inapproximable.


Grothendieck's inequality, from his days in functional analysis, was initially proved to relate fundamental norms on tensor product spaces. Grothendieck called the inequality "the fundamental theorem of the metric theory of tensor product spaces", and published it in a now famous paper in 1958, in French, in a limited circulation Brazilian journal. The paper was largely ignored for 15 years, until it was rediscovered by Lindenstrauss and Pelczynski (after Grothendieck had left functional analysis). They gave many reformulations of the paper's main results, related it to research on absolutely summing operators and factorization norms, and observed that Grothendieck had solved "open" problems which had been raised after the paper was published. Pisier gives a very detailed account of the inequality, its variants, and its tremendous influence on functional analysis in his survey.

Grothendieck's inequality is very naturally expressed in the language of combinatorial optimization and approximation algorithms. It says that the non-convex, NP-hard optimization problem
$$
\max\{x^TAy: x \in \{-1, 1\}^m, y \in \{-1, 1\}^n\}
$$
is approximated up to a fixed constant by its semidefinite relaxation
$$
\max\{\sum_{i,j}{a_{ij}\langle u_i, v_j\rangle}: u_1, \ldots, u_m, v_1, \ldots, v_n \in \mathbb{S}^{n+m-1}\},
$$
where $\mathbb{S}^{n+m-1}$ is the unit sphere in $\mathbb{R}^{n+m}$. Proofs of the inequality give "rounding algorithms", and in fact the Goemans-Williamson random hyperplane rounding does the job (but gives a suboptimal constant). However, Grothendieck's inequality is interesting because the analysis of the rounding algorithm has to be "global", i.e. look at all terms of the objective function together.

Having said this, it should not be surprising that Grothendiecks's inequality has found a second (third? fourth?) life in computer science. Khot and Naor survey its multiple applications and connections to combinatorial optimization.

The story does not end there. The inequality is related to Bell inequality violations in quantum mechanics (see Pisier's paper), has been used by Linial and Shraibman in work on communication complexity, and even turned out useful in work on private data analysis (shameless plug).


This is done in Chapter 6 "Decomposition of sequential functions" of

[1] S. Eilenberg, Automata, languages and machines, Vol. B, Academic Press, New York, 1976

and there is indeed a connection with the Krohn-Rhodes decomposition. However the decomposition is weaker than just $h = f \circ g$, just like in K-R decomposition, which works up to division. See also

[2] H. Straubing, Families of recognizable sets corresponding to certain
varieties of nite monoids, J. Pure Appl. Algebra, 15, (1979) 305{318.

for application to regular languages (or Google "wreath product principle" for more recent papers).


Problems between NC and P: How many have been resolved from this list?

BTW: The list of known CC-complete problems has grown since both versions of the book.   See this paper by Greenlaw and Kanlabutra.


Database query languages for efficient queries

One way of looking at database query languages is through the lens of deductive databases, where queries are represented as logic programs. In this setting, the most relevant work related to your question is McAllester's On the complexity analysis of static analyses, which observed that you can reason about the running time of a query by reasoning about the number of "prefix firings" in the rules of your program. What a "prefix firing" is isn't terribly complicated, but I'll refer you to the paper for that.

In the functional programming world, this sort of thing is called a cost semantics: it doesn't mean you can only implement efficient queries (programs), but it means that you can reason about the asymptotic complexity of your declarative program in a reasonable way.

Some later work on implementations of McAllester's ideas include From datalog rules to efficient programs with time and space guarantees (Liu and Stoller) and Dedalus: Datalog in Time and Space (Alvaro, Marczak, Conway, Hellerstein, Maier, and Sears). I admit I haven't yet read the latter of those two papers, however.


Complexity of finding a graph separator with a given property

Our paper:

http://arxiv.org/abs/1110.4765

shows that many of these problems are fixed-parameter tractable, i.e., we can decide in time f(k)*O(n+m) if an s-t separator of size k exists. This is true for example for the problem of finding a connected s-t separator, or a separator that is an independent set, or a separator that induces a bipartite graph. A forthcoming paper addresses the problem of finding a 2-connected s-t separator.


Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

There is a relation between the width of an OBDD for a function $f$ and the communication complexity of a one-way communication protocol for the best-case partition of variables for $f$ (see E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997).

This is a powerful tool for proving exponential size OBDDs for various functions (together with coauthors, we used this method for proving that $\epsilon$-bipartiteness is hard for OBDDs, see here).
Basically, if there exists an OBDD of width at most $w$ that solves $f$, then $\kappa_{best}(f) \leq \log w$.
I think this is more intuitive to think in terms of communication complexity rather than OBDD.


A total language that only a Turing complete language can interpret

This is a badly phrased question, so let's first make sense of it. I am going to do it the style of computability theory. Thus I will use numbers instead of strings: a piece of source code is a number, rather than a string of symbols. It does not really matter, you may replace $\mathbb{N}$ with $\mathtt{string}$ throughout below.

Let $\langle m, n\rangle$ be a pairing function.

Let us say that a programming language $L = (P, ev)$ is given by the following data:

a decidable set $P \subseteq \mathbb{N}$ of "valid programs", and
a computable and partial function $ev : P \times \mathbb{N} \to \mathbb{N}$.

The fact that $P$ is decidable means there is a total computable map $valid : \mathbb{N} \to \{0,1\}$ such that $valid(n) = 1 \iff n \in P$. Informally, we are saying that it is possible to tell whether a given string is a valid piece of code. The function $ev$ is essentially an interpreter for our language: $ev(m,n)$ runs code $m$ on input $n$ – the result may be undefined.

We can now introduce some terminology:

A language is total if $n \mapsto ev(m,n)$ is a total function for all $m \in P$.
A language $L_1 = (P_1, ev_1)$ interprets language $L_2 = (P_2, ev_2)$ if there exists $u \in P_1$ such that $ev_1(u, \langle n, m \rangle) \simeq ev_2(n, m)$ for all $n \in P_2$ and $m \in \mathbb{N}$. Here $u$ is the simulator for $L_2$ implemented in $L_1$. It is also known as the universal program for $L_2$.

Other definitions of "$L_1$ interprets $L_2$" are possible, but let me not get into this now.

We say that $L_1$ and $L_2$ are equivalent if they interpret each other.

There is "the most powerful" language $T = (\mathbb{N}, \varphi)$ of Turing machines (which you refer to as "a Turing machine") in which $n \in \mathbb{N}$ is an encoding of a Turing machine and $\varphi(n,m)$ is the partial computable function that "runs the Turing machine encoded by $n$ on input $m$". This language can interpret all other languages, obviously since we required $ev$ to be computable.

Our definition of programming languages is very relaxed. For the following to go through, let us require three more conditions:

$L$ implements the successor function: there is $succ \in P$ such that $ev(succ,m) = m+1$ for all $m \in \mathbb{N}$,
$L$ implements the diagonal function: there is $diag \in P$ such that $ev(diag,m) = \langle m, m \rangle$ for all $m \in \mathbb{N}$,
$L$ is closed under composition of functions: if $L$ implements $f$ and $g$ then it also implements $f \circ g$,

A classic result is this:

Theorem: If a language can interpret itself then it is not total.

Proof. Suppose $u$ is the universal program for a total language $L$ implemented in $L$, i.e., for all $m \in P$ and $n \in \mathbb{N}$,
$$ev(u, \langle m, n \rangle) \simeq ev(m, n).$$
As successor, diagonal, and $ev(u, {-})$ are implemented in $L$, so is their composition $k \mapsto ev(u, \langle k, k \rangle) + 1$. There exists $n_0 \in P$ such that $ev(n_0, k) \simeq ev(u, \langle k, k \rangle) + 1$, but then
$$ev(u, \langle n_0, n_0\rangle) \simeq ev(n_0, n_0) \simeq ev(u, \langle n_0, n_0 \rangle) + 1$$
As there is no number equal its own successor, it follows that $L$ is not total or that $L$ does not interpret itself. QED.

Observe that we could replace the successor map with any other fixpoint-free map.

Here is a little theorem which I think will clean up a misunderstanding.

Theorem: Every total language can be interpreted by another total language.

Proof. Let $L$ be a total language. We get a total $L'$ which interprets $L$ by adjoining to $L$ its evaluator $ev$. More precisely, let $P' = \{\langle 0, n\rangle \mid n \in P\} \cup \{\langle 1, 0\rangle\}$ and define $ev'$ as
$$ev'(\langle b, n \rangle, m) =
\begin{cases}
ev(n,m) & \text{if $b = 0$},\\
ev(m_0, m_1) & \text{if $b = 1$ and $m = \langle m_0, m_1 \rangle$}
\end{cases}
$$
Obviously, $L'$ is total because $L$ is total. To see that $L'$ can simulate $L$ just take $u = \langle 1, 0\rangle$, since then
$ev'(u, \langle m, n\rangle) \simeq ev(m, n)$, as required. QED.

Exercise: [added 2014-06-27] The language $L'$ constructed above is not closed under composition. Fix the proof of the theorem so that $L'$ satisfies the extra requirements if $L$ does.

In other words, you never need the full power of Turing machines to interpret a total language $L$ – a slightly more powerful total language $L'$ suffices. The language $L'$ is strictly more powerful than $L$ because it interprets $L$, but $L$ does not interpret itself.


Counting the number of distinct s-t cuts in a oriented graph

Counting the number of s,t-cuts is #P-complete.  This is a result by Provan and Ball.

J. Scott Provan, Michael O. Ball: The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected. SIAM J. Comput. 12(4): 777-788 (1983)

Therefore, unless some complexity-theoretic collapse happens, you cannot get essentially faster algorithm than listing all of them.


"Smallest" path that visits a given set of vertices

So you want to find the smallest set $S$ of vertices that can be used for a walk containing $s$, $t$, and the vertices $x_i$, from $s$ to $t$. In the undirected case this can be simplified to: you want to find the smallest set $S$ of vertices containing $s$, $t$, and $x_i$ such that $S$ is connected.

This is the graph Steiner tree problem and is NP-hard. You are looking at the directed case, but making this problem directed cannot make it easier, so it remains NP-hard. The reduction from the undirected case is: replace each undirected edge by two directed edges, one in each direction.


In the UK, some of the universities to study at are Oxford, Cambridge, York and Imperial College London, though this list will vary depending on precisely which topic you are interested in. The group of Abramsky at Oxford does research in Quantum Computation, so going there and following courses he offers (and related ones) would certainly help you reach your goal.

It would be a good idea to go through the web sites of the computer science departments of the above mentioned universities and see whether they offer courses (or even a program) that heads in the right direction. Look not only at the descriptions of courses, but also of the personal web pages of the researchers, who will often have some description of their research interests, which may differ from the courses on offer, but will be available to study as you enter later phases of your study.


Quantum Money where not even the Bank can counterfeit

There are proposals for quantum money where it appears that not even the bank can produce two copies of a quantum money state with the same serial number. See

Farhi et al's paper Quantum Money from Knots,
Mark Zhandry's paper Quantum Lightning Never Strikes the Same State Twice,
Daniel Kane's paper Quantum Money from Modular Forms.

In order to make sure that the bank can only produce $k$ banknotes, one would need to have the bank publish the serial numbers of exactly $k$ banknotes in some secure location. Otherwise it could make as many bank notes as it wants (although they would all have different serial numbers).


Complexity of Computing Lexicographically Minimal Element of Orbit

This problem is NP-hard.

Although it may be possible to find some canonical form for string isomorphism, say, in quasi-poly time, without upsetting our current guesses as to how the complexity world looks, finding the lexicographically least isomorphic string is NP-hard. This is precisely the content of Proposition 3.1 here. In fact, they show it remains NP-hard even when $G$ is an elementary abelian 2-group (=every nontrivial element of $G$ has order 2).


Calculate sum of reciprocal rank in arbitrary large graph

If I understand the requirements correctly, the answer is no. I will restate (what I understand to be) the problem:

We are dealing with graphs $(V,E,\delta)$ (undirected, though directed edges won't change the answer), equipped with a distance $\delta$ which generates a ranking $Rank_u$ for each node $u$. This means that there are no $u,v,w$ with $v\neq w$ and $d(u,v)=d(u,w)$; for any node $u$, $Rank_u$ is then the unique function $V\to\{1,...,|V|\}$ such that $Rank_u(v)<Rank_u(w)$ iff $d(u,v)<d(u,w)$.

I will concentrate on the case $a=b=1$, i.e. consider the sums

$s_1 := \sum_{v\neq u}\frac{1}{Rank_u(v)Rank_v(u)}$ and $s_2 := \sum_{v\neq u}\frac{1}{Rank_u(v)^2}$.

The question is whether $s_2$ can be used to approximate $s_1$. Note that for a graph with $n$ nodes, $s_2$ will always be equal to $n\sum_{i=2}^n\frac{1}{i^2}$, which is in $O(n)$, since $\sum_{i=2}^\infty\frac{1}{i^2}$ converges. It is enough to find a family $(V_n,E_n,\delta_n)$ of graphs with $|V_n|=n$ for which $s_1$ grows more quickly. Consider this example:

$(V_n,E_n)$ is the complete graph $K_n$ on $n$ nodes. The metric $\delta_n$ is given by $\delta_n(v_i,v_j) = 2^i+2^j$ for $i\neq j$ (and $0$ for $i=j$). The resulting ranking functions are

$Rank_{v_i}(v_j) = 1+j$ for $j<i$,
$Rank_{v_i}(v_i) = 1$,
$Rank_{v_i}(v_j) = j$ for $j>i$.

The first sum above then becomes

$s_1 = 2\sum_{i<j}\frac{1}{Rank_{v_i}(v_j)Rank_{v_j}(v_i)} = 2\sum_{i<j}\frac{1}{j(1+i)} = 2\sum_{j=2}^n(\frac{j-1}{j}\sum_{i=1}^{j-1}\frac{1}{i})$;

the summand is in $\Theta(\log j)$, and $s_1$ is in $\Theta(n\log n)$.


Specifically this looks like the Stable Roommate Problem (SRP). Alternate the order of preference based on position in a list sorted by distance from the total score. I.E., imagine a list with the following scores:

1, 3, 18, 19, 20, 21.

Then the preference list would be:

1: 3, 18, 19, 20, 21
3: 1, 18, 19, 20, 21
18: 19, 20, 21, 3, 1
19: 18, 20, 21, 3, 1
20: 19, 21, 18, 3, 1
21: 20, 19, 18, 3, 1

For more accuracy use the Stable Roommate With Ties (SRT) algorithm.

The way Swiss Teams differs from SRP is that not everyone will be listed. That is, if the teams with scores 20 and 18 have played each other already then neither list each other as preferences. It's possible that SRP will still give the correct result but it remains to be verified.


Reduction from SAT to binary matrix subset problem

The original problem asks for a given $k$ whether there is a solution with this $k$, so we can choose to instantiate $k=m$. This means we are forced to pick $m$ columns.
Then if you choose both $x_i$ and $\neg x_i$, there will be a $j$ so that the line number $j$ is left with only zeros, so this choice cannot be good.


Application of methods from dynamical system to the study of k-SAT and similar problems

in my opinion after looking into this to some degree, you will probably not do any better than the paper you've cited for background and references which are extensive. the authors specifically indicate that they have devised a novel approach that does not seem to have any direct precedent in the literature, and this seems correct. in other words, as they state themselves:

  Here we present a novel continuous-time dynamical system for k-SAT, with a dynamics that
  is rather different from previous approaches.

so their formulation (in the introduction, eg eqs.1,2) can be seen/regarded as a seminal new "bridge theorem" between two previously mainly different fields of dynamical systems theory and the theory of NP completeness.

this has happened many times in the past with NP completeness, and an early notice of this came in 1988 by Papadimitriou, in NP Completeness, a retrospective, which can be seen as a kind of TCS sequel/analog to the famous essay Unreasonable effectiveness of mathematics in the physical sciences, Wigner.

they cite the following as nearest references to their work:

  Although the theoretical possibility of efﬁcient computation via chaotic dynamical systems has been shown previously [15], nonlinear dynamical systems theory has not been
  exploited for NP-complete problems in spite of the fact that, as shown by Gu et al.[19], Nagamatu
  et al. [20] and Wah et al. [21], k-SAT can be formulated as a continuous global optimization
  problem[19], and even cast as an analog dynamical system [20, 21].

in SAT literature Mezard was a pioneer in introducing statistical physics analogies which have some strong connections to their new framework, but again they cite him.

here are two other sideways angles outside the paper references. Linear programming algorithms have a concept of continous variables, iteration and convergence somewhat analogous to a constrained dynamical systems trajectory. there is a significant amount of research in this vein under the heading of Maslov's method. here is another early reference on using linear programming to solve SAT:

Combining Linear Programming and
Satisability Solving for Resource Planning, Wolfram/Weld

another area that seems loosely similar is the use of artificial neural networks to solve SAT. again there is a concept of an algorithm with continuous variables that converges to a solution under update rules expressed as differential equations. see eg

A NN Algorithm for Boolean Satisfiability Problems (1996) Spears


What was the original intent for the creation of Lambda calculus?

He wanted to create a formal system for the foundations of logic and mathematics that was simpler than Russell's type theory and Zermelo's set theory.

The basic idea was to add a constant $\Xi$ to the untyped lambda calculus (or combinatory logic) and interpret $XZ$ as expressing "$Z$ satisfies the predicate $X$" and $\Xi XY$ as expressing "$X\subseteq Y$". With rules expressing these intentions one can then interpret the ${\to}{\forall}$-fragment of intuitionistic predicate logic and unrestricted comprehension, the only problem being that by Curry's paradox, every $X$ is derivable.

See p. 7 of:

Cardone and Hindley, History of Lambda-calculus and Combinatory Logic, 2006:
http://www.users.waitrose.com/~hindley/SomePapers_PDFs/2006CarHin,HistlamRp.pdf

As well as the introduction to:

Barendregt, Bunder and Dekkers, Systems of Illative Combinatory Logic Complete for First-Order Propositional and Predicate Calculus, JSL 58-3 (1993):
http://ftp.cs.ru.nl/CompMath.Found/ICL1.ps


What is the minimum required depth of reductions for NP-hardness of SAT?

Reposting my comment:

From a quick look, it seems like your question should be answered by "Manindra Agrawal, Eric Allender, Steven Rudich, Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem, JCSS 57: 127-143, 1999." They say "we prove that all sets complete for NP under AC0 reductions are complete under reductions that are computable via depth two AC0 circuits." But I may be missing something.


Construction of graph embeddings with non-intersecting edges

There is a "simpler" algorithm to check embeddability of graphs in surfaces of genus g.
See this paper.

Having a bipartite graph does not help. From any graph we can obtain a bipartite version by subdividing each edge once. The embeddability of the new graph and the original one is the same.


Let $f: \{0,1\}^* \rightarrow \{0,1\}$ be a function, and let $C$ be a class of algorithms working on finite slices of $f$. Every circuit lower bound whatsoever is a proof that $f \notin C$, for some $f$ and some $C$. Consider the "combinatorial property of Boolean functions" ${\cal P}_f$, such that

${\cal P}_f(f) = 1$ and ${\cal P}_f(g) = 0$ for all $g \neq f$.

A proof that $f \notin C$ is a proof that ${\cal P}_f$ is useful against $C$, in the terminology of Razborov and Rudich. That is, "usefulness" is totally unavoidable -- there is no way to "fall outside its scope." If you have proved a circuit lower bound at all, you have given some useful property.

Note that, if $f \in TIME[2^{O(n)}]$, then ${\cal P}_f$ is also constructive as well, in the terminology of Razborov and Rudich. So for functions $f$ computable within $E$ but not in (say) $P/poly$, constructivity would also apply to at least one property of Boolean functions that is useful against $P/poly$.

So, Razborov and Rudich is more fundamental than you might initially think.


Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?

A counterexample to this Murphy's Law could actually be the famous paper

Baker, Theodore; Gill, John; Solovay, Robert, Relativizations of the $\cal P=?\cal N\cal P$ question, SIAM J. Comput. 4, 431-442 (1975). ZBL0323.68033.

It shows that the $P=^? NP$ question is

hard: you cannot solve it with relativizable techniques; but also
easy: we can establish $P^A= NP^A$ for some oracles $A$, and $P^B \ne NP^B$ for some oracles $B$, so now we just have to figure out what whether a trivial oracle is more like $A$ or like $B$...


Extension to the Stable Marriage Problem ?

There is an open conjecture regarding 3 types of people. Suppose you have men women and dogs so that men have preference lists on women, women have preference lists on dogs, and dogs have preference lists on man. Is there always a stable marriage?

(For other preference structures on 3-types society the answers are known to be negative).

Another comment is that stable marriage represent a non empty core and there is a well known condition by Scarf that implies the existence of nonempty core. It is known that Scarf conditions are satisfied for the original stable marriage problemand for the house allocation problem. (But failed for the men/women/dogs problem).

Some references:

A reference to Scarf's paper: H.E. Scarf, The core of an $N$ person game, Econometrica 35 (1967) 50--69.
A paper showing various applications for Scarf's crucial lemma and quote quite a few others: (In particular, a fractional version of Gale-Shapley theorem for hypergraphs by Aharoni and Holzman is described): R. Aharoni, and T. Fleiner, On a lemma of Scarf, J. Combin. Theory Ser. B 87 (2003), 72--80.
A solution of the men-women-dogs problem when there are at most 4 of each gender appears in a paper by Eriksson et al (Math Soc Sci 2006).


Feasibility of equations with max constraints

Let $y_i=\min\{b_k| i\in J_k\}$. Observe for any feasible solution, $x_i\leq y_i$.

Claim: The system of $\max$ equations is feasible iff $x_i=y_i$ for $1\leq i\leq n$ is a solution.

Proof.
If $x_i=y_i$ is a solution, then the system of $\max$ equations is feasible

Consider any solution, and $x_i < y_i$ for some $i$. We can increase $x_i$ to $y_i$ without violate any equation. Assume it violates the $k$th equation, namely $\max\{x_j|j,i\in J_k\}=b_k$, then it implies $y_i = \max\{x_j|j,i\in J_k\} > b_k$, but that's a contradiction because
$$
b_k \geq \min\{b_j| i\in J_j\} = y_i = \max\{x_j|j,i\in J_k\} > b_k
$$.

The algorithm is just compute $y_i$s and check if it satisfies all the equations. This takes linear time.


What is conjunctive truth table reduction?

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

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


you will find an introductory text on clique-width (cwd for short) here: Upper bounds to the clique-width of graphs (B. Courcelle and S. Olariu, DAM 101). You can find more recent results in this survey: Recent developments on graphs of bounded clique-width (M. Kaminski, V. Lozin, M. Milanic, DAM 157(12): 2747-2761 (2009))

Cwd is a complexity measure based on graph operations that generalise word concatenation. Infinite countable graphs can have bounded cwd. You will say that a set (possibly infinite) of graphs (finite or countable) has bounded cwd if there exists a constant k such that any graph in this set has cwd at most k. For instance, complete graphs have cwd 2, distance hereditary graphs cwd at most 3, ...

1) The link between cwd and modular-dec is the following: cwd(G) = max {cwd(H) | H prime in the modular dec of G}. Hence, you can say that cwd generalises the fact that "prime graphs has bounded size". You can have graphs with prime-graphs of unbounded size but with bounded cwd.

2) if the size of prime-graphs is bounded, the cwd is bounded. The results in the paper you cite says that any problem expressible in MSOL can be solved efficiently in graph classes of bounded cwd. This set of problems include many NP-complete problems: clique-number, stable number, 3-colorability, ...

Some algorithmic aspects of  modular dec are studied here "A survey of the algorithmic aspects of modular decomposition" (M. Habib and C. Paul, Computer Science Review 4(1): 41-59 (2010))


Finding a matching whose contraction minimizes the number of arcs in a graph

I do not know if your intent is to allow undirected edges in E and arcs in A to be parallel or not, but it does not matter in the end.  In this answer, we assume that you do not allow edges and arcs to be parallel.

Consider a special case where for each arc in A, A also contains the arc in the opposite direction.  In this case, we can ignore the orientation of arcs and consider them to be undirected.  We call edges in E black edges and edges in A red edges.

Even under these two restrictions, the problem is NP-complete by a reduction from Max-2SAT.  Let φ be a 2CNF formula in n variables $x_1,\dots,x_n$ with m clauses.  Construct a graph G with 3n vertices $v_1,\dots,v_n,x_1,\dots,x_n,\bar{x}_1,\dots,\bar{x}_n$ as follows.  G has 2n black edges: $(v_i,x_i)$ and $(v_i,\bar{x}_i)$ for i=1,…,n.  G has $5\binom{n}{2}-m$ red edges.  First, connect $v_i$ and $v_j$ for i≠j by a red edge.  Next, for every distinct variables $x_i$ and $x_j$, consider four pairs of literals $(l,l')=(x_i,x_j),(x_i,\bar{x}_j),(\bar{x}_i,x_j),(\bar{x}_i,\bar{x}_j)$.  Connect literals $l$ and $l'$ by a red edge if and only if clause $(\bar{l}\vee\bar{l}')$ does not appear in φ.

It is clear that we only have to consider maximal matchings in black edges in order to minimize the number of red edges after contraction.  It is also clear that every maximal matching M in black edges consists of n edges connecting $v_i$ to $l_i\in\{x_i,\bar{x}_i\}$ for i=1,…,n.  Identify this maximal matching M with truth assignment $\{l_1,\dots,l_n\}$.  It is easy to verify that after contracting M and removing parallel edges, the graph has exactly $4\binom{n}{2}-k$ red edges, where k is the number of clauses satisfied by this truth assignment.  Therefore, minimizing the number of red edges after contracting a matching in black edges is equivalent to maximizing the number of satisfied clauses.


What is the proof that the existence of one-way-functions implies $P \neq NP$?

$P \ne NP$ if and only if worst-case one-way functions exist.

Reference:

Alan L. Selman. A survey of one-way functions in complexity theory. Mathematical systems theory, 25(3):203–221, 1992.


Name for "uniformly polynomial" subclass of XP?

I don't think this subclass of $\textsf{XP}$ has been studied in the literature (and given a name).

One reason why researchers might shy away from studying this subclass, is that it is not closed under fpt-reductions (and so one would have to deal with an 'annoying' new type of reductions). This is because fpt-reductions allow the parameter value to blow up superpolynomially (as long as it is bounded by some computable function of the old parameter value). To get a restricted notion of fpt-reductions under which your subclass of $\textsf{XP}$ is closed, you would need to add the restriction that fpt-reductions require the new parameter value to be bounded by some polynomial of the old parameter value.


What is the complexity of computing optimal prefix free codes, when the frequencies are similar?

It took a few years (five!), but here is a partial answer to the question:

http://arxiv.org/abs/1602.00023

Optimal Prefix Free Codes With Partial Sorting
Jérémy Barbay
(Submitted on 29 Jan 2016)

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in time within O(n(1+lgα))⊆O(nlgn), where the alternation α∈[1..n−1] measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size n and alternation α. Such results refine the state of the art complexity of Θ(nlgn) in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort a multiset depending on the queries on it (known since 1988).


If $p$  can be a function of $t$, then the problem can be intermediate. Set up $p$ so that the number of edges will be say $\log^4 t$. Then obviously $s$ can be at most $\log^2 t$ and hence there is a $t^{\log^2 t}$ algorithm for this problem, meaning that the problem (under standard assumptions, say SAT doesn't have subexponential algorithms) cannot be NP hard.

On the other hand, this problem is harder than the standard clique problem on $\log^2 t$ vertices (you can always place all the edges on those vertices and ignore the rest). And so again, under the same assumption the problem doesn't have a polynomial time algorithm.

If $p$ is a constant then it's always NP hard as gphilip said.


Of course there are many systems for modelling processes. These fall under the category of process algebras.  The key examples are $\pi$-calculus, CCS, ACP and CSP.

Process calculi have basic mechanisms for specifying process behaviour including: sending and receiving of messages (synchronously or asynchronously), creating parallel processes, nondeterministic choice between behaviours, and the replication of processes. Although the calculi are small in terms of the number of constructs, they are very expressive and a vast amount of research has gone into studying their properties.

The $\pi$-calculus differs from the others in that it allows, in essence, processes to be passed as first class values. It actually allows channel names to be passed around as first class values, enabling changes in the dynamic topology. This is probably the calculus you want because it offers the greatest dynamicity.

CSP (communicating sequential processes) is a little odd, when seen from a perspective of modelling molecules. It does have plenty of backing theory and tool support. (Invented by C. A. R. Hoare.)

CCS and ACP have less dynamicity than the $\pi$-calculus, but they are much easier to analyse and simulate. A solid toolset called $\mu$CRL (and $\mu$CRL2) are available for ACP. Similar tools are sure to exist for CCS.

I'd start examining the related work (see below) and then find which of the modelling formalisms suit what you are looking for.

There has in fact been quite a lot of work modelling chemical reactions and biological processes using process algebra.
Probably the best place to look  is Luca Cardelli's publication list. His whole line of research on BioComputing has probably 30 papers on the topic. This talk gives an overview of much of his work. This one is slightly more formal, though reading the papers is really the only way to see the details.

One approach that directly models chemical processes is CHAM (the chemical abstract machine). The key ingredient here is a solution of molecules and membranes. There are heating and cooling rules for rearranging the molecules and for removing junk. These rules are reversible. Finally there reaction rules which model reactions. In contrast to process algebras, CHAM models are not so worried about the syntax of processes, so you can invent your own representation of the molecules.

Rewrite logic as realised in the toolset Maude offers another more or less direct approach to specifying such reactions. One need only specify the rewrite rules, the handing of the "soup" is automatic. The toolset would enable the simulation and analysis of (smallish) chemical reactions. A probabilistic variant of Maude also exists.


The formulas are formulas of Abadi-Plotkin logic, which they describe in their paper A Logic for Parametric Polymorphism.

The semantics of System F that Abadi and Plotkin used to interpret their logic can be found in Bainbridge, Freyd, Scedrov, Scott's paper Functorial Polymorphism.


Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices

The problem is polynomial-time solvable.
Observe that we have to pick exactly one vertex from each color class to form a $k$-clique.
If there is a vertex $x \in V_{i}$ that has no neighbor in some $V_{j}$ with $i \ne j$,
then no $k$-clique includes $x$. Thus, we can remove such a vertex.
Repeat this until every vertex has a neighbor in each color class (except for the class it belongs to).
If some class becomes empty, then the graph does not have a $k$-clique.
Otherwise, since the property ``every pair of color classes induces a biclique + isolated vertices''
is closed under taking induced subgraphs,
the remaining graph is a complete $k$-partite graph, which contains a $k$-clique.


Minimum weights needed to derandomize weight assignment by isolation lemma

A deterministic scheme with tiny weights is easy to achieve: first, compute an arbitrary perfect matching, deterministically. Then, give the matched edges weight zero and all other edges weight one. The difficult question is how to compute a deterministic isolating scheme more quickly than finding a perfect matching.


Almost uniform sampling implies approximate counting

Given a set $A \subseteq B$, if you can sample uniformly from $B$, then you can estimate by repeated sampling the probability of the event that the sample is in $A$. That is, you can approximate the probability $|A| / |B|$, which is indeed close to enumerating the elements of $A$, and thus computing its size.


Why Tomita created GLR and didn't use Earley?

Better late than never.

If I understand correctly, Earley is top-down, and will spend time and memory creating Earley items for every production at a given S(i). This means that for natural language, in S(0) we create and check an Earley item for every possible word that starts a sentence, and there are quite a lot of those.

But GLR is bottom up, so assuming efficiently hashed table/state lookups, the first token selects the next transition(s) in constant time.

This is true specifically for natural languages, with the huge number of distinct productions. But not really meaningful for programming languages, with the very small set of productions.


Are there distribution properties which are "maximally" hard to test?

Sorry for unearthing this post -- it is quite old, but I figured having it answered may not be that bad an idea.

First, it looks like you performed your Chernoff bound with some slightly odd setting of parameters. Note that to perform your suggested "testing by learning" approach, it is sufficient to learn the distribution in total variation distance (or $\ell_1$, if you prefer, which is the same up to a factor 2) to distance $\frac{\varepsilon}{2}$. (before checking "offline" if there is any distribution $p'$ having the property $\mathcal{P}_n$ which itself is at distance at most $\frac{\varepsilon}{2}$ from your learnt hypothesis $\hat{p}$). This would naively lead to an $O\big(\frac{n\log n}{\varepsilon^2}\big)$ sample complexity upper bound for this approach; however, it is known (and "folklore") that learning an arbitrary distribution over a domain of size $n$ up to distance $\varepsilon$ (in total variation distance) can be done with only $O(\frac{n}{\varepsilon^2})$ samples (and this is tight).

So the baseline should actually be $O(\frac{n}{\varepsilon^2})$, which is already linear in $n$. Now, one can ask the next question -- are there "natural" properties for which testing (say, for constant $\varepsilon$) requires a linear dependence in the domain size $n$?

The answer is (as far as I know) "not quite, but close." Namely, following a significant line of work on estimating properties of distributions (or equivalently, tolerant property testing), the results of Valiant and Valiant imply (STOCS'11, FOCS'11, and some others) that the rather contrived property "being $1/10$-close to uniform" has sample complexity $\Theta_\varepsilon(\frac{n}{\log n})$.

(Note that it's a bit "cheating," in the sense that the property is simply a way to take a tolerant testing question and relabel it as testing of an ad hoc property).

If that is not entirely sufficient to quench your thirst, one can also show that for the (natural?) property of "being a $k$-histogram" (is the distribution piecewise constant on a set of $k$ unknown intervals?), setting $k=n/10$ for instance also results in an $\Omega(\frac{n}{\log n})$ lower bound (it's in a paper of mine from 2016; the lower bound follows from a rather simple reduction to the Valiants' result). Now, whether you consider "being an $\frac{n}{100}$-histogram" to be a natural property is up to you.


In the most authoritative reference on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.


Explicit type system with infinite non-cumulative universe hierarchy

Ali Asaf worked out a hierachy of universes with explicit coercions (lifting) in A calculus of constructions with explicit subtyping and established a relationship with cummulative universes.


TSP heuristics for limited distance information

There is no algorithm that runs in time $o(n^2)$ on an $n$-point metric space and returns a tour with weight within a constant factor of the minimum weight: see the argument in Section 9 of this paper by Indyk.

On the other hand, if you just want an approximation to the weight of the optimal tour, without actually getting a tour, then you can use this algorithm by Czumaj and Sohler. Their algorithm runs in time which is nearly linear in $n/\varepsilon^{O(1)}$ and returns a $1+\varepsilon$ approximation to the weight of minimum weight spanning tree. Since the minimum weight spanning tree is a factor 2 approximation to the minimum weight TSP tour, this gives a factor $2+\varepsilon$ approximation for TSP.

Of course these are worst-case bounds, but I find it implausible to be able to find a good tour by querying $o(n^2)$ edges unless you know more about your metric space. Metric spaces are very general objects and it's easy to hide information while still satisfying the triangle inequality.


There is a simple reduction from the subset sum problem. (We usually give it as an exercise.)

The idea is to encode in the weights that an element can only be included 0 or 1 times.

Assume the subset sum instance consists of numbers $w_1,\dots,w_n$ with target $W$. Assume that $w_i < B$ for all $i$.

We will have two new elements for each old element, simulating whether the element is used 0 or 1 times. For element $i$ we get two new weights $w^1_i = (2^{n+1} + 2^i)nB + w_i$ and $w^0_i = (2^{n+1} + 2^i)nB$. The new weight bound is defined as $W' = (n2^{n+1} + 2^n + \dots + 2^1)nB + W$. Values of elements are the same as their weights, and the target value is $W'$


Proof of decidability of type checking of calculus of (co)inductive constructions?

I found another reference that goes through a detailed proof of the decidability of typechecking for systems of dependent types up to the CIC:

Chapter 2 of Advanced Topics in Types and Programming Languages: Dependent Types, David Aspinall & Martin Hofmann.

As you probably know, the proof of decidability is conditional on decidability of $\beta$-equality, which itself is implied by the normalization of the calculus.

The proof of that statement is significantly more difficult, partly because it implies consistency of the logical system.


Super-polynomial time approximation algorithms for optimization problems

One example is Maximum Independent Set. It is NP-hard to approximate the problem with ratio $n^{1-\epsilon}$ (Zuckerman, 2007). However, Bourgeois et al. (2011) give a simple $n^{1/2}$-approximation algorithm with running time $O^*(2^{\sqrt{n} \log n})$. Here, $n$ denotes the number of vertices of the input graph and the $O^*$-notation hides polynomial factors.

Another example is the Bandwidth problem. Dunagan & Vempala (2001) design an algorithm with approximation ratio $O(\log^3 n)$ and running time $O(n^{\log n})$. To my knowledge, the best known polynomial time approximation has approximation ratio $O(\log^3 n (\log \log n)^{1/4})$ (Lee, 2009); however, no $\omega(\sqrt{\log n / \log \log n})$ lower bound is known for the best approximation ratio achievable in polynomial time.


Permanent Approximation - Why can the JSV algorithm not handle matrices with negative entries?

The answer to the title question is: it's difficult to simulate a Markov chain with negative transition probabilies.

Valiant's reduction uses the Chinese remainder theorem, which requires an exact number, not just an approximation. The JSV algorithm cannot tell you what the permanent of a matrix is modulo 3, for example.

The type of reductions you'd need to reduce to JSV were named "approximation preserving reductions" by Dyer at al. An approximation-preserving reduction from a problem X to a problem Y is a way of turning an FPRAS for Y into an FPRAS for X (in a way that relativises). A simpler case of the same pattern is #DNF and #SAT:

There is an approximation algorithm (an FPRAS) for counting solutions of a formula in disjunctive normal form.
It is NP hard to approximate the number of solutions of a formula in conjunctive normal form to within a multiplicative constant (because it is NP hard to determine whether there is any satisfying assignment at all).
There is a reduction from #SAT to #DNF: given a CNF formula $\phi$ on $n$ variables, replace all the conjunctions by disjunctions and vice versa. If the resulting formula has $x$ solutions, then $\phi$ has $2^n-x$ solutions.

There is no contradiction, because the reduction described above is not approximation-preserving. Another common non-approximation-preserving reduction for counting problems is polynomial interpolation.


With the exception of cryptography applications like Shor's algorithm and quantum key distribution, I think engineering 'killer-apps' are not the norm for quantum computing, and nobody expects them to be. As such, quantum walks are a natural generalization of random walks and thus worth studying in their own right. However, to avoid side-stepping any longer, I can give you some motivation and past successes.
First, just like with classical random walks, we can use quantum random walks in the design of algorithms. This can give us complexity seperations in the quantum query model by looking at glued trees (two binary trees attached leaf-to-leaf via a random permutation); there is no classical randomized algorithm (walk or otherwise) to get from one root to the other in a polynomial number of queries, but the quantum walk does it in polynomial number of queries:

Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003). Exponential algorithmic speedup by a quantum walk. In SToC (pp. 59-68). ACM.

Of course, this relies on this problem being a partial function, since for total-functions we know that exponential separations are not possible, and expect quadratic separation to be the best generally achievable result for quantum query complexity of total-functions. However, if you have a good classical Markov-chain based algorithm then we know that in many cases, the quantum version will have a quadratically faster hitting time, saturating the expected speed up:

Szegedy, M. (2004). Quantum speed-up of Markov chain based algorithms. In FoCS (pp. 32-41). IEEE.

Quantum walk approaches also resulted in optimal query algorithms for less "artificial" problems like element distinctness, where it is the best known algorithm:

Ambainis, A. (2007). Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1), 210-239.

In general, quantum walks are very powerful, and could also be used as models of universal computation:

Childs, A. M. (2009). Universal computation by quantum walk. Physical Review Letters, 102(18), 180501.
Childs, A. M., Gosset, D., & Webb, Z. (2013). Universal Computation by Multiparticle Quantum Walk. Science, 339(6121), 791-794.

If you want to take your applications outside of theoretical computer science and into the real-world of natural sciences, then you can also use quantum random walks just like classical ones: to model and understand certain natural processes. The paradigmatic example of this is for modeling photosynthesis:

Engel GS, Calhoun TR, Read EL, Ahn TK, Mancal T, Cheng YC et al. (2007). Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems. Nature 446 (7137): 782–6.
Rebentrost, P., Mohseni, M., Kassal, I., Lloyd, S., & Aspuru-Guzik, A. (2009). Environment-assisted quantum transport. New Journal of Physics, 11(3), 033003.

In the above work it was shown (roughly) that after a photon hits the chlorophyll, it is transformed into an exciton which does a quantum random walk on the chlorophyll complex until it finds a binding site where it can share its energy to turn an ADP into ATP. A quantum random walk is required by nature, because the lifetime of the exciton is not sufficient for a classical random walk to have sufficient energy transfer. We could get speculative and combine the previous two observations to suggest a nature-inspired model of computation but there is no reason to believe it could be anything better than a toy due to the fast decoherence times.


maximum weighted 2D coverage problem by a rectangle

Let me describe first how to solve this problem without precomputation, then I'll describe how to make use of precomputation.  I'll focus on the unweighted case (each point has weight 1); all the ideas should extend to the weighted case straightforwardly.

Here is an algorithm without precomputation: Use a sweep line.  Think of sweeping a vertical line from left to right.  This line represents the right edge of the rectangle.  The set of possible values for this sweep line will be the set of possible $x$-value of some point, so we only need to consider $O(n)$ locations of the sweep line.  Imagine that it starts at the left and slowly moves rightward.

The one thing we don't know is the $y$-value of the bottom edge of the rectangle; call it $b$ (for "bottom").  However, for any specific position of the sweep line, we can build a data structure that counts the number of points in the rectangle with bottom $b$, for all $b$ (i.e., that maps from the value of $b$ to the number of points if the rectangle's bottom edge is $b$ units above the axis, and the right edge coincides with the sweep line).  I suggest you use an interval tree to represent this data structure.  There are $O(n)$ possible values for $b$, and thus $O(n)$ intervals in the interval tree.  When we move the sweep line right, we might need to add or remove one interval from the interval tree.  When the sweep line hits a new point $(x_i,y_i)$, we add a new interval to the tree for the interval $[y_i,y_i+h]$ (where $h$ is the height of the rectangle).  When the sweep line hits $w$ units to the right of the point $(x_i,y_i)$, i.e., the sweep line hits $x=x_i+w$, then we delete the interval $[y_i,y_i+h]$ from the interval tree.  For each location of the sweep line, we can also use the interval tree to efficiently find the rectangle that covers the most points and has its right edge coincide with the sweep line; doing that for each possible location of the sweep line gives us the optimum rectangle.

The running time of this algorithm is $O(n \lg n)$.  Each insertion/deletion can be done in $O(\lg n)$ time, and we do $O(n)$ insertions and deletions, so the whole thing can be done in $O(n \lg n)$ time.

What about precomputation?  Well, if we are given the width $w$ and height $h$ of the rectangle in advance, along with the set of points, then we can build all of the interval trees.  Naively, it sounds like we need to store $O(n)$ interval trees, each of size $O(n)$, for a total of $O(n^2)$ space -- but one can do better.  We can reduce this to $O(n \lg n)$ space in total by using persistent data structures.  It is straightforward to build a persistent version of the interval tree data structure, using standard methods.

Once you've done the precomputation, given any vertical line representing the right edge of the rectangle, you can efficiently find the best rectangle that coincides with that right edge (in $O(1)$ time).  (Actually, you don't need persistent data structures for that: since there are only $O(n)$ possible queries, you can just record the answer for each possible query.)  I don't know if this is what you are looking for, though, as I found your question hard to understand (it was hard for me to tell what is available during precomputation and what is made available later for each query).


Are space and time hierarchies even comparable?

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$.

For example, let $g(n) = n^3$ and $$f(n) = \begin{cases}
 n & \text{if $n$ is odd},
\\\
 2^{n^5} & \text{if $n$ is even}.
\end{cases}
$$

Then choose $L_1$ and $L_2$ as follows:

$L_1$ is a language containing only strings of even length which can be decided in time $O(2^{n^5})$ but not in time $O(2^{n^4})$. The existence of such a language is pretty easy to prove from the time hierarchy theorem.

$L_2$ is a language containing only strings of odd length which can be decided in space $O(n^3)$ but not in space $O(n^2)$. The existence of such a language is pretty easy to prove from the space hierarchy theorem.

Then we have the following facts:

$L_1 \in TIME(f(n))$:

To decide whether a string is in $L_1$, simply check whether the length $n$ is even. If it is, then continue to use the $O(2^{n^5})$ time decider for $L_1$ whose existence is guaranteed by the definition of $L_1$. If $n$ is odd, immediately reject since $L_1$ does not include any odd length strings anyway. This procedure decides $L_1$, runs in time $O(n)$ when $n$ is odd, and runs in time $O(2^{n^5})$ when $n$ is even. In other words, this procedure decides $L_1$ in time $O(f(n))$. As desired, $L_1 \in TIME(f(n))$.

$L_2 \in SPACE(g(n))$:

By the definition of $L_2$, $L_2$ can be decided in space $O(n^3)$. Thus, $L_2 \in SPACE(n^3) = SPACE(g(n))$, as desired.

$L_1 \not\in SPACE(g(n))$:

Suppose for the sake of contradiction that $L_1 \in SPACE(g(n)) = SPACE(n^3)$. We know that $SPACE(n^3) \subseteq TIME(2^{O(n^3)}) \subsetneq TIME(2^{n^4})$. Thus, there exists a decider for $L_1$ which runs in time $O(2^{n^4})$. This directly contradicts the definition of $L_1$. Then by contradiction, we see that $L_1 \not\in SPACE(g(n))$.

$L_2 \not\in TIME(f(n))$:

Suppose for the sake of contradiction that $L_2 \in TIME(f(n))$. This means that there exists a constant $c$ and an algorithm $A$ deciding $L_2$ such that on any input of size $n$, algorithm $A$ terminates in time $c\times f(n)$.

We construct a new algorithm $A'$ as follows: given some input, walk through the entire input, keeping track of whether the input length is even or odd; if at the end of the input the length is determined to be odd, return to the start of the input and run $A$; otherwise, reject. For any input of odd length, $A'$ returns the same answer as $A$. For any input of even length, $A'$ rejects, which matches the expected behavior since $L_2$ contains no even length strings. Thus, $A'$ also decides $L_2$. On even length inputs, $A'$ runs for exactly $n$ steps. On odd length inputs, $A'$ runs for exactly $2n$ steps more than $A$ requires. But $A$ requires at most $c\times f(n)$ steps, which for odd $n$ is $cn$. Thus, in all cases, $A'$ runs in at most $(c+2)n$ steps. In other words, algorithm $A'$ decides $L_2$ in time $O(n)$.

But since $TIME(n) \subseteq SPACE(n)$, we can conclude that $L_2 \in SPACE(n) \subsetneq SPACE(n^2)$. This contradicts the definition of $L_2$. Thus, by contradiction we see that $L_2 \not\in TIME(f(n))$.


Reynolds: "the basic laws of variable binding"

See chapter 1 of Robert Harper's book Practical Foundations of Programming Languages. He formalizes syntax with binding operators using the notion of "abstract binding trees", which IIRC were originally introduced in the Nuprl proof assistant. The main keyword you need to find further information is "alpha-equivalence".


What do people mean by capabilities and capacities?

A comment in capability.h says

// The Task currently holding this Capability.  This task has
// exclusive access to the contents of this Capability (apart from
// returning_tasks_hd/returning_tasks_tl).

This looks to be an access control mechanism.

In the security literature, the word capability is used to refer to a way of controlling access.  The dominant usage is as a reference to an object that encapsulates authority such that denying access to the object denies access to that authority but there are others as explained at "Capability Myths Demolished"

  We know of no security mechanisms outside  of the
  object-capability model that have described themselves
  using the word capability except for “POSIX
  capabilities”, “Netscape capabilities”, and “split
  capabilities” [14]. POSIX capabilities are not generally
  described as “capability-based security”. The
  “Netscape capabilities” extensions to Java were fairly
  short-lived and have not been presented in the research
  literature as a capability system. Moreover, both
  “POSIX capabilities” and “Netscape capabilities” have
  never been presented as security mechanisms that can
  stand on their own, instead only serving as an extension
  to existing security systems. The split capabilities
  model is explicitly presented in contrast to the pure
  capability model [14].

The Haskell usage is not an object-capability model.  The pointer from a task to a capability would have to go the other way, and probably be proxied through a revokable wrapper to qualify as a capability in the sense explained above.


Here is an alternative to the answer by R B ; It is somewhat simpler, but has the disadvantage of an increase in degree.

Simply take $g(x) = x^{2n}f(x)f(-x)f(1/x)f(-1/x)$.


Research and open challenges in Programming Language Theory

I think the overall goal of PL theory is to lower the cost of
large-scale programming by way of improving programming languages and
the techincal ecosystem wherein languages are used.

Here are some high-level, somewhat vague descriptions of PL research
areas that have received sustained attention, and will probably
continue to do so for a while.

Most programming language research has been done in the context of
sequential computation, and by now we have arguably converged on a
core of features that are available in most modern programming
languages (e.g. higher-order functions, (partial) type-inference,
pattern matching, ADTs, parametric polymorphism) and are well
understood. There is as yet no such consensus about programming
language features for concurrent and parallel computation.
Related to the previous point, the research field of typing systems
has seen most of its activity being about sequential computation.
Can we generalise this work to find tractable and useful typing
disciplines constraining concurrent and parallel computation?
As a special case of the previous point, the Curry-Howard
correspondence relates structural proof theory and functional
programming, leading to sustained technology transfer between computer
science and (foundations of) mathematics, with e.g. homotopy type theory being
an impressive example. There are many tantalising hints that it can be
extended to (some forms of) concurrent and parallel computation.
Specification and verification of programs has matured a lot in
recent years, e.g.  with interactive proof assistants like Isabelle
and Coq, but the technology is still far away from being usable at
large scale in everyday programming. There is still much work to be
done to improve this state of affairs.
Programming languages and verification technology for novel forms of computation. I'm
thinking here in particular of quantum computation, and the biologically inspired
computational mechanisms, see e.g. here.
Unification. There are many approaches to programming languages,
types, verification, and one sometimes feels that there is a lot of
overlap between them, and that there is some more abstract approach
waiting to be discovered. In particular, biologically inspired
computational mechanisms are likely to continue to overwhelm us.

One problem of PL research is that there are no clear-cut open
problems like the P/NP question where we can immediately say if a
proposed solution works or not.


How common is phase transition in NP-complete problems?

expert researchers in this area basically assert that phase transitions are a universal feature of NP complete problems although this has yet to be formulated/ proven rigorously and it is not yet widely regarded/ disseminated in the larger field (it emanates more from an empirical-oriented branch of study). its nearly an open conjecture. there is strong evidence. there are no plausible candidates for non phase-transition NP complete problems. here are two refs that support this pov:

Phase transitions in NP-complete problems:
a challenge for probability, combinatorics, and
computer science / Moore
Phase transition behavior / Walsh (ppt)

here is a rough sketch of the truth of the assertion. it has to do with P contained in NP complete. an NP complete problem/ language must have instances that are solvable in P time and others that are solvable in exponential (or at least superpolynomial-) time if P≠NP. but there must always be some way to "group" the P instances from the "non-P" instances. therefore there must also always be some "transition criteria" between the P and non-P instances. in short, maybe this phenomenon is intrisically coupled with P≠NP!

another rough argument: all NP complete problems are interchangeable via reductions. if a phase transition is found in a single one, it must be found in all of them.

more circumstantial evidence for this, more recently (~2010) it was shown the phase transition shows up for lower bounds on monotone circuits for clique-detection on random graphs.

Average case complexity of detecting cliques / Rossman

full disclosure: Moshe Vardi has studied phase transitions particularly in SAT and has a contrasting more skeptical view in this talk/ video.

Phase transitions and computational complexity


What is known about the H-factor problem?

This can be considered as a type of read-twice constraint satisfaction problem. Unless I'm mistaken, it is quite easy to construct an "equality" gadget whenever $H$ has a double gap, if you allow constant constraints (requiring an edge to be in or out). Then you can use Schaeffer's Boolean CSP classification. So the problem then comes down to whether constants are important.

There is a big generalisation:

"Fanout limitations on constraint systems", Tomás Feder, Theoretical Computer Science, Volume 255, Issue 1-2, March 28, 2001, Pages 281 - 293.

http://www.sciencedirect.com/science/article/pii/S0304397599002881

Basically, for constraint languages $\Gamma$ (i.e. a finite set of Boolean relations) such that $\Gamma$ contains the constant relations $\{(0)\}$ and $\{(1)\}$, Feder considers the following problem: the input is a conjunction of constraints of the form $(v_{i_1},\dots,v_{i_k})\in R$ for some $R\in\Gamma$, such that each variable appears at most twice, and we ask if there is a satisfying assignment. Feder shows that if the constraint language contains a non-delta-matroid, the problem is equivalent to the unbounded-degree CSP. A set $H$ that has gaps (i.e. whenever Cornuejols' algorithm doesn't work) is a non-delta-matroid.

You can reduce read-once-or-twice to read-twice by doubling the instance and identifying the variables that were read exactly once.

Added later:

For your particular problem, I believe the assumption about constants is easy to get around. Let $\mathbb{N}=\{0,1,2,\dots\}$. For all $\mathcal{H}\subseteq 2^{\mathbb{N}}$ and all $d\in\mathbb{N}\cup\{\infty\}$, the following problem is either in P or NP-complete.

Name: Factor$(\mathcal{H},d)$.
Input: a simple graph $G$ of maximum degree at most $d$, and a set $H_v\in\mathcal{H}$ for each $v$.
Output: Is there a spanning subgraph of $G$ in which the degree of each vertex $v$ is in $H_v$?

Sketch proof:

If for all $H\in\mathcal{H}$, there are no gaps of length $\geq 2$ in $H\cap\{0,\dots,d\}$, the problem is tractable by Cornuejols' algorithm.
If for $H\in\mathcal{H}$ we have $0\in H$ or $H\cap\{0,\dots,d\}=\emptyset$, the problem is trivial: every graph has a 0-factor so all inputs are accepted.
Otherwise, since (2.) fails, there is a non-empty set $H\in\mathcal{H}$ with $0\notin H$ and $\min(H)\leq d$.
So if a vertex $v$ has degree $\min(H)$ and $H_v$, then all its edges must be in. So we can force edges to be in, and simulate constants,
and appeal to Feder's result.

This kind of gadgetry fails if we restrict the degrees of the input graph. For example let $H=\{1,4\}\subset\{0,1,2,3,4,5\}$,
and restrict the inputs to graphs that are regular of degree five. By symmetry, one cannot simulate constants.


Are recursive forms of Godel's statement possible?

As others have pointed out, there are certain technical difficulties with the statement of your question.  To straighten them out, let's start by avoiding the use of the term "unprovable" without qualification, and be explicit about which set of axioms your statement T is supposed to be unprovable from.  For instance, let's suppose that we're interested in statements T that are unprovable from PA, the axioms of first-order Peano arithmetic.

The first annoyance is that "T is true" is not expressible in the first-order language of arithmetic, by Tarski's theorem.  We could get around this by working in a metatheory that is powerful enough to define the truth of an arithmetical statement, but I think for your purposes this is an unnecessarily complicated route to take.  I think you're not so interested in truth per se but in provability.  That is, I suspect you'd be satisfied with defining T to be Godel_0 if T is true but unprovable in PA, and defining T to be Godel_1 if T is unprovable in PA but "T is unprovable in PA" is unprovable in PA, and defining T to be Godel_2 if T is unprovable in PA and "T is unprovable in PA" is unprovable in PA but "‘T is unprovable in PA’ is unprovable in PA" is unprovable in PA, etc.  That way we don't have to fuss with truth predicates.

This suffices to make your question precise, but unfortunately there is then a rather trivial solution.  Take T = "PA is consistent."  Then T is true because PA is consistent, and T is unprovable in PA by Goedel's 2nd incompleteness theorem.  Furthermore, "T is unprovable in PA" is also unprovable in PA for a somewhat silly reason: any statement of the form "X is unprovable in PA" is unprovable in PA because "X is unprovable in PA" trivially implies "PA is consistent" (since inconsistent systems prove everything).  So T is Godel_n for all n, but I don't this really gets at your intended question.

We could try to "patch" your question to avoid such trivialities, but instead let me try to address what I think is your intended question.  Tacitly, I believe you are conflating the logical strength needed to prove a theorem with the psychological difficulty of proving it.  That is, you interpret a result of the form "T is unprovable in X" as saying that T is somehow beyond our ability to understand.  There are these monstrous conjectures out there, and we puny humans crack PA-whips or ZFC-whips or what have you at those ferocious beasts, trying to tame them.  But I don't think that "T is unprovable in X" should be interpreted as meaning "T is impossible to reason about."  Rather, it's just measuring a particular technical property about T, namely its logical strength.  So if you're trying to come up with the über-monster, I don't think that finding something that is not only unprovable, but whose unprovability is unprovable, etc., is the right direction to go.

Finally, regarding your question about whether unprovability seems at all related to separability of complexity classes, there are some connections between computational intractability and unprovability in certain systems of bounded arithmetic.  Some of this is mentioned in the paper by Aaronson that you cite; see also Cook and Nguyen's book Logical Foundations of Proof Complexity.


Differences between Quantum Computing and Parallelism

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number generation) and parallelism.

In randomized computation, depending on the outcome of the coin-flips, you explore one out of many possible computational possibilities. If the vast majority of those paths give quickly rise to a particular answer, then that is the answer. In quantum computation, one is tempted to consider these different computational possibilities as being more "real" than in randomized computation, for the reason that we can cause them to cancel each other out — which seems a little as though the different computational possibilities are distinct processes which communicate with one another to collaboratively give an answer. However, while these different computational paths do interfere, they do not interact: a partial answer in one cannot be communicated to another, and as with the purely randomized computation, we cannot choose which one we observe — that is chosen at random from among the possibilities whose amplitudes haven't been cancelled out. In the end, the result is (as with randomized computation) taken as a sort of uncontrolled democratic vote between different so-called "computational branches", with only a small chance of an upset due to getting the answer from a small minority of computations which cast the objecting vote.

By contrast, in a truly parallel computation, each parallel process is obviously and independently present for querying and inspection. The decomposition of the computation as being performed by a collection of communicating agents, or 'processes', is a much more meaningful description. Whether a particular part of the computation 'belongs' to a particular process is something which we might impose by fiat, e.g. if we design a piece of hardware or software which is given responsibility (by us) for performing that computation, but at least there we may consider the activity of an individual agent and in principle design a protocol so that it determines the final output of the computation. This is simply not what happens in the mathematical model of quantum computation.

In the end, one must remember that the (very rough) intuition that quantum computing involves any parallelism at all, is just part of a struggle to obtain robust insights into how quantum computation differs from classical computation. From a point of view of interpretations of quantum mechanics, it corresponds to the Many Worlds Interpretation: but it is dubious to say that any 'world' which is to be cancelled out by destructive interference 'exists' independently, as such. Especially in the case where we may have a large amount of destructive interference and tight control over something like time-reversible operations, the choice of how we decompose the state of the computation into multiple "classical looking" branches is likely to be a description that we impose on the system to understand it, not one that necessarily refers to the physics or the nature of the computation in itself. This is especially true if you consider the various transformations that we can apply on a single qubit: sure, we can describe them as variations on performing a bit-flip or not performing a bit-flip, but what is the meaning of the differences between these quantum-superpositions-of-performing-a-bit-flip-or-not?

Thus, the difference between quantum computation and parallelized computation is that the so-called 'parallel' processes in quantum computation are much more like the imaginary parallel processes of a randomized computation: they cannot be addressed directly, but only in statistical bulk.


Is there algorithmic mathematical analysis?

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

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


In what sense are coroutines dual to (sub)routines?

I think this a misanalysis of the "co" prefix in this case.

"Coroutine" is "co" in the sense of "co-worker"; something that works together with another.

The term precedes by a long way the gross overuse for programming concepts of the prefix "co" in the Category Theoretic sense of a dual of another concept.

(Yes, there is editorial content there. ;-) )


Locating a point inside a union of simple polygons

You can consider every polygon one by one. You should update the answer after adding each polygon. For every polygon, first consider whether the polygon enclose the point. If yes, consider the every edge. Finding the edges going into the current minimum polygon (your current answer) and going outside. Then you can find all intersection and edges which generates your new answer. Iterate this procedure you can finally get the final answer