Michael Soltys and I have succeeded in proving that the problem of determining whether a string can be written as a square shuffle is NP complete. This applies even over a finite alphabet with only $7$ distinct symbols, although our proof is written for an alphabet with $9$ symbols.  This question is still open for smaller alphabets, say with only $2$ symbols. We have not looked at the problem under the restriction that each symbol appears only $6$ times (or, more generally, a constant number of times); so that question is still open.

The proof uses a reduction from $3$-Partition.  It is too long to post here, but a preprint, "Unshuffling a string is $\text{NP}$-hard", is available from our web pages at:

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

and

http://www.cas.mcmaster.ca/~soltys/#Papers.

The paper has been published in the Journal of Computer System Sciences:

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


Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants

[EDIT]

For consistency, I switched the notations from $c(n)$ to $dc(n)$.
It was asked by v s in the comments whether my answer generalize to higher dimensions. It does and gives an upper bound over any field:
$$dc(n)\le 2^n-1.$$
See my draft on this: An Upper Bound for the Permanent versus Determinant Problem.

[/EDIT]

[A side comment: I think you could edit your previous question instead of creating a new one.]

I have the following answer for you:

$$\operatorname{per}\begin{pmatrix} a&b&c\\d&e&f\\g&h&i\end{pmatrix}=
    \det\begin{pmatrix}
    0 & a & d & g & 0 & 0 & 0 \\
    0 & 1 & 0 & 0 & i & f & 0 \\
    0 & 0 & 1 & 0 & 0 & c & i \\
    0 & 0 & 0 & 1 & c & 0 & f \\
    e & 0 & 0 & 0 & 1 & 0 & 0 \\
    h & 0 & 0 & 0 & 0 & 1 & 0 \\
    b & 0 & 0 & 0 & 0 & 0 & 1
    \end{pmatrix}$$

Note that looking for such references about explicit examples, I could'nt find any and thus the example I give you is an example I built.

This question you are asking is commonly called the "Permanent vs Determinant problem". Suppose we are given an $(n\times n)$ matrix $A$, and we want the smallest matrix $B$ such that $\operatorname{per} A=\det B$. Let us denote by $dc(n)$ the dimensions of the smallest such $B$. Here are historical results:

[Szegö 1913] $dc(n)\ge n+1$
[von zur Gathen 1986] $dc(n)\ge n\sqrt 2-6\sqrt n$
[Cai 1990] $dc(n)\ge n\sqrt 2$
[Mignon & Ressayre 2004] $dc(n)\ge n^2/2$ in characteristic $0$
[Cai, Chen & Li 2008] $dc(n)\ge n^2/2$ in characteristic $\neq 2$.

This shows that $5\le dc(3)\le 7$ (the upper bound is the matrix given above).

As I am lazy, I just give you one reference where you can find the other ones. It is the most recent paper I cited, by Cai, Chen and Li: A quadratic lower bound for the permanent and determinant problem over any characteristic $\neq 2$.

If you read French, you can also have a look to my slides on this subject: Permanent versus Déterminant.


Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below).

We want to show that $P^{NP \cap coNP} = NP \cap coNP$. Clearly, one direction is obviously true: $NP \cap coNP \subseteq P^{NP \cap coNP}$. To prove the other direction, it is sufficient to show that $P^{NP \cap coNP} \subseteq NP$ since then $P^{NP \cap coNP} \subseteq coNP$ follows simply by complementing all the languages involved and as a result $P^{NP \cap coNP} \subseteq NP \cap coNP$.

So let's prove that $P^{NP \cap coNP} \subseteq NP$.

Suppose we have a deterministic polynomial time machine $M$ which makes oracle queries for languages in $NP \cap coNP$. We define a new, non-deterministic machine $M'$ based on $M$ as follows:

Simulate $M$ until $M$ needs to run an oracle query on some input $x$ for some language $L$. At that point, run a subroutine which branches $M'$ into some number of branches each of which attempts to learn the answer to the oracle query. The subroutine is designed so that no branch learns the wrong answer, at least one branch learns the correct answer, and some branches get "inconclusive" as a result when trying to learn the answer to the query. In $M'$, the branches with inconclusive results then reject. At this point, the only branches left are ones which know the correct answer to the query. Thus we can continue the simulation of $M$ in these branches. At the end of the simulation, the only branches which haven't rejected are the ones which successfully got through all of the steps of the simulation. These branches accept iff $M$ accepts, so the overall $NP$

Since $L \in NP \cap coNP$, there exists a NP machine $N_L$ with language $L$ and another machine $N_{\neg L}$ whose language is the complement of $L$. To simulate the oracle query (is $x$ in $L$), $M'$ first runs $N_L$ on $x$ and then runs $N_{\neg L}$ on $x$ in every branch. Every resulting branch will have one branch of $N_L$'s computation and one branch of $N_{\neg L}$'s computation. Within any single branch, both the $N_L$ computaion and the $N_{\neg L}$ computation cannot be accepting since that would require $x$ to both be in $L$ and in $\neg L$. Thus each branch will have either the $N_L$ computation accepting, the $N_{\neg L}$ computation accepting, or neither computation accepting. Furthermore, there must be at least one accepting branch of either $N_L$ or $N_{\neg L}$. Next, $M'$ rejects in the branches in which the computations of both $N_L$ and $N_{\neg L}$ reject. In all other branches, $M'$ has learned the answer to the oracle query (since either $N_L$ or $N_{\neg L}$ accept $x$ in the particular branch considered in this $M'$ branch). At that point, $M'$ can continue the simulation of $M$. Note that the simulation will actually continue in at least one branch since at least one accepting branch of either $N_L$ or $N_{\neg L}$ exits.


There are lots of applications to transcendence in finite characteristic.  Christol's theorem makes it possible to give proofs of theorems about transcendence of formal power series using the tools of formal language theory.  This was pioneered by Allouche, Valerie Berthe in her thesis, etc.


Universal Turing Machines in "Computational Complexity" by Papadimitriou

In response to your second question, you are correct -- a 2-state, 3-symbol state TM was shown to be universal by then-undergraduate Alex Smith in 2007 by reduction to a universal cyclic tag system, which makes for a complex encoding.  Here's the original proof, which uses Wolfram's nonstandard notation for representing Turing Machines.

It's easy to intuit why simpler universal Turing Machines require more complicated encodings -- after all, the information involved in the computation needs to go somewhere.  For example, in the encoding scheme implicit in Smith's proof, we would first need to first encode the Turing Machine under simulation within a cyclic tag system, then use Smith's scheme to represent the cyclic tag system within the 2-3 Turing Machine.


To put this in complexity terms, could it be possible that P = BPP and EXP has polynomial-size circuits (so no general derandomization)? Relative to a generic oracle you do get P=BPP for all input lengths, and EXP in P/poly for infinitely many lengths, a partial answer to your query. I don't know an oracle where P = BPP and EXP is in P/poly, but I'd think it should be possible.


For tree automata, you have the Mostowski hierarchy, which is about the complexity of acceptance condition: each level is of the form $(i,j)$ with $i\in\{0,1\}$ and $i\leq j$. Being at level $(i,j)$ means that there is a parity automaton using parities from $i$ to $j$ recognizing the language. For more on parity condition, see here: https://en.wikipedia.org/wiki/%CE%A9-automaton. This hierarchy exists in 3 versions: deterministic, nondeterministic, or alternating, depending on the model of automaton you are looking at (although the deterministic hierarchy does not cover all regular languages).

There is an other hierarchy called Wadge hierarchy, with a more topological flavour, but it is getting further from complexity of acceptors: http://en.wikipedia.org/wiki/Wadge_hierarchy


Can consume/produce be modeled in linear logic?

With non-commutative linear logic (cf. Retoré 1997, for pomset logic), you can model the sequentiality of checking resources and avoid having the resource checking occur within the scope of whatever choice operator you want to use.
For example, you could model your query so:
$$(r; a \vee b) \multimap (c; r)$$
You might interpret this as saying: if I can take $r$ and then consume $a \vee b$, then I can provide $c$ and then free $r$.  Is that the semantics you want?
It looks, unfortunately, like you can't combine non-commutative linear logic with usual linear logic in the sequent calculus and maintain the needed proof-theoretic properties to model planning via proof search.  You can do this is the Calculus of Structures, see (Strassburger, 2003), which has been used for planning (Kahramanogullari 2009).
If you want to go the route of having a modality decorating just $t$, well that might be tricky because you essentially want to be able to look at $r$ without consuming it, and without having it available for unlimited use, which is not a propositional attitude of regular linear logic.  You can try to see if
$$((?r \otimes a) \vee (?r \otimes b)) \multimap c$$
works for you, but it probably won't, because $?r$ is cheaper than $r$ — it is a bit like having a reference ro $r$; and so does not actually ensure that you can put your hands on $r$.  $?!r$ might work better, and is the basis for the two encodings used to model classical logic in linear logic, but to have $r$ doesn't mean you can provide $?!r$.  Looking at one of the various weak exponentials for linear logic might help here.
References

Retoré 1997, Pomset logic: a non-commutative extension of classical linear logic
Strassburger 2003, Linear Logic and Noncommutativity in the Calculus of Structures
Kahramanogullari 2009, On Linear Logic Planning and Concurrency,
Information and Computation 207:1229 - 1258.


Preprocessing Sparse, Directed Non-Planar Graphs for Faster Shortest Path

There have been many results on distance oracles and approximate distance oracles for directed graphs. A distance oracle for a graph is a data structure which can be queried on any pair of vertices (u,v) and returns the distance from u to v. It might also return the path realizing this distance. A good place to start (for the undirected case) would be:

Mikkel Thorup and Uri Zwick. Approximate distance oracles.
Journal of the ACM, 52(1):1–24, 2005.

For the directed case you should check out:

Edith Cohen, Eran Halperin, Haim Kaplan, Uri Zwick,
Reachability and distance queries via 2-hop labels
SIAM Journal on Computing 32, 1338--1355 (2003).

Some other works also manage to construct such data structures which are also dynamic, that is, it is possible to update the data structure with changes to the graph.


Simply-stated restriction on imperative programming language that captures the elementary functions?

According to a classic result of Meyer and Ritchie (mentioned in the paper cited in the question), the elementary functions are characterized by LOOP programs in which the nesting depth of for-loops is restricted to be at most 2.


Arithmetic circuits with just one threshold gate

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$.

First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, and either $ab,a'b\ge t$ as well, or $ab=a'b(=0)$.

With this in mind, we can simulate the circuit with a Boolean monotone circuit by replacing each node $c$ with nodes $c_0,\dots,c_t$, where $c_i$ is intended to compute the predicate $c\ge i$. (We need $c_0$ only for notational convenience, it computes the constant $1$ function.) If $c$ is a Boolean input variable $x$, we take $c_1=x$, $c_2=\dots=c_t=0$. If $c$ is an addition gate, say $c=a+b$, we implement it via
$$c_i=\bigvee_{\substack{j,k\le t\\j+k\ge i}}(a_j\land b_k).$$
Multiplication gates are handled in the same way.

This takes $O(t^3)$ gates per one gate of the original circuit. As a minor optimization, we can reduce it to $O(t^2)$ by putting
\begin{align*}
c_t&=\bigvee_{j+k\ge t}(a_j\land b_k),\\
c_i&=c_{i+1}\lor\bigvee_{j+k=i}(a_j\land b_k),\qquad i<t,
\end{align*}
so that each $a_j\land b_k$ is used as an input of only one of the $c_i$ gates.


Where is the error in the following P != NP pseudo-proof ?

You are being a little sloppy with your definitions: what exactly is the input to U, and what exactly are the conditions to accept? In particular, you probably need to include in the input  to U not just a Turing machine but also a specific polynomial that bounds the running time of the machine, because otherwise it's undecidable whether any particular TM really is polynomial time. But that's not the real problem.

The actual problem is that L(U) is not in NP. To be in NP, there needs to be a single polynomial p(n) that bounds the time to check a solution. But in your case this time is bounded by a polynomial q(n) that depends on the particular TM given as input. It's easy to choose inputs that cause q(n) to be larger than any fixed choice of p(n).


Implications of approximating the determinant

With a risk of not having understood the details of the question properly: Being able to approximate the determinant within any factor requires being able to decide whether a square matrix is singular or not, which should have some consequences.

For one thing, it gives a randomized test for whether a general graph has a perfect matching (via the Tutte matrix and Schwarz-Zippel). I don't think the latter is known in randomized logspace (e.g., the Complexity Zoo lists bipartite perfect matching as hard for NL).


One can solve this problem either by a direct proof or using an extended version of Rice's theorem (Theorem II.4.2 in Oddifredi's book Classical Recursion Theory I, where it is attributed to Myhill, Sheperdson, McNaughton and Shapiro). I'll start by the latter.

Rice's theorem says that given a property $P$ of languages:

either $P$ is trivial (i.e. either all languages satisfy $P$, or none does)
or the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is not computable

But here we want to know whether $\mathcal{A}$ can be recursively enumerable (the current trend is to say "computably enumerable" instead). This can happen: take for example: {$M$ | $M$ halts on at least 7 inputs}

The generalized version of Rice's theorem says the following. Given a property $P$ of languages, the set $\mathcal{A}$ = {$M$ | $L(M)$ has the property $P$} is computably enumerable if and only if there exists a computably enumerable set $F$ of finite sets of strings such that: $M \in L \Leftrightarrow (\exists u \text{ finite})~[u \in F  \text{  and  }  u \subseteq L(M)]$.

(Notice that it makes sense to talk about a computably enumerable set of finite sets of strings, as such objects can themselves be encoded by strings).

Here we have the set $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. Suppose $\mathcal{A}$ is finite. Then there exists a computably enumerable set $F$ as above. Now

If $F$ is non-empty and contains a finite set of strings $u$, then let $M_u$ be a Turing machine whose domain $L(M_u)$ is exactly $u$ (this is easy to build). Then by definition of $F$, $M_u \in \mathcal{A}$, but this means that $HP$ reduces to $L(M_u)=u$, which is a finite set (hence computable), a contradiction since $HP$ is not computable.
Or $F$ is empty, in which case $\mathcal{A}$ is also empty, but this is not the case as there does exist a machine $M_{HP}$ whose domain is exactly $HP$ (as $HP$ is computably enumerable).

We have a contradiction!

But if you don't like using too powerful theorems we can do this directly, via an adaptation of Yohay's proof. Let $\mathcal{A}$ = {$M$ | $HP$ reduces to $L(M)$}. If $\mathcal{A}$ were computably enumerable, it would reduce to the halting problem $HP$. To show that this is not the case, we will show that some set harder than $HP$ can be reduced to $\mathcal{A}$. We'll take the following: $INF$ = {$M$ | $L(M)$ is infinite}. The fact that $HP$ reduces to $INF$ but not vice-versa is standard (if you don't believe me, here is a nice and fairly easy exercise for you!).

Now we want to reduce $INF$ to $\mathcal{A}$. Let $M_{HP}$ be a fixed machine such that $L(M_{HP})=HP$. Let $M$ be any machine. Using $M$, construct the machine $M'$ which does the following.

For all input $x$, $M'$ counts the numbers of elements in $L(M)$. Whenever $n$ elements are found in $L(M)$, $M'$ runs the computation of $M_{HP}(x)$ during $n$ steps of computation. If this halts at any point, then $M'$ halts too, if not it waits to find more elements in $L(M)$ and repeats the process. There are two cases:

If $M \notin INF$, then calling $k$ the number of elements of $L(M)$, by construction $M'$ will only emulate $M_{HP}$ during $k$ steps of computation for any input. For large inputs (|x|>k), this will be insufficient as $k$ steps won't even be enough to read the input! Hence $M'$ will not halt for all inputs $x$ such that $|x|>k$, hence $L(M')$ is finite, and hence $L(M') \notin HP$
If $M \in INF$, then for any input $x$, $M'$ emulates $M_{HP}$ for infinitely many steps of computation, hence $L(M')=L(M_{HP})=HP$. And therefore $M' \in \mathcal{A}$.

We have proven $M \in INF \Leftrightarrow M' \in \mathcal{A}$, so $INF$ reduces to $\mathcal{A}$, which is what we wanted.


The problem is NP-hard. Proof is by reduction from the following problem:

Given a tripartite graph $G$ with $N$ vertices in each part, are there $N$ vertex-disjoint triangles in $G$?

Here's the reduction: given an instance $G$ of the above problem, let $A_1$, $A_2$, $A_3$ denote the set of vertices in each part of $G$, and $E_{ij}$ be the set of edges between $A_i$ and $A_j$. Also, number the vertices in each part by $1,\dotsc,N$.

We construct an instance of your problem with $n = |E(G)| + M$, where $M$ is a large number (say, $M = 10 |E(G)|$), and $p = N + 1$.  The first $|E(G)|$ elements of $\{1,\dotsc,n\}$ correspond to the edges of $G$.  The partition $P$ is defined as follows: $P_i$ for $i=1,\dotsc,N$ is the set of edges that have the $i$th vertex of $A_1$ as one of their endpoints. Clearly these sets are disjoint and their union is $E_{1,2} \cup E_{1,3}$. $P_{N+1}$ is everything else, i.e., $E_{2,3} \cup \{|E(G)| + 1, \dotsc, |E(G)| + M\}$. Similarly, we define $Q$ using $A_2$ instead of $A_1$, and $R$ using $A_3$ instead of $A_1$.

Now, we claim is that this instance has a solution of cost at most $3|E(G)| - 3N + M$ if and only if $G$ has $N$ disjoint triangles. To see this, first notice that since $M$ is large, any solution that has cost less than $2 M$ must map $P_{N+1}$ to $Q_{N+1}$ and $R_{N+1}$. This already accounts for $|E(G)| + M$ of the total cost, so we are left with $2 |E(G)| - 3 N$. Now, note that the intersection of each $P_i$ and each $Q_j$ is at most one (and similarly for $P_i$ and $R_k$, and also for $Q_j$ and $R_k$). So, the objective function is minimized if all these intersections can be 1 at the same time. This corresponds to $N$ disjoint triangles in $G$.


Characterizing the set of problems solvable via network flow

It depends on how you define "solvable via network flows". If you allow the preprocessing step to take arbitrarily long, then anything is solvable using network flows by simply solving it an then outputting a trivial network flow that has the desired answer.

Under log-space reductions, network flow is $P$-complete so any problem in $P$ can be solved "efficiently" using a network flow.

Another interesting aspect of flows is that if you start with integer capacities, then the solution will be integer as well. Network Flows (when viewed as Linear Programs) are actually part of a larger class of problems called totally unimodular. The optimal solutions to these programs are always integer.


Does the order of declarations in an inductive type matter?

The order does not matter. I cannot think of a case where it would. As Andrej Bauer points out in a comment, if you change the order the result is canonically isomorphic to the original.
One case cannot depend on another case. The elements of the sum represent a choice, so it doesn't make sense that the choice taken depends upon a choice that is not taken.


Can interaction combinators implement any interaction net efficiently?

The answer is yes.  It is an immediate consequence of the definition of translation used by Lafont in his paper introducing the interaction combinators.

A Lafont translation $\Phi$ from an interaction net system to another is an arity-preserving map from the symbols (i.e. the atomic agents) of the first system to principal nets of the other.  Basically, a principal net of arity $n$ is a "tree" of agents with some leaves connected to each other and with exactly $n$ free leaves.  In particular, it has exactly one free principal port and $n$ free auxiliary ports, so it may be seen as a "macro-agent".  See Lafont's paper for the exact definition.

A translation $\Phi$ must also satisfy the following simulation property: for all symbols (i.e. agents) $\alpha,\beta$ of the source system,

$$\alpha\bowtie\beta\to\nu\qquad\text{implies}\qquad\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$$

where the notation $\alpha\bowtie\beta$ stands for an active pair, and $\Phi(\alpha)\bowtie\Phi(\beta)=\Phi(\alpha\bowtie\beta)$ for its translation.

Now, let $M$ be the longest simulating reduction $\Phi(\alpha)\bowtie\Phi(\beta)\to^\ast\Phi(\nu)$ (such $M$ exists because the number of possible active pairs is finite).  It is clear that, if $\mu\to^\ast\mu'$ in $n$ steps the source system, then $\Phi(\mu)\to^\ast\Phi(\mu')$ in at most $M\cdot n$ steps in the target system.  This is stated as Proposition 4 in Lafont's paper.  So the simulation is efficient according to the notion of efficiency given in the question.

The interaction combinators are universal in the sense that every system of interaction nets may be translated in the interaction combinators, in the above sense.  Hence the claim.


Problems with Unknown Single Exponential Time Agorithms

In the Graph Homomorphism problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\in E(G)$ we have that $h(u) h(v)\in E(H)$.

The problem can be solved in time $O^*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^*$-notation hides factors polynomial in the input size).

However it is open whether it can be solved in time $O^*(c^{|V(H)|+|V(G)|})$, and this appears as an open question in

Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch:
Exact Algorithms for Graph Homomorphisms. Theory Comput. Syst. 41(2): 381-393 (2007)


Sure. If $C_1\ni x_i$ and $C_2\ni\neg x_i$ are in $F\restriction I$ (in particular, $x_i$ is unset by $I$), pick clauses $D_1,D_2$ in $F$ which restrict to $C_1$ and $C_2$, respectively. Then $x_i\in D_1$ and $\neg x_i\in D_2$, hence their resolvent $(D_1\let\bez\smallsetminus\bez\{x_i\})\cup(D_2\bez\{\neg x_i\})$ is subsumed by some $D\in F$. If $D$ contains a literal made true under $I$, then so does $D_1$ or $D_2$, contradicting their choice. Thus, $D\restriction I$ is in $F\restriction I$, and it subsumes $(C_1\bez\{x_i\})\cup(C_2\cup\{\neg x_i\})$.


Usually the question is interesting for constant alphabet sizes, since otherwise Reed-Solomon codes obviously achieve the Singleton bound.

For constant (but still large) alphabet sizes, there are explicit codes that "approximately" achieve the Singleton bound, and are thus also asymptotically good. See

Venkatesan Guruswami and Piotr Indyk. Linear time encodable and list decodable codes Proceedings of STOC 2003.

Also there are several flavors of Expander and Concatenated Codes (rather than the famous constructions) that are asymptotically good. For example see

"Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs" by Alon et al.

Also there are more sophisticated "concatenated-like" constructions that achieve much more than asymptotic-goodness, for example:

V. Guruswami and A. Smith. Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate, FOCS 2010.

Finally, any construction of codes for stochastic errors (that is, the channel BSC(p)) that achieves constant rate and exponentially small error must be asymptotically good. However, I'm not aware of any such explicit constructions other than concatenated codes (Forney/Justesen and similar variations).


Graph nodes preserving changes to the overall graph

I believe you are thinking of persistent data structures.
http://en.wikipedia.org/wiki/Persistent_data_structure


Factoriality testing algorithms and their efficiency

Notice that the input size is $n = \lceil \log_2 P \rceil$. The problem can be solved in time near linear in $n$, i.e. in time $n \log^{O(1)} n = (\log P)(\log \log P)^{O(1)}$.

The trick is to do binary search on the integers in $[1, 2\log_2 P]$ in order to find the largest $N$ such that $N! \leq P$: call this number $N(P) = \max\{N: N! \leq P\}$. If $N(P) = P$, the answer is 'yes', otherwise it is 'no'.

Let us first show that $N(P) \leq 2\log_2 P$ for $P \geq 4$ (for smaller $P$ you can use a lookup table). This follows because for every $N$, $N! \geq (N/2)^{N/2}$, and therefore
$$
\log_2 P \geq \frac{N}{2}\log_2 \frac{N}{2} \geq \frac{N}{2}.
$$

The complexity is $T(2\log_2 P) \cdot O(\log \log P)$, whete $T(N!)$ is the complexity of computing $N!$. This is because the binary search performs $O(\log \log P)$ steps, and at each step computes $N!$ for some $N \leq 2\log_2 P$. The work by Borwein, referenced in Chad's answer, gives a near-linear in $N$ bound on $T(N)$.


Yes, it is well known it can be done by diagonalizing the matrix using row and column operations. An outline of the procedure is given in the paper The Complexity of Solving Equations over Finite Groups by Goldmann and Russell.


Rademacher Complexity of the Composition with an Indicator

In general, composing a threshold function with a function class can arbitrarily increase the Rademacher complexity (so the answer to your question is negative). Let $\Omega$ be a finite set, $|\Omega|=N$, and let $F=[-a,a]^\Omega$ be the set of all functions from $\Omega$ to $[-a,a]$.
When $N\gg n$, the Rademacher complexity (either empirical or expected) of $F$ will be $\Theta(a)$. Let $F'$ be $F$ composed with the sign function; now $F'=\{-1,1\}^\Omega$ and its Rademacher complexity in this regime is $\Theta(1)$. Since $a>0$ can be taken arbitrarily small, this shows that the multiplicative gap can be arbitrarily large.


Any resources describing an OS assigning process priority via distance to HD head?

That would be pragmatically challenging under most OSes due to the abstraction layers and difference in subsystems. Vista offers I/O priority, which is as close as I've ever seen to anything like that.. And it isn't very close. All theory here... also won't matter soon as we go to SSDs that have no seek time.


Explaining monad transformers in categorical terms

According to Oleksandr Manzuk, they are "translation of a monad along an adjunction", see "Calculating Monad Transformers with Category Theory". By the way, that's the third hit on Google for "monad transformer categorically". The first is a Stackoverflow question about this and the second is your question.


Poly-time approximation scheme for problems with pseudo-polynomial time algorithms

The short answer is NO. Petra Schuurman and Gerhard Woeginger have written about this in their tutorial. See Example 0.6.3 on p.46 in their paper when there's no FPTAS while problem has pseudopolynomial algorithm. What concerns an example when there's no PTAS while problem has pseudopolynomial algorithm I suggest Binary Paint Shop Problem (discussed also here, definition can be found in the first answer).

Also there is good picture in tutorial on p.5 on relations between approximation classes and Pseudo-Polynomial Time.


Page 1 explains how you can go from the $\delta$-based formulation to the $f$-based formulation and back. But it doesn't matter for the algorithm. The first step is to solve the LP, thus obtaining values for the $\delta(i, j)$ values. From a pseudocode standpoint, you solve this by calling your favorite LP solver.
$c$ is the cost per edge, and is part of the input.
Terminals are the elements of the tree T (also given as part of the input)
$A_u$ is defined in the line above the text 'Rounding procedure' as the minimum distance between u and elements of T.
\sigma_j denotes the jth element of T in some random ordering of the elements (basically scramble the array of indices corresponding to T and take the jth element)


What is the state of the art in cache algorithm theory?

I don't know about a method for analyzing an arbitrary given algorithm to come up with a cache policy in general (this sounds quite hard), but this is essentially what's been done (optimally, in an asymptotic sense) on a case-by-case basis for most known cache-oblivious algorithms, by analyzing their divide-and-conquer structure. Cache-oblivious algorithms are known for FFT, matrix multiplication, sorting, and a few others. See the Wikipedia page and references therein.


Complexity of multi-linear polynomial computing Boolean function

If I understand your question correctly, the answer is no (independently from the field, assuming $\mathsf{VP}\neq\mathsf{VNP}$).


Upper bound on Independence Number of Random Regular Graph with degree $\Theta(\sqrt{|V|} \log^2 |V|)$

I don't think the Bollobás paper asserts the bound on the independence number; rather, it seems to me that it asserts that for any given maximum degree $\Delta$ and lower bound on the girth $g$, there exists graphs of degree at most $\Delta$ and girth at least $g$ with independence ratio at most $2\log \Delta/\Delta$. In contrast, as you mention, the Frieze and Łuczak paper seems to give concentration of random $\Delta$-regular graphs that holds for $\Delta=o(n^{1/3})$, so that the desired upper bound holds with probability $1-o(1)$. This result is thus incomparable to the Bollobás paper, I think.
For your specific application, I think one can give an upper bound of roughly $\alpha(G)\leq O(n/\sqrt{\Delta})=\tilde{O}(n^{3/4})$ that holds with probability $1-o(1)$ (in fact, at least inverse polynomial error probability). I have no idea if this bound is closer to the truth for this regime, and this is of course much weaker than the bound that you want (note that no bound better than $\tilde{O}(n^{1/2})$ is possible anyway, for any $\Delta$-regular graph with $\Delta=\tilde{O}(n^{1/2})$-here, I'm using the tilde notation to mean up to logarithmic factors, in either direction).
Here's two ways that I hope work to get this bound: one is to note that the Frieze and Łuczak paper upper bound does not seem to rely on the constant degree restriction. In particular, just mimicking their proof of the upper bound (which is by far the easier direction in their concentration result), it seems to me like everything should go through to show that the probability of having an independent set of size greater than $\tilde{O}(n^{3/4})$ is $1-o(1)$. The reason their bound degrades this much when the degree is not constant is because it incurs a $e^{\Delta^2}$ loss when moving between simpler random graph models.
Another way to get it is to use some recent high-powered results that show that if $\Delta\to \infty$ with $n$ but $\Delta=o(n^{1-\epsilon})$ for some fixed $\epsilon>0$, then the spectral radius of the adjacency matrix (excluding the trivial eigenvalue $\Delta$) is $O(\sqrt{\Delta})$ with probability $1-o(1)$ (where the constant depends on $\epsilon$, but not $\Delta,n$). If $\lambda=\lambda(G):=\max\{\vert \lambda_2(G)\vert,\vert \lambda_n(G)\vert\}$ is the second largest eigenvalue of the adjacency matrix of a graph $G$, Hoffman's bound asserts that for a $\Delta$-regular graph on $n$ vertices:
\begin{equation}
\alpha(G)\leq \frac{\lambda}{\Delta-\lambda}n.
\end{equation}
For $\Delta=\tilde{O}(n^{1/2})$ and using the estimate above gives with probability $1-o(1)$ that $\alpha(G)\leq O(n/\sqrt{\Delta}) = \tilde{O}(n^{3/4})$.


Legally speaking, the term "calculus" is almost always used to describe a language, i.e., a piece of syntax, with added rules of calculation or reasoning.  Examples include the good old predicate calculus, lambda calculus, process calculi, various type theories and logics (e.g., Martin-Lof type theory and linear logic).  From a programming language point of view, a "calculus" is just a bare bones programming language, that we take to be fundamental in some way.

People with an engineering bent of mind often take calculi to be good enough for using as a foundation, and describe the "semantics" of other languages in terms of such calculi.  (Prominent examples of such people include Christopher Strachey, Robin Milner, and Tony Hoare to some extent.)  People with a logical/philosophical bent of mind regard such calculi as being inadequate on their own, and needing a proper "semantics".  (Prominent examples include Dana Scott, Gordon Plotkin, John Reynolds and again Tony Hoare to some extent.)  A true "semantics" then is expressed in terms of abstract concepts, rather than pieces of syntax.

From this point of view, the F# paper that you cite is doing the right thing by describing the semantics in terms of concepts.  It is indeed the preferred way of describing the semantics of programming languages (at least for those of us with a logical bent of mind).

[Additional note: See also the previous question What constitutes denotational semantics for related discussion, even though it is dealing with denotational rather than operational semantics.]


How to find a specific research topic to concentrate on?

Let me offer a slight variant of @Shir's answer.  For your first problem, it really doesn't matter what you work on.  Just pick a random problem out of the air and start working on it.  Do not worry about "finding a thesis".  Do not worry about "finding an advisor".  However, you may find more problems floating in the air near active researchers—both faculty and students—than, say, in your apartment or at the library.  And you may find that people are more willing to help you solve your problem (and polish the solution for publication) if it's a problem they care about.  Talk to everyone.  Listen to everyone.  Read everything.  Then pick your own problem.

Once you've solved your first problem, start over.  Pick a different problem, and talk to different people.  Meanwhile, write up your first solution, and give talks about it, if only to a faculty member or another student or your cat.  Listen to their feedback.  (Meow.)  Practice, practice, practice.  (Don't forget to ace your classes and your qualifying exams.  If necessary, find a faculty member to sign your paperwork.)

Once you have experience solving individual problems, then you can start developing a larger research program (aka a thesis direction).  [This is probably about the point where you finish your MS thesis and start as a PhD student.]  With a two-point sample of problem space, you have a better view of your own talents and interests.  With a multiple-point sample of potential-collaborator-space, you have some idea of what kind of researchers (in particular, what kind of advisor) you work well with.  Having feedback from multiple audiences, you'll have some clue about what problems other people and/or cats care about, and what kind of intuition you're best at conveying.  All that information will help you make more informed decisions about what to work on in the future.

But for your first problem, it really doesn't matter.  Just pick something you're interested in and start working.


Is there a complexity theory analogue of Rice's theorem in computability theory?

Proving such a complexity theoretic version of Rice's Theorem was a motivation for me to study program obfuscation.

Rice's theorem says in essence, that it is hard to understand the functions that programs compute, given the program.  However, the reason these problems are undecideable is that they are infinitary.  Even on one input, a program may never halt, and we need to consider what
the program does on infinitely many inputs.

A finitary version of Rice's theorem would fix the input size and running time of a program,
and say that the program is hard to understand.  Once you've fixed these, you might as well
view the program as a Boolean circuit.  What properties of the function computed by a Boolean circuit are hard to compute?  One example is ``not always 0'', which is the NP-complete
Satisfiability problems.    But unlike Rice's Theorem, there are some properties that are
non-trivial but easy, even without understanding the circuit.  We can always know that:
the function computed by a circuit has a bounded circuit complexity (the size of the circuit).  Also, we can always evaluate the circuit on inputs of our choice.

So say a property of $f_C$ is easy with Black-box access if it can be compute,d
in probabilistic polynomial time by an algorithm that gets as input $n$, a bound on $|C|$ and oracle access to $f_C$.  For example, satisfiability is not easy with black-box access, because we could imagine a circuit of size $n$ that only produces answer 1 on a
randomly chosen input $x$.  No black box algorithm could distinguish such a circuit from one that always returned 0, since the probability of querying the oracle on $x$ is exponentially small.  On the other hand, the property $f(0..0)=1$ is black-box easy.
The question is:  are there any properties of $f_C$ that are decideable in probabilistic polynomial-time that are not easy with Black-box access?

While this question is open as far as I know, our intended approach was ruled out.  We had
hoped to prove this by showing that cryptographically secure program obfuscation was possible.  However, Boaz proved the opposite: that it was impossible.  This implicitly shows that black-box access to circuits is more limited than full access to the circuit description, but the proof is non-constructive, so I can't name any property as above
that is easy given the circuit description but not with black-box access.  It is interesting (at least to me) if such a property could be reverse engineered from  our paper.

Here is the reference:Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang: On the (Im)possibility of Obfuscating Programs. CRYPTO 2001:1-18


Unary languages recognized by two-way deterministic counter automata

This is only an idea that came to my mind while reading Marvin L. Minsky, "Recursive Unsolvability of Post's Problem of Tag and other Topics in Theory of
Turing Machines"; in particular the famous theorem Ia:

Theorem Ia: We can represent any partial recursive function $f(n)$
by a program operating on two integers $S_1$ and $S_2$
using instructions $I_j$ of the forms:
(i) ADD 1 to $S_j$, and go to $I_{j_1}$
(ii) SUBTRACT 1 from $S_j$, if $S_j \neq 0$ and go to $I_{j_1}$, otherwise go to $I_{j_2}$
That is, we can construct such a program that starts with $S_1 = 2^n$ and $S_2 = 0$ and
eventually stops with $S_1 = 2^{f(n)}$ and $S_2 = 0$

If you have a two way DFA with one counter over a (semi)infinite tape where the input is given in unary: $\$1^{2^n}000...$ then the DFA can:

read the unary input (and store it in the counter);
work on the $0^\infty$ part of the tape and use the distance from the $1$s as the second counter.

so it can simulate a Turing complete two counters machine.

Now, if you have a recursive function $f(n)$ that runs in time $T(n)$ on a standard Turing machine, a two way DFA with one counter that starts on the finite tape $\$1^m\$ \;$ (where $m = 2^n3^{T'(n)}$ and $T'(n) \gg T(n)$) can:

read the unary input (and store it in the counter);
return to leftmost symbol;
divide the counter by 3 until the counter contains $2^n$ in this way: go right looping from states $q_{z_0}, q_{z_1}, q_{z_2}$ and subtracting 1; if counter reaches 0 in state $q_{z_0}$ go to leftmost symbol adding +1 and continue the division loop, otherwise add 1 (if in state $q_{z_1}$) or 2 (if in state $q_{z_2}$) and go to leftmost symbol adding +3 (i.e. recover the previous value of the counter not divisible by 3) and proceed with step 4.;
at this point the counter contains $2^n$;
calculate $2^{f(n)}$ using the $T'(n)$ space available on the right as the second counter (the value of the second counter is the distance from the leftmost symbol $\$$).

So with the special input encoding described above that gives it enough space on the finite tape, a two-way DFA with one counter and unary alphabet can compute every recursive function.

If the approach is correct, it would be interesting to reason about how to choose $T'(n) \gg T(n)$ or when it is enough to pick a large odd $k \gg 2$ and encode the input as $1^m$, $m = 2^n k^n$


Alternative proofs of Schwartz–Zippel lemma

As a followup to Per Vognsen's answer, Dana Moshkovitz's proof already suggests a really easy proof for only a slightly weaker version of the Schwartz-Zippel Lemma that, I think, suffices for most applications.

Let $f : \mathbb{F}^n \to \mathbb{F}$ be a nonzero polynomial of degree $d$, where $\mathbb{F}$ is a finite field of order $q$, and let $x \in \mathbb{F}^n$ be a point such that $f(x) \neq 0$.  There are $(q^n-1)/(q-1)$ many distinct lines passing through $x$ such that they partition $\mathbb{F}^n-\{x\}$.  The restriction of $f$ to each of these lines is a degree $d$ univariate polynomial, which is nonzero, because it is nonzero at $x$, and so, has at most $d$ zeros.  Thus, the total number of zeros of $f$ is at most $d(q^n-1)/(q-1)$.  Schwartz-Zippel, for comparison, gives the stronger upper bound of $d q^{n-1}$.

Given this proof's easiness, I'm sure it's folklore; if not, it should be :)  I'd appreciate if someone could provide a reference.


Complexity of a GLR parser on an ambiguous grammar

This example grammar is worst case ambiguity, unless I do not
understand what you mean by worst case ambiguity. Why do you think it
should not be? Try to analyse $a+a+a+a+a$.

It's time complexity is $O(n^3)$ with any general CF parser, such as
CKY, Earley, GLR, GLL, etc. However, you need only $O(n^2)$ space if
you do not keep parse-tree information (though I would have to check how you manage not to keep it in GLR ... it may require minor modification).

But then, if you are not interested in parse-trees, but only in
recognition, you should forget ambiguities, and just change it for a
regular grammar that recognizes the same language, in linear time.

Reasonning with GLR is a bit of a pain. But you can do it easily
enough with CKY. There is no essential difference in principle (see
the second part of my answer to a previous question), but reasonning
with the more complex construction of GLR is more obfuscated.

Alternatively, take the code of a GLR parser, and add counters in
proper places. Then run a few example and you will see that it checks
with $O(n^3)$. The last reference of the question I answered actually
did that (though I do not recall which general CF parser flavors they
tried).

Answering comments, and sketching a proof:

Regarding worst case grammar, you suggest $S \rightarrow SSS \mid SS
\mid a$ given in a paper by Mark Johnson.  I do not have the paper
handy, but my guess is that he uses the $S \rightarrow SSS$ rule to
show that the complexity will $O(n^4)$ unless specific steps are taken
to binarize this rule (there are actually 2 ways to do it). The reason
is that the polynomial complexity exponent can be the length of the
longest right hand side (RHS), at least in non terminals. So he
deliberately uses a RHS with 3 non-terminals. Your example grammar
does not have that problem, and in that sense you can indeed consider
that it is not as bad. Johnson's example would be even worse with a RHS of length 4, or more.

I questioned your "not a worst case" statement because, it is easy to bring time complexity
down to $O(n^3)$ by binarization of right-hand sides, which is straightforward and changes
the trees only in an obvious and very readable way. However, in the
current state of the art, you cannot go below $O(n^3)$, unless you use
very complex recognition techniques that do not give you parse trees
and are based on a reduction to matrix multiplication as
shown by Leslie Valiant in 1974.  Since then, the theoretical
complexity of these multiplication algorithms has gone down fron the
$O(n^{2.807})$ of Strassen algorithm to $O(n^{2.373})$ of Williams
algorithm, though those faster than Strassen are unusable in practice.
It is not known (afaik) whether this bound can be brought down further.
These bounds can certainly apply to your grammar, as well as they do
to all others, but I would not call it "parsing".

Going back to the more classical parsing algorithms, I guess one can
give a common proof based on the following remark: all classical
parsing algorithms are based on the (non-deterministic) pushdown
automaton (PDA) model (it is not always very visible, but it is always
there). The deterministic algorithms, like precedence, LR(k) or LL(k)
and their variants are just deterministic PDAs built in some
systematic way (when possible), that correspond to a technique using
the grammar to walk the (unique) parse-tree as efficiently as
possible. These techniques are limited to subclasses of CF grammars
and languages.

The general context-free parsing algorithms can handle all CF grammars
and languages. They are usually built using the very same techniques,
but the consruction accepts that there may be conflicts in the the
steps to be applied. These conflicts are simply non-deterministic
choices. But the construction is basically the same as in the deterministic case. That means that
the resulting non-deterministic PDA can walk all possible parse-trees,
sometimes having to walk parse-tree fragments that do not belong to a
full parse-tree (for example in unambiguous CF languages that are not
deterministic).

So these algorithms walk all parse-trees, independently of whether
they actually produce these parse-trees as output. There may be
exponentially many (even sometimes infinitely many) such parse trees.
The General CF parsers use a tabular (dynamic programming /
memoization) technique to share computation, in order to do the work
a bit faster. They all use the same tabular technique (from an
abstract point of view) and get all the same worst case complexity
$O(n^3)$. They may however differ on some example, for example if a
grammar falls in the domain wherhe one PDA construction gives a
dterministic PDA, while another does not. But they all have $O(n^3)$
time complexity when there are exponentially many parse trees as in
your example.

I do not believe I ever encountered a parsing algorithm that does not
fall in this schematic description (up to some bells and whistles). This is essentially the basis of the work in the Billot & Lang paper cited above.

Now, as I said, if you are not interested in parse-tree, you can
always modify one of these algorithms to do better in some cases. For
example, as I said, the rules $S \rightarrow SS \mid a$ could be
noticed by the recognizer (no longer parser) construction
technique, and replaced by the simpler rules $S \rightarrow aS \mid
a$. But then it is no longer the same "parsing" algorithm.

For an analysis of tree sharing into forests and the effect on parsing complexity, you may want to read
"Observations on Context Free Parsing" by Beau Sheil In Statistical
Methods in Linguistics, 1976:71-109. The point is that all general CF
parsing algorithms walk this shared forest completely. And it has size
$O(n^3)$ for your example grammar.


Effect of constraints Density on the hardness of Betweness problem

As mentioned in the comments, the case with $\Theta(\log n)$ clauses is in PTIME. The other cases are NP complete.

From Chor&Sudan, we know that solving Betweenness instances with $m\in\Theta(n)$ clauses is NP complete (as they present a gadget reduction from gap-E3SAT instances with a linear number of clauses). We also know that there are trivially-satisfiable instances with up to $\Theta(n^3)$ constraints. We can therefore reduce the hard language of Betweenness instances with $m \in \Theta(n)$ to the language with $m \in \Theta(n^c)$ clauses, for any rational $0 < c \le 3$, simply by composing the hard instances with trivially-satisfiable instances of suitable density.

Chor and Sudan, 1998, A Geometric Approach to Betweenness.


Minimal-size extending set in a directed graph

There is a linear time algorithm.

Contract all strongly connected components, then you get a DAG.
Find all the source vertex in the DAG. For each source vertex in the DAG, pick a single vertex from the strongly connected component represented by the source vertex.


EDIT: I quickly completed the amateur proof that I started a few months ago and never finished.

You can download it in PDF format on my blog ... nobody has checked it yet, so refutations, comments and suggestions are welcome.

I don't know if there is an official proof, but a few months ago I built the gadgets to mimic a planar 3-CNF formula; for example the OR, SPLIT and TURN gadgets are:

I built/checked the gadgets using a simple constraint solver program.

The uniqueness of each row/column (rule 2) can be achieved marking them with a unique "binary number" using a 2x2 block that acts like a "digit":

01 = 0   10 = 1
10       01

And the equal number of 1s and 0s (rule 3) can be achieved mirroring the whole puzzle, and inverting the 0s with 1s (using special walls in the middle that allow the transition without breaking the rules):

  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....

So deciding if a partially filled $N \times N$ Binary Puzzle board has a solution, is NP-hard.

Like other similar puzzles it's not immediate to say that it is in NP (see for example the discussion on succinct Nurikabe on cstheory). However if the initial board is given as a full string $\{0,1,\bot\}^{N \times N}$ (the representation is not succinct), and you drop the the unique solution constraint (which is another rule of the game), then the problem is in NP (and thus NP-complete).


Computational complexity in quantitative finance

The question you begin with relates to predicting the stock market, but you seem to have broader concerns.  I'll attempt to tackle your meta-question; apologies in advance for my sweeping generalizations.

As far as I can tell, academic computer science is far removed from the actual concerns of hedge funds and people who try to model and predict markets.

The current focus areas in algorithmic game theory are not obviously relevant to finance practitioners.  In particular, worst case results are not seen as useful at all, and average case analysis based on artificial distributions seems largely irrelevant also.  Yet the only way to obtain information about real distributions seems to be to actually engage in the market, updating one's information using a variety of learning techniques.  This creates messy models that change dynamically and are not amenable to most types of analysis.

As an example, there has been a focus in finance on understanding the microstructure of trades.  Market microstructure is an emergent property of the specific low-level market mechanisms that are in place, such as how frequently pending trades are matched, what information traders believe exists in the order book, techniques used to obfuscate that information, the roll-back mechanisms in place, contractual arrangements relating to settling trades, network latency in receiving updates about the current state of the order book, and many other factors.  Market microstructure is a highly reflexive system, so the clean models typical of TCS seem beyond reach.

The market design community is trying to tackle questions like this (for instance see Huang and Stoll and the recent Kirilenko et al. paper on the flash crash), but they do not seem to have much interaction with TCS.

Finance has become increasingly complex as IT has pervaded markets.  This means that most markets now consist of multiple interlocking systems which it may not be possible to meaningfully model separately.  In addition, as markets move closer to continuous trading, I am not sure the TCS lens of computation is currently all that useful in finance; control theory, graphical models, fluid dynamics, and many other areas of applied mathematics seem more directly useful.

TCS methods could well be useful, but one needs to expend effort to understand what happens in finance, to find a place to apply the lever, and to acquire an appropriate mathematical toolkit.  Personally I would like to see more work along the lines of Arora/Barak/Brunnermeier/Ge, which engage with deep questions.  For instance, does adding more degrees of freedom to financial systems lead to good outcomes for the users of these systems?  Or does adding complexity mainly serve to help intermediaries set up asymmetric zero-sum games against the users?  There is probably a neat complexity-based argument waiting to be discovered...

So in a nutshell: you haven't seen much TCS/finance research because it is hard to apply TCS to finance.


I want an easy Gadget to prove Planar Hamiltonian Cycle NP-Complete (from Hamiltonian Cycle)

No.  At least, no "nice" gadget for one crossover.

Let $(a, b)$ and $(x,y)$ be a cross we want to replace.

There are many cases for our graph, $G$, but we have to satisfy at least the following four.  Case 1: there is at least one hamiltonian cycle, but none use either of the edges.  Case 2: there is at least one cycle, and all cycles use exactly one of the two edges.  Case 3: there is at least one cycle, and all cycles use both edges.  Case 4: there is no hamiltonian cycle.

If our gadget has two (or more) vertices for each of $a, b, x, y$ adjacent to all the same neighbors (so that $a_0$ and $a_1$ retain $a$'s neighbors) then $G'$ will not necessarily still be planar.  In order to satisfy the first of our cases above, we then cannot have any new vertices in the gadget.

In order to satisfy case 3 above, we must have at least two edges in the gadget.  Neither planar and covering pair, $(a, x), (y, b)$ nor $(a, y), (x, b)$ satisfies case 2, so we need a third edge.  Without loss of generality, let those three be $(a, y), (y, b), (x,b)$.

However, that replacement breaks the fourth case, because $G'$ could contain a hamiltonian cycle when $G$ does not.  Take, for example, $G = (V, E)$ where $V = \{a, b, x, y, p, q, r, s, t\},$ and
$E = \{(a, b), (x, y), (a, r), (a, p), (a, q), (b, s), (b, x), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$.  $G$ is not planar and does not have a hamiltonian cycle.

Then $G' = (V, E')$ where $E' = \{(a, y), (y, b), (x, b)\} \cup$
$\{(x, y), (a, r), (a, p), (a, q), (b, s), (p, s), (p, t), (p, y), (q, x), (r, y), (t, x)\}$.  $G'$ is planar, and has a hamiltonian cycle ($a, q, x, t, p, s, b, y, r, a$).

Note that if $(b, y)$ was the edge not added instead of $(a, x)$, then $G'$ would not have a hamiltonian cycle.  It seems that you'd have to have knowledge of the possible cycle to choose the edge correctly, though.

A similar problem exists for having the gadget include one of the diagonal edges, such as: $(a, b), (a, y), (x, b)$.

Since adding three edges breaks case 4, adding more won't help.

Thus, no "nice" gadget exists.  It could be that a gadget exists that pays more attention to the neighbors of each of $a, b, x$ and $y$, but that doesn't seem very "nice".

(Note: please let me know if I made any errors above!)

(Note 2: I had some nice figures, but can't post them.  Posted.)


How to translate general recursion into a set of $\mu$-recursive operator applications?

Klaus Draeger’s method can be fairly easily generalized, we just need one more piece to make it fully functional - a code stack. If we add in a code stack to the state, we can suddenly push things, or run multiple functions in one stack machine. The code would have only a few basic operators, a push operation and functions that are externally paired with a mu-recursive function. The mu-recursive functions take in some number of items from the top of the stack and return some items to be pushed to the stack and some code to be pushed to the code stack. To illustrate all of this, here’s an example of an addition function being defined within the machine. We will use two functions, the successor function and the addition function itself. The successor function is easy enough to define, just S(n) = <[S(n)],[]>, where <,> is the pairing function, the lists are encoded in the obvious way, and the S(n) within the definition is the standard successor function. The first list in the pair is what is pushed to the stack, and the second list is what is pushed to the code stack. More interestingly, the addition function is defined as +(0,m) = <[m],[]> and +(S n,m) = <[n,m],[+,S]>. The push operation is defined in the obvious way, push x pushes x to the stack and removes the instruction, as with every other instruction. One may ask after all this, “why is this modification required for everything but the ackermann function?” Well, simply, if you use this method to encode the ackermann function, you see that the only thing in the code stack at any point is just a string of ackermann functions, so you can simplify in the ackermann case, assume there’s nothing in the code stack but an infinite string of ackermann functions, and then eliminate the code stack entirely, using the empty stack to let you know once it’s finished evaluating.


Neural Networks: what's the point of learning features that don't linearly separate?

Indeed, one would like to construct features that make classes linearly separable. However, what patterns exactly should be linearly separable?

It is easy to make patterns in training set linearly separable by greatly increasing feature space dimensionality. However, this will not necessarily imply good generalization (correct classification of new patterns).  Quite opposite, it can lead to overfitting. Thus, it is problematic to use the criterion of linear separability directly to select good nonlinear features for classification.

Deep learning networks adopt different approach. They try to select features with good generalization of patterns irrelative to the classification task. Thus, “useful” nonlinear features are selected without danger of overfitting. Indeed, it doesn’t necessarily ensure linear separability of classes, but it makes sense from induction point of view. If one extract statistically independent factors from initial features, in which these factors are mixed, it will be easier to solve any further classification task.


The question this response was trying to answer, roughly: "What is a way to reveal information about the outcome of $n$ i.i.d. coin flips that helps you learn the bias of the coin, but wihout revealing too much about the individual bits?"

Since the bits are i.i.d., the numbers $h$ and $t$ (number each of heads and tails) are completely sufficient to describe what the sequence tells you about the bias of the coin. (Or if you know $n$, either number alone.) This follows because, for each possible parameter $p$, all sequences resulting in a particular count $(h,t)$ are equally likely. So revealing the individual bits adds no information about the bias of the coin once $h$ and $t$ are known. On the other hand, presumably you don't mind releasing $h$ and $t$ as they do not give too much information about any one bit flip.

As a sidenote, one way to approach this general sort of problem is differential privacy. I'm not sure that it's a good fit for your setting, but it formalizes the notion of how much one learns about data from computing some function on the data. The idea is that, if I have two sequences $x$ and $x'$ that differ only on a single bit (say the $i$th bit), then my function, which is randomized, should produce approximately the same distribution over outputs:

\begin{equation}
\Pr[f(x) = a] \leq e^{\varepsilon} \Pr[f(x') = a]
\end{equation}
for all $a$.


Selection algorithm on depth-$\text{O}(\log n)$ sorting network

You can construct selection networks of depth O(log n) using graph expanders or using variants of the AKS sorting network.

S. Jimbo and A. Maruoka, A Method of Constructing Selection Networks with $O(\log n)$ Depth,SIAM J. Comput. 25, pp. 709-739, http://dx.doi.org/10.1137/S0097539793248329


Consequences of $NP\subseteq P/poly$ to $BQP$

I'm not aware of any direct consequence of $NP\subset P/poly$ for $BQP$.  Of course it might lessen the interest in quantum computing, since it would mean that we could do something far more impressive with just good old classical nonuniformity than we could with quantum mechanics.  And it would imply $NP\subset BQP/poly$. :-)  OK, it would also weaken the arguments that BosonSampling, and other quantum sampling tasks of that kind, are classically hard.  For those arguments involve showing that if the sampling tasks can be done in classical polynomial time, then $PH$ collapses to the second or third level (along with several other strange things, like $P^{\#P}=BPP^{NP}$).  But if $NP\subset P/poly$, then $PH$ collapses anyway.


You could encode these into Horn Clauses (= Prolog) and use resolution (= Prolog's implementation technique).

More explicitly, your Prolog code file will look like the following:

add( 0,    N, N ).
add( succ(N), M, succ(Sum) ) :- add( N, M, Sum ).

Asking the following query at the command prompt in a prolog interpreter will give you an answer for X:

add( X, succ(succ(succ(succ(0)))), succ(succ(succ(succ(succ(succ(0))))))).

Which is:

X = succ(succ(0)) .

Using tracing within the Prolog interpreter will give you the series of substitutions used.

Fill all the gaps in yourself, and you will learn a lot.


The survey that Suresh pointed to brings up a paper by Wegener [1] that partially confirms the conjecture. It holds for all monotone graph properties and the inequality is tight (consider the property "Has no isolated vertices"). Any more recent results would be appreciated as well.

Wegener, L. The critical complexity of all (monotone) Boolean functions and monotone graph properties. Information and Control, 67:212-222, 1985.


decision tree complexity and query complexity

Chapters-3,4 in book Analysis of Boolean Functions by Ryan O'Donnell might be a good starting point.


Massive online collaboration for solving open problem in theoretical computer science

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See https://en.wikipedia.org/wiki/Polymath_Project#Problems_solved. As such, you would have to pick a problem of this nature in CS. The only one that comes immediately to mind is improving the constant in matrix multiplication https://en.wikipedia.org/wiki/Matrix_multiplication#Algorithms_for_efficient_matrix_multiplication, which is currently at 2.4... But frankly, I am not sure enough people care about it enough to work on it...

Questions for which I would expect polymath to fail miserably: P=NP, online optimality, UGC, etc.


The state-of-the-art for PCPs that yield a reduction to $(\frac{7}{8}+\varepsilon)$ 3-SAT (even for sub-constant $\varepsilon$) are those of Dana Moshkovitz and Ran Raz, which have length $n^{1 + o(1)}$. I do not know, however, if anyone tried to compute the exact dependence of the length on $\varepsilon$, or the computation complexity of the reduction. Their main technical result was simplified later by Irit Dinur and Prahladh Harsha.

If you are interested in short PCPs with a constant number of queries that do not necessarily give optimal hardness-of-approximation reductions (a.k.a. "high-error PCPs"), then the state-of-the-art result is PCPs of length $n\cdot \mathrm{poly}\log n$ due to Eli Ben-Sasson and Madhu Sudan and its improvement by Dinur. Again, I do not know if anyone what is the exact complexity of computing the reduction.


The complexity of sampling (approximately) the Fourier transform of a Boolean function

The Kushilevitz-Mansour algorithm in learning theory establishes, that whenever $\hat{f}(x)$ is approximately sparse, i.e. there are only $O(poly(n))$-many large Fourier coefficients of absolute value $\Omega(1/poly(n))$, then we can find their locations and approximate their complex values in $\sf{BPP}$. Of course you can also efficiently sample from that list. To be precise, Kushilevitz-Mansour only talked about Fourier transforms over $\mathbb{Z}_2$, but generalization to FTs over general finite Abelian groups (see e.g. Akavia's thesis) are known.

As an application of this to quantum computing, one can show that the output state of quantum circuits structured in blocks of Hadamard-Toffoli-Hadamard gates can be efficiently approximated given the promise that the output state written in the computational basis is approximately sparse (see my QIP'2010 poster here, and the pre-print here). If the sparsity assumption is dropped, we could simulate Simon's algorithm (or Shor's), which is of exactly that structure, contradicting the $\Omega(2^{n/2})$ query lower-bound for Simon's problem.


Inclusion probability of irregularly shaped polygon

The first thing to notice is that an $n$-vertex polygon polygon $B$ is inside circle $A$ if and only if all of the vertices of $B$ are inside $A$. (1)

So the solution to your problem is exactly the area of $n$ arbitrary intersecting circles, each of radius $r$ and centered at a vertex of $B$. (You then divide by $S$ to get the final probability).  There's an interesting blog about this problem here which includes some heuristic solutions which may be sufficient for your use case.

From a theoretical point of view, the furthest-point Voronoi diagram gives us a good starting point.  Let's look at a point $p$ inside a cell of the furthest-point Voronoi diagram.  We want to know if the circle $A$ centered at $p$ contains $B$.  By the above, this happens if and only if all vertices of $B$ are within distance $r$ of $p$.  Now, since we're inside a cell of the furthest-point Voronoi diagram, we can just test whether or not $p$ is within distance $r$ of that furthest point.

In particular, the area we want within a given Voronoi cell is the intersection of that Voronoi cell with a single circle of radius $r$.  This can be easily calculated in time linear in the number of edges of the cell.  Since the furthest-point Voronoi diagram has $O(n)$ cells with $O(n)$ total edges, this takes $O(n)$ time in total.

Then the total running time is dominated by the time to calculate the furthest-point Voronoi diagram, which is $O(n \log n)$. A similar strategy gives you an explicit region $C$ in the same amount of time.

(1): The "only if" direction is obvious.  To see the "if" direction, we can first note that by convexity if all vertices of $B$ are inside $A$, then all edges of $B$ must be as well.  The same argument then extends to all interior points of $B$ since they must lie on a line between two vertices or edges.


Oracle Construction for Grover's Algorithm

The oracle is basically just an implementation of the predicate you want to search for a satisfying solution to.

For example, suppose you have a 3-sat problem:

(¬x1 ∨ ¬x3 ∨ ¬x4) ∧
    (x2 ∨ x3 ∨ ¬x4) ∧
    (x1 ∨ ¬x2 ∨ x4) ∧
    (x1 ∨ x3 ∨ x4) ∧
    (¬x1 ∨ x2 ∨ ¬x3)

Or, in table form with each row being a 3-clause, x meaning "this variable false", o meaning "this variable true", and space meaning "not in clause":

1 2 3 4
-------
x   x x
  o o x
o x   o
x o x

Now make a circuit that computes whether the input is a solution, like this:

Now, to turn your circuit into an oracle, hit the output bit with a Z gate and uncompute any garbage you made (i.e. run the compute circuit in reverse order):

That's all there is to it. Compute the predicate, hit the result with a Z, uncompute the predicate. That's an oracle.

Iterate diffusion steps with oracle steps, and you've got yourself a grover search:

... although you should probably pick an example with fewer solutions, so the progress is gradual (instead of rotating along the start-state-solution-state plane by more than 90 degrees per step as my example is).


Optimal insertion times in insertion-only data structures beyond Bentley-Saxe

Think about your question in reverse: suppose you have a dynamic data structure for some problem — does that imply that you can solve it statically, faster by a log? Why should it? And in fact it is not true.

Consider range counting in one-dimensional intervals, in a comparison model of computation. That is, the data is a set $S$ of numbers, the query is an interval $[\ell,r]$, and the answer to a query is the size of $S\cap[\ell,r]$. Statically, you can solve it in $O(\log n)$ query time by storing $S$ as a sorted array and using binary search, in preprocessing time $P(n)=\Theta(n\log n)$. Dynamically, you can still solve it in $O(\log n)$ query time by using balanced binary search trees, with insertion time $O(\log n)=O(P(n)/n)$.


Best parameterized algorithm for maximum clique

Maximum clique in graphs with degree $d$ can be reduced to $n$ instances of maximum clique in a graph with at most $d$ vertices: for each vertex, compute maximum clique in the induced subgraph of the neighborhood of the vertex.

Therefore, if we omit polynomial factors, the time complexity of maximum clique in graphs with degree at most $d$ is the same as time complexity of maximum clique in graphs with $d$ vertices. I think currently the best known (and peer reviewed) algorithm works in $O(1.1996^n)$ time [1]. Confusingly, there also seems to be an older claimed result with $O(1.1892^n)$ time [2].

[1] M. Xiao and H. Nagamochi. Exact algorithms for maximum independent set.
Information and Computation, 255:126–146, 2017.

[2] J.M Robson. Finding a maximum independent set in time $O(2^{n/4})$. LaBRI, Université de Bordeaux I, Technical report, 2001.


Your problem is Maximum Common Edge Subgraph Problem (Max CES) defined as follows:
given two graphs $G$ and $G'$, find a graph $H$ with the maximum number of edges
that is isomorphic to a subgraph of $G$ and to a subgraph of $G'$.

Proof: You are finding a subgraph $H$ of $G$ isomorphic to a subgraph of $G'$,
where $|E_{G}| - |E_{H}|$ is minimized. Since $|E_{G}|$ is an invariant of $G$,
$|E_{G}| - |E_{H}|$ is minimized if and only if $|E_{H}|$ is maximized.
Clearly, $H$ is isomorphic to a subgraph of $G$ and to a subgraph of $G'$. Q.E.D.

Approximability. In the Ph.D thesis of Kann, I found the description
"not known to be approximable within a constant" [3] (p. 115).
In a recent paper by Bahiense et al. [1],
it is mentioned that if $|V_{G}|$ and $|V_{G'}|$ are not required to be equal,
the problem becomes APX-hard.
But the citation for this result is an unpublished private communication [2].

L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, to appear. doi:10.1016/j.dam.2012.01.026
M.M. Halldorsson, Personal communication, unpublished manuscript, 1994.
V. Kann. On the Approximability of NP-complete Optimization Problems. Ph.D. Thesis, NADA report TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf


Here is a proof using a well-known hammer.

Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges which are part of the spanning tree.

I claim that the treewidth of $G$ is $O(\sqrt{t})$ which would imply the desired separator (and some more). To prove the claim let $k$ be the treewidth of $G$. Then by a theorem of Robertson-Seymour-Thomas, since $G$ is planar, there is a grid minor of size $\Omega(k)$. However a grid minor of size $\Omega(k)$ has $\Omega(k^2)$ disjoint cycles and each of them requires one of the $t+1$ edges. Hence $k = O(\sqrt{t})$.


Example of $MSO_2$ definable NP-hard problem on bounded clique-width graphs

One example is the vertex disjoint paths problem, which is linear time solvable in graphs of bounded tree width but NPC in graphs of clique width at most $6$.


Can such machines be built in practice?

Yes. By "machine", Schmidhuber just means "computer program".
Are they at least feasible in our Universe?

Not in their current form -- the algorithms are too inefficient.

From a ten thousand meter perspective, Jürgen Schmidhuber (and former students, like Marcus Hutter) have been investigating the idea of combining Levin search with Bayesian reasoning to work out algorithms for general problem-solving.

The basic idea behind Levin search is that it's possible to use dovetailing and Goedel codes to give a single algorithm which is, up to constant factors, optimal. Loosely, you fix a Godel encoding of programs, and then run a Turing machine that runs the $n$-th program once every $2^{n}$ steps. This means that if the $n$-th program is optimal for some problem, then Levin search will "only" be a constant factor of $2^n$ times slower.

They have done a fair amount of work on making the constant factors less stupendously, horrifically awful, and are optimistic that this kind of scheme can work in practice. I am (based on my experience in automated theorem proving) very skeptical, since good data structures are critical to theorem proving, and Goedel encodings are terrible data structures.

But you don't know it can't work until you try to make it work! After all, we already live in a world where people solve problems by reduction to SAT.


Recursively enumerable, non-recursive language without using Gödel's number


Generalizing linear interpolation to posets

In a recent paper, we propose such a scheme. The scheme is illustated in a specific crowdsourcing application setting, but the idea is fairly simple. We just see the order constraint $\mu(u) \leq \mu(v)$ of each DAG edge $(u, v)$ as a linear inequality constraint, we consider the admissible convex polytope of assignments to these linear inequalities, and we choose the center of mass of this polytope as our interpolation result.

The paper explains the scheme in more detail, includes an algorithm, computational hardness results, an approximation scheme that derives from existing work, a tractable case when the DAG is a tree, and a discussion of alternate schemes.


Computational query complexity of SQ-learning

I've asked (myself) this question a while ago. At least for learning with respect to a specific distribution there is a fairly simple example of a concept class that is information theoretically SQ-learnable but is NP-hard to SQ learn. Let \phi  a binary encoding of a SAT instance and y be its lexicographically first satisfying assignment (or 0^n is the instance is unsatisfiable). Now let f(\phi) be a function that over one half of the domain is the MAJ(\phi) and over the second half of the domain equals PAR(y). Here MAJ is the majority function over variables which are set to 1 in the string \phi and PAR(y) is the parity function over variables which are set to 1 in the string y. Let F be the class of functions obtained in this way. To SQ learn F over the uniform distribution U one only needs to learn majorities (which is easy) to find \phi and then find y. On the other hand, it is fairly easy to reduce SAT to SQ learning of F (to any accuracy noticeably greater than 3/4) over the uniform distribution. The reason for this, naturally, is that parities are essentially "invisible" to SQs and hence it is necessary to solve SAT to learn F.


What are the general classes of measured systems

I don't think there will be any result of the form you want.  There's no single "most general system" that has this property.

(Instead, it'd be better to choose some specific pair of classes of systems you're interested in and ask specifically how to distinguish those two; that's more likely to yield an answerable question.)

To learn about work in the computer science literature that might be applicable to your situation, here are some subjects you should probably take a look at:

Total variation distance measures the "probability" with which we can distinguish two distributions, given a single sample from each, and assuming we have unlimited computational power.  (There are also other metrics.)
Computational indistinguishability, as studied in the cryptographic literature, measures the "probability" with which we can distinguish two distributions, assuming that the distinguishing algorithm is limited to some feasible amount of computation (e.g., no more than one billion CPU-years).

Your situation amounts to the following: we have a family of distributions $D_1(\theta_1)$ parameterized by $\theta_1$ (corresponding to systems of class A, where $\theta_1$ indicates which specific system instance we are working with) and a family of distributions $D_2(\theta_2)$ parameterized by $\theta_2$ (corresponding to systems of class B, where $\theta_2$ indicates the specific instance).  The observer doesn't know $\theta_1,\theta_2$ but gets to observe either a single value sampled from distribution $D_1(\theta_1)$ or a single value $D_2(\theta_2)$, and wants to try to distinguish which of those two types of values he has been given.
You want to know whether, for all $\theta_1,\theta_2$, it's always possible to distinguish with good probability (say, better than guessing).

The special case of this is: given two distributions $D_1,D_2$, if the observe gets to observe either a single value sampled from $D_1$ or a single value sampled from $D_2$, can the observe distinguish which of those two types of values he has been given?  That's been studied carefully.  If there are no limits on the computational power of the algorithm used by the observer, the answer is characterized by the total variation distance.  If the observer is limited to use a computationally-feasible algorithm, the answer is characterized by computational distinguishability.

For the case of a family of distributions, the answer will be characterized by

$$\min \{d(D_1(\theta),D_2(\theta_2) : \theta_1,\theta_2\}$$

where $d(\cdot,\cdot)$ is some appropriate distance measure (total variation distance, computational distinguishability).

There's also a corresponding theory about what happens if the observer gets to see $n$ samples drawn independently from the chosen distribution.


There is an optimal edit sequence in which the edit operations occur in order from left to right.  There are only three options for the last edit operation: insert the last character of the target string, delete the last character of the source string, or replace the last character.  Everything before the last edit operation must be optimal.

See section 3.7 of this textbook.


On the paper "Quantum Computing Hamiltonian cycles"

I emailed the author.
He replied "yes that paper is wrong!".
He has lost the passwords to remove it from the web.


Is there any problem which is in AWPP but conjectured to be not in BQP?

The relationship of $\mathsf{AWPP}$ to $\mathsf{BQP}$

$\mathsf{AWPP}$ is the class of languages $L$ for which, for each $\varepsilon \in 2^{-O(\mathop{\mathrm{poly}} n)}$,
there is $g \in \mathsf{GapP}$ and $f \in \mathsf{FP}$,
such that

for $x \notin L$ we have $0 \leqslant \frac{g(x)}{f(x)} \leqslant \varepsilon$ and
for $x \in L$ we have $1-\varepsilon \leqslant \frac{g(x)}{f(x)} \leqslant 1$.

This is a [technical but relatively well-known] upper bound for the class $\mathsf{BQP}$. Its relationship to other "gap-defined classes" could be summarised as
$$ \mathsf{SPP \subseteq LWPP \subseteq WPP \subseteq AWPP \subseteq PP}, $$
where $\mathsf{LWPP}$ is notable as a [once more technical but relatively-well known] upper bound on $\mathsf{EQP}$ (with algebraic coefficients over any constant set), and $\mathsf{SPP}$ is the gap-definable version of $\mathsf{UP}$. Thus all of these contain $\mathrm{UNIQUE\text-SAT}$.
By Valiant-Vazirani and the closure of $\mathsf{BQP}$ under subroutines, if $\mathrm{UNIQUE\text-SAT} \in \mathsf{BQP}$, we then have $\mathsf{NP \subseteq PH \subseteq BQP}$. We may reasonably consider this to be unlikely, so $\mathrm{UNIQUE\text-SAT}$ is an easy example of a problem in $\mathsf{AWPP}$ which one may consider unlikely to be in $\mathsf{BQP}$ (albeit a problem which belongs to classes which "seem much smaller" than $\mathsf{AWPP}$ as well).
The relationship of $\mathsf{MQ^2}$ to $\mathsf{BQP}$
The class $\mathsf{AWPP}$ also upper bounds the following (not generally well-known) class defined by Tušarová [arXiv:cs/0507057]:

$\mathsf{MQ^2}$ is the class of languages $L$ for which there is

a [concisely] poly-time computable family $\bigl\{ T_n \bigr\}_{n \geqslant 1}$ of unitary matrices [i.e. a family of matrices $T_n$ such that the function $(j,k,n) \mapsto \left\langle j \:\!\right\vert \!\!\; T_n \!\!\;\left\vert \:\!k \right\rangle$ can be computed in polynomial time, and where we probably want to impose the restriction to functions computing coefficients over a finite-degree extension of the rational numbers]

a poly-time computable string-valued function $I$, and

a poly-time computable predicate $\alpha$ on strings,

such that $\displaystyle\sum_{c : \alpha(c,x) = L(x)} \Bigl\vert\langle c \:\!\lvert\;\! T^2 \!\!\:\ \rvert I(x) \rangle\Bigr\vert^2 \geqslant \tfrac{2}{3}$  [the exponent on the $T$ is significant here].

(In the definition above, we let $L(x) \in \{0,1\}$ denote the characteristic function of $L$.)
The functions $I$ and $\alpha$ serve the role of classical pre-processing and post-processing, respectively, in a quantum algorithm in which we have somehow managed to perform a quite possibly complicated unitary, twice in succession.
The input state $\lvert I(x) \rangle$ is a standard basis state which could be efficiently computed by deterministic classical computation, and $\alpha$ serves to deterministically compute whether a possible measurement outcome $\lvert c \rangle$ is a possible "accepting state" for the problem instance $x$.
It is not clear that $\mathsf{MQ^2}$ is comparable to $\mathsf{BQP}$. The operator $T$ in the definition of $\mathsf{MQ^2}$ is specified by its coefficients rather than as a tensor network, so Solovay–Kitaev does not suffice to allow $\mathsf{BQP}$ to simulate such operators; and clearly we do not expect the coefficients of a tensor network such as a quantum circuit family to be easily evaluated, so the reverse containment would also be surprising.
The class $\mathsf{MQ^2}$ is itself not really well-known enough for there to be any common conjectures about it. (This question is the only place I'm aware of it being discussed, apart from the eprint by Tušarová.) But I get the impression that if the native problem of $\mathsf{MQ^2}$ — that of simulating (the square of) an exponentially large matrix with efficiently specifiable coefficients — is in $\mathsf{BQP}$, the techniques used to show this may have important implications for quantum circuit synthesis, and may shed light on the question of $\mathsf{BQP \mathrel{?\!\!\:=} BPP^{BQNC}}$. Thus, if not unlikely, this result would be quite interesting.


Translation of Counter-free automata into Linear Temporal Logic

As mentioned in the comments, the translation is shown in:
Diekert, Volker, and Paul Gastin. "First-order definable languages." (2008)
http://www.lsv.fr/Publis/PAPERS/PDF/DG-WT08.pdf
And it goes via a characterization of $LTL$ as $FO[<]$.


The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time
B. Saha, "The Dyck Language Edit Distance Problem in Near-Linear Time," 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 611-620, doi: 10.1109/FOCS.2014.71.
Indeed, the problem is easy for $s=1$. For $s\ge2$ the exact complexity is not known. The classical techniques for correcting context-free languages are $O(sn^3)$ (Valiant 1975). On the other hand, the usual string editing problem which can be solved in quadratic time can be reduced to Dyck($s$).
Saha's result gives a nearly linear time algorithm that returns an approximation of the true edit distance. I am not sure whether this algorithm can produce the edit sequence.


"Verifiable information": is this a known concept?

$K\subseteq\{0,1\}^\omega$ is $\mathsf{R}$-verifiable if and only if $K$ is a $\Pi^0_1$ class (in Cantor space), a concept that has been studied extensively in computability-theory. They are also called effectively closed sets.

A set $K$ is a $\Pi^0_1$ class iff it is the set of infinite paths through a recursive (computable) tree, and this is the version of the concept that you defined.

A monograph devoted to them:

Effectively Closed Sets (Douglas Cenzer and Jeffrey B. Remmel), Perspectives in Logic, Cambridge U. Press, 350 pages, to appear.


What evidence do we have for (and against) Unique Games Conjecture?

Khot gave a UGC survey talk at CCC 2010. The write-up is here. The final segment (bottom of page 30) has his opinions on this question.


What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"

In this context, uniformity usually means that there exists an algorithm/Turing machine computing the thing that is being called uniform. That is, in this case, that there is a Turing machine that will compute $i,j$ from (Turing machines for) $f,g$.
More formally (in the context of the paper), it means:
There is a Turing machine $B$ such that, for any total Turing machines $F,G$, where $G$ has infinite range, $B(F,G)=(i,j)$ such that...


How can theoretical modelling be converted into viable product?

I'm assuming that you're really asking, "how do I do something useful with modelling and theory."

The easiest answer is to work in a modelling and simulation field that makes useful products. Computational Electromagnetics is used a lot in RF, Finite Element Analysis is used in mechanical product design.

The broken part of your reasoning is that "more expertise = more practically useful." This is wrong. Usefulness is an instrinsic property of a task. A task is either useful or not useful. Expertise is only important in as much it allows you to perform a task. Therefore, you need to:

Pick a useful task
Have enough expertise to perform that task.

Sounds obvious, but perhaps it isn't.


Parity is a regular language not computable in NLOGTIME, or even in nonuniform AC^0. The set of all strings whose length is a power of 2 is a non-regular language computable in DLOGTIME.


Optimization problems with same optimal value, but different approximation behavior

What about something like minimum vertex cover vs. minimum fractional vertex cover (i.e., optimal solution of the LP relaxation of the vertex cover problem) in bipartite graphs?

These two problems have the same optimal value.

However, if I give you a black-box algorithm that finds a $(1+\epsilon)$-approximation of the minimum fractional vertex cover, this does not help much if you would like to output a $(1+\epsilon)$-approximation of the minimum vertex cover.

This can be formalized in some sufficiently weak models of computation. For example, if we look at distributed algorithms, one can show that a $(1+\epsilon)$-approximation of the minimum fractional vertex cover is easy to find, while a $(1+\epsilon)$-approximation of the minimum vertex cover is hard to find in bipartite graphs. (Here "easy" is e.g. constant time in the LOCAL model and "hard" is e.g. at least logarithmic time in the same model, assuming a sufficiently small constant $\epsilon > 0$ and some constant upper bound on the maximum degree. So there cannot be e.g. constant-time approximation-preserving LOCAL model reductions between the two problems, even if the optimum is the same.)


A special class of languages: “circular” languages. Is it known?

In the first part, we show an exponential algorithm for deciding circularity. In the second part, we show that this the problem is coNP-hard. In the third part, we show that every circular language is a union of languages of the form $r^+$ (here $r$ could be the empty regexp); the union is not necessarily disjoint. In the fourth part, we exhibit a circular language which cannot be written as a disjoint sum $\sum r_i^+$.

Edit: Incorporated some corrections following Mark's comments. In particular, my earlier claims that circularity is coNP-complete or NP-hard are corrected.

Edit: Corrected normal form from $\sum r_i^*$ to $\sum r_i^+$. Exhibited an "inherently ambiguous" language.

Continuing Peter Taylor's comment, here's how to decide (extremely inefficiently) whether a language is circular given its DFA. Construct a new DFA whose states are $n$-tuples of the old states. This new DFA runs $n$ copies of the old DFA in parallel.

If the language is not circular then there is a word $w$ such that if we run it through the DFA repeatedly, starting with the initial state $s_0$, then we get states $s_1,\ldots,s_n$ such that $s_1$ is accepting but one of the other ones is not accepting (if all of them are accepting then then the sequence $s_0,\ldots,s_n$ must cycle so that $w^*$ is always in the language). In other words, we have a path from $s_0,\ldots,s_{n-1}$ to $s_1,\ldots,s_n$ where $s_1$ is accepting but one of the others is not accepting. Conversely, if the language is circular then that cannot happen.

So we've reduced the problem to a simple directed reachability test (just check all possible "bad" $n$-tuples).

The problem of circularity is coNP-hard. Suppose we're given a 3SAT instance with $n$ variables $\vec{x}$ and $m$ clauses $C_1,\ldots,C_m$. We can assume that $n = m$ (add dummy variables) and that $n$ is prime (otherwise find a prime between $n$ and $2n$ using AKS primality testing, and add dummy variables and clauses).

Consider the following language: "the input is not of the form $\vec{x}_1 \cdots \vec{x}_n$ where $\vec{x}_i$ is a satisfying assignment for $C_i$". It is easy to construct an $O(n^2)$ DFA for this language. If the language is not circular then there is a word $w$ in the language, some power of which is not in the language. Since the only words not in the language have length $n^2$, $w$ must be of length $1$ or $n$. If it is of length $1$, consider $w^n$ instead (it is still in the language), so that $w$ is in the language and $w^n$ is not in the language. The fact that $w^n$ is not in the language means that $w$ is a satisfying assignment.

Conversely, any satisfying assignment translates to a word proving the non-circularity of the language: the satisfying assignment $w$ belongs to the language but $w^n$ does not. Thus the language is circular iff the 3SAT instance is unsatisfiable.

In this part, we discuss a normal form for circular languages. Consider some DFA for a circular language $L$. A sequence $C = C_0,\ldots$ is real if $C_0 = s$ (the initial state), all other states are accepting, and $C_i = C_j$ implies $C_{i+1} = C_{j+1}$. Thus every real sequence is eventually periodic, and there are only finitely many real sequences (since the DFA has finitely many states).

We say that a word behaves according to $C$ if the word takes the DFA from state $c_i$ to state $c_{i+1}$, for all $i$. The set of all such words $E(C)$ is regular (the argument is similar to the first part of this answer). Note that $E(C)$ is a subset of $L$.

Given a real sequence $C$, define $C^k$ to be the sequence $C^k(t) = C(kt)$. The sequence $C^k$ is also real. Since there are only finitely many different sequences $C^k$, the language $D(C)$ which is the union of all $E(C^k)$ is also regular.

We claim that $D(C)$ has the property that if $x,y \in D(C)$ then $xy \in D(C)$. Indeed, suppose that $x \in C^k$ and $y \in C^l$. Then $xy \in C^{k+l}$. Thus $D(C) = D(C)^+$ can be written in the form $r^+$ for some regular expression $r$.

Every word $w$ in the language corresponds to some real sequence $C$, i.e. there exists a real sequence $C$ that $w$ behaves according to. Thus $L$ is the union of $D(C)$ over all real sequence $C$. Therefore every circular language has a representation of the form $\sum r_i^+$. Conversely, every such language is circular (trivially).

Consider the circular language $L$ of all words over $a,b$ that contain either an even number or $a$'s or an even number of $b$'s (or both). We show that it cannot be written as a disjoint sum $\sum r_i^+$; by "disjoint" we mean that $r_i^+ \cap r_j^+ = \varnothing$.

Let $N_i$ be the size of the some DFA for $r_i^+$, and $N > \max N_i$ be some odd integer. Consider $x = a^N b^{N!}$. Since $x \in L$, $x \in r_i^+$ for some $i$. By the pumping lemma, we can pump a prefix of $x$ of length at most $N$. Thus $r_i^+$ generates $z = a^{N!} b^{N!}$. Similarly, $y = a^{N!} b^N$ is generated by some $r_j^+$, which also generates $z$. Note that $i \neq j$ since $xy \notin L$. Thus the representation cannot be disjoint.


Properties of convex polytope of 0-1 matrices

Sasho already gave you a yes/no answer, but here's an actual convex combination for you: If $B_\ell$ is the $k \times k$ matrix which is $1$ when $|S_i \cap S_j| \ge \ell$ and zero otherwise, then $M = \sum_{\ell=1}^{n'} \frac{1}{n'} B_\ell$.


Arguments for existence of one-way functions

Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map:

$$(x, r) \rightarrow s$$

where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random bits as you need) and $s$ is a $k$-SAT problem having $x$ as a planted solution, where the random number generator determines exactly which $k$-SAT problem you choose. To invert this one-way function, you need to solve a $k$-SAT problem with a planted solution.

This argument shows that inverting a one-way function is as hard as solving $k$-SAT problems with planted solutions. And since $k$-SAT is an NP-complete problem, if you can figure out how to construct hard instances with planted solutions for any NP problem, you can plant solutions in $k$-SAT formulas.

It has not been proven that it's possible to come up with a class of NP-complete problems with planted solutions that are just as hard as arbitrary NP-complete problems (and even if this is true, it's going to be incredibly hard to prove), but people definitely know how to plant solutions in $k$-SAT problems in ways that nobody currently knows how to solve.

ADDED: I now realize that this connection was already given (in more detail) in Abadi, Allender, Broder, Feigenbaum, and Hemachandra; they point out that one-way functions can give solved hard instances of SAT, and vice versa.

Putting it in more informal language, the non-existence of one-way functions shows that truly hard puzzles can't exist. If there is a type of puzzle where somebody can come up with both a puzzle and its solution algorithmically, then there is also a polynomial-time algorithm for finding a solution to the puzzle. This seems very counter-intuitive to me. Of course, a polynomial gap could exist; it might be the case that if creating the puzzle took $n$ steps, then solving it might take $O(n^3)$ steps. However, my intuition says that there should be a superpolynomial gap.


Questions about regular languages and their sublanguages

3) It is undecidable to know whether a given context-free grammar generates a regular language. So even for context-free languages, you are in trouble.


Travelling Salesman Problem where a subset of the nodes must be visited in a particular order

This is a special case of the precedence-constrained TSP which has been studied quite a lot. For instance, there are a polyhedral analysis by Balas, Fischetti and Pulleyblank, and a branch-and-cut algorithm by Ascheuer, Jünger and Reinelt.


It follows from work of Valiant [1, 2] that linear-size $\textrm{NC}^1$ can be simulated by $2^{O(n / \log \log n)}$-size circuits of depth three and unbounded fan-in.

For a nice exposition of this result, see section 3 of the survey by Viola [3].

[1] Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In: Mathematical Foundations of Computer Science 1977. MFCS 1977. Lecture Notes in Computer Science, vol 53. Springer, Berlin, Heidelberg.

[2] Leslie G. Valiant. Exponential lower bounds for restricted monotone circuits. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing (STOC '83). ACM, New York, NY, USA, 110-117.

[3] Emanuele Viola. On the power of small-depth computation
. Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 1--72, 2009.


When we say that a monotone machine is a set $L$ of pairs of strings $(x,y)$, the first component $x$ is the part of the input tape being read in order to produce the output $y$.

This set is c.e. (computably enumerable) because we can run computations with all (finite parts of) oracles in parallel, and watch for pairs $(x,y)$ where this happens.

The condition that if $(x,y)\in L$, $(x',y')\in L$ and $x\preceq x'$ then $y\preceq y'$ or $y'\preceq y$ just says that we have consistency, i.e., if you see more of the input bits you can't go back and say that you now outputted something different on an earlier input after all.

Conversely, given such a c.e. set we can produce a machine that monitors the c.e. set $L$ and looks for pairs $(x,y)$ entering $L$, and checks whether $x$ is a prefix of what's on the input tape given to the machine. If so, it extends its output string to $y$.