If the untyped language is terminating, can we still derive a contradiction from `Type : Type`?

The 'logic' of the contradiction with Type:Type is that you can create a term of any type including 'empty' type by 'cheating' by never returning. This is essentially the only way to cheat because of subject reduction and the subformula properties.

Subject reduction states that evaluation of terms preserves their type.
If you have subject reduction and strong normalization (through whatever means), then you can infer that if you have a term of type T, you have a term of type T in a normal form - without any redexes (cuts) in it.

You have to go over all your type rules and verify that all of them have subformula property except the cut rule (which normalization eliminates).
I.e you have to verify that if one of the non-cut rules were to produce a term of type T then you'll have one of its premises produce the term of type T (perhaps somewhere deeper in the derivation tree).
AFAIK every good type system requires sub-formula property (I'd like to learn of examples that contradict it).

Since type derivations are supposed to be finite trees, and you have no axiom (0 premises) rule to introduce a term of an empty type, you can prove by induction that no tree can build a term of an empty type.

To reiterate, the role of normalization is that cut rule does not have sub-formula property, so we have to eliminate it first while preserving the type of the term.

This is the general sketch of Gentzen's proofs of consistency of logics.


Is there a generalization of the GO game that is known to be Turing complete?

Related:  Rengo Kriegspiel, a blindfolded, team variant of Go, is conjectured to be undecidable.

http://en.wikipedia.org/wiki/Go_variants#Rengo_Kriegspiel

Robert Hearn's thesis (and the corresponding book with Erik Demaine) discuss this problem.  They prove other problems undecidable through "TEAM COMPUTATION GAME", which is reduced directly from Turing machine acceptance on empty input (see Theorem 24 on page 70 of the thesis).  So it seems to me that such a reduction would imply Rengo Kriegspiel is Turing complete.

On the other hand, their discussion says that this reduction would be very difficult (see page 123). So while this is a potential avenue, it appears that it has been looked into previously.


1-way Quantum Finite Automata Example Question

For sure, the automata performs a measurement after reading each symbol "a" and applying an associated unitary $V_a$. Yet, it is not really meaningful to compute the amplitudes of the state to be measured over $|q_{0}⟩$ and $|q_{1}⟩$ and to put them on the diagram, for the automata does neot measure the projectors $|q_{0}⟩\langle q_{0}|$, and $|q_{1}⟩\langle q_{1}|$. In other words, this numbers do not represent probabilities, they do not correspond to outcomes of the measurement to be performed. Therefore, labeling the arrows of the diagram with this numbers would give a potentially-misleading illustration of how the measurement process is working.

Although I might say things you already know, let us elaborate on the topic a bit to clarify the meaning of the transition diagrams you depicted. It is important to highlight that after reading a symbol $a$ and applying $V_a$, the automata does not perform a measurement in the standard computational basis: $$\{|q_0⟩,|q_1⟩,|q_{acc}⟩,|q_{rej}⟩\}$$ Instead, the automata measures this complete set of orthogonal projectors:

$P_{acc}=|q_{acc}⟩\langle q_{acc}|$
$P_{rej}=|q_{rej}⟩\langle q_{rej}|$
$P_{non}= |q_{0}⟩\langle q_{0}|+|q_{1}⟩\langle q_{1}|$

In other words, the measurement has three possible outcomes: (acc) the automata measures an accepting state and halts; (rej) the automata measures a rejecting state and halts; (non) the automate measures something else, does not halt, and reads next symbol (non states for non-halting).

Now, this is a problem I see in your diagrams: if you had a state $(|q_{0}⟩+|q_{1}⟩)/2$ before some measurement, and you happened to obtain the outcome (non), the state would remain invariant after the measurement (just apply $P_{non}$ and check). Therefore, depicting the probability of transition to either $|q_{0}⟩$ or $|q_{1}⟩$ creates confusion.

Taking all said into account it is easy to follow the calculation given in your main reference. In order to illustrate everything said, and, for completeness, I will quote it with here with some minor comments (though I added some modifications, I do not know whether this type of quoting is acceptable;  if its is not, please, let me know or edit the answer yourself):

  The automaton starts in $|q_0\rangle$.

  Read "a".  $V_a$ is applied,
  giving $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle+
\frac{1}{\sqrt{2}} |q_{rej}\rangle$.
  This is observed. Two outcomes are possible. With probability
  $(1/\sqrt{2})^2=1/2$, a rejecting state is observed.
  Then, the superposition collapses to $|q_{rej}\rangle$,
  the word is rejected and the computation terminates.
  Otherwise (with probability $1/2$), a non-halting state is observed and the
  superposition collapses to $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$.
  In this case, the computation continues.
  Read "a" again. A simple computation (we leave the details out)
  shows that $\frac{1}{2} |q_0\rangle+\frac{1}{2} |q_1\rangle$ is mapped
  to itself by $V_a$.
  After that, a non-halting state is observed. (There are no
  accepting or rejecting states in this superposition.)
  Read final symbol \$. The transformation $V_{\$}$ corresponding
  to the right endmarker $\$$ is done. It maps
  the superposition to $\frac{1}{2} |q_{rej}\rangle+\frac{1}{2} |q_{acc}\rangle$.
  This is observed. With probability $(1/2)^2=1/4$, the rejecting state $q_{rej}$
  is observed. With probability $1/4$, the accepting state $q_{acc}$ is observed.

  The total probability of accepting is $1/4$, the probability
  of rejecting is $1/2+1/4=3/4$.


Barriers and Monotone Circuit Complexity

Benjamin Rossman's recent paper summarises the state of the art for the monotone circuit complexity of k-CLIQUE.  In short, Razborov proved a lower bound in 1985, later improved by Alon and Boppana in 1987: $\omega(n^k/(\log n)^k)$, versus the brute force upper bound $O(n^k)$.

Rossman shows a lower bound of $\omega(n^{k/4})$ for the average-case complexity in the Erdős-Rényi model of random graphs; Amano previously showed this was essentially also the upper bound.  The quasi-sunflower lemma that forms a key part of the paper is rather neat.

So the natural proofs barrier does not seem to apply to monotone circuit complexity.

Norbert Blum has discussed why lower bounds for monotone circuits are essentially different from circuits with negations.  The key observation of Éva Tardos is that a small modification of the Lovász theta function has exponential monotone circuit complexity.

Benjamin Rossman, The Monotone Complexity of k-Clique on Random Graphs, FOCS 2010.
Norbert Blum, On Negations in Boolean Networks, LNCS 5760, 18–29, 2009.
É. Tardos, The Gap Between Monotone and Non-Monotone Circuit Complexity is Exponential, Combinatorica 8, 141–142, 1987.  doi:10.1007/BF02122563


Most efficient way to convert an $\text{AC}^0$ circuit to a circuit  (of any depth) with gate fanout 1

I will try to summarize my previous comments.

Let us first ignore the fact that your original circuit has (constant) depth $k$; just assume it has size $S$. Let $A$ be the smallest number such that every unbounded fanin circuit size $S$ can be transformed into an unbounded fanin formula $F$ of size $O(S^A)$. I claim that the best we can do so far is to achieve $A=O(S/\log^2 S)$. Say, it is even not known whether whether any (fanin-2) circuit of size $S=O(n)$ can be simulated by a formula of size smaller than $\exp(n/\log n)$.

To show the claim, we transform the formula $F$ into a fanin-2 formula $F′$ of size $M=O(S^{2A})$. It is well known that the depth $D$ of every formula $F′$ can be made logarithmic in its size, that is $D=O(\log M)=O(A\log S)$. [This was first shown by Khrapchenko 1968, and then the constant under big-O was improved to $D\leq 1.73\log_2M$ by several authors.] On the other hand, the best known result for fanin-2 circuits [Paterson and Valiant, TCS 2(3), 397-400] says that $Depth=O(Size/\log Size)$. Thus, having a simulation with $A$ much smaller than $S/\log^2 S$ would improve the best known Size-Depth simulation for circuits.

This, however, is only a "word of caution" - it does not answer your question because you assume that your original circuit has constant depth $k$, implying that in this case we can just take $A=k$ (or $A=k−1$ if we have a single output gate). The power of Paterson-Valiant simulation is that it applies to arbitrary, even very unbalanced circuits whose depth is almost the entire size! But in your bounded-depth setting, even the case $k=3$ is not clear: can every depth-3 circuit of size $S$ be transformed into a depth-3 formula of size much smaller than $S^2$? I guess the answer should be "no" (could be an interesting exercise for students). A depth-3 formula is just a big OR of CNFs. The question is to find an OR of CNFs that share many clauses in common, but otherwise are "very different" to force a large depth-3 formula.

The problem is that we want to obtain a formula (a fanout-1 circuit). As was pointed above, allowing gates of fanout-2 makes simulation simpler: Hoover, Klawe and Pippenger [JACM 31(1), 1980] show that any fanin-2 circuit of size $S$ and depth $D$ has an equivalent fanin-2 and fanout-2 circuit of size $3S−2n$ and depth $2D$. Thus, if fanin is unbounded, then the resulting circuit will have size $O(S^2)$ and depth $O(D\log S)$.

There is yet another result somehow related to your question. Lozhkin (1981) proved that if a boolean function $f$ can be computed by an $AC^0$ formula of depth $k$ and size $S$, then $f$ can be computed by fanin-2 formula of depth $D\leq k-1+\lceil\log_2S\rceil$ (this follows from Theorem 6.2 in my book). Note that a trivial upper bound would only be $D\leq k\log S$ (if we would simulate each single gate by a tree of depth $\log S$).


Major conjectures used to prove complexity lower bounds?

The unique games conjecture has recently been one of the most fruitful assumptions for proving good lower bounds, although it is more controversial than most assumptions about complexity class separation.  See On the Unique Games Conjecture for a list of consequences.


Reference for fundamental theorem on tree rotations

An early paper that made this observation explicitly -- that rotations preserve inorder traversals -- is (in Figure 2 of) Sleator and Tarjan's 1983 Self-adjusting binary search trees.  The move-to-root heuristic was studied in Allen and Munro's 1978 Self-Organizing Binary Search Trees paper.


Efficient way to generate random planar cubic bipartite graphs

Would you be satisfied with generating planar cubic bipartite maps (i.e., such graphs equipped with a planar embedding specified by a cyclic ordering on half-edges)? That problem was addressed in:

Gilles Schaeffer, Bijective Census and Random Generation of Eulerian Planar Maps with Prescribed Vertex Degrees, The Electronic Journal of Combinatorics 4(1), 1997.

Schaeffer describes how to efficiently generate (rooted) Eulerian planar maps uniformly at random using a bijection with a certain family of trees. In turn, Eulerian maps have a simple bijection with bi(partite-)cubic maps: see the second bullet point on slide 5 of this talk by Éric Fusy.

(Generating a uniformly random rooted planar bicubic map and then throwing away the rooting + embedding would give you a non-uniform distribution on planar bicubic graphs, but depending on what you have in mind that might be okay?)


NP hard proving: separate graph into a set of the same size disjoint parts by maximizing the shared neighbours of each part

You can notice that $SN_i$ is maximum if $P_i$ is a clique of size $|P_i|$.

So the decision version of your problem is very similar to the CLIQUE PARTITION PROBLEM which is NP-complete, the only difference is that you require that all parts $P_i$ have the same size.

But the problem of partitioning a graph into 3 cliques of the same size is still NP-complete.

Indeed 3-COLORING remains NP-complete even if we require that all color classes have the same size (I'll call it EQUAL SIZE 3-COLORING). A quick proof idea is: given $G$ make 3 copies of it $G_1, G_2, G_3$, pick the same node $v$ in each copy of $G$: ($v_1, v_2, v_3 $) and "link" them to form a clique $K_3$. $G$ is 3 colorable if and only if $G' = G_1 \cup G_2 \cup G_3 \cup K_3$ is 3 colorable with equal size color classes.

But EQUAL SIZE 3-COLORING a graph $G$ with $3n$ nodes is equivalent to find 3 cliques of size $n$ in its dual $\bar G$. Which is also equivalent to partition $\bar G$ into 3 parts with a total sum $\sum SN_i = 3n$


What to do as a Theoretical computer science PhD student in a free time?

I strongly agree with other comments that over-optimizing your time is not healthy and your brain needs downtime, preferably social interaction or physical exercise. However, if you feel you have that covered, what I think separates good from great researchers, is having an overarching vision; a generic direction, or specific goal to strive to. To see the forest for the trees, if you will.

One way to achieve this, is to reflect in those moments of spare time; to philosophize very generically on society and identify problems in it. This can range from wicked problems like climate change and inequality, to more practical problems like cybersecurity (e.g. Heartbleed) and software safety (e.g. the Toyota incidents). Don't worry about staying inside your field if things fascinate you. Read widely to find interests. Read popular media, popular science writing, quality newspapers and see what other people worry about. Read the solutions that are being proposed, evaluate their feasibility, and think hard to come up with better ones. Better ideas can make all the difference. For example, the Rust language is tackling the security and software safety issues commonly found in C infrastructure, the Julia language is focused on solving the two language problem in scientific computing and improving the state of the art in data science and machine learning, while Elon Musk's Tesla is aiming to accelerate the advent of sustainable energy in order to counter climate change. Each of these admirable projects started with good research ideas, by people committed to a higher level ideal. Finding your higher level ideal is what you should focus on.

A higher level goal will motivate you to get up in the morning, shape your career in a given direction and give you a sense of purpose and satisfaction. Most likely it is not something you'll settle on in a single afternoon. It is something that requires plenty of reflection, that can shift as your knowledge of the world shifts, changes as your priorities change. If you're ambitious, a good question to ask is "What will have the greatest positive impact on the largest amount of people?". Go crazy, get creative and consider scifi: "Maybe I should solve the inequality problem by writing a Decentralized Autonomous Organisation on Ethereum that unconditionally distributes a Global Basic Income to all." If, however, you are somewhat more realistically inclined, you might just choose to work on Blockchain tech because you believe in its huge potential for leveraging social benefit.

Maybe you are satisfied with something lower profile, that concerns you more directly, which is perfectly fine. What matters is that you find it valuable and worth spending your time on. These are the same principles successful entrepreneurs use to identify possible projects; two considerations are "Am I passionate about this?" and "What's the benefit to society?" The greater the benefit to society, the greater the market for it will be. A great researcher understands this, and chooses to accumulate expertise towards solving a general, overarching problem in his domain. This will have the largest impact both on his career, as well as society. Whatever you do, don't think a paper at a time, but see papers as building blocks towards an end, and take control of where you're going.


Is it possible to generate a collision free hash function from an equality function?

Question 1: Can I write a function $f$ with the type
  $\forall\alpha,\;(\alpha\to\alpha\to\mathbb{B})\to(\alpha\to t)$
  such that $f\;e$ is an injection for
  all equivalence relations $e$?

The answer is negative. Neel Krishnaswami noticed that $f\;(=_{t'})$ is an injection only if $|t'|\le|t|$, which is not the case when $t'$ is $t\to\mathbb{B}$. Tsuyoshi Ito noticed that an even stronger statment must be true: $f\;e$ is a constant function.

Here is a proof that was shown to me by Rasmus Petersen. Go to the free theorem generator and type in "(a->a->Bool)->(a->Integer)". (The last type is Integer instead of $t$ so that the website knows that it is a type, not a type variable.) The free theorem for this type is $$\forall t\,t'\,\forall R\,\forall p\,p',\;\bigl(\forall (x,x')\,(y,y'),\;p\;x\;y=p'\;x'\;y'\bigr)\Rightarrow\bigl(\forall (x,x'),\;f\;p\;x=f\;p'\;x'\bigr).$$ Here, $t$ and $t'$ are types; $R$ is a relation on these types; (in our case) $p$ and $p'$ are equivalence relations on $t$ and, respectively, $t'$; and we have $xRx'$ and $yRy'$. We now pick a relation $R$ such that the premise is satisfied and the right hand side of the conclusion reduces to a constant: $R=\{(x,())\}$, where $x$ is some fixed but arbitrary element of $t$, and $t'=\mathbb{U}=\{()\}$ is the unit type. $$f\;p\;x=f\;(=_\mathbb{U})\;()$$

Q.E.D. The notes I posted in a comment contain a longer proof, and more explanations.

  Question 2: Can I implement it if $f$
  keeps some state?

Neel's observation still holds. You can't.

  Question 3: Huh? But I did implement
  a version that works slow!

First, I believe your implementation is not polymorphic.
Second, and more important, even if there is no injection from $\mathbb{Z}\to\mathbb{B}$ to $\mathbb{Z}$, there is one from the elements of $\mathbb{Z}\to\mathbb{B}$ that your program constructs in some finite time.

(If you give up polymorphism but not state, then there is a way to find a counterexample to any potential implementation. I learned this from Paulo Oliva, but I don't know how yet.)

  Question 4: That's all good and
  theoretical. Can you also tell me
  something actually helps me write my
  program?

After all those impossibility results, I think it's reasonable to settle for the question: "How do I implement a hash function without collisions for some given type $t$?'' The standard solution is hash-consing, a technique first described by Ershov in 1957 (in Russian, and in 1958 in English) that should be much better known than it is.

If the equivalence relation is (reference) equality, then there is a very simple hash: Just take the address of the object. So we can recast the problem as follows: "How do we ensure that we build at most one element from each equivalence class?" Let's use structural equality as equivalence relation. If we want to build an object whose parts are $x_1,\ldots,x_n$ we call $\mathit{mk}\;x_1\ldots x_n$. In that function, we first lookup the tuple $(x_1,\ldots,x_n)$ in a dictionary and, if a value is found, we return it. (Since $x_1,\ldots,x_n$ were built before, they are class representatives.) Otherwise, we construct a new data structure.

For a different equivalence relation you need to adapt hash-consing, exploiting properties of your particular equivalence.

The implementation is a bit trickier than this description might suggest. Some (hidden) test data is here.

PS: I mentioned some people from which I learned some parts of the answer. Naturally, if those parts are wrong, it is likely I misunderstood what I've been told.


Is there a typed lambda calculus which is consistent and Turing complete?

Alright I'll give a crack at it: In general for a given type system $T$, the following is true:

  If all well-type terms in the calculus $T$ are normalizing, then $T$ is consistent when viewed as a logic.

The proof generally proceeds by assuming you have a term $\mathrm{absurd}$ of type $\mathrm{False}$, using subject reduction to get a normal form, and then proceeding by induction on the structure of such a term to get a contradiction.

It is natural to wonder if the converse holds, i.e.

  For any type system $T$, if $T$ is logically consistent, then every well-typed term in $T$ is normalizing.

The problem with this is that there is no real most general notion of "type system", and even less agreement on the meaning of logical consistency for such systems. However, we can empirically verify that

  For most known type systems which have a logical interpretation, the converse does indeed hold.

How does this tie into Turing Completeness? Well, for one, if type-checking is decidable, then Andrej's argument shows that one of the following must hold:

The set of all well-typed programs is not Turing Complete.
There is a non-terminating well typed program.

This tends to suggest that:

  Type systems which have a logical interpretation and are consistent and are recursively enumerable are not Turing Complete.

Giving an actual theorem rather than a suggestion requires making the notion of type systems and logical interpretations mathematically precise.

Now two remarks come to mind:

There is an undecidable type system, the intersection type system which has a logical interpretation and can represent every normalizing $\lambda$-term. As you remark, this isn't quite the same as being Turing Complete, as the type of a total function may need to be updated (refined, in fact) before applying it to the desired argument. The calculus is a "curry style" calculus and is equal to STLC +
$$ \frac{\Gamma\vdash M:\tau\quad \Gamma\vdash M:\sigma}{\Gamma\vdash M:\tau\cap\sigma} $$
and
$$\frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\tau}\quad \frac{\Gamma\vdash M:\tau\cap\sigma}{\Gamma\vdash M:\sigma}$$
It is clear that the "interpretation" $\cap=\wedge$ leads to a consistent logical interpretation.
There is a class of type systems, the Pure Type Systems, in which such a question might be made precise. In this framework however, the logical interpretation is less clear. One might be tempted to say: "a PTS is consistent if it has an uninhabited type". But this doesn't work, since types may live in different "universes", where some might be consistent and some not.
Coquand and Herbelin define a notion of Logical Pure Type Systems, in which the question makes sense, and show

  Every inconsistent, non-dependent LPTS has a looping combinator (and so is Turing Complete)

Which answers the question in one direction (inconsistent $\Rightarrow$ TC) in this case. As far as I know, the question for general LPTS is still open and quite difficult.

Edit: The converse of the Coquand-Herbelin result is not as easy as I thought! Here is what I came up with so far.

A Logical Pure Type System is a PTS with (at least) the sorts $\mathrm{Prop}$ and $\mathrm{Type}$, (at least) the axiom $\mathrm{Prop}:\mathrm{Type}$ and (at least) the rule $(\mathrm{Prop},\mathrm{Prop},\mathrm{Prop})$, with the further requirement that there are no sorts of type $\mathrm{Prop}$.

Now I'm going to assume a particular statement of Turing Completeness: fix an LPTS $L$ and let $\Gamma$ be the context

$$ \Gamma = \mathrm{nat}:\mathrm{Prop},\ 0:\mathrm{nat},\ S:\mathrm{nat}\rightarrow \mathrm{nat}$$

$L$ is Turing Complete iff for every total computable function $f:\mathbb{N}\rightarrow\mathbb{N}$ there is a term $t_f$ such that
$$ \Gamma \vdash t_f : \mathrm{nat}\rightarrow \mathrm{nat}$$
and for every $n\in\mathbb{N}$
$$ t_f\ (S^n\ 0)\rightarrow^*_{\beta} S^{f(n)}\ 0$$

Now Andrej's diagonalization argument shows that there are non-terminating $t$ of type $\mathrm{nat}$.

Now it seems like we are half-way there! Given a non terminating term $\Gamma \vdash \mathrm{loop}:\mathrm{nat}$, we want to replace occurrences of $\mathrm{nat}$ by some generic type $A$ and get rid of $0$ and $S$ in $\Gamma$, and we will have our inconsistency ($A$ is inhabited in the context $A:\mathrm{Prop}$)!

Unfortunately this is where I get stuck, since it is easy to replace $S$ by the identity, but the $0$ is much harder to get rid of. Ideally we would like to use some Kleene recursion theorem, but I haven't figured this out yet.


What's the complexity of factoring over a set of generators (say in $GL_2$)?

This is usually called the (constructive) membership problem (rather than a "factorization" problem). The membership problem is to decide whether $C \in \langle A,B \rangle$; the constructive membership problem is to actually find a word (if any) in $A,B$ that equals $C$.

Its complexity may depend on whether you want to allow $A^{-1}, B^{-1}$ in your word (in which case it is the membership problem for a subgroup of a general linear group) or not (in which case it is the membership problem for a submonoid or subsemigroup of a general linear group).

I don't know a complete answer to your question, but here are some special cases and hopefully relevant references:

In general, the membership problem in linear groups over infinite fields is undecidable [Mihailova, 1968]. I do not know whether undecidability holds for the case of 2-generated subgroups.
The Tits alternative implies that the group generated by $A,B$ is either solvable-by-finite, or contains a nonabelian free group. The intro of Eick-Kirschmer-Leedham-Green contains pointers to algorithms that solve the Tits alternative for subgroup of $GL_n(\mathbb{Q})$, in the sense of deciding which of the two cases holds.
In the solvable-by-finite case, the membership problem is decidable [Kopytov, 1968].
In the free case less is known. Eick, Kirschmer, and Leedham-Green ("The constructive membership problem for discrete free subgroups of rank 2 of $SL_2(\mathbb{R})$") give an efficient-in-practice algorithm for 2-generated subgroups of $SL_2(\mathbb{R})$ that are not only free but also discrete.
If $A,B$ commute, then Cai-Lipton-Zalcstein [FOCS 1994] show how to solve even the constructive subsemigroup membership problem in P. If $A,B$ don't commute, it's not even clear to me whether your problem is in NP, as it's not obvious to me that the desired word is polynomial-length nor has a polynomial-length description.
See also the final report of a 2014 Banff workshop on algorithms for linear groups.

(PS - If by "falls under Ladner's theorem" you mean "is likely to be NP-intermediate" (in the sense of being in NP but neither being in P nor being NP-complete), that's an unusual phrase, but I know what you meant. But, in case you're not aware, essentially no natural problem is known to have this status, even under standard complexity assumptions (such as PH not collapsing). See here for a list of natural problems that are currently candidates for being NP-intermediate.)


Finding out a set by intersection comparison

This is a variation of the famous puzzle of finding a counterfeit coin by using the balance.  But before proceeding to that, first let’s solve the question, because the technique in solving it is also useful to see the connection to the counterfeit coin problem.

First, suppose that the query sets A and B do not have to be from the family F.  Then you can find the set S by at most $\binom{n}{2}=O(n^2)$ queries as follows.  Make $\binom{n}{2}$ queries ({a}, {b}) for 1≤a<b≤n.  Note that every element i∈{1,…,n} is used in n−1 queries.  If an element i belongs to S, then the set {i} is answered at least when the opponent does not belong to S, and therefore the set {i} is answered at least n−t times.  If an element i does not belong to S, then the set {i} cannot be answered if the opponent belongs to S, and therefore the set {i} is answered at most n−t−1 times.  Therefore, counting how many times each set is answered, we can determine the whole set S.

This requires query sets not from the family F, which is not allowed in the problem.  But we can work around this by adding the same t−1 elements to both sides.  For example, instead of making the query ({1}, {2}), we can make the query ({1,3,4,…,t+1}, {2,3,4,…,t+1}).  Therefore, the problem can be solved by O(n2) queries.

Now fun part begins.  Consider n coins labeled 1,…,n, and t of them are counterfeits and slightly heavier than the real coins.  All the counterfeit coins have the same weights.  You have to find the set S of the labels of the t counterfeit coins by using a balance only poly(n) times.  Every time you use a balance, you can put at most min{t, n−t} coins to each side of the balance.  The balance is slightly inaccurate in the sense that if the two sides have the same weight, either side can go down (adversarially).  As I hope that you can see by now, this is exactly the same problem as the question.

Edit: Revision 4 and earlier had one error or another (oops) in the precise connection to the counterfeit coin puzzle.


Is equivalence of unambiguous context-free languages decidable?

This is currently an open problem.
As correctly pointed out, if it is decidable, then one expects the proof to be hard since it generalises the famous DPDA equivalence problem.
On the other hand, the classical arguments for undecidability of the CFL universality problem make use of inherently ambiguous languages, and thus one needs new ideas to show undecidability.

Let me point out that the universality problem for UCFLs is decidable (in PSPACE), using generating functions [1].

REFERENCES

[1] N. Chomsky and M. P. Schützenberger, The Algebraic Theory of Context-Free Languages, Computer Programming and Formal Systems, 1963.


Under what conditions is the Dining Philosophers Problem unsolvable?

Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must occur: Whenever one (Aristotle) picks up the left fork then the philosopher on the right (Beauvoir) takes Aristotle's right fork.

If you allow access to a source of randomness this should be easily fixable, however (everyone eats for a short time when possible and waits for a long, random, time thereafter).


If possible, find a survey, book, or a lecture note. This will help a lot to see the jungle through the trees! To find books, Google Books is your friend. Search the keywords in the Google Books, and try to find a relevant book on the subject.
Take the top-down / bottom-up approach, and alternate. That is, read the most recent papers first (the top research), and references thereof (bottom). Why? Because the top research is likely to be better, and has probably surveyed bottom works and improved them. However, to understand top, it is usually the case that you need to skim the bottom works. Important: Don't get stuck at the bottom. After reviewing older works, take the bottom-up approach. Finally, alternate between the top-down and bottom-up approaches.
Don't read a paper unless you are somehow sure that it is really relevant. The relevancy depends on several factors: The amount of citations, the fame of authors, the conference/journal it is published in, and so on.
Be sure to read the title and abstract carefully, and skim the sections. Decide if you should ever read this paper now, and to what extent.
If a paper has a conference version and a journal (full) version, select the first one. The conference version usually gives the general idea, and avoids cumbersome proofs. Read the full version only when you really need to learn the proof details/technique.

Edit 1: Some of my colleagues use reference manager tools like Zotero to help them organize their references. I'm not acquainted with such tools, but I think you should give it a go.


What is the name of this algorithm on direct acyclic graph?

Looks to me like some additional restrictions on a topological sort: https://en.m.wikipedia.org/wiki/Topological_sorting .
Also git already supports this operation for instance git rev-list --topo-order .


What is the descriptive complexity of the basic modal logic?

Modal logic does not capture any interesting complexity class. As it is invariant under bisimulation, it cannot even test whether the vertex $w$ has degree greater than $2$, which is a constant time property. We are interested in ML for a different reason: ML is the bisimulation invariant fragment of first-order logic (Theorem of van Benthem). In other words, ML is the "first-order logic of process behaviour". Similarly, the bisimulation invariant fragment of monadic second-order logic is the $\mu$-calculus (Theorem of Janin/Walukiewicz).


Lower bounds for the size of nondeterministic circuits

A partial answer to the second question:

exponential lower bounds for explicit functions for any class that contains 3-CNF do not translate into exponential lower bounds for unlimited nondeterminism, because one can transform any circuit of size $S$ into a nondeterministic 3-CNF of size $O(S)$ with non-determinism $S$,
even if you want non-determinism less than S, this is still doable if the function is computed by a $B_2$ formula (for example, parity), because one can split this formula of size $S$ into, say, $S/100$ pieces introducing $S/100$ new variables, and the resulting formula will be $O(S)$ size (though the constant in the $O()$ will be large),
for limited (but growing) nondeterminism one can, of course, use good old bounds (for example, Hastad's exponential lower bound $2^{n^{1/d}}$ for parity remains exponential if the nondeterminism is much less than $n^{1/d}$: just enumerate all possible bits for the nondeterminism and take a big OR of the resulting formulas).

A partial answer to the first question:

not known to me :) it would be interesting to see the proof (in particular, how can you substitute values for the existential variables).


Nested automatization of type inference of forall elimination

This can be solved as easily as the other problem, as in this solution. It's basically unification.

Ensure that the variables $X_1,\ldots,X_n$ do not appear in $V$. Replace
any variables that do by fresh ones and perform appropriate substitution into $W$.
Unify $V$ and $W$ using an algorithm that finds the most general unifier (mgu). The essence of this is in the other algorithm, or, for example, page 10 of this.
The resulting mgu $[\bar{X}/\bar{W}]$ is the subtitution you require.


Original reference for Huffman shaped Merge Sort?

I found the result hidden in an obscure 4p technical report: I share my results here in case others are interested.

Knuth mentions runs in his description of "natural merge sort" (page 160 of the tome 3 of the 3rd edition), but he analyzes its complexity only on average (which yields n/2 runs), not in function of the number ρ of runs
in 1985, Mannila proved that Natural Mergesort takes time within O(n(1+lg(r+1))) to sort n elements forming r runs.
in 1996, Tadao Takaoka (http://dblp.uni-trier.de/pers/hd/t/Takaoka:Tadao) introduced the notion of the entropy of the distribution of the sizes (n1,…,nρ) of the runs in an tech report  4 pages article titled "Minimal MergeSort", and proved a complexity of $n(1+2H(n1,…,nρ))$ comparisons
in 2009, the technique was presented at the symposium Mathematical Fundation of Computer Science (along with results on sorting, shortest paths and minimum spanning trees).
in 2010, it was published  in the  journal of Information Processing under the title "Entropy as Computational Complexity", with an added co-author, Yuji Nakagawa (https://www.semanticscholar.org/author/Yuji-Nakagawa/2219943).

I join the bibtex references below.

@TechReport{1997-TR-MinimalMergesort-Takaoka,
  author =   {Tadao Takaoka},
  title =    {Minimal Mergesort},
  institution =  {University of Canterbury},
  year =     1997,
  note =     {http://ir.canterbury.ac.nz/handle/10092/9676, last accessed [2016-08-23 Tue]},
  abstract =     {We present a new adaptive sorting algorithm, called minimal merge sort, which merges the ascending runs in the input list from shorter to longer, that is, merging the shortest two lists each time. We show that this algorithm is optimal with respect to the new measure of presortedness, called entropy.}
}

@InProceedings{2009-Chapter-PartialSolutionAndEntropy-Takaoka,
author="Takaoka, Tadao",
editor="Kr{\'a}lovi{\v{c}}, Rastislav
and Niwi{\'{n}}ski, Damian",
title="Partial Solution and Entropy",
bookTitle="Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings",
year="2009",
publisher="Springer Berlin Heidelberg",
address="Berlin, Heidelberg",
pages="700--711",
isbn="978-3-642-03816-7",
doi="10.1007/978-3-642-03816-7_59",
url="http://dx.doi.org/10.1007/978-3-642-03816-7_59",
abstract = {If the given problem instance is partially solved, we want to minimize our effort to solve the problem using that information. In this paper we introduce the measure of entropy H(S) for uncertainty in partially solved input data S(X) = (X 1, ..., X k ), where X is the entire data set, and each X i is already solved. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sorting X i is an ascending run, and for shortest paths, X i is an acyclic part in the given graph. For minimum spanning trees, X i is interpreted as a partially obtained minimum spanning tree for a subgraph. The entropy measure, H(S), is defined by regarding p i  = |X i |/|X| as a probability measure, that is, H(S)=−nΣki=1pilogpi, where n=Σki=1|Xi|. Then we show that we can sort the input data S(X) in O(H(S)) time, and solve the shortest path problem in O(m + H(S)) time where m is the number of edges of the graph. Finally we show that the minimum spanning tree is computed in O(m + H(S)) time.}
}

@article{2010-JIP-EntropyAsComputationalComplexity-TakaokaNakagawa,
  author    = {Tadao Takaoka and
               Yuji Nakagawa},
  title     = {Entropy as Computational Complexity},
  journal   = jip,
  volume    = {18},
  pages     = {227--241},
  year      = {2010},
  url       = {http://dx.doi.org/10.2197/ipsjjip.18.227},
  doi       = {10.2197/ipsjjip.18.227},
  timestamp = {Wed, 14 Sep 2011 13:30:52 +0200},
  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jip/TakaokaN10},
  bibsource = {dblp computer science bibliography, http://dblp.org},
  abstract = {If the given problem instance is partially solved, we want to minimize our effort to solve the problem using that information. In this paper we introduce the measure of entropy, H (S), for uncertainty in partially solved input data S (X) = (X1, . . . , Xk), where X is the entire data set, and each Xi is already solved. We propose a generic algorithm that merges Xi's repeatedly, and finishes when k becomes 1. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sorting Xi is an ascending run, and for minimum spanning trees, Xi is interpreted as a partially obtained minimum spanning tree for a subgraph. For shortest paths, Xi is an acyclic part in the given graph. When k is small, the graph can be regarded as nearly acyclic. The entropy measure, H (S), is defined by regarding pi = ¦Xi¦/¦X¦ as a probability measure, that is, H (S) = -n (p1 log p1 + . . . + pk log pk), where n = ¦X1¦ + . . . + ¦Xk¦. We show that we can sort the input data S (X) in O (H (S)) time, and that we can complete the minimum cost spanning tree in O (m + H (S)) time, where m in the number of edges. Then we solve the shortest path problem in O (m + H (S)) time. Finally we define dual entropy on the partitioning process, whereby we give the time bounds on a generic quicksort and the shortest path problem for another kind of nearly acyclic graphs.}
}


Building a decision tree to approximate a known function (not to learn an unknown function)

For bitstring to boolean functions, people usually build binary decision diagrams instead of decision trees to represent functions compactly. If you want to find a small BDD and are willing to sacrifice correctness on a few inputs (as your question implies) then you might want to look into approximate BDDs as studied in the following two papers:

Hinsberger, U., Kolla, R., and Kunjan, T. [1997] "Approximative Representation of boolean Functions by size controllable ROBDD's"

Ravi, K., McMillan, K.L., Shiple, T.R., and Somenzi, F. [1998] "Approximation and decomposition of binary decision diagrams"

I am not sure if there is work that generalizes this for $\mathbb{R}^d \supset \mathbb{D}  \rightarrow \{0,1\}$ functions, but I would use those papers as a starting point and do a forward-reference search.


An algorithm for counting to Graham’s Number

With only a polynomial amount of memory, a program that terminates can run for at most exponential time. This is because there are only exponentially many states (i.e. a combination of tape content (exponential), Turing machine state (constant) and position of the head over the tape (polynomial)). Thus any machine that runs for more than exponential time would have to visit some state more than once and hence loop.

In general, to get a program to run for $T(n)$ time you need $\Omega(\log(T(n)))$ memory.


The simple proof of uniqueness of solution for The tower of Hanoi problem

Without knowing the proof you mention or being very formal, I'd go for the combined one below.

With induction: For the case $n=1$, it is easy to see that you need at least one step to do anything and if you enumerate the possible steps you'll get that there is precisely one step that moves the tower to the right place.

For the case $n=m+1$, for some $m\ge 1$, looking at the bottom stone it is clear that it can only be moved after all others are moved elsewhere first. To move the bottom stone there are two options, one of which puts it where it needs to be in the end, but in both cases it can only move if the target "site" is empty. This leaves only one place for all the other stones to be, and by the rules of the game they have to be in order and thus form a tower. This means the top has to be moved as a whole from one place to another. So in both cases the smallest number of moves is the smallest number of moves to move the top (of size $m$) completely, which is $2^m-1$ and unique by induction, plus $1$ for the bottom stone, giving $2^m$ so far.

Now we are left with two cases. For the one where the bottom stone is already in place, we have a tower of size m elsewhere that needs to be moved on top of it. Moving the bottom stone itself either gives use a previous state or the same state as the following case and these paths can therefore not be minimal. To move the top we know, again by induction, that the smallest number of moves is $2^m-1$ and that the moves are unique. The total number of moves in this case therefore is $2^m+2^m-1=2^{(m+1)}-1=2^n-1$.

In the other case we know that we still have to move the bottom stone to the right place and in fact we can easily see that the current case is effectively the same as the situation before the bottom stone was moved there (but after the top was moved). The last move being superfluous means this path cannot lead to a minimal number of moves. This leaves the previous case as the only suitable case.


You can generalize the standard algorithm for enumerating Hamming numbers in increasing order by merging with a min-heap. The Hamming numbers are the numbers expressible with primes 2, 3 and 5.

If you can enumerate the expressible numbers in order, the non-expressible numbers are easily found in the successive gaps. To solve the problem for an interval [i, j], find the greatest expressible number less than i and the least expressible number greater than j, and use that to initialize and terminate the algorithm.

Edit: I forgot to mention how you might efficiently find the bounds for the interval problem. Modified bisection should work. You have an exponent sequence as your current guess. For each individual exponent split the difference as in bisection, yielding n variants, and then find the numerically smallest of the variants (or the largest, depending on whether you're searching for lower or upper bounds), and use that as your next guess.

  I don't know if it's important that the set be a list of primes, but I'll keep it in there just in case.

No, it doesn't matter. If you use the algorithm I suggested, the effect of allowing composites is that you generate duplicates when unique factorization fails; this happens when two or more numbers in the generating set aren't relatively prime. For generators 2 and 4, the sequence goes

1 = 2^0 4^0, 2 = 2^1 4^0, 4 = 2^2 4^0, 4 = 2^0 4^1, ...

Any duplicates will occur in contiguous runs, so they are easily filtered out without keeping a black list. You could also kill them upon insertion in the min-heap.


Is Clique completion for intersection models hard?

Good question. I hope this is not a homework problem.

I don't know if this problems exists in the literature, so let's call your problem Min Set Clique Completion Problem (MSCC). Here is a reduction from Hitting Set Problem to MSCC. Hitting Set problem is a well-known NP-complete problem.

Instance of Hitting Set problem is as follows : Let $U = \{1,2,\dots,n\}$ be the ground set. Let $T_1, T_2, \dots, T_l$ be $l$ subsets of $U$. Find a set $H \subseteq U$ that has at least one element from each set $T_i$. The goal is to minimize $|H|$.

We construct an instance of MSCC with $U' = U \cup \{n+1\}$ and sets $S_1, S_2, \dots, S_{l+1}$ such that for $1 \leq i \leq l$, $S_i = T_i \cup \{n+1\}$ and $S_{l+1}$ is an empty set. (Edit : this is wrong as pointed out in the comment.)
We construct an instance of MSCC with $U' = U$ and sets $S_1, S_2, \dots, S_{l+1}$ such that for $1 \leq i \leq l$, $S_i = T_i$ and $S_{l+1}$ is an empty set (Edit : Use this along with Karolina's fix in the comments).

Now if we run MSCC on this instance the solution $S_{l+1}$ returned by MSCC is precisely the hitting set of the sets $T_1, T_2, \dots, T_l$.


Consider the polynomial $p(t) = \prod_{i=1}^n (s_i t + 1)$. Then we want to compute the coefficient of $t^k$ in $p(t)$. We can compute $p(t)$ using fast polynomial multiplication and then output the coefficient of $t^k$.

Say, partition $n$ polynomials $s_i t + 1$ into pairs and multiply the product of polynomials in each pair (using the standard fast polynomial multiplication algorithm). Then divide the obtained $n/2$ polynomials into pairs, and compute the product in each pair. Repeat this step over and over until we get one polynomial. At each step we can get rid of terms of degree higher than $k$.

Also note that if $k$ is small, we can just use dynamic programming.


Applications of HHL's algorithm for solving linear equations

If by "classically using the solutions of the linear equation" you mean "accessing the information in the exactly same way a classical computer does" or, in other words, "obtaining the classical solution $x$ to a system $Ax=b$" then the answer is no. As you mention, the final quantum state  in Harrow, Hassidim, Lloyd's algorithm does not immediately give you the classical solution $x$ of the system but a quantum states that encodes $x$ in its amplitudes; it is hard to extract the "explicit information" $x$ from that state.

However there are indeed interesting applications of the HHL linear systems algorithm as a subroutine to solve other problems, using the output of the quantum algorithm in "more quantum" ways.

The HHL algorithm can be readily applied to compute expectation values
$\langle x| M | x \rangle$ of a poly-size Hermitian operator $M$.
Dominic Berry gave a generalized version of hte HHL algorithm to solve linear systems of the differential equations. The HHL algorithm is used as a subroutine there. (Berry's algorithm uses HHL's as a subroutine.) The final solution of Berry's algorithm is also encoded in the amplitudes of a quantum state.
Wiebe, Braun, Lloyd  gave an algorithm based on HHL's that can be used to find the optimal least-square fit to some discrete data. Although the output of that algorithm is again encoded in some quantum amplitudes, the authors also gave a quantum algorithm to asses the quality of an optimal least-square fit in a quantum computer, and there the output is classical. For certain types of fit functions, their quantum algorithm outperforms classical ones.
Recently, HHL's algorithm has been employed in Lloyd-Mohseni-Rebentrost's quantum algorithm for machine learning.

Note that, in all of these algorithms,   quantum manipulations of the output state of the HHL's algorithm are performed, instead of classical ones. This is similar to the case of the quantum Fourier transform (QFT), which can be computed exponentially faster in a quantum computer as a quantum gate than the classical discrete Fourier transform. We cannot use this fact in quantum algorithms to Fourier-transform classical functions faster. However, the QFT has remarkable applications in Shor's factoring algorithm and quantum phase estimation.


Finding optimal subset for quadratic function

For all $\beta_i = 0$, asking whether one can get objective function value $1$ is equivalent to Subset Sum, and therefore NP-complete. Simple reductions from Subset Sum also prove that it is NP-complete to approximate the objective function within any factor polynomial in $n$.

We can reduce the $\beta_i = 0$ case to the case where $\beta_i = 1$ by just setting all $\beta_i$ values to $1$ and scaling both $\lambda$ and all $\alpha_i$'s by the same (large) integer factor. Then the $\beta_i$'s dont affect the objective function significantly anyway.

On the other hand, if all the integers $\alpha_i$ are small, one can solve the problem in pseudo-polynomial time - similar to the pseudo polynomial time algorithm for the Knapsack Problem. Thus for practical applications i'd expect that you can get good results by dividing down all the $\alpha_i$'s (and $\lambda$) by the same factor so that they become (relatively) small, round to the nearest integer, and solve using the Knapsack-like DP.


What is the complexity of distinguishing a true Fourier spectra from a fake one?

Sorry I'm late -- it's a wonderful question!  As others have already pointed out, that's exactly why I asked the question in my BQP vs. PH paper, and why I spent 4 or 5 months working on it without success back in 2008.  One way to answer the question would have been to prove a much more general statement that I called the "Generalized Linial-Nisan Conjecture"---but unfortunately, that conjecture turned out to be false, at least for circuits of depth 3 and higher.  (I still think it's probably true for depth-2 circuits, which would at least yield an oracle separation between BQP and AM.)  For more recent ideas (the latest, as far as I know) toward an oracle separation between BQP and PH, see the nice followup paper by Fefferman, Shaltiel, Umans, and Viola.


What does $\#P\subseteq FP^{PPAD}$ imply?

First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., $\mathrm{FP^{PPAD}\subseteq PPAD}$. Thus, if we assume
$$\mathrm{\#P\subseteq PPAD},$$
then
$$\mathrm{\#P^{PPAD}\subseteq PPAD},$$
which by induction implies
$$\mathrm{FCH=PPAD}.$$
Passing to decision problems, since $\mathrm{P^{PPAD}\subseteq P^{TFNP}\subseteq NP\cap coNP}$, this shows
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP}.$$
(Note that using the closure of $\mathrm{PPAD}$ under Turing reductions, $\mathrm{P^{PPAD}}$ consists of predicates whose characteristic functions can be computed as projections of $\mathrm{PPAD}$ problems.)

As for $\oplus\mathrm P$, I believe $\mathrm{PPA\supseteq PPAD}$ can be solved by binary search on the predicate “the sum of degrees of vertices whose labels start with a given string is odd”, which means
$$\mathrm{PPAD\subseteq FP^{\oplus P}},$$
thus (using $\mathrm{P^{\oplus P}=\oplus P}$)
$$\mathrm{\#P\subseteq PPAD}\implies\mathrm{CH=P^{PPAD}=NP=coNP=\oplus P}.$$
A similar argument applies with $\mathrm{Mod}_p\mathrm P$ in place of $\oplus\mathrm P$ for any prime $p$.

I don’t know about UP.


I'm not going to try to answer the first question, as someone like Scott Aaronson, Peter Shor or John Watrous can no doubt give you a far more comprehensive answer on that front.

As regards question 2, it is important to note that quantum computers are in fact more powerful than classical computers in many instances:

There is a rather generic polynomial speed-up gained by quantum computers over classical computers in quite a number of problems. From a complexity point of view, this is perhaps somewhat less interesting than an exponential speed-up, but is something that we can actually prove.
Quantum communication complexity can often vary dramatically from classical communications complexity for the same problem. Again, this is something that can be proven (see for example the Mermin-GHZ game).
Quantum queries to oracles are very often far more powerful than classical queries to the same oracle (see for example the Deutsch-Josza algorithm).

With this is mind, it is already known that quantum computers are fundamentally more powerful than classical computers. I think I would be correct in saying that the majority of physicists who work on such things would already assume that it is not possible to find a classical algorithm to efficiently simulate every quantum system, and so while a result showing that NP was contained in BQP would certainly be surprising, it would not be particularly likely to provide a breakthrough in the understanding of any particular physical phenomenon. Rather it would provide somewhat stronger evidence that quantum physics is hard to simulate.

There is no fundamental physics that is dependent on the computational complexity of simulating it, so finding an efficient quantum algorithm for an NP-complete problem would not have fundamental consequences for the correctness of our current understanding of how the universe functions (though I am inclined to agree with Scott Aaronson's suggestion that it is interesting to see if you could have physical laws emerge from computational assumptions).

It is extremely tempting to say that this would have consequences for adiabatic evolution of quantum systems (and I guess you might get an answer or two suggesting that), etc., but this would be incorrect, as they are governed by a specific physical process, and so showing that it is in principle possible to solve SAT in polynomial time on a quantum computer, wouldn't say anything about their specific evolution.

As regards your last question, we already have examples where problem structure is exploited to yield a polynomial quantum algorithm, but which do not lead to such a classical algorithm (factoring for example). So, as far as our current understanding goes, a problem with a structure exploitable to yield a polynomial time quantum algorithm does not imply that the structure is exploitable to yield a classical polynomial time algorithm.


Is the feedback vertex set problem on planar bounded degree graphs hard?

According to Garey and Johnson's book Vertex Cover is NP-complete on planar graphs of maximum degree four. Using a simple reduction from Vertex Cover to Feedback Vertex Set should give maximum degree eight and preserve planarity.

VC to FVS: Replace each edge by a triangle (or a double edge).

One note:
Garey and Johnson also state that directed FVS is NP-complete on planar digraphs with no in- or out-degree exceeding two. They do not specifically mention undirected FVS under such restrictions.


Partition planar graph into connected subgraphs of equal size

For a graph $G=(V,E)$, deciding if $V$ can be partitioned into equal sized subsets (say, for a fixed size $r$) where each subset induces a connected subgraph is $\mathsf{NP}$-hard. It remains $\mathsf{NP}$-hard for planar graphs, and also if the number of subsets is fixed instead of the subset size ($|V|/r$ fixed).

However, the problem is polynomial for cycles, and thus for Hamiltonian graphs. It is also polynomial for trees and for series-parallel graphs when the number of subsets is fixed.

You can find these results in:

M. E. Dyer and A. M. Frieze. On the complexity of partitioning graphs into connected subgraphs.  Discrete Applied Mathematics, 10(2), 139-153. 1985.
N. Apollonio & al. Bicolored graph partitioning, or: gerrymandering at its worst.  Discrete Applied Mathematics, 157(17), 3601-3614. 2009.

Edit (bis): I think that I was wrong about Hamiltonian graphs. They may be partitioned even if their Hamiltonian cycle cannot. Thus the problem can be not polynomial. See the first comment.


SDPs usually provide relaxations, so for a minimization problem you'll get a lower bound. The Lovasz theta function does provide such a lower bound on chromatic number (see wiki). Upper bounds can be provided by rounding schemes (constructive or otherwise). In general, if you have an upper bound $U$ on the integrality gap of the SDP, you can scale the objective of the SDP by $U$ and you'll get an upper bound as well. However, there exist graphs for which the Lovasz theta gives a lowerbound of $k = O(1)$ and the chromatic number is at least $n^{1 - 2/k}$. There is some hope that higher levels of the Lasserre hierarchy can give stronger relaxations. However, notice that chromatic number is  hard to approximate within $n^{1 - \epsilon}$ (see this) in general (i.e. if you're not just interested in the promise problem where the yes instance has constant chromatic number). So, for any SDP, integrality gaps better than $n^{1-\epsilon}$ will either be restricted to cases where the SDP relaxation has  constant value or will be nonconstructive (i.e. superpolynomial time rounding or superpolynomial size relaxation), unless P=NP.


Topological sort with constraints on the relative difference between the vertex labels

The problem is $\mathsf{NP}$-hard. See [GT41] DIRECTED BANDWIDTH in Garey and Johnson.


I'll take a shot at your first question:

Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?

Well, it depends on the exact model and the resource being minimized. One option is to compare the sample complexity (for distribution-independent PAC learning) of the standard classical model with a quantum model that is given quantum samples (i.e., instead of being given a random input and the corresponding function value, the algorithm is provided with a quantum superposition over inputs and their functions values). In this setting, quantum PAC learning and classical PAC learning are basically equivalent. The classical upper bound on sample complexity and the quantum lower bound on sample complexity are almost the same, as shown by the following sequence of papers:

[1] R. Servedio and S. Gortler, “Equivalences and separations between quantum and classical learnability,” SIAM Journal on Computing, vol. 02138, pp. 1–26, 2004.
[2] A. Atici and R. Servedio, “Improved bounds on quantum learning algorithms,” Quantum Information Processing, pp. 1–18, 2005.
[3] C. Zhang, “An improved lower bound on query complexity for quantum PAC learning,” Information Processing Letters, vol. 111, no. 1, pp. 40–45, Dec. 2010.

Moving on to time complexity, using the same quantum PAC model, Bshouty and Jackson showed that DNFs can be quantum PAC learnt in polynomial time over the uniform distribution [4], further improved in [5]. The best known classical algorithm for this runs in $O(n^{\log n})$ time. Atici and Servedio [6] also show improved results for learning and testing juntas.

[4] N. Bshouty and J. Jackson, “Learning DNF over the uniform distribution using a quantum example oracle,” SIAM Journal on Computing, vol. 28, no. 3, pp. 1136–1153, 1998.
[5] J. Jackson, C. Tamon, and T. Yamakami, “Quantum DNF learnability revisited,” Computing and Combinatorics, pp. 595–604, 2002.
[6] A. Atıcı and R. Servedio, “Quantum Algorithms for Learning and Testing Juntas,” Quantum Information Processing, vol. 6, no. 5, pp. 323–348, Sep. 2007.

On the other hand, if you're interested in the standard classical PAC model only, using quantum computing as a post-processing tool (i.e., no quantum samples), then Servedio and Gortler [1] observed that there is a concept class due to Kearns and Valiant that cannot be classically PAC learnt assuming the hardness of factoring Blum integers, but can be quantumly PAC learnt using Shor's algorithm.
The situation for Angluin's model of exact learning through membership queries is somewhat similar. Quantum queries can only give a polynomial speedup in terms of query complexity. However, there is an exponential speedup in time complexity assuming the existence of one-way functions [1].
I have no idea about the second question. I'd be happy to hear more about that too.


Proving running time upper bounds for algorithms in dependent type theory

As usual, (a) the high-level conceptual approach is basically the same as it is on paper, but (b) mechanization makes new things reasonable to attempt.

The way you do things is to define a cost semantics for a programming language, where you assign a cost for each of the operations in the language. Next, you define a machine model, with its own cost semantics assigning costs to each of the primitive machine operations. Next, you prove that translating programs into the machine model is cost-preserving, so that the language-level costs correspond to the machine-level costs.

Then, you can take any particular program written in the language and prove things about its running time, memory usage, or whatever other costs your cost semantics tracks. You prove these things with math, the same as on paper. :)

However, once you have a computer checking all the details of all your proofs, new things become possible. For example, it is fairly common in paper proofs to only give the machine cost model, and handwave the language and its cost model (people say "pseudocode" when they don't want to specify the details of the language). But this is only plausible when the language and machine are very close to each other, and when you don't care about constant factors. If you need the compiler to make nontrivial optimizations, or if you need to reason about exact (and not just asymptotic) complexity, then you need to be more precise about the language.

A good example of this is the CerCo project, which did verified compilation from C to microcontroller assembly in a way that enabled source-level reasoning about things like worst-case execution times.


Linear Programming with Modulo Linear Constraints

If one uses the standard notion of a "linear program", i.e., minimization of a linear functional over a polyhedral set, then it is not clear to me if your problem is actually a linear program. The constraint with the modulo function is equivalent to a disjunction of several affine constraints. This would in general make your problem nonconvex, and thus quite hard.

If you are willing to deal with an integer program, you can exploit the structure. You can write the modulo constraints as  e.g.,
$c_i - c_j -\alpha_{ij} k \geq z_{ij}$, where $\alpha_{ij}$ is an integer for all $i,j$ and a new variable added to your problem. The resulting problem is a mixed integer linear program. Results/algorithms for these are based on the structure of the linear constraints. I am not an expert in MILPs, but I thought this may give you some pointers.


Is there a Quantum equivalent of the Time hierarchy theorem ?

The answer is no. We don't even have a time hierarchy theorem for bounded-error probabilistic polynomial time (i.e., BPTIME).  The deterministic and non-deterministic time hierarchy theorems have a diagonalization argument, which does not seem to work for semantic classes. This is why we don't have strong hierarchy theorems for semantic classes.

The best result I'm aware of is a hierarchy theorem for BPTIME with 1 bit of advice: Fortnow, L.; Santhanam, R. (2004). Hierarchy Theorems for Probabilistic Polynomial Time.

I don't know of any groups working on a quantum time hierarchy theorem. I would guess that this is because it seems like the BPTIME hierarchy problem is easier, so researchers would attack that problem instead.

(Somewhat related questions: Is there a syntactic characterization for BPP, BQP, or QMA? on MathOverflow and Semantic vs. Syntactic Complexity Classes on cstheory.)


Can constant ambiguity reduce the state complexity of a regular languages?

I claim that if for some language there is a CFA with with $s$ states and $0$ or $c$ accepting paths for every word, then there is a UFA with $C_ss^c$ states. The basic idea is that the states of the UFA are the (ordered) c-tuples of the states of the CFA and it accepts if and only if all c states accept. Of course we also have to make sure that these were indeed different computations and that we do not count all $c!$ permutations, so for these we need some extra $C_s$ bits of storage.

A bit more detailed description of the basic idea: If $(s_1,\ldots,s_c)$ is a state of the UFA, then it has a transition from it (reading some letter $a$) to the state $(s_1',\ldots,s_c')$ if and only if the CFA has a transition (reading letter $a$) from $s_i$ to $s_i'$ for every $i$. A state $(s_1,\ldots,s_c)$ is accepting if and only if $s_i$ is accepting for every $i$. Of course the starting state of the UFA is $(s_0,\ldots,s_0)$ where $s_0$ is the starting state of the CFA.

The problem with the above is that the $c$ simulated runs of the CFA might be the same. So we add some extra information, encoded, say, in a graph on $c$ vertices that has an edge between vertex $i$ and vertex $j$ if during the run so far at least once we had that $c_i\ne c_j$.

Now we still have a problem, that we have counted everything $c!$ times because of the possible permutations. We can remedy this by requiring that if the $i$-th and $j$-th states have been the same until now and in the next step they would differ, then in the next step the $i$-th state should have a larger index.


On the first question:

First off, I do not think the statement $\mathsf{XP} \subseteq \mathsf{NP}$ is meant to be implied at that point. To explain what is meant, let me ask a question: What is the parameterized counterpart to $\mathsf{NP}$?

This question naturally arises when defining a notion of intractability of parameterized problems as classical intractabilty is thought to correspond with $\mathsf{NP}$-hardness. A first attempt yields $\mathsf{ParaNP}$, basically a nondeterministic $\mathsf{FPT}$, but a theorem states that if some parameterized problem $(L, \kappa)$ is $\mathsf{ParaNP}$-complete, then already a finite union of slices (the $k$th slice of $(L,\kappa)$ is the set of instances $x$ in $L$ of parameter $\kappa(x) = k$) is already $\mathsf{NP}$-complete and thus all the hardness is already exhibited by some parameter values. Conversely, it means that problems whose slices (for fixed $k$) are solvable in polynomial time are not $\mathsf{ParaNP}$-hard -- thus this class does not yield hardness results for problems like SAT (parameterized by the number of variables), $k$-Clique (parameterized by the size of the solutions) and many other problems which are believed not to be in $\mathsf{FPT}$.

Now, (uniform) $\mathsf{XP}$ deals exactly with this kind of problems whose slices are in $\mathsf{P}$, but the definition allows for very large running times if the parameters get large w.r.t. the input size and indeed, if we parameterize by the input length, we can use exponential time algorithms and as such, $\mathsf{XP}$ contains problems from $\mathsf{EXP}$ using some suitable parameterization, but not problems like $k$-Colorabilty parameterized by $k$.

So neither $\mathsf{ParaNP}$ nor $\mathsf{XP}$ are the class that we sought out to find and in this light, we can (sort of) understand that slide as an attempt to partition the landscape of $\mathsf{NP}$ problems and their parameterized versions into somewhat meaningful parameterized complexity classes (however, it suggests $\mathsf{XP} \subseteq \mathsf{ParaNP}$ which is not the case).

On the second question:

Arguably, one can interpret the statement $\mathsf{XP} = \mathsf{NP}$ to mean that "the class of unparameterized versions of the naturally parameterized problems in $\mathsf{XP}$ coincides with $\mathsf{NP}$" and since membership in $\mathsf{XP}$ means that the slices of a problem are in $\mathsf{P}$, we get that unless $\mathsf{P} = \mathsf{NP}$ there exist some problems in $\mathsf{NP}$ which are not in $\mathsf{XP}$ when using some parameterizations (like $k$-Colorability parameterized by $k$) and thus falsifying our interpretation of $\mathsf{XP} = \mathsf{NP}$.

This of course is a bit speculative, but given that one class is parameterized while the other is not together with the results we have seen, I have no better interpretation to give.

Sources:

M. Grohe, J. Flum: Parameterized Complexity Theory


Largest embeddable hypersphere given membership oracle

If S is convex, that this is a linear programming problem. It can as such be solved/approximated in polynomial time using the standard sequence of reductions to the ellipsoid algorithm. I do not know any reference that describe it cleanly, but the following book describe it:

Geometric Algorithms and Combinatorial Optimization (Algorithms and Combinatorics) [Paperback]
Martin Grötschel, Laszlo Lovasz, Alexander Schrijver


An equation relating Time complexity, Space complexity, and entropy of output

(Too long for a comment.)

There are two aspects to your question. There is the idea of a time-"space" tradeoff, and the idea of entropy as a measure or bound for how hard this tradeoff must be for a problem. Both aspects have some issues relating to how theorists usually study these problems. Here is why and some suggestions.

Regarding entropy: This is an interesting idea but either wrong or hard to formalize for several reasons. Notice that a program that just spits out a long sequence of independent bits (whether it produces them or reads them from an input) has very high entropy but is also very simple. Its running time and space requirements are minimal. And in general there are deterministic algorithms with 0 entropy that solve very difficult problems on both time and space axis. Finally, many problems of theoretical interest are decision problems where the output is just one bit.

So entropy seems unrelated at least from usual perspectives, and you have to think it through more or else switch to a notion like Kolmogorov complexity (e.g. compressibility of the truth-table of a decision problem or something).

Regarding time-space tradeoffs: It's hard to reconcile your ideas with what we traditionally call space-time tradeoffs, which refer to time and memory usage of an algorithm starting from scratch (unlike your hashtables etc). It is studied but very, very hard. You are asking to go even farther and relate this tradeoff to some other notion of complexity of the problem, so we are probably even farther from those results (maybe not in some specific domain?).

However, I do think your intuition can be captured by complexity classes involving "advice". For instance, P/poly are problems solved by polynomial time algorithms with access to polynomial-length advice strings. You seem to be observing that all problems are in O(n)/EXP: trivial linear-time algorithm, or constant time in word RAM model, that has access to a lookup table for all answers. Whereas the problem might not be in P/poly or might not be in Exp/O(1) or so on. We trade off advice space for running time. I don't know of work on this -- I'm not an expert so maybe it exists, but it sounds hard. A general theorem relating this tradeoff to a measure of complexity of the problem would be very cool, but even harder.


Quantified Boolean Formulas with logarithmic alternations

(1) What we already know:

As you've already stated, QBF with $\log(n)$ alternations of quantifiers is hard for every level of the polynomial hierarchy.

(2) I think that we can also prove the following:

The problem is $NSPACE(log^2(n))$-hard.

(3) Here is my informal justification for the preceding assertion:

Given a $log^2(n)$ space bound NTM and an input string, we need to determine whether there exists an accepting computation on the given input string.

Each configuration in the computation can be represented by essentially $\log^2(n)$ bits.  In other words, we can represent a configuration by a group of $\log^2(n)$ variables.

The idea is that we have a start configuration and a final configuration and we need to guess the computation that happens in between.  We recursively guess the "middle" configurations using exist quantifiers and recurse verifying that the "left" configuration goes to the "middle" and the "middle" configuration goes to the "right" using for all quantifiers.

Now to make this work, instead of picking one "middle" configuration, we need to pick a group of equally spaced "intermediate" configurations between the "left" and "right" configurations.  In particular, we could guess $\sqrt{n}$ equally spaced "intermediate" configurations using exist quantifiers with $\sqrt{n} * log^2(n)$ variables and then recurse on every gap between configurations using for all quantifiers with roughly $\log(n)$ variables.

The recursion only needs to continue on to depth $2 * \log(n)$ to be able to cover a computation of length $\sqrt{n} ^ {2 * \log(n)} = n^{\log(n)} = 2^{\log^2(n)}$ where each configuration has at most $\log^2(n)$ many bits.

Since the recursion is of depth $O(\log(n))$, we only have $O(\log(n))$ groups of variables i.e. alternations.  Since each group of quantifiers only has $\sqrt{n} * log^2(n)$ variables, in total we have $O(\sqrt{n} * log^3(n))$ variables.

Feel free to offer any feedback or corrections.  Thank you very much and I hope this helps a little bit.

(4) A more general assertion as suggested by Ryan's answer:

You should be able to carry out the preceding construction in a more general way.  Consider the following:

At each step of the recursion, break up into $g(n)$ groups of "intermediate" configurations using $c(n)$ bits per configuration.  Then, do the recursion to depth $d(n)$.

As long as we don't have too many variables and too many alternations, this seems to work fine.  Roughly, we need the following to be satisfied:

$g(n) * c(n) * d(n) \leq n$
$d(n) \leq \log(n)$

Our generalized approach will be used to simulate non-deterministic Turing machines that run for $g(n)^{d(n)}$ steps using $c(n)$ bits of memory.

In particular, we pick the following:

$g(n) = \sqrt{n}$
$c(n) = \frac{\sqrt{n}}{2 * log^2{n}}$
$d(n) = 2 * \log^2(n)$

The preceding inequalities are satisfied and we can carry out the construction to simulate non-deterministic Turing machines that run for roughly $2^{\log^2(n)}$ steps using $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, we have a better hardness result than before.  In particular, the problem is hard for $NTISP(2^{\log^2(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$.

(5) Further generalizations:

In the preceding generalization, we were simulating non-deterministic time and space bounded Turing machines.  However, we may be able to simulate alternating time and space bounded Turing machines as well.

Let me explain a little bit.  So we use roughly $\log(n)$ alternations to do the recursion to depth $\log(n)$.  However, we could use some of the alternations initially, let's say $\sqrt{\log(n)}$.  Then, we could use the remaining $\sqrt{\log(n)}$ alternations to go to depth $\sqrt{\log(n)}$.

In this case, we could simulate alternating Turing machines that have $\sqrt{\log(n)}$ alternations with sublinear witness lengths, run for $2^{\log^{\frac{3}{2}}(n)}$ steps, and use $\frac{\sqrt{n}}{2 * log^2{n}}$ bits of memory.

In other words, the problem is hard for $AltTimeSpace(\sqrt{\log(n)}, 2^{\log^{\frac{3}{2}}(n)}, \frac{\sqrt{n}}{2 * log^2{n}})$ with sublinear witness lengths.  Alternatively, this class could be written using the $STA$ notation mentioned in the comments above.

Thank you for the comments and feel free to offer any further corrections or clarifications.  :)


Important papers and open problems in Boolean functions

Bryant's "Graph-Based Algorithms for Boolean Function Manipulation" introduced Reduced-Order Binary Decision Diagrams (ROBDDs) for representing and manipulating Boolean functions.  I believe these see a lot of use in CAD tools and circuit synthesis problems.  Bryant's paper is a good place to start a literature review for BDD.  He cites a few key earlier works and a lot of the more recent work grew out of, and cited, his paper.


Your first question is the topic of Brendan Juba's PhD thesis on Universal Semantic Communication. You should take a look at it, as well as some of the papers on his website.

As for your second question, you might want to read about zero-knowledge proofs.


On the coloring number of small graphs with small cliques

Uniformly random $k^2$-vertex graphs have clique size $O(\log k)$, well under $k$, and independent set size also $O(\log k)$, implying that their chromatic number is $\Omega(k^2/\log k)$.

As for $k^2$-vertex triangle-free graphs, their chromatic number can be $\Theta(k/\sqrt{\log k})$ (and not higher); see Kim, Jeong Han (1995),
"The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$", Random Structures & Algorithms 7 (3): 173–207, doi:10.1002/rsa.3240070302

If by "size" you mean edges rather than vertices, then the maximum chromatic number of triangle-free $k^2$-edge graphs is $\Theta((k/\log k)^{2/3})$. See Nilli, A. (2000), "Triangle-free graphs with large chromatic numbers", Discrete Mathematics 211(1–3): 261–262, doi:10.1016/S0012-365X(99)00109-0.


A "simple" language outside $CFL \cup coCFL$?

How about $L:=\{a^{n^2}\mid n\in\mathbb{N}\}$? It is easy to see that $L$ and its complement are not regular, and hence (as we are dealing with a unary alphabet) not context-free.


How to check if a number is a perfect power in polynomial time

Given a number n, if at all it can be written as $a^b$ (b > 1), then $b < \log(n) + 1$. And for every fixed $b$, checking if there exists an $a$ with $a^b = n$ can be done using binary search. The total running time is therefore $O(\log^2 n)$ I guess.


MACing from an arbitrary high min-entropy shared secret

As you may know, the problem of taking a weak shared key, about which the adversary knows some information, and extracting from it a key about which the adversary has essentially no information, is often referred to as privacy amplification. Once this is done, we can use the new strong key for authentication, encryption, etc.

If interaction is allowed, Alice and Bob can extract a strong key over an inauthentic channel very efficiently, in particular there is no requirement that the min-entropy rate be at least 1/2. See "Privacy Ampliﬁcation with Asymptotically Optimal Entropy Loss" by Chandran, Kanukurthi, Ostrovsky, Reyzin, and references therein.

Their introduction mentions that non-interactive solutions (one message from Alice to Bob) exist as well (references 5, 10, 15), but these do require min-entropy rate 1/2. Depending on the application, another possibility for a one-message solution would be to use deterministic (aka seedless) extractors, which work only for certain classes of sources with some restricted structure. For instance, the adversary knows some fraction of the key's bits, but the remainder are uniformly random to him. See for example Kamp and Zuckerman, "Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography" or Kamp, Rao, Vadhan, Zuckerman, "Deterministic Extractors for Small-Space Sources"


Are there any schools with researchers interested in cellular automata?

The AUTOMATA workshop series focuses on cellular automata:

http://www.eng.u-hyogo.ac.jp/eecs/eecs12/automata2014/


An explicit separation between time-constructibility and space-constructibility?

A function $T \colon \mathbb{N} \to \mathbb{N}$ is time constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto T(|x|)$ in time $O(T(n))$.

A function $S \colon \mathbb{N} \to \mathbb{N}$ is space constructible if there is a Turing machine $M$ which, on input $1^n$, computes the function $x \mapsto S(|x|)$ in space $O(S(n))$.

Some texts require that time/space constructible functions be non-decreasing. Some texts require the time constructible functions satisfy $T(n)\ge n$, and the space constructible functions satisfy $S(n)\ge \log n$. Some texts do not make use of the $O(\cdot)$ notation in the definition.

Anyway, it is easy to show that every "ordinary" function $f$, satisfying $f(n)\ge \log n$ and $f(n) = o(n)$ is space constructible, but not time constructible.

The constructibility problem is not directly related to possible separation between complexity classes DTIME(f(n)) and SPACE(f(n)). However, the statement of time and space hierarchy theorems incorporates the constructibility. For example:

Time Hierarchy Theorem
If $f$, $g$ are time-constructible functions satisfying $f(n)\log f(n) = o(g(n))$, then
$\mathbf{DTIME}(f(n))$ is a proper subset of $\mathbf{DTIME}(g(n))$.

See Arora & Barak's book or Papadimitriou's for more information. (The latter uses the term "proper complexity function" to refer to one that is both time and space constructible.)


VC-dimension of Cylinders within a Cylinder

You need the sigmoid restriction on $f$ for the VC-dimension to be finite.  Otherwise, you can let $f$ behave like a staircase, with arbitrarily many steps.  Then these staircases can have arbitrarily many intersections.  This allows $n$ ranges to admit $2^n$ different subsets.

If $f(z)$ is a polynomial, then you can bound the VC-dimension using the degree of the polynomial (combined with the degree of the polynomial (2) describing the disc).  But not sure how to apply this type of result for $\tanh$.


Homotopy type theory and Gödel's incompleteness theorems

HoTT "suffers" from Gödel incompleteness, of course, since it has a computably enumerable language and rules of inference, and we can formalize arithmetic in it. The authors of the HoTT book were perfectly aware of its incompletness. (In fact, this is quite obvious, especially when half of the authors are logicians of some sort).

But does incompleteness "impair" HoTT? No more than it does any other formal system, and I think the whole issue is a bit misguided. Let me try an analogy. Suppose you have a car which can't take you everywhere on the planet. For instance, it can't climb vertically up a wall. Is the car "impaired"? Of course, it can't get you to the top of the Empire State building. Is the car useless? Far from it, it can take you too many other interesting places. Not to mention that the Empire State building has elevators.


It puts NP into P/poly, and therefore collapses PH to its second level.

By basically the same as the usual proof that BPP is in P/poly, there is polynomial advice that provides good random bits for the randomized reduction of Valiant-Vazirani. Use that advice to produce the queries to UnambiguousSAT. Apply the reduction from UnambiguousSAT to the sparse language $S$ - which is in P/poly - and use the additional advice to decide $S$.


It seems that you are looking for this paper: http://portal.acm.org/citation.cfm?id=1382439.1382962


Agnostic Learning of K-Juntas over "small" distribution

Uniform convergence bounds should imply that agnostic learning with respect to a succinct distribution specified by a finite set S is no easier than learning with respect to the uniform distribution, at least for large enough $S$. Specifically, for any class of functions $C$ with VC-dimension $d$, the canonical algorithm which takes a randomly sampled collection of $m$ points for $m = O(d/\epsilon^2)$ and finds the function $f \in C$ which minimizes error with respect to the sample, will be within an additive $\epsilon$ of the minimum error function over the entire target distribution. So if you have an algorithm for agnostically learning with respect to an explicitly represented set of points $S$, you can learn over the uniform distribution by just taking a sufficiently large sample of points $S$ and feeding $S$ to your algorithm for concise distributions. In fact, this holds for any distribution, not just the uniform distribution.

Now there are ${d \choose k}\cdot 2^{2^{k}}$ size $k$ juntas, and so they have VC-dimension at most $d \leq 2^k + k\log d \approx 2^k$.  So for large enough $S$ (at least, larger than $2^k$), lower bounds for agnostically learning w.r.t. the uniform distribution (or any other distribution) should apply to the problem of learning w.r.t. a concise distribution.


I don't have an exact characterization but it's unlikely this problem is EXPSPACE-complete. Suppose $M^{\Sigma^*}(x)$ accepts and let $S$ be the polynomial-size set of strings queries by this machine. If I understand the game right, Alice can win by playing every string in $S$. The only way to prevent this is if $m_A$ is polynomially-bounded but that would put the game somewhere inside the exponential-time hierarchy (or lower).


Algebraic effects and handlers, dynamic effects

Let us take the example, the input/output effect. Ordinarily, one presents this with two algebraic operations print and read. We can then imagine that things get "printed out" and "read in" from some sort of a communication channel. In fact, that's how I/O works in a typical operating system.

Except that in a typical operating system one can open lots of communication channels: open files, bind to internet sockets, etc. Whenever a new channel opens, something new gets created dynamically (i.e., while the program is running). An operating system typically just creates a new integer, the "file handle", but that's just a cheap version of what we really want: an identifier that is guaranteed to be unique and that cannot be guessed by any part of the program, unless it was already given to it. (Integers can be guessed.) Let us call such a thing an instance. (In cryptography it is often called a nonce, but they cheat and think of it as an "unguessable integer". In programming languages we can make sure that instances are abstract tokens that really are unguessable.)

There are other examples where we need to create new instances. One is state, i.e., a memory location with operations update and lookup. Typical programs want to allocate any amount of memory locations, each of which is then an instance of the state effect. In general, instances allow us to create local effects, such as local exceptions and local references. In many applications it is essential to have such effects, for instance so that we can guarantee that only a certain part of the program is allowed to use a certain effect.

There is a tendency among the theoreticians to ignore effect instances because they complicate the theory. I feel that they should not be ignored because a programming language without dynamic creation of effects is next to useless. Who wants to write programs in which all memory allocations, files, and sockets, have to be specified ahead of time?


Parallel algorithms for reachability in directed planar graphs

See

Kao, Ming-Yang; Klein, Philip N. (1993), Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, J. Comput. System Sci. 47 (1993), no. 3, 459–500.

Their Theorem 10 gives a deterministic CRCW algorithm for $st$-reachability in planar digraphs with $O(n)$ processors and $O(\log^3 n)$ time. Searching Google scholar for other papers that cited theirs, I didn't see anyone else with improvements to this.


Advice for attending my first TCS conference

Talk to people, even if they are scary big names.
Attend all the keynote/invited presentations.
Attend the talks most relevant to you.
Don't be afraid to ask questions.
Attend the social events, meet other graduate students, have fun.
Talk enthusiastically about your research.
Make sure you have a 1 minute pitch describing your work, plus a 5 minute description, and also be prepared to enter into a more detailed discussion.
Ask people about their research.   Simply asking what are you working on? will get the conversation started.
Be open to possible collaborations, and follow up after the conference.


Maximum weight matching and submodular functions

Definition. For a given finite set $A$, a set function $f:2^A \rightarrow \mathbb{R}$ is submodular if for any $X, Y \subseteq A$ it holds that:
$$
f(X) + f(Y) \geq f(X \cup Y) + f(X \cap Y).
$$

Lemma
Given a bipartite graph $G = (A \cup B, E)$ with positive edge weights, let $f: 2^A \rightarrow \mathbb{R}^+$ be the function that maps $S\subseteq A$ to the value of the maximum weight matching in $G[S \cup B]$.  Then $f$ is submodular.

Proof.
Fix two sets $X, Y \subseteq A$ and let $M_\cap$ and $M_\cup$ be two matchings for the graphs $G[(X\cap Y) \cup B]$ and $G[(X \cup Y) \cup B]$ respectively.  To prove the lemma is enough to show that it is possible to partition the edges in $M_\cap$ and $M_\cup$ into two disjoint matchings $M_X$ and $M_Y$ for the graphs $G[X\cup B]$ and $G[Y\cup B]$ respectively.

The edges of $M_\cap$ and $M_\cup$ form a collection of alternating paths and cycles.  Let $\mathcal{C}$ denote this collection and observe that no cycle of $\mathcal{C}$ contains vertices from $X\setminus Y$ or $Y\setminus X$.   This holds because $M_\cap$ does not match those vertices.

Let $\mathcal{P}_X$ be the set of paths in $\mathcal{C}$ with at least one vertex in $X \setminus Y$ and let $\mathcal{P}_Y$ be the set of paths in $\mathcal{C}$ with at least one vertex in $Y \setminus X$.  Two such paths are depicted in the figure below.

Claim 1.
$\mathcal{P}_X \cap \mathcal{P}_Y = \emptyset$.

Assume by contradiction that there exists a path $P \in \mathcal{P}_X \cap \mathcal{P}_Y$.  Let $x$ be a vertex in $X\setminus Y$ on path $P$ and similarly let $y$ be a vertex in $Y \setminus X$ on path $P$.  Observe that since neither $x$ nor $y$ belong to $X \cap Y$ they do not belong to the matching $M_\cap$ by definition, and therefore they are the endpoints of the path $P$.  Moreover, since both $x$ and $y$ are in $A$, the path $P$ has even length and since it is an alternating path, either the first or last edge belongs to $M_\cap$. Therefore $M_\cap$ matches either $x$ or $y$, which contradicts the definition and proves the claim.

Let
$$M_X = (\mathcal{P}_X \cap M_\cup) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cap)$$
and
$$M_Y = (\mathcal{P}_X \cap M_\cap) \cup ( (\mathcal{C} \setminus \mathcal{P}_X) \cap M_\cup).$$
It is clear that $M_X \cup M_Y = M_\cap\cup M_\cup$  and $M_X \cap M_Y = M_\cap \cap M_\cup$.  To prove the theorem it remains to show that $M_X$ and $M_Y$ are valid matchings for $G[X\cup B]$ and $G[Y\cup B]$ respectively.
To see that $M_X$ is a valid matchings for $G[X\cup B]$ observe first that that no vertex of $Y \setminus X$ is matched by $M_X$ since $\mathcal{P}_X$ does not intersect $Y \setminus X$ by Claim 1, and $M_\cap$ does not intersect $Y \setminus X$ by definition.  Therefore, $M_X$ only uses vertices of $X \cup B$.  Second observe that every vertex $x\in X$ is matched by at most one edge of $M_X$ since otherwise $x$ belongs to either two edges of $M_\cup$ or two edges of $M_\cap$, contradicting the definition.  This proves that $M_X$ is a valid matching for $G[X\cup B]$;  showing that $M_Y$ is a valid matchings for $G[Y\cup B]$ is similar.


What is a zipper, and how does it relate to a tree-like structure?

A zipper, in general, is a data structure with a hole in it. Zippers are used for traversing/manipulating data structures, and the hole corresponds to the current focus of the traversal. Typically there is also an element of the data structure under consideration, so that one has a (list) zipper and a list or a (tree) zipper and a tree. The zipper allows the programmer to efficiently move around the data structure, even replacing the element at the focus. The pair of the zipper and the element in the focus satisfy the constraint that placing the element at the focus in the hole gives the original data structure.

Zippers can be generalised to arbitrary inductive data types. The concept can be defined in type-indexed fashion (See type-indexed data types). They are also related to the idea of the derivative of a data structure, and has been studied from a Category Theoretic perspective.


By the definition in the linked paper on page 5, the statement is wrong. Binary space partition (BSP) trees have been used for decades on computer graphics to speed up spatial queries, as have quadtrees and octrees. K-d trees are used extensively in machine learning to speed up nearest-neighbor searches. If you squint just a little, decision trees also fit the general definition.


Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?

What you ask for should have bad consequences but I cannot think of any immediately. So I have only some pointers to what we know.

Check out Viola's On the power of small depth computation The best we know is Valiant's construction for boolean circuits: log depth linear sized circuits to depth 3 subexp circuits. (We know better for arithmetic circuits.)
There are also some results of Beigel/Tarui on ACC begin contained in bounded depth circuits of superpoly size. I don't recall it being extended to all of $NC^1$ though.


How to prove that a formula can not be expressed in LTL, but can be in Buchi automata?

First you need to know what you want to express and how you are going to express it. For instance, you can represent a property as a set of infinite traces.

The properties definable by Buechi automata are the $\omega$-regular languages. The properties definable by LTL formulae are the star-free regular languages. The star-free languages are a strict subset of the $\omega$-regular languages.

Section 5.1 of Principles of Model Checking by Baier and Katoen is a good, elementary starting point. If you want general proof techniques there are a variety of ways to proceed. One general technique that appeals to me is to use games. The first player is trying to show two structures can be distinguished with an LTL formula. The second shows they are the same. Two structures are LTL equivalent if the second player has a winning strategy. So, if you take two structures which are not isomorphic but the second player has a winning strategy, then, there is no LTL formula to distinguish between the two.

  An Until Hierarchy and Other Applications of an Ehrenfeucht-Fraisse Game for Temporal Logic, K. Etessami and Th. Wilke.

There are algorithms for checking if a given $\omega$-regular language is star-free. Unfortunately these are usually couched inside the proofs of theorems.

  Logical definability on infinite traces, Werner Ebinger and Anca Muscholl

I'll dig around a bit more and try to find a more algorithmic presentation.


This is an "Orienteering problem" and is NP-hard [1]. If the starting vertex is given the problem is rooted; your variant is unrooted. Some authors call it the "selective travelling salesman" [2].

[1] B. L. Golden, L. Levy, and R. Vohra. "The orienteering problem". In: Naval Research Logistics 34.3 (1987), pp. 307-318.

[2] M. Gendreau, G. Laporte, and F. Semet. "A tabu search heuristic for the undirected selective travelling salesman problem". In: European Journal of Operational Research (1998), pp. 539-545.


Lower bounds on 2-query locally decodable codes

Yes, there is.  Ben-Aroya, Regev and de Wolf in "A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs" (FOCS '08) provide a non-quantum proof of the exponential lower bound for 2-query LDC's, although there are similarities between the quantum and non-quantum proof techniques.

Here's a rough sketch of their proof.  Let $C: \{\pm 1\}^m \to \{\pm 1\}^n$ be a $2$-query LDC.  Then, for a given $x \in \{0,1\}^m$, set $M(x)$ to be the rank-1 matrix whose $(i,j)$'th entry is $C(x)_i C(x)_j$. $M$ is a matrix-valued function, and we can look at its matrix-valued Fourier coefficients: $\widehat{M}(\alpha) = \sum_{x} M(x) \prod_{i \in \alpha} x_i$.  But now, observe that $\widehat{M}(\{i\})$ computes the matrix whose $(j,k)$'th entry is the expected correlation of $x_i$ with $C(x)_j C(x)_k$.  Thus, if $C$ is a $2$-query LDC, we know that for every $i \in [m]$, many entries in $\widehat{M}(\{i\})$ are larger than some $\epsilon$.  This allows you to lowerbound the $p$-norm of $\widehat{M}(\{i\})$.  Finally, you can then apply their matrix-valued hypercontractive inequality, which is the main theorem of the paper, to get a lowerbound on $n$.


Dick Lipton has a beautiful post from 2009 on the relationship between the factorial function and factoring. There's a lot there that is unrelated to this question, but one salient point is this theorem:

  If $n!$ can be computed by a
  straight-line arithmetic computation
  in $O(\log^{c} n)$ steps, then
  factoring has polynomial size
  circuits.

I suspect that this is evidence that your question, especially within the time bounds you mention, is going to be difficult to answer.


Nonstandard dual parametrization of graph problems

I think this problem is FPT. Suppose that the graph contains a path on $2k+1$ vertices. Then, I claim the answer is YES: we select the second, fourth, sixth, etc. vertices of this path in a solution and remove them from the graph. We now have a graph $G'$ with $|E(G')|\le |E(G)|-2k$. It is easy to find a vertex cover of $G'$ with size at most $|E(G')|$. Together with the removed vertices this gives a vertex cover of size at most $|E(G)|-k$ for $G$.

If the graph does not contain a path on $2k+1$ vertices, then a DFS tree of the graph has height at most $2k+1$, and hence can be used to construct a tree decomposition of width at most $2k$. We can then solve Vertex Cover optimally with the standard algorithm for treewidth.


Finding Tours through Near-Hamiltonian Paths?

There are no polynomial-time $\alpha$-approximation algorithms for TSP where $\alpha$ is a constant unless $\mathsf{P} = \mathsf{NP}$.

However, for metric TSP there are approximation algorithms, e.g. Christofides algorithm. A simpler 2-approximation is obtained by taking an MST.


Restating the definition to make the quantifiers easier to understand:

  A molecule is a finite stable approximable mapping, such that there exists a largest pair $(a,p) \in m$, such that for all other pairs $(b,q) \in m$ we have $b \subseteq a$ and $\{p\} \vdash q$.

In other words, a molecule is a mapping that closes off neatly, having a largest pair.