When are two algorithms said to be "similar"?

It is a tough problem to give even a coherent definition of "Algorithm A is similar to Algorithm B". For one, I don't think that "they must be solving the same problem" is a necessary condition. Often when one says in a paper that "the algorithm $A$ of Theorem $2$ is similar to the algorithm $B$ in Theorem $1$", the algorithm $A$ is actually solving a different problem than that of $B$, but has some minor modifications to handle the new problem.

Even trying to determine what it means for two algorithms to be the same is an interesting and difficult problem. See the paper "When are two algorithms the same?" http://research.microsoft.com/~gurevich/Opera/192.pdf


What applications of Cantor space are there?

It is used heavily in algorithmic information theory. For example, if you want to define random sequence with respect to a particular measure, you should first define this measure on Borel sets of cantor space.

Compactness of Cantor tree is used implicitly or explicitly in compactness arguments in combinatorics (in particular, it is used in the proof of compactness theorem for boolean functions).


Boundary between decidability and undecidability for small theories

Let $V_k (n)$ be the function that maps $n$ to the largest power of $k$ dividing $n$.  (Not the exponent of the largest power; the largest power itself.)  It follows from the work of Büchi (as corrected by, e.g., Hodgson) that the first-order theory Th($N, +, V_k$) for fixed integer $k \geq 2$ is decidable.  But Villemaire showed (￼Theoretical Computer Science 106 (1992), 337-349) that Th($N, +, V_k, V_l$) is undecidable if $k, l$ are multiplicatively independent.  So this is a nice boundary between decidable and undecidable.

The survey paper of Bès (available here:  http://lacl.univ-paris12.fr/bes/publi/survey.ps ) makes good reading!


A question of relationships between #P and PSPACE

It is already known that Sharp-P is contained in PSPACE. You are claiming that what you wrote shows that PSPACE is contained in Sharp-P. To do that, you would need to simulate TQBF formula with a Sharp-P oracle. What you wrote does not do that!


Problems that are hard to prove in $\mathcal{P}$

The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.


Why does the Placid Platypus function grow faster than any computable function?

The function $PP(n)$ is essentially the Kolmogorov complexity of the number $n$, and is non-computable by standard arguments, which I present below.

Suppose to the contrary that $PP$
is computable. Then so is the function $f:k\mapsto n$ that maps a number $k\in\mathbb{N}$
to the least integer $n$ such that $PP(n)>k$. (Such an $n$ always exists by simple counting arguments.)
If $PP$ is computable then so is $f$.

Now define the Turing machine $M$ as follows:
$M$ prints $f(|M|)$ ones, where $|M|$ is the number of states in $M$.
Thus, $M$ has size $\ell=|M|$,
and it prints
a string of $\ell$ ones.
By construction, $PP(\ell)>\ell$,
and so
$\ell$
ones cannot be printed by any TM with $\ell$ states or fewer.
Contradiction.


What is known about the effectiveness of reliable computing?

While there are some techniques that can be applied to fault-tolerance for all models, how resistant a computational model is to fault tolerance depends on the model. For instance, Peter Gacs has done quite a bit of research with fault tolerance on cellular automata, and he shows that (with a lot of work) you can build fault-tolerant cellular automata.

Von Neumann proved that by using redundancy, you could build a reliable computer out of unreliable components using only logarithmic overhead.

For quantum computation, quantum circuits can be made fault tolerant with polylogarithmic overhead ($\log^c n$ overhead, where finding the correct value of $c$ is still open). Another open question for quantum computation is whether adiabatic quantum computation can be made fault tolerant in a physically reasonable manner (physically reasonable means it is possible that the method leads to a scalable adiabatic quantum computer; for example, you're not allowed to take the temperature to 0 as the size of the computation gets larger).


How can algorithms with nested combinatorial searches be quasi-linear?

As I see it, that is a combinatorial problem, i.e. exhausting which number and composition of vertices constitutes a suitable set.

No, it's just a selection problem, for which there are well-known linear algorithms.


What's the simplest to implement of all decent LTL-to-Buchi translation or other LTL verification algorithms?

One construction not listed on the SPOT website is given in a survey by Demri & Gastin, Specification and Verification using Temporal Logics, 2009.  The construction is simple and yields reasonably small automata, so it can be carried out by hand for small formulæ, which is good for teaching (which is how I use it), but might also be helpful for debugging an implementation.  I wouldn't bet on it being more efficient than the one used by SPOT though.

About minimization, there is no canonical minimal Büchi automaton for a given $\omega$-regular language.  In order to get smaller automata, one can quotient the automaton by some simulation relation.  A classical paper on the subject is by Etessami, Wilke & Schuller, Fair Simulation Relations, Parity Games, and State Space Reduction for Büchi Automata, SIAM Journal on Computing 34: 1159--1175, 2005.


What is the motivation behind the definition of pseudorandom in Nisan/Wigderson?

There are two aspect that need to be mentioned.

The first is the general idea of defining a PRG by having its output look different than uniform to small circuits. This idea goes back to Yao and is really the strongest possible definition you can ask for when aiming explicitly at pseudo-randomness for computationally-bounded observers.

The second aspect is the choice of parameters where we limit the circuit size to be $n$ and the acceptance probability difference to be $1/n$, where $n$ is also the PRG output size. This choice is somewhat different than the usual crypto one where the circuit size is $poly(n)$ and the probability difference is required to be smaller than any $poly(n)$.  In our case specific parameters (rather than $poly(n)$) were needed as to get the tightest results including, in particular polynomial simulations.  While in principle one could have 3 different parameters, it turned out that our results had these working essentially in the same way so we folded them to a single one (in addition to the input size $l(n)$ which was viewed as a function of $n$).


Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

Josh's answer uses two conjectures and
both of them are considered to be highly likely to be correct by experts
even if not proven yet.
A positive answer means that at least one of the two conjecture is incorrect.
That would be a major very surprising result.
In other words,
it is highly unlikely that the answer to your question is positive, and
even if the answer is positive,
it is not possible to prove it at this time
(otherwise we would have already refuted one of those conjectures).


Computing the approximate population of a bloom filter

Yes.  From Wikipedia:

If you have inserted $i$ elements into a filter of size $n$ using $k$ hash functions, the probability that a certain bit is still 0 is

$$
z = \left(1 - \frac{1}{n}\right)^{ki}
$$

You can measure this probability as the proportion of 0 bits in your filter.  Solving for $i$ gives

$$
i = \frac{\ln(z)}{k\ln\left(1 - \frac{1}{n}\right)}
$$

I have used this in practice, and as long as your filter does not exceed its capacity, the error is generally less than 0.1% for filters up to millions of bits.  As the filter exceeds its capacity, the error of course goes up.


I see the confusion, but I think the document you provided pretty well explains what is meant: solving MAXCUT on a graph $G$ is equivalent to finding the smallest value of $c$ such that $c-f_G(x)\geq 0$ for every $x\in \{-1,1\}^n$. As you write, it is trivially true that $c^*=\mathsf{OPT}(G)$ is the optimal value where this holds by definition, but for one, you want to determine the value of $\mathsf{OPT}(G)$ explicitly, and equally as important, there will not in general be a degree 2 sum-of-squares proof for any $c$ better than $\mathsf{OPT}(G)/.878$ (this doesn't rely on UGC or anything fancy like that; if I remember right, there are known hard examples that basically embed vectors in a high-dimensional sphere with edges that emulate where the GW algorithm has a tough time in the rounding and uses the isoperimetric inequality on the sphere to argue about the real optimal value). The point of doing the degree 2 sum-of-squares algorithm is that there for sure exists a degree 2 sum-of-squares certificate of this polynomial inequality over $\{-1,1\}^n$ for any $c\geq\mathsf{OPT}(G)/.878$ (which is what the work in the literature you reference establishes), so by doing binary search, you can algorithmically determine this looser quantity efficiently.


What are current open problems in compiler theory?

In my experience, I've seen the following new compiler developments:

Work on automating data parallelism (or at least, reducing the amount of explicit work done by the programmer). This typically requires extensions to the language as well.
Work on extreme optimization strategies such as supercompilation or partial evaluation (where a program is collapsed via evaluation until it is reduced to its "smallest" form and then compiled)

I've seen a variety of work on things such as type checkers and so on, but I assume you're talking more about compiler-specific stuff.


Reasoning about non-deterministically terminating loops

In [dB80] Hitchcock and Park's analysis of the termination properties
of recursion is proven to correspond to a semantic analysis based on
the so-called Egli-Milner interpretation of relations [Egl75, Plo76],
which expresses erratic nondeterminism. This notion captures
that a nondeterministic union of relations is correct if it generates
at least one computation leading to a desired result (even in the
presence of a nonterminating computation). This appears to correspond
to what you are trying to do.

Next characterize the meaning of a statement $S$ as a function $f_S$
mapping each initial state $\sigma$ to some nonempty set of states,
possibly containing $\bot$, such that $f_S$ is strict in the sense
that $f_S(\bot) = \{\bot\}$. The nondeterministic choice between
statements $S_1$ and $S_2$ is described by the function mapping each
initial state $\sigma$ to the union of the individual results $f_{S_1}
(\sigma) \cup f_{S_2} (\sigma)$. Thus, whenever $S_1$ or $S_2$ has the
nondeterministic possibility of producing an undesirable result, then
so does their nondeterministic choice. As the resulting sets of final
states one obtains in this analysis the so-called Egli-Milner
powerset of states:

${\cal P}_{\text{E--M}}(S) = \{ ~s\subseteq S_\bot ~|~ s$ is finite and nonempty, or contains $\bot\}$

Why are infinite subsets of $S$ not considered possible sets of final
states in this model? Under the assumption that all basic building
blocks of relational terms produce only finite, nonempty sets of
possible final states, an infinite set of possible final states can
only be generated when an infinite computation is possible. This can
be seen as follows. Structure the set of all possible computations
starting in a given state $\sigma_0$ as a tree with root $\sigma_0$
and states as nodes. The set of leaves is then exactly the set of
possible final states reachable from $\sigma_0$, except for $\bot$,
which might be missing among the leaves but is represented in the set
of final states by the fact that there is an infinite path in the
tree. By the assumption above, and since only finite nondeterministic
choice is available, this tree is finitely branching. Thus, there is
only a finite number of leaves at any given finite depth. Consequently
an infinite number of possible final states can only be generated in
the presence of an infinite computation (an application of König's
lemma [Kön32]).

$({\cal P}_{\text{E--M}}(S),\sqsubseteq_{\text{E--M}})$ is a poset for
$\sqsubseteq_{\text{E--M}}$ defined by: for $s,t\in{\cal
  P}_{\text{E--M}}(S)$,

$
  s\sqsubseteq_{\text{E--M}} t\quad = \quad
  (\bot\in s \land s\setminus\{\bot\}\subseteq t)
  \lor (\bot\notin s \land s=t)~.
$

Here, $\bot$ can be seen as a placeholder through which
$\sqsubseteq_{\text{E--M}}$-greater sets can be generated by inserting
more states in lieu of $\bot$. Therefore, $\{\bot\}$ is the least
element of $({\cal P}_{\text{E--M}}(S),\sqsubseteq_{\text{E--M}})$.
Furthermore, the poset $({\cal
  P}_{\text{E--M}}(S),\sqsubseteq_{\text{E--M}})$ possesses lub's for
$\omega$-chains. Similarly, the strict functions from $S\cup\{\bot\}$
to ${\cal P}_{\text{E--M}}(S)$ are partially ordered by the pointwise
extension of $\sqsubseteq_{\text{E--M}}$. Moreover, the least such
function is $\lambda\sigma.\{\bot\}$ and lub's of $\omega$-chains of
such functions exist, too.

[dB80] JW de Bakker. Mathematical Theory of Program Correctness.
Prentice Hall, 1980.

[Egl75] H Egli. A mathematical model for nondeterministic
computations. Technical report, ETH Zürich, 1975.

[Kön32] D König. Theorie der endlichen und unendlichen Graphen.
Technical report, Leipzig, 1932.

[Plo76] GD Plotkin. A powerdomain construction. SIAM Journal on
  Computation, 5(3):452-487, 1976.

Disclaimer: this is taken almost verbatim from a book I once co-authored:

WP de Roever and K Engelhardt. Data Refinement: Model-Oriented
  Proof Methods and their Comparison. Cambridge University Press, 1998.


What does mechanism design constitute? (Game Theory)

Mechanism design is basically just algorithm design, where you don't control the inputs: instead, you assume that the inputs are controlled by different agents, who each have their own set of feasible actions, and their own utility function over outcomes, and are acting to maximize their own utility (and not yours, as the mechanism designer). So you are constrained in how you can design your algorithm, because you have to design it in such a way so as to manage the incentives of the agents so that they will want to share their data with you. The classic example is designing an auction for a good in such a way so that the bidders will reveal to you how much they really value the good.

So the fundamental characteristic in mechanism design is that you have agents who will act independently of the mechanism to further their own goals. Its hard to tell from your description, but it sounds like you simply have an algorithms problem. Possibly your problem is to design an algorithm to compute an equilibrium of some sort, but this would not typically be thought of as mechanism design.


Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

Here is a very slow algorithm, but it handles more general cases, like when density is defined as $d_\beta(G) = \frac{m(G)}{n(G)-\beta}$.
Let $f$ be a submodular function, $g$ be a modular function strictly larger than $0$. The min ratio problem $\min_S f(S)/g(S)$ can be solved in polynomial time. Indeed, use the standard to convert min ratio problem to parametric search problem with linear terms.
Consider we have input graph $G=(V,E)$.
For $d_\beta$ density, fix a set $T$ of size $k = \lfloor \beta \rfloor + 1$, and define $f_T:2^{V-T} \to \mathbb{R}$ as $f_T(S) = -m(G[T\cup S])$, and define $g_T:2^{V-T} \to \mathbb{R}_{>0}$ as $g_T(S) = |S|+|T|$. You can check $f$ is submodular through a counting argument.
Consider the optimum $T$ and $S$ for $$\min_{T:|T|=k, T\subset V} \min_{S:S\subset V\setminus T} f_T(S)/g_T(S).$$ Let $T$ and $S$ be the optimum of the problem. The densest subgraph is $G[T\cup S]$.
Running time is $O(n^k)$ calls to the min ratio oracle. Maybe faster algorithm exists, be nice to avoid that $k$ in the exponent.


Uses of quasi-PERs/difunctional relations/zig-zag relations?

Makoto Takeyama and I sent the following to data-refinement@etl.go.jp on Jan 5, 1996:

  Subject: what is a data refinement relation?

  Dear all:  anyone still interested in data refinement?

  Recently Mak and I have been looking again at an idea we considered
   many months ago.  The motivation is to characterize
   the logical relations relevant to showing data refinement.
   This was stimulated by the realization that logical relations can
   be used to show "safety" of abstract interpretations
   (see Section 2.8 of the chapter by Jones and Nielson in
   volume 4 of the Handbook of Logic in CS), but such relations
   are more general than those used to show data refinement.

  My reasoning goes as follows.  If a relation R is establishing a data
   refinement between (among) sets, then it must be inducing
   (partial) equivalence relations on each of the sets, with
   these equivalence classes in one-to-one correspondence,
   and every element of an equivalence class must be related
   to all elements of the corresponding equivalence classes in
   the other domains of interpretation.  The idea is that each
   equivalence class represents an "abstract" value; in a fully
   abstract interpretation the equivalence classes are singletons.

  We can give a simple condition to ensure that an n-ary relation R induces
   this structure.  Define v ~ v' in domain V iff there exists a value
   x in some other domain X (and arbitrary values ... in the
   other domains) such that R(...,v,...,x,...) and R(...,v',...,x,...).
   This defines symmetric relations on each of the domains.  Imposing
   local transitivity would then give us pers on each domain, but
   this would not suffice because we want to ensure transitivity
   across interpretations.  The following condition achieves this:
   if v_i ~ v'_i for all i, then R(...,v_i,...) iff R(...,v'_i,...)
   I call this "zig-zag completeness"; in the case n=2, it says
   that if R(a,c) & R(a',c') then R(a,c') iff R(a',c).

  Proposition. If R and S are zig-zag complete relations, so
   are R x S and R -> S.

  Proposition.  Suppose t and t' are terms of type th in context pi,
   and R is a zig-zag complete logical relation;
   then, if the equivalence judgement t=t' is interpreted as follows:

  for all u_i in V_i[[pi]],
      R^{pi}(...,u_i,...) implies that, for all i, V_i[[t]]u_i ~ V_i[[t']]u_i

  this interpretation satisfies the usual axioms and rules
   for equational logic.

  The intuition here is that the terms are to be "equivalent" both
    within a single interpretation (V_i) and across interepretations;
    i.e., the meanings of t and t' are in the same R-induced
    equivalence class, no matter which interpretation is used.

  Questions:

  Has anyone seen this kind of structure before?
  What are the natural generalizations of these ideas to
    other propositions and "arbitrary" semantic categories?

  Bob Tennent
  rdt@cs.queensu.ca


Graph Isomorphism Completeness for Perfect Graphs
and Subclasses of Perfect Graphs
C. Boucher D. Loker (2006)

  In this paper, we prove that deciding
  isomorphism of double split graphs, the class of graphs exhibiting a 2-join, and the class of
  graphs exhibiting a balanced skew partition are GI-complete. Further, we show that the GI
  problem for the larger class including these graph classes–that is, the class of perfect graphs–is
  also GI-complete.


Are there stronger notions of equivalence over lambda terms than beta equivalence?

Alright I'll give it a crack. It seems what you are describing is close to contextual equivalence, which is defined in the following manner $t$ and $t'$ ($t\simeq t'$) are contextually equivalent iff:

$$\forall E, E[t]\!\downarrow\ \Leftrightarrow\ E[t']\!\downarrow $$
where $E$ ranges over the set of term contexts (terms with one "hole") and $t\!\downarrow$ means $t$ is normalizing. Now this definition works for all untyped $\lambda$-terms and it is possible to show that if $t$ and $t'$ are normalizing, then
$$ t\simeq t'\ \Leftrightarrow\ t=_{\beta\eta}t'$$

Here $\beta$ is the usual $\beta$-conversion and $\eta$ is the equality
$$ \lambda x.t\ x = t$$
if $x\not\in \mathrm{FV}(t)$

This shows that $\beta+\eta$ is a rather strong form of equivalence for normalizing terms in the untyped setting. However in general the statement
$$ \forall v:T,\ t\ v=_{\beta\eta} t'\ v\qquad (1)$$
in some (normalizing) typed calculus is significatnly stronger than $t=_{\beta\eta}t'$: the first one is usually undecidable, and the second is not.

If You take as a starting point $\beta+\eta$ equality at non-functional types and $(1)$ at functional types, what you get is extensional equality of terms, and it holds in most "natural" models. See e.g. Berardi et al for models of system $F$ and the classic Barendregt chapters 5 and 10.


One way to augmenting an embedded planar graph (i.e. a plane graph) to become biconnected, while preserving the embedding, is

for each articulation vertex v:
  for each two edges vu and vw that are consecutive in the cyclic order around v:
    if u and w belong to different biconnected components of G:
      add edge uw

You have to be a little careful about the ordering of operations, though, because if you did this simultaneously at both endpoints of a bridge edge you could create a non-planarity. You have to do them one at a time.

This method can add significantly fewer edges than triangulation: each new edge reduces the number of biconnected components by one, so the total number of edges added is less than the original number of biconnected components.


Note that point location in an arrangement of balls (of different radii) is equivalent to point location in an arrangement of hyperplanes one dimension higher by using the usual paraboloid lifting map $(x_1, \ldots, x_d) \mapsto (x_1, \ldots, x_d, \sum_i x_i^2)$. If you call this lifting map $\Phi$, then it's easy to see that $p \in B$ if and only if $\Phi(p)$ is above $\Phi(B)$.

Now you have the problem of point location in an arrangement of hyperplanes (note that once you have such a structure it's usually easy to annotate each cell with the list of hyperplanes it is above). That problem can be solved by a variety of methods: for example there's an algorithm by Meiser that runs in time $O(d^5 \log n)$ but requires $n^d$ space. It's not clear from the question which is more important: space or time...


Stochastic gradient methods and risk of neural nets

The question has changed somewhat in the comments, so I'll address its new version: "Given a class of algorithms $A$ and an $\epsilon >0$ and a loss class $L$ and a data distribution $D$, one cannot use algorithms of type $A$ to find a member of $L$ whose generalization error is below $\epsilon$ unless running time is $f(\epsilon)$"... .

One such lower bound I'm aware of is for the case of Statistical Query based algorithms. See, for example, the paper by Yang, "New lower bounds for statistical query learning",
https://www.sciencedirect.com/science/article/pii/S0022000004001291
where, in particular,
it is shown that "any SQ-based algorithm needs running time $\Omega(2^n)$".


$\def\N{\mathbb N}\DeclareMathOperator\sym{Sym}\def\cC{\mathcal C}\def\cD{\mathcal D}\def\cP{\mathcal P}\def\cI{\mathcal W}\def\cMI{\mathcal{MW}}\DeclareMathOperator\pol{Pol}\DeclareMathOperator\inv{Inv}\DeclareMathOperator\minv{MInv}\let\pres\parallel$This is a presentation of one half of a duality for reversible transformations, analogous to the standard clone–coclone duality (such as here). It doesn’t answer the question, but it shows that all closed classes of such functions are determined by preservation of properties of a particular form.

In contrast to the standard case, the main complication is that permutations can count (they preserve cardinality), hence their invariants need to involve a bit of arithmetic to account for this.

Let me start with some tentative terminology. Fix a finite base set $A$. (In the classical case Scott asks about, $A=\{0,1\}$. Parts of the discussion also work for infinite $A$, but not the main characterization.)

A set of permutations (or: reversible transformations) is a subset $\cC\subseteq\cP:=\bigcup_{n\in\N}\sym(A^n)$, where $\sym(X)$ denotes the group of permutations of $X$. A permutation clone is a set of permutations $\cC$ such that

  Each $\cC\cap\sym(A^n)$ is closed under composition.
  For any $\pi\in\sym(\{1,\dots,n\})$, the permutation $\tilde\pi\in\sym(A^n)$ defined by $\tilde\pi(x_1,\dots,x_n)=(x_{\pi(1)},\dots,x_{\pi(n)})$ is in $\cC$.
  If $f\in\cC\cap\sym(A^n)$ and $g\in\cC\cap\sym(A^m)$, the permutation $f\times g\in\sym(A^{n+m})$ defined by $(f\times g)(x,y)=(f(x),g(y))$ is in $\mathcal C$.

Since $A$ is finite, 1 means that $\cC\cap\sym(A^n)$ is a subgroup of $\sym(A^n)$. The OP only demands 2 for transpositions $\pi$, but the version here is clearly equivalent. Condition 3 is equivalent to what I called introduction of dummy variables in the comments above.

A master clone is a permutation clone with allowance of ancillas:

  Let $f\in\sym(A^{n+m})$, $g\in\sym(A^n)$, and $a\in A^m$ be such that $f(x,a)=(g(x),a)$ for all $x\in A^n$. Then $f\in\cC$ implies $g\in\cC$.

We aim to characterize permutation clones and master clones by certain invariants. Let me first motivate the latter by a few examples on $A=\{0,1\}$:

The master clone of permutations preserving Hamming weight (generated by the Fredkin gate). If $w$ denotes the inclusion of $\{0,1\}$ in $\N$, these permutations are characterized by the property
$$y=f(x)\implies\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i),$$
where $f\in\sym(A^n)$, and I write $x=(x_1,\dots,x_n)$.
The master clone of permutations preserving Hamming weight modulo fixed $m$, mentioned in the comments. This is characterized by the same formula as above, if we interpret $w$ as a function from $\{0,1\}$ to the cyclic group $C(m)$, and compute the sum there.
The master clone of affine permutations $f(x)=Mx\oplus b$, $M\in\mathrm{GL}(n,\mathbb F_2)$, $b\in\mathbb F_2^n$ (generated by CNOT). One checks easily (or knows from the Post case) that a single-output function $\mathbb F_2^n\to\mathbb F_2$ is affine iff it preserves the relation $x^1\oplus x^2\oplus x^3\oplus x^4=0$. Thus, if we define $w\colon\{0,1\}\to\{0,1\}$ by
$$w(x^1,x^2,x^3,x^4)=x^1\oplus x^2\oplus x^3\oplus x^4,$$
an $f\in\sym(A^n)$ is in the clone iff
$$y^1=f(x^1)\land\dots\land y^4=f(x^4)\implies\max_{i=1}^nw(x^1_i,\dots,x^4_i)=\max_{i=1}^nw(y^1_i,\dots,y^4_i),$$
so we are dealing with sums in the monoid $(\{0,1\},0,\max)$.

In general, a weight function is a mapping $w\colon A^k\to M$, where $k\in\N$, and $M$ is a commutative monoid. A master weight function is one that maps all the diagonal $k$-tuples $(a,\dots,a)$, $a\in A$, to invertible elements of $M$. Let $\cI$ denote the class of all weight functions, and $\cMI$ the master weight functions.

If $f\in\sym(A^n)$, and $w\colon A^k\to M$ is a weight function, we say that $w$ is an invariant of $f$, or (mindlessly borrowing the terminology) that $f$ is a polymorphism of $w$, and write $f\pres w$, if the following condition holds for all $(x_i^j)_{i=1..n}^{j=1..k},(y_i^j)_{i=1..n}^{j=1..k}\in A^{n\times k}$:

  If $y^1=f(x^1),\dots,y^k=f(x^k)$, then
  $$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).$$

Here, $x^j=(x^j_1,\dots,x^j_n)$, $x_i=(x_i^1,\dots,x_i^k)$, and similarly for $y$. In other words, $f\pres w$ if $f$ (or rather its parallel extension to $(A^k)^n$) preserves the sum of $w$-weights of its arguments.

The relation $\pres$ between $\cP$ and $\cI$ (or $\cMI$) induces a Galois connection between sets of permutations $\cC\subseteq\cP$, and classes of weight functions $\cD\subseteq\cI$, in the usual way:
\begin{align*}
\pol(\cD)&=\{f\in\cP:\forall w\in\cD\,(f\pres w)\},\\
\inv^*(\cC)&=\{w\in\cI:\forall f\in\cC\,(f\pres w)\},\\
\minv^*(\cC)&=\cMI\cap\inv^*(\cC),
\end{align*}
and thus a dual isomorphism between the complete lattices of closed sets of permutations, and closed classes of (master) weight functions, respectively. To see that we are on the right track, we observe that closed sets of permutations are indeed clones:

  Lemma: If $\cD\subseteq\cI$, then $\pol(\cD)$ is a permutation clone. If $\cD\subseteq\cMI$, then $\pol(\cD)$ is a master clone.

Proof: The first assertion is more or less obvious. For the second, let  $w\in\cD$, $f,g,a$ be as in condition 4 so that $f\pres w$, and let $(x_i^j),(y_i^j)$ be as in the definition of $g\pres w$. Put $\bar x^j=(x^j,a)$, $\bar y^j=(y^j,a)=f(\bar x^j)$, and $u_i=w(a_i,\dots,a_i)$. Then $f\pres w$ implies
$$\sum_{i=1}^nw(x_i)+\sum_{i=1}^mu_i=\sum_{i=1}^{n+m}w(\bar x_i)=\sum_{i=1}^{n+m}w(\bar y_i)=\sum_{i=1}^nw(y_i)+\sum_{i=1}^mu_i.$$
However, $u_i$ are invertible in $M$ as $w$ is a master weight function, hence
$$\sum_{i=1}^nw(x_i)=\sum_{i=1}^nw(y_i).\tag*{QED}$$

Before we proceed further, we need to fix one problem: monoids can be huge, hence invariants of this form can be rightly suspected of being useless abstract nonsense.

First, given a weight function $w\colon A^k\to M$, we can assume that $M$ is generated by $w(A^k)$ (and by additive inverses of images of diagonal elements in the master case), as other elements of $M$ do not enter the picture. In particular, $M$ is finitely generated. Second, by general results from universal algebra, we can write $M$ as a subdirect product
$$M\subseteq\prod_{i\in I}M_i,$$
where each $M_i$ is subdirectly irreducible, and $M_i$ is a quotient of $M$ via the $i$th product projection $\pi_i$; in particular, it is still a finitely generated commutative monoid. By a result of Mal'cev, f.g. subdirectly irreducible commutative monoids (or semigroups) are in fact finite. The mapping $w_i=\pi_i\circ w\colon A^k\to M_i$ is again a weight function, master if $w$ was, and it is easy to see that
$$\pol(w)=\bigcap_{i\in I}\pol(w_i).$$
Thus, we can without loss of generality restrict attention to weight functions $w\colon A^k\to M$, where $M$ is finite and subdirectly irreducible. Let $\mathcal{FW}$ be the class of such weight functions, and put
\begin{align*}
\inv(\cC)&=\mathcal{FW}\cap\inv^*(\cC),\\
\minv(\cC)&=\mathcal{FW}\cap\minv^*(\cC).
\end{align*}
Examples of finite subdirectly irreducible commutative monoids are the cyclic groups $C(p^d)$, and the truncated addition monoids $(\{0,\dots,d\},0,\min\{d,x+y\})$. The general case is more complicated, nevertheless one can say a lot about their structure: one can write each in a certain way as a disjoint union of a $C(p^d)$, and a finite nilsemigroup with some properties. See Grillet for details.

Now we are ready for the main point of this post:

  Theorem: The closed sets of permutations in the Galois connection to finite subdirectly irreducible (master) weight functions are exactly the permutation clones (master clones, resp.).

  That is, if $\cC\subseteq\cP$, then the permutation clone generated by $\cC$ is $\pol(\inv(\cC))$, and the master clone generated by $\cC$ is $\pol(\minv(\cC))$.

Proof: In view of the preceding discussion, it suffices to show that if $\cC$ is a permutation clone, and $f\in\sym(A^n)\smallsetminus\cC$, there is an invariant $w\colon A^k\to M$ of $\cC$ such that $f\nparallel w$, and one can take $w$ to be a master weight function if $\cC$ is a master clone.

Put $k=|A|^n$, and let $F$ be the free monoid generated by $A^k$ (i.e., finite words over alphabet $A^k$). We define a relation $\sim$ on $F$ by
$$x_1\cdots x_m\sim y_1\cdots y_m\iff\hbox{$\exists g\in\cC\cap\sym(A^m)\,\forall j=1,\dots,k\,g(x^j_1,\dots,x^j_m)=(y^j_1,\dots,y^j_m).$}$$
(Words of unequal length are never related by $\sim$.) Since each $\cC\cap\sym(A^m)$ is a group, $\sim$ is an equivalence relation (in fact, its restriction to words of length $m$ is just the orbit equivalence relation of $\cC\cap\sym(A^m)$ acting in the obvious way on $A^{mk}$). Moreover, $\sim$ is a monoid congruence: if $g\in\cC\cap\sym(A^m)$ and $g'\in\sym(A^{m'})$ witness that $x_1\cdots x_m\sim y_1\cdots y_m$ and $x'_1\cdots x'_{m'}\sim y'_1\cdots y'_{m'}$, respectively, then $g\times g'\in\cC\cap\sym(A^{m+m'})$ witnesses $x_1\cdots x_mx'_1\cdots x'_{m'}\sim y_1\cdots y_my'_1\cdots y'_{m'}$.

Thus, we can form the quotient monoid $M=F/{\sim}$. The swap permutation witnesses that $xy\sim yx$ for each $x,y\in A^k$; that is, the generators of $M$ commute, hence $M$ is commutative. Define a weight function $w\colon A^k\to M$ as the natural inclusion of $A^k$ in $F$ composed with the quotient map.

It is easy to see that $\cC\subseteq\pol(w)$: indeed, if $g\in\cC\cap\sym(A^m)$, and $y^1=f(x^1),\dots,y^k=f(x^k)$, then
$$\sum_{i=1}^mw(x_i)=x_1\cdots x_m/{\sim}=y_1\cdots y_m/{\sim}=\sum_{i=1}^mw(y_i)$$
by the definition of $\sim$ (using the notation as in the definition of $\pres$). On the other hand, assume $f\pres w$. Let $\{a^j:j=1,\dots,k\}$ be an enumeration of $A^n$, $b^j=f(a^j)$, and let $a_i,b_i\in A^k$ for $i=1,\dots,n$ be again as in the definition of $\pres$. Then
$$a_1\cdots a_n/{\sim}=\sum_{i=1}^nw(a_i)=\sum_{i=1}^nw(b_i)=b_1\cdots b_n/{\sim},$$
hence by the definition of $\sim$, there exists $g\in\cC\cap\sym(A^n)$ such that $g(a^j)=b^j=f(a^j)$ for each $j$. However, since the $a^j$ exhaust $A^n$, this means $g=f$, i.e., $f\in\cC$, a contradiction. This completes the proof for permutation clones.

Even if $\cC$ is a master clone, $w$ needn’t  be a master weight function, in fact, the diagonal elements are not even necessarily cancellative in $M$, hence we need to fix it. For each $c\in A$, let $c^*=(c,\dots,c)\in A^k$, and define a new equivalence relation $\approx$ on $F$ by
$$x_1\cdots x_m\approx y_1\cdots y_m\iff\exists c_1,\dots,c_r\in A\,x_1\cdots x_mc_1^*\cdots c_r^*\sim y_1\cdots y_mc_1^*\cdots c_r^*.$$
Using the fact that elements of $A^k$ commute modulo $\sim$, it is easy to show that $\approx$ is again a congruence, hence we can form the monoid $M'=F/{\approx}$, and a weight function $w'\colon A^k\to M'$. Since $\approx$ extends $\sim$, $M'$ is commutative, and a quotient of $M$; in particular, $\cC\subseteq\pol(w')$. On the other hand, if $f\pres w'$, then the same argument as above together with the definition of $\approx$ would give a $g\in\cC\cap\sym(A^{n+r})$, and $c_1,\dots,c_r\in A$ such that
$$g(x,c_1,\dots,c_r)=(f(x),c_1,\dots,c_r)$$
for all $x\in A^n$, thus $f\in\cC$ as $\cC$ is a master clone, a contradiction.

The definition of $\approx$ ensures that
$$xc^*\approx yc^*\implies x\approx y$$
for all $x,y\in F$, and $c\in A$. It follows that the elements $c^*/{\approx}=w'(c^*)$ are cancellative in $M'$. It is an easy well-known fact that any commutative monoid can be embedded in another one where all cancellative elements become invertible. The composition of such an embedding with $w'$ is then a master weight function $w''$, and $\pol(w')=\pol(w'')$, hence $w''\in\minv^*(\cC)\setminus\minv^*(f)$.  QED

EDIT: A generalization of the clone–coclone duality above is now written up in

[1] E. Jeřábek, Galois connection for multiple-output operations, preprint, 2016, arXiv:1612.04353 [math.LO].


What exactly are the classes FP, FNP and TFNP?

Emil Jerabek's comment is a nice summary, but I wanted to point out that there are other classes with clearer definitions that capture more-or-less the same concept, and to clarify the relation between all these things.

[Warning: while I believe I've gotten the definitions right, some of the things below reflect my personal preferences - I've tried to be clear about where that was.]

In the deterministic world, a function class is just a collection of functions (in the usual, mathematical sense of the word "function", that is, a map $\Sigma^* \to \Sigma^*$). Occasionally we want to allow "partial functions," whose output is "undefined" for certain inputs. (Equivalently, functions that are defined on a subset of $\Sigma^*$ rather than all of it.)

Unfortunately, there are two different definitions for $\mathsf{FP}$ floating around, and as far as I can tell they are not equivalent (though they are "morally" equivalent).

$\mathsf{FP}$ (definition 1) is the class of functions that can be computed in polynomial-time. Whenever you see $\mathsf{FP}$ and its not in a context where people are talking about $\mathsf{FNP}, \mathsf{TFNP}$, this is the definition I assume.

In the nondeterministic world things get a little funny. There, it is convenient to allow "partial, multi-valued functions." It would be natural to also call such a thing a binary relation, that is, a subset of $\Sigma^* \times \Sigma^*$. But from the complexity point of view it is often philosophically and mentally useful to think of these things as "nondeterministic functions." I think many of these definitions are clarified by the following classes (whose definitions are completely standardized, if not very well-known):

$\mathsf{NPMV}$: The class of "partial, multi-valued functions" computable by a nondeterministic machine in polynomial time. What this means is there is a poly-time nondeterministic machine, and on input $x$, on each nondeterministic branch it may choose to accept and make some output, or reject and make no output. The "multi-valued" output on input $x$ is then the set of all outputs on all nondeterministic branches when given $x$ as input. Note that this set can be empty, so as a "multi-valued function" this may only be partial. If we think of it in terms of binary relations, this corresponds to the relation $\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$.
$\mathsf{NPMV}_t$: Total "functions" in $\mathsf{NPMV}$, that is, on every input $x$, at least one branch accepts (and therefore makes an output, by definition)
$\mathsf{NPSV}$: Single-valued (potentially partial) functions in $\mathsf{NPMV}$. There is some flexibility here, however, in that multiple branches may accept, but if any branch accepts, then all accepting branches must be guaranteed to make the same output (so that it really is single-valued). However, it is still possible that no branch accepts, so the function is only a "partial function" (i.e. not defined on all of $\Sigma^*$).
$\mathsf{NPSV}_t$: Single-valued total functions in $\mathsf{NPSV}$. These really are functions, in the usual sense of the word, $\Sigma^* \to \Sigma^*$. It is a not-too-hard exercise to see that $\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ (using Def 1 for FP above).

When we talk about potentially multi-valued functions, talking about containment of complexity classes isn't really useful any more: $\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$ unconditionally simply because $\mathsf{NPSV}$ doesn't contain any multi-valued "functions", but $\mathsf{NPMV}$ does. Instead, we talk about "c-containment", denoted $\subseteq_c$. A (potentially partial, multi-valued) function $f$ refines a (potentially partial multi-valued) function $g$ if: (1) for every input $x$ for which $g$ makes some output, so does $f$, and (2) the outputs of $f$ are always a subset of the outputs of $g$. The proper question is then whether every $\mathsf{NPMV}$ "function" has an $\mathsf{NPSV}$ refinement. If so, we write $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$.

$\mathsf{PF}$ (a little less standard) is the class of (potentially partial) functions computable in poly-time. That is, a function $f\colon D \to \Sigma^*$ ($D \subseteq \Sigma^*$) is in $\mathsf{PF}$ if there is a poly-time deterministic machine such that, on inputs $x \in D$ the machine outputs $f(x)$, and on inputs $x \notin D$ the machine makes no output (/rejects/says "no"/however you want to phrase it).

$\mathsf{FNP}$ is a class of "function problems" (rather than a class of functions). I would also call $\mathsf{FNP}$ a "relational class", but really whatever words you use to describe it you need to clarify yourself afterwards, which is why I'm not particularly partial to this definition. To any binary relation $R \subseteq \Sigma^* \times \Sigma^*$ there is an associated "function problem." What is a function problem? I don't have a clean mathematical definition the way I do for language/function/relation; rather, it's defined by what a valid solution is: a valid solution to the function problem associated to $R$ is any (potentially partial) function $f$ such that if $(\exists y)[R(x,y)]$ then $f$ outputs any such $y$, and otherwise $f$ makes no output. $\mathsf{FNP}$ is the class of function problems associated to relations $R$ such that $R \in \mathsf{P}$ (when considered as a language of pairs) and is p-balanced. So $\mathsf{FNP}$ is not a class of functions, nor a class of languages, but a class of "function problems," where "problem" here is defined roughly in terms of what it means to solve it.
$\mathsf{TFNP}$ is then the class of function problems in $\mathsf{FNP}$ - defined by a relation $R$ as above - such $R$ is total, in the sense that for every $x$ there exists a $y$ such that $R(x,y)$.

In order to not have to write things like "If every $\mathsf{FNP}$ (resp., $\mathsf{TFNP}$) function problem has a solution in $\mathsf{PF}$ (resp., $\mathsf{FP}$ according to above definition), then..." in this context one uses Definition 2 of $\mathsf{FP}$, which is:

$\mathsf{FP}$ (definition 2) is the class of function problems in $\mathsf{FNP}$ which have a poly-time solution. One can assume that the solution (=function) here is total by picking a special string $y_0$ that is not a valid $y$ for any $x$, and having the function output $y_0$ when there would otherwise be no valid $y$. (If needed, we can modify the relation $R$ by prepending every $y$ with a 1, and then take $y_0$ to be the string 0; this doesn't change the complexity of anything involved).

Here's how these various definitions relate to one another, $\mathsf{FNP} \subseteq \mathsf{FP}$ (definition 2, which is what you should assume because it's in a context where it's being compared with $\mathsf{FNP}$) is equivalent to $\mathsf{NPMV} \subseteq_c \mathsf{PF}$. $\mathsf{TFNP} \subseteq \mathsf{FP}$ (def 2) is equivalent to $\mathsf{NPMV}_t \subseteq_c \mathsf{FP}$ (def 1).


Applying higher homotopy-theoretic ideas to CS is still a very nascent field! My understanding is that it's not even that old as a mathematical field.

Certainly HoTT is the central impetus for such ideas. Even there though, there only have been few applications of category theory of "dimension" higher than 2.

One nice "computer science-y" one is Homotopical Patch Theory by Anguili et al. They show that some common operations and properties inherent git like version control systems can be best understood using homotopy type theory.

Another rather unrelated train of thought is some interesting work on the relationship between (2-)Homology theory and confluence of term rewrite systems (or more complex structures such as higher algebras). Some examples are

Y. Guiraud Confluence of linear rewriting and homology of algebras .

Y. Lafont & A. Proute Church-Rosser property and homology of monoids.


Number of non-isomorphic connected graphs of $n$ nodes and $m$ edges

According to Bollobas (Random Graphs), if you make "natural assumptions" on $n$ and $m$ there are $n!$ times more labelled graphs on $n$ vertices and $m$ edges than random unlabelled graphs on $n$ vertices and $m$ edges, so roughly $\frac{1}{n!}{{n \choose 2} \choose m}$ unlabelled graphs on $n$ vertices and $m$ edges. If you pick something like $m = \frac{1}{2}{n \choose 2}$, all those graphs should be connected with high probability, so I'd say --> massively superpolynomial !

Of course, you can break those "natural assumptions" by setting $m = 0$, or $m<n-1$ in your case...

Nathann


Indeed, set packing, partitioning, and covering have been studied in terms of exact algorithm running times.
 To address your last question, you can solve weighted set packing in $O(m2^n)$ time by dynamic programming across all subsets of $[n]$.
 Moreover, if your integer weights are bounded by $M$, you can solve it in $O(M2^n)$ time, even if $m$ is as large as $2^n$, see

http://dx.doi.org/10.1137/070683933

BTW, The parameterized result you list for $3$-sets is not the best known, see

http://arxiv.org/abs/1007.1161

for a state-of-the-art algorithm and a list of previous results on the problem.


What's the definition of join on iso-recursive types?

I thought a bit about this and I am afraid that it is harder than it
looks -- as you suspected! In the spirit of encouraging discussion,
I'll write my chain of thoughts.

The subtyping rules are often defined as judgments of the form t1 <:
t2, where --- is an inductive rule (you can only use them finitely
many times along each path in the derivation tree) and === is
a coinductive rule (you can use it infinitely many times).

t1 <: t2
t'1 <: t'2
=================
t1*t'1  <: t2*t'2

t1 :> t2
t'1 <: t'2
======================
t1 -> t'1 <: t2 -> t'2

========
t <: top

========
bot <: t

------
t <: t

t1 <: t2
t2 <: t3
--------
t1 <: t3

t1[a \ mu a. t1] <: t2
----------------------
(mu a. t1) <: t2

t1 <; t2[a \ mu a. t2]
----------------------
t1 <: (mu a. t2)

I would think you can define the /\ and \/ by turning this into
a three-place judgment. Only showing one half:

t1 /\ t2 = t3
t'1 /\ t'2 = t'3
=========================
t1*t'1 /\ t2*t'2 = t3*t'3

t1 \/ t2 = t3
t'1 /\ t'2 = t'3
==================================
t1 -> t'1 /\ t2 -> t'2 = t3 -> t'3

===============
t1 /\ top <: t1

================
top /\ t2 <: tt2

================
t1 /\ bot <: bot

================
bot /\ t1 <: bot

----------
t /\ t = t

t1 /\ t2 = t12
t12 /\ t3 = t23
-----------------------
(t1 /\ t2) /\ t3 = t123

t1 /\ t23 = t123
t2 /\ t3 = t23
-----------------------
t1 /\ (t2 /\ t3) = t123

(The two halves, /\ and \/, can be factorized with a parametrized
presentation where /\^{-1} is \/ and top^{-1} is bot.)

The problem here are the mu-unfolding rules:

t1[a \ mu a. t1] /\ t2 = t3
---------------------------
(mu a. t1) /\ t2 = t3

t1 /\ t2[a \ mu a. t2] = t3
---------------------------
t1 /\ (mu a. t2) = t3

Clearly there should be a rule that allows to build a (mu a. t3) on
the right-hand side; I think the rules above are probably not
complete.

Some presentations of recursive subtyping have rules of the form:

Gamma, a <: b |- t1 <: t2
---------------------------------
Gamma |- (mu a. t1) <: (mu b. t2)

-------------------------------
Gamma ∋ (t1 <: t2) |- t1 <: t2

(Technically these interact with the induction/coinduction
presentation: you may not use an hypothesis in Gamma without using one
of the coinductive/productive rules first.)

I guess that those could be adapted to:

Gamma, a /\ b = c |- t1 /\ t2 = t3
-----------------------------------------------
Gamma |- (mu a. t1) /\ (mu b. t2) = (mu c . t3)

----------------------------------------
Gamma ∋ (t1 /\ t2 = t3) |- t1 <: t2 = t3

I thought that the syntax/coinduction-based presentations of recursive
subtyping ("Coinductive axiomatization of recursive type equality and
subtyping", Brandt and Henglein, 1997; "Subtyping, Declaratively", Danielsson, 2010) would avoid having to think about the tree-form of mu-types,
but it looks like the syntax alone does not scale that nicely to
defining the meet/join, so maybe going back to the tree presentation
would better reveal what should happen.


Complexity of factorial exponent over composite moduli

Borwein's method to compute the exponent and the doubling method for multiplying out the $a$'s wouldn't be too terrible, but as @SashoNikolov pointed out it is exponential with regards to the input size. You can store all intermediate results in $O(log(n))$ bits when multiplying out $a$.

I don't see what this has to do with P vs NP.


Clustering formalizations other than K-means for separable data

One recent model trying to capture such a notion is by Balcan, Blum, and Gupta '09.  They give algorithms for various clustering objectives when the data satisfies a certain assumption: namely that if the data is such that any $c$-approximation for the clustering objective is $\epsilon$-close to the optimal clustering, then they can give efficient algorithms for finding an almost-optimal clustering, even for values of $c$ for which finding the $c$-approximation is NP-Hard.  This is an assumption about the data being somehow "nice" or "separable."  Lipton has a nice blog post on this.

Another similar type of condition about data given in a paper by Bilu and Linial '10 is perturbation-stability.  Basically, they show that if the data is such that the optimal clustering doesn't change when the data is perturbed (by some parameter $\alpha$) for large enough values of $\alpha$, one can efficiently find the optimal clustering for the original data, even when the problem is NP-Hard in general.  This is another notion of stability or separability of the data.

I'm sure there is earlier work and earlier relevant notions, but these are some recent theoretical results related to your question.


Quantum algorithms for QED computations related to the fine structure constants

The general belief seems to be that the expansion in $\alpha$ is an asymptotic series but not a convergent series. The handwaving estimate is that in $\sum_k c_k \alpha^k$, the scaling for the coefficients is roughly $c_k \sim k!$. So, since $\alpha \simeq 1/137$ the terms will start to get bigger rather than smaller for $k$ larger than around 137. (I assume there is serious literature on this topic, but I'm not too familiar with it. The above is what high energy physicists have told me in casual conversation.)

The fine structure constant itself is not something for which anyone knows a purely theoretical formula. So getting more digits of $\alpha$ is a fundamentally different problem from getting more digits of $\pi$. That being said, the challenges are both experimental and computational. Various experiments in particle accelerators and atomic physics laboratories are dedicated to making progressively more precise measurements of fundamental constants such as $\alpha$. Often, the high-precision theoretical calculation of the factors relating the experimentally observed quantities (such as scattering probabilities or spectral lines) to fundamental constants of interest such as $\alpha$ is very difficult and computationally heavy. The computational side can be just as much a limiting factor as the experimental side in these precision metrology problems. (Some of my coworkers at NIST specialize in this sort of thing.)

In the quantum algorithm that Keith and John and I developed, we do not use a perturbative expansion in powers of the coupling constant. The simulation algorithm is much more directly analogous to an actual experiment. However, one advantage over experiment is that in a simulation we are free to change $\alpha$ to whatever value we want. So, by computing scattering amplitudes at varying $\alpha$ it might be easier to determine the individual coefficients $c_k$ than it is in the real world. However, the study of quantum algorithms for simulating quantum field theories is in its infancy. The extraction of such coefficients is one of the numerous interesting questions that have not really been explored yet! Also, our algorithms don't yet tackle QED but rather some simplified models.

Today, we primarily have two classical algorithms for QFT: Feynman diagrams and lattice simulations. Feynman diagrams break down at strong coupling or high precision, as discussed above. Lattice calculations are mostly only good for computing static quantities such as binding energies (e.g. the mass of the proton), rather than dynamic quantities such as scattering amplitudes. This is because the lattice calculations use imaginary time. (Also, for certain condensed matter systems that are highly frustrated, even finding static quantities such as ground state energies is exponentially hard. It is not clear to me to what extent this phenomenon is relevant to high energy physics.) There is also a current research program on speeding up the computation of scattering amplitudes in supersymmetric quantum field theories. You may have heard about the "amplituhedron", which is part of this. This seems kind of exciting, but it's recent stuff and I don't know too much about it.

So, there is room for exponential speedup by quantum computation in the case that you wish to compute dynamical quantities such as scattering amplitudes with high precision or in a strongly coupled quantum field theory. My papers with Keith and John work out polynomial-time quantum algorithms for computing scattering amplitudes in simple quantum field theories which can be strongly coupled. We would like to extend our algorithms to simulate more complete models such as QED and QCD but we are not there yet. Doing so involves nontrivial challenges, but my feeling is that quantum computers should be able to compute scattering amplitudes in quantum field theories in polynomial time quite generally.

So, that's the perspective based on known classical and quantum algorithms. There is also a perspective from complexity theory. For many classes of physical systems, the problem of computing transition amplitudes to polynomial precision is BQP-complete, and the problem of computing ground energies is QMA-complete. So, for worst case instances we expect quantum computers to compute transition amplitudes in polynomial time, whereas classical computers require exponential time. We expect both quantum and classical computers (as well as nature itself) to require exponential time to find ground states in the worst case. The question is whether the worst case instances of the computational problems look like any real physics. In the context of condensed matter physics, the answer is basically yes, I would say. In the context of high energy physics, one can construct BQP-hard instances of the scattering amplitude problem that correspond at least loosely to something a physicist might need to calculate. (We are currently working on a paper about this.) Whether one can construct QMA-hard instances of the problem of computing a vacuum state for a quantum field theory is something that I have not really thought about. However, I think this could be done if one is willing to allow non-translationally-invariant external fields.


Reference Request: Asymptotic hardness of $hk$ coloring $k$-colorable graphs

Here are the references:

S. Khanna, N. Linial, and S. Safra, On the hardness of approximating the chromatic number,
Combinatoria, 20 (2000), pp. 393–415.
C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, J.
ACM, 41 (1994), pp. 960–981.


What is the parameterized complexity of following model checking problem?

This problem is $\mathsf{FPT}$ for $\varphi_i \in MSO$ (and hence also for $\varphi_i \in FO$).

More precisely, Courcelle et al. prove in [1] the following:

  Theorem [1, Thm. 32]
  Let $\mathcal{C}$ be a class of graphs which is of bounded tree-width $k$.
  Then any $MSO_2$ definable counting problem, given by $\varphi$, can be solved in time $c_k \cdot \mathcal{O}(|V| + |E|)$, where $c_k$ is a constant which depends only on $\varphi$ and $k$.

$MSO_2$ stands for monadic second-order logic where the universe is $V \cup E$ (vertices and edges), and we are given a binary relation $R(v,e)$ for the incidence between a vertex $u$ and an edge $e$. This is a quite natural representation of graphs, sufficiently powerful to e.g. define Hamiltonicity.

[1]: B.Courcelle, J.A.Makowsky, U.Rotics. On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Applied Mathematics 108, pp. 23-52 (2001)


Strongly Regular Graph and GI-Completeness

I believe all known GI-completeness results are functorial (definition in the paper), and Babai has recently shown (ITCS 2014, free author's copy) - based on bounds on the structure of automorphism groups of strongly regular graphs - that there is no functorial reduction from GI to strongly regular GI.


If the edges are permitted to be laid both inside and outside the circle, then it is called the 2-page graphs; if edges can only be laid inside the circle, it is the 1-page graphs, which is also know as the outerplanar graphs. See the book embedding entry in Wikipedia for more information.

By your comment, I guess the term you're searching for is outerplanar, since the complete graph on 4 vertices is 2-page. Outerplanar graphs can be recognized in linear time; see

  Linear algorithms to recognize outerplanar and maximal outerplanar graphs, S.L. Mitchell, Information Processing Letters, 1979.


Open/unsolved problems in (computational) random matrix theory / matrix completion?

Not sure if this is the kind of thing you want but here is something I find fascinating : This particular breakthrough paper's proof technique is in a sense  "random matrix theory", https://arxiv.org/abs/1505.08010
(..I dont know if before this paper anyone had guessed that random matrix is the way of think of this question..)

I feel it is a deeply important question to be able to (a) come up with a version of this which shows this existential result restricted to only simple graphs and (b) come up with a deterministic polynomial time algorithm (or prove that such a thing can't exist!) which makes this existential argument constructive in the case of simple graphs.  This isnt clear for even just bipartite graphs!


Linear time in-place riffle shuffle algorithm

The problem is surprisingly non-trivial. Here is a nice solution by Ellis and Markov, In-Situ, Stable Merging by way of the Perfect Shuffle (section 7). Ellis, Krahn and Fan, Computing the Cycles in the Perfect Shuffle Permutation succeed in selecting "cycle leaders", at the expense of more memory. Also related is the nice paper by Fich, Munro and Poblete, Permuting In Place, which gives a general $O(n\log n)$ time algorithm for the oracle model. If only an oracle for the permutation is available, the algorithm requires logarithmic space; if we also have an oracle for the inverse, it requires constant space.

Now for Ellis and Markov's solution. First, suppose $n = x+y$. Then computing the perfect shuffle of order $n$ reduces to computing the perfect shuffle of orders $x$ and $y$, with a rotation preceding them. Here is a proof by example ($n=5$, $x=3$, $y=2$):
$$
\begin{array}{cc}
012\mathbf{345} & \mathbf{67}89 \\
012\mathbf{567} & \mathbf{34}89 \\
051627 & 3849
\end{array}
$$

Ellis and Markov found an easy way to compute the perfect shuffle when $n=2^k$, using constant space and linear time. Using this, we obtain an algorithm for computing the perfect shuffle for arbitrary $n$. First, write $n = 2^{k_0} + \cdots + 2^{k_w}$ using the binary encoding of $n$, and let $n_i = 2^{k_i} + \cdots + 2^{k_w}$. Rotate the middle $n_0$ bits, shuffle the right-hand $2^{k_0}$ bits. Ignoring the righthand $2^{k_0}$ bits, rotate the middle $n_1$ bits, and shuffle the right-hand $2^{k_1}$ bits. And so on. Note that rotation is easy since the first few elements rotated function as cycle leaders. The total complexity of rotation is $O(n_0 + \cdots + n_w) = O(n)$, since $n_{t+1} < n_t/2$. The total complexity of the inner shuffles is $O(2^{k_0} + \cdots + 2^{k_w}) = O(n)$.

It remains to show how to compute the perfect shuffle when $n=2^k$. In fact, we will be able to identify cycle leaders, following classical work on necklaces (Fredricksen and Maiorana, Necklaces of beads in $k$ colors and $k$-ary de Bruijn sequences; Fredricksen and Kessler, An algorithm for generating necklaces of beads in two colors).

What is the connection? I claim that the shuffle permutation corresponds to right shifting of the binary representation. Here is a proof by example, for $n=8$:
$$
\begin{array}{cccccccc}
000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\
000 & 100 & 001 & 101 & 010 & 110 & 011 & 111
\end{array}
$$
Therefore, to find cycle leaders, we need to find one representative out of each equivalence class of the rotation of binary strings of length $k$. The papers mentioned above give the following algorithm for generating all cycle leaders. Start with $0^k$. At each step, we are at some point $a_1 \ldots a_k$. Find the maximal index $i$ of a zero bit, divide $k$ by $i$ to obtain $k = d\cdot i + r$, and let the following point be $(a_1\ldots a_{i-1}1)^d a_1\ldots a_r$. Whenever $r = 0$, the new string is a cycle leader.

For example, when $n=16$ this generates the sequence
$$
\mathbf{0000}, \mathbf{0001}, 0010, \mathbf{0011},
\mathbf{0101}, 0110, \mathbf{0111}, \mathbf{1111}.
$$

The cycle leaders are highlighted.


What is the proof-theoretic significance of the existence of a Brown-Palsberg self-interpreter for system $F_\omega$?

There is no proof significance, since already Gödel's $T$ has a Brown-Palsberg self-interpreter for free. We need a better definition of a typed self-interpreter.


Universe polymorphism: the inference of universes and their constraints

It's complicated because universe constraints are simplified during inference (in order to avoid an explosion of constraints). Have a look at:

Matthieu Sozeau and Nicolas Tabareau: Universe Polymorphism in Coq, Interactive Theorem Proving - 5th International Conference, ITP 2014
Beta Ziliani & Matthieu Sozeau: A Unification Algorithm for Coq featuring Universe Polymorphism and Overloading, ACM SIGPLAN International Conference on Functional Programming 2015.


off-policy and offline policy reinforcement learning

I assume that you know what "policy evaluation" means. Briefly speaking, it refers to the task of estimating the value of a given policy.

In the RL literature, the off-policy scenario refers to the situation that the policy you want to evaluate is different from the data generating policy. In other words, you behave in one way, but you want to evaluate the value of another policy. This should be contrasted with the on-policy scenario that the policy you want to evaluate is the same policy that generates (or generated) data.

The offline sampling scenario (and not "offline policy") is the scenario that you already have some samples and now you want to perform tasks like policy evaluation. In this scenario, the agent cannot have any further interaction with the environment. In other words, the data are given and fixed. This should be contrasted with the online sampling scenario that the agent actually interacts with the environment.

These two are orthogonal. So it is possible to have a on-policy/off-policy offline/online scenario.

Hope my short discussion has helped. You may also take a look at Sutton and Barto's textbook.

Amir massoud


Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict subclass of $\mathrm{EXP^{NP}}$ (which is the exponential analogue of $\Delta^P_2$).
$\Theta^{\exp}_2$ can be variously defined as
$$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=EXP^{NP[poly]}=PSPACE^{NEXP}=P^{NEXP}=\exists\cdot DEXP},$$
where $\|$ denotes parallel (nonadaptive) access to the oracle, $\mathrm{[poly]}$ restricts the number of oracle queries to polynomial, the oracle tape is included in the space requirements of the $\mathrm{PSPACE}$ machine, and $\mathrm{DEXP}=\{L_0\smallsetminus L_1:L_0,L_1\in\mathrm{NEXP}\}$ is the exponential analogue of $\mathrm{DP}$.
For the $\mathrm{EXP_{poly}^{NEXP}}\subseteq\Theta^{\exp}_2$ inclusion, note that there are only exponentially many strings of polynomial length, hence the exponential-time machine may first ask all possible queries of that length in parallel, and then proceed with the computation, showing $\mathrm{EXP_{poly}^{NEXP}\subseteq EXP^{\|NP}}$.
For the $\Theta^{\exp}_2\subseteq\mathrm{EXP_{poly}^{NEXP}}$ inclusion, it is obvious that $\mathrm{P^{NEXP}\subseteq EXP_{poly}^{NEXP}}$.


Gap between $BB(n)$ and "second largest" $BB(n)$

The number of states is just a notion of complexity of the description of computable functions in a model, you can pick any model of computation and any encoding of them as binary strings and then take the length as n and define BB(n) based on that and all the interesting results about BB(n) would still be true, there is boring special about TM model and number of states.
There is nothing that prevents them from picking any modified model of TMs. Generally the questions which are not invariant under such changes of representation of TMs are not about computability or TMs but about the particular representation (like BB(n) mod 2, etc. ) and unless there is some particular reason for them being interesting they don't worth pursuing imho. They are nice puzzles but not of much value.
l
Note that "BB(n) is not computable" is invariant under change of representations of TMs.
So is this question invariant under change of representation of computable functions? The answer I think is no.

i. Consider a representation where we have two special states 0 and 1 and either 0 is initial and just can transition to 1 or 0 is unreachable and 1 is initial. In this encoding the difference is 1.

ii. Consider another representation where we have a UTM plus a part that writes n bits on tape before transitioning to UTM. So the question becomes max f(x) - 2ndmax f(x) where maxes are over n bits strings and where f is an arbitrary computable function. We only need to find a computable function where this is not computable. I haven't thought about it much but my gut says there is such a computable function.


Overlapping BFS Layers in Dominating Set with Baker's Technique

In a single layer of the partition, consisting of the vertices at distance $d$ to $d+k$ from the root, the vertices at distance $d+1$ through $d+k-1$ can be dominated the same way as they are in the whole graph, but you have no control of the size of the dominating sets of the vertices at distances $d$ or $d+k$, on the boundary of the layer: in the original graph, those vertices could be dominated by a small number of vertices in a different layer that aren't there when you restrict to that layer. So the solution is to find a system of layers with the property that the subsets of vertices at distance $d+1$ through $d+k-1$ within each layer form a partition of the whole graph, and then within each layer to only try to dominate that subset. To do this, you need to overlap the layers by two levels.


Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$

Time $O(d^3\log d)$

lemma: Fix any $x\in[0,1]^d$.  Then there is a set $S$ containing $d+1$ corners of $\{0,1\}^d$ that are closest to $x$ and such that $S$ is connected (meaning that the subgraph of the hypercube induced by $S$ is connected).

Proof.
First consider the case that $x$ has no coordinates equal to $1/2$.

Given any corner $a$ in $S$, flipping a coordinate $a_j$ of $a$ will not increase the distance from $a$ to $x$ if $|a_j - x_j| \ge 1/2$.

Consider any two corners $a,b$ in $S$ that differ in at least one coordinate $j$, and assume WLOG that $a_j=0$ and $b_j=1$.  If $x_j<1/2$ then flipping $b_j$ in $b$ gives another point in $S$ (because it decreases the distance from $b$ to $x$).  Or, if $x_j>1/2$ then flipping $a_j$ in $a$ gives a point in $S$.  Repeating this process for each differing coordinate in $a$ and $b$ gives a path connecting $a$ and $b$ within $S$.

If $x$ has coordinates equal to $1/2$, then, in choosing $S$, break ties among equidistant points by giving precedence to those with more zero coordinates.  Then the same argument will work.  QED

By the lemma, you can use a Dijkstra-like algorithm to find $S$.  Start with a corner closest to $x$ ($a$ with $a_j = 0$ if $x_j \le 1/2$).  Then repeatedly add to $S$ a corner that is closest to $x$ among those that are adjacent to some point in $S$.  Stop when $d+1$ points have been added.

Naively (using a min-heap to find the next closest point to $x$ in each iteration), I guess there are $d+1$ iterations, and each iteration requires $O(d^2)$ work to generate the $d$ neighbors of the added node (each of which has representation of size $d$), giving run time $O(d^3\log d)$.

Time $O(d^2\log d)$

Represent each corner $a$ implicitly as a pair $(h, d)$, where $h$ is a hash of the set of indices $i$ such that $a_i=1$, and $d$ is the distance from $x$ to $a$.  From a given corner $a$, the pairs for all neighboring corners can be generated in $O(d)$ time (total).  This brings the run time down to $O(d^2\log d)$.

Faster?

To make discussion easier, let's rephrase the problem as follows.  Given a sequence of $d$ non-negative numbers $y_1 \le y_2 \le \cdots \le y_d$, find the $d+1$ minimum-cost subsets of the numbers, where the cost of a subset is the sum of the numbers in it.  (To see the connection with the previous problem, take $y_i = |x_i - 1/2|$; then each subset $Y$ of the $y_i$'s corresponds to a corner $a(y)$ of the hypercube, where $a_i(y)$ is 1 if ($x_i \le 1/2$ and $y_i\in Y$) or ($x_i>1/2$ and $y_i\not\in Y$); and the cost of $Y$ is the distance from $x$ to $a(y)$.)

Here's a general idea for a faster algorithm.  Maybe somebody can figure out how to make it work.

Define an implicit directed graph where each node is a subset $Y$ of the $y_i$'s.  The start node is the empty set.  Represent the nodes implicitly as pairs $(h, c)$ where $h$ is the hash of the subset and $c$ is the cost.  For each subset $Y$, define the neighboring subsets somehow so that (i) if $Y\rightarrow Y'$ is a directed edge then the cost$(Y') \ge$ cost$(Y)$, and (ii) for any subset $Y'$, there is a directed edge $Y\rightarrow Y'$ from some subset $Y$ where cost$(Y) \le$ cost$(Y')$.  Then run Dijkstra's on this implicit graph starting at the start node.

Choose the edges (somehow) so that (i) and (ii) both hold, and the sum of the degrees of the cheapest $d+1$ nodes is $O(d)$.  (This is always possible, for example, take the edges to be those in some shortest-path tree rooted at the start.)  But can one define such a graph without a-priori knowledge of the shortest-path tree?  If so, this could lead to an $O(d\log d)$-time algorithm (?).


Why is shifting bits different from shifting qubits?

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special subclass of quantum operations.

As a technology

We're still working on how to implement a large-scale quantum computer. Part of the reason for this is that it is a non-trivial engineering problem to devise quantum memories on which we can reliably act.

Many of the proposed architectures involve physical qubits which are in a fixed(-ish) position, relative to the others. Whether these are quantum dots (attached to a substrate), ions in a linear trap (mobile but often penned in between two other ions), or even nuclear spins in liquid NMR (locations fixed mostly by the chemical bonds within each molecule), those qubits don't have much freedom to move relative to the ones you want it to interact with.
You can't necessarily shuffle them around like cups and balls.

The fixed wires in a classical circuit get around this physical location problem by being physically extended. The wire acts as if tracing out the trajectory of "moving" logical bits, and may weave around each other somewhat between two logic gates. When we draw quantum circuit diagrams, we're dreaming of this — but at least one of the dimensions in the diagram represents not space, but time between the physical operations which we perform. Not many physical architectures for quantum information admit that sort of physical extension, while keeping the quantum bit coherent and available to be acted upon. If locations are more or less fixed, this prevents us from literally swapping around the qubits.

In summary, in quantum implementation, we can't be confident that SWAP operations will be easily achievable "in hardware", i.e. by swapping around the physical qubits. We thus have to resort to be achieving SWAP operations "in software" — by performing suitable operations to 'transport' the information from one physical qubit to another. Thus our interest in decomposing SWAP in terms of elementary gates.

As a model of computation

As a part of theory of computation, you are exactly right: decompositions of SWAP are only a curiousity, much like the logical universality of the NAND gate. It is worth taking note of, in elementary courses; but much beyond that we treat decompositions of SWAP almost exactly as seriously as we do the decomposition of classical algorithms into NAND gates — not very seriously, most of the time. So long as we consider a model of computation in which elementary gates have a constant cost and which generate SWAP, then SWAP can be performed with at most a constant cost — and if the cost due to SWAP gates does not dominate the run-time of the algorithm, then talking about them doesn't really shed any insight onto the complexity of a problem.

Of course, because of the technological promise of quantum computation, the technical difficulty in implementing quantum computers, not to mention the promise of any technique (including classical ones) to simulate bits of quantum mechanics, specialized and related models of computation have attracted some theoretical interest. One of these are "matchgate" circuits, which may be described as unitary circuits in which

Qubits are arranged in a linear array;
Only two-qubit nearest-neighbor unitary transformations are allowed (and possibly Hadamard operations, on the first qubit only);
All two-qubit operations are of the form $$\begin{bmatrix} a_{00} & 0 & 0 & a_{01} \\ 0 & b_{00} & b_{01} & 0 \\ 0 & b_{10} & b_{11} & 0 \\ a_{10} & 0 & 0 & a_{11} \end{bmatrix} \quad\text{where $\begin{bmatrix} a_{00} & a_{01} \\ a_{10} & a_{11} \end{bmatrix}, \begin{bmatrix} b_{00} & b_{01} \\ b_{10} & b_{11} \end{bmatrix} \in \mathrm{SU}(2)$}$$
  i.e., acting unitarily (with determinant 1) on the odd- and even-parity subspaces of the pair of qubits.

These computations can be efficiently simulated by classical computers (provided that the coefficients are efficiently computable, etc.) However, if you consider circuits which have these gates, and also SWAP gates, they become universal for quantum computation. The same holds if you allow the gates to act even on next-nearest neighbour qubits, or allow Hadamard operations on other lines than just the first. What appear to be trivial modifications of the model, which one could imagine performing by just moving qubits around, transform a model which is tractible to simulate to one which (we think) is intractible to simulate. Nor, obviously, can we decompose SWAP into gates which are allowed.

In summary

From a theoretical perspective, SWAP operations are exactly as boring as you think they should be, for much of the research in quantum computation. But a model of computation is a mathematical model of something we hope to achieve in hardware: the model is not necessarily representative of reality. And even if SWAP is boring in one model of computation, that doesn't mean it is boring in another model!

We are complacent about SWAP in classical computation because electronic computers are a mature technology in which these details are mostly safe to ignore. As soon as you switch models of computation, you must check your computational assumptions.


Sending people to lunch together with minimal repetition

This is sometimes known as the Social Golfer problem (see also the Wolfram MathWorld page and this page from CSPlib). Probably the most famous instance of this problem is Kirkman's Schoolgirl problem.


Complexity of graph isomorphism with properly colored edges (ref. request)

In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same arguments works for edge colors as well. For example, you could subdivide each edge and instert a new vertex that encodes the edge color.


Is there a concept of something like co-applicative functors sitting between comonads and functors?

First of all:

  Any monad is also an applicative functor and any applicative functor is a functor.

This is true in the context of Haskell, but (reading Applicative as "strong lax monoidal functor") not in general, for the rather trivial reason that you can have "applicative" functors between different monoidal categories, whereas monads (and comonads) are endofunctors.

Further, identifying Applicative with strong lax monoidal functors is slightly misleading, because to justify the name (and the type signature of (<*>)) requires a functor between closed monoidal categories which preserves both the monoidal structure and the internal hom. This could plausibly be called a "lax closed monoidal functor", except that a functor between monoidal closed categories that preserves either property preserves the other in the obvious way. Because Applicative describes only endofunctors on Hask preserving the monoidal structure of (,), its instances gain a lot of properties automatically, including their strength, which can thus be elided.

The apparent connection with Monad is arguably an artifact of the implicit limitations on Applicative causing aspects of their respective monoid structures to coincide, a happy coincidence which unfortunately does not survive dualization.

Just as a comonad on a category $C$ is a monad on $C^{op}$, an oplax monoidal functor $C \rightarrow D$ is a lax monoidal functor $C^{op} \rightarrow D^{op}$. But $ \boldsymbol{Hask}^{op}$ is not monoidal closed, and a co-Applicative that doesn't include function application hardly merits the name. Anyway, the result wouldn't be terribly interesting:

class (Functor f) => CoMonoidal f where
    counit :: f () -> ()
    cozip :: f (a, b) -> (f a, f b)

We could instead imagine a notion of "colax closed functor", which would look much more like Applicative if it existed. Unfortunately, $\boldsymbol{Hask}^{op}$ is not (to the best of my knowledge) a closed category at all: newtype Op b a = Op (a -> b) in $\boldsymbol{Hask}$ corresponds to morphisms $b \rightarrow a$ in $\boldsymbol{Hask}^{op}$, but Op b a doesn't work as an internal hom there--because the arrows are reversed some sort of co-function would be required instead, which we can't define in general for $\boldsymbol{Hask}$.

If we simply pretend that "colax closed functors" existed for $\boldsymbol{Hask}$, and furthermore worked in the way we'd naively hope they would, a co-Applicative based on that would probably look like this:

class (Functor f) => CoApplicative f where
    copure :: f a -> a
    coap :: (f a -> f b) -> f (a -> b)

Adding duplicate :: f a -> f (f a) to copure would produce a comonad (assuming the laws are satisfied), of course. But there's no obvious relationship between coap--whatever it might be--and extend :: (f a -> b) -> f a -> f b. Comparing the types it becomes clear that the dualization is happening in different ways: the comonoidal structures underlying duplicate and cozip have little to do with each other or with coap (which probably doesn't make sense anyway), whereas liftA2 (,) and (<*>) are equivalent and can be derived from join.

Another possible way of dualizing Applicative, which has even less to do with comonads, is to consider contravariant monoidal functors:

class (Contravariant f) => ContraMonoidal f where
    contraunit :: f a
    contrazip :: f a -> f b -> f (Either a b)

But this runs afoul of the same issues as above, namely that $\boldsymbol{Hask}^{op}$ is not a closed category. If it were, we would have some type b <~ a such that we could write functions like contracurry :: (Either c b <~ a) -> (c <~ (b <~ a)) and contraapply :: b -> Either a (a <~ b) and so on that actually worked as expected.

If memory serves me, the obstacles here are not specific to Haskell, but rather arise from $\boldsymbol{Hask}$ being cartesian closed (up to the usual hand-waving, of course), a property it shares with most typed lambda calculi, so you're not likely to get very far with a CoApplicative in most settings.

However, in a monoidal closed category more hospitable to dualization you might have better luck. In particular, I believe both Kleisli (Cont r) and its opposite category are monoidal closed, so that might be a better context to explore these ideas.


Random 3-SAT: What is the consensus experimental range of the threshold?

In light of the Ding--Sly--Sun verification of the 1-step Replica Symmetry Breaking picture for kSAT (when k is large enough) I think experts would now be pretty surprised if the MPZ/MMZ-conjectured formula for the 3SAT satisfiability threshold (approximate value: 4.2667) is incorrect.


This was proven in

  M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, pages 28–76, 1994.

This is mentioned in e.g. this paper (Section 1.1.2), which does a pretty good job (in my opinion) of summarizing the landscape.


Family of functions with properties similar to k-wise independent hash functions

Let $m = 1 + \log \ell$. Identify a hash function $h \colon \{0, 1\}^k \to \{0, 1\}^m$ with its $n$-bit truth table $h \in \{0, 1\}^n$ where $n = m \cdot 2^k$. Our hash family $\mathcal{H} \subseteq \{0, 1\}^n$ consists of an $\varepsilon$-biased set for a suitable $\varepsilon = \ell^{-\Theta(k)}$. Explicit constructions of such a hash family are known with
$$
\log |\mathcal{H}| = O(\log(n/\varepsilon)) = O(k \log \ell) = O(k \log k).
$$
See e.g. this paper.
To prove that this works, fix any $\vec{x} = (x_1, \dots, x_{\ell}) \in \mathcal{S}$. Let $f_{\vec{x}} \colon \{0, 1\}^n \to \{0, 1\}$ be the function indicating whether there is a collision on the last hash, i.e.,
$$
f_{\vec{x}}(h) = \bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq h(x_{\ell})).
$$
We will show that $\mathcal{H}$ fools this function, i.e., $|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr[f_{\vec{x}}(U_n) = 1]| \leq 2^{-k}$. Conditions 1 and 2 will follow.
For each $z \in \{0, 1\}^m$, define $f_{\vec{x}}^{(z)} \colon \{0, 1\}^n \to \{0, 1\}$ by
$$
f_{\vec{x}}^{(z)}(h) = \left(\bigwedge_{i = 1}^{\ell - 1} (h(x_i) \neq z)\right) \wedge (h(x_{\ell}) = z).
$$
For a fixed $z$, the function $f_{\vec{x}}^{(z)}$ can be computed by a read-once CNF with $\ell-1+m=O(\ell)$ clauses that reads the bits of the truth table of $h$. For a suitable $\varepsilon = \ell^{-O(\log(1/\delta))}$, an $\epsilon$-biased distribution fools such read-once CNFs with error $\delta$ -- see this paper. Therefore, $\mathcal{H}$ fools $f_{\vec{x}}^{(z)}$ with error $\delta$. Now, $f_{\vec{x}} = \sum_z f_{\vec{x}}^{(z)}$, so by the triangle inequality, $\mathcal{H}$ fools $f_{\vec{x}}$ with error $\delta \cdot 2^m$. Choosing $\delta = 2^{-k - m}$, we have $\varepsilon = \ell^{-O(k + m)} = \ell^{-O(k)}$ as promised.
Now let's see how conditions 1 and 2 follow. For any $\vec{x} \in \mathcal{S}$, we have $\Pr[f_{\vec{x}}(U_n) = 1] = (1 - 2^{-m})^{\ell - 1}$. This value is independent of $\vec{x}$, and it changes by at most $2^{-k}$ when we use $\mathcal{H}$ instead of $U_n$, so for every two $\vec{x}, \vec{x}' \in \mathcal{S}$, we have $|\Pr_{h \in \mathcal{H}}[f_{\vec{x}}(h) = 1] - \Pr_{h \in \mathcal{H}}[f_{\vec{x}'}(h) = 1]| \leq 2 \cdot 2^{-k}$, verifying condition 1. Meanwhile, by the union bound, $\Pr[f_{\vec{x}}(U_n) = 0] \leq \ell 2^{-m} \leq 1/2$. Again, when we switch to $\mathcal{H}$, this value increases by at most $2^{-k}$, verifying condition 2.


The usual course is to feign ignorance and let it happen.

However, it is generally bad, so you'd ideally take steps to make it less likely to happen. The brute force solution is of course to simply check for equality and reselect one of the parents if necessary. You can do this, but there's a decent chance that if all you do is throw away the duplicates, the overhead of checking every time may start to limit the returns you get.

Another way to minimize these effects is to use a selection operator that is less biased. Roulette-wheel selection has a very high probability of selecting from only the handful of best individuals in many cases (depends on the particular distribution of fitness values of course). You're probably better off starting off with tournament selection as your default choice. It will give you a wider coverage of the parent pool, which keeps more diversity around for longer. Also, you can tweak the knobs a bit by looking at how you do environment selection (replacing old parents by some combination of old parents and new offspring). The more strongly elitist you are, the faster you'll converge, which you usually want to avoid.

One of the best black-box GAs out there is CHC (Eshelman, 1990) (always be wary of black boxes, but if you're going to treat the method as one, CHC seems to be one of the more effective ones). CHC is worth looking at, partly because it is a pretty good search algorithm, and partly because it provides a window into the types of things you can do to a standard GA to try and exert a bit more control over what it's doing.

CHC takes a very odd approach. It pairs parents completely randomly and without replacement. This means that every parent is selected exactly once (recombination produces two offspring, so each parent is selected as part of one mating pair giving N/2 pairs * 2 offspring/pair = N offspring). Crossover is "HUX" or half-uniform crossover, which produces offspring maximally distant from their parents. Combined, these give a very explorative search. In addition though, it is maximally elitist. Of the N parents and N offspring, the best N of the total are kept. This drives convergence very quickly -- very exploitative. Finally, parents produce no offspring at all if they are closer than a threshold value to one another. The threshold starts at L/4 (L=length of encoding), and is decremented each time zero offspring are produced in a generation. Thus the number of offspring produced in each generation is variable, and this number is used to determine how much the population has converged. At some point, when it has converged sufficiently (when the threshold reaches zero), CHC performs a "cataclysmic mutation" in which all but one individual have 35% of their bits randomly flipped and the process restarts.

Unfortunately the original paper describing CHC is only available in dead-tree form as far as I know. However, you can find a few descriptions online and in other papers that reference it.


Intermediate/Coding representation for Levenshtein Distance

There's indeed some research in this vein for the edit distance with some positive and some negative results. (I might not be understanding the question precisely, so I'll try to answer questions I know to answer.)

Here's one interpretation: (I1) you want to compute, for each string A a set f(A) such that, for any two strings A,B, the edit distance ed(A,B) is equal to the symmetric difference between f(A) and f(B) (in some sense the opposite of intersection of the two sets). This question has been well-studied (though by far is not solved), and is known as the question of embedding edit distance into Hamming distance ($\ell_1$). In particular, achieving (I1) precisely is not possible, but is possible up to some approximation (i.e., we approximate ed(A,B) up to some factor):

Krauthgamer and Rabani prove that $\Omega(\log n)$ approximation is required ($n$ is the length of the strings);
Ostrovsky and Rabani prove that $2^{O(\sqrt{\log n\log\log n})}$ approximation is achievable.

Here's a slightly more liberal interpretation: (I2) we produce some sketch f(A) for each string A, and we estimate the distance ed(A,B) via some calculation on f(A), f(B) (i.e., not necessarily by taking the symmetric difference).  The question is to have f(A) to be much shorter than the length of the original string, $n$ (otherwise, one has a trivial solution by f(A)=A). This interpretation (I2) is more general than (I1) (=easier to achieve), though we do not know of any strictly better solutions. There's some partial progress, where the estimation of ed(A,B) is done from f(A) and B (i.e., one string, say B, is fully known).

There's surely more literature in this vein, but let me know first if this is anywhere close to what you meant.


Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?

Take any language $L$ (that consists of binary strings). Construct the set $S$ of graphs as follows:

For each string $x \in L$ with $|x| = n$, we have the graph $G_x = (V_x,E_x)$ in $S$, with the set of nodes $V_x = \{1,2,...,3n\}$ and the following edges: if bit $i$ of $x$ is $0$, then the nodes $3i-2$ and $3i-1$ are adjacent, otherwise $3i-2$ and $3i$ are adjacent. There are no other edges.

Now let $p$ be a permutation of $\{1,2,...,3n\}$. Assume that $p$ is an automorphism of some graph in $S$. That is, $p$ is an automorphism of $G_y$ for some $y \in L$. Let $i \in \{1,2,...,n\}$. Let us consider the following two cases:

$p(3i-2) = 3i-1$, $p(3i-1) = 3i-2$, $p(3i) = 3i$. Then we must have bit $i$ of $y$ equal to $0$.
$p(3i-2) = 3i$, $p(3i-1) = 3i-1$, $p(3i) = 3i-2$. Then we must have bit $i$ of $y$ equal to $1$.

Hence if we can solve the question "is a given $p$ automorphism of some $G \in S$", we can also solve the question "is a given string $y$ in $L$". Moreover, if we can do the former in, say, polynomial time in $|p|$, we can do the latter in polynomial time in $|y|$ as well.

Now you can just let $L$ be your favourite NP-hard problem. Or the halting problem...


Wouldn't the calculus of constructions with linear types be a simple functional core that is consistent and expressive?

This is a tough question to answer, since simplicity is in the eye of the beholder.

Certainly $\lambda$-encodings have their drawbacks, there are reasons why Coq decided to move away from them, the most obvious one is the inability to introspect the subterms during recursion. The second is the general awkwardness in defining deeply or mutually recursive functions.

As you note, the "fix-encoding" avoids this but then it is hard to define non-constant functions (which is the point Damiano brings up)! You have to choose: introspection or recursion. Often we want both.

I'm also a bit skeptical of Gabriel's proposal: how does he compute exponentials on "native" ints without recursion?

In addition, the fact that EAL can only express elementary functions seems intuitively like it should restrict "natural" ways of writing recursions. In particular this shouldn't be well-defined:

Fixpoint acker m := match m with
| O => S
| S m => (fix acker' f n := match n with
    | O => f 1
    | S n => f (acker' f n)
    end)
   (acker m)
end.

since it defines a non-elementary function. So what feature of EAL is preventing this definition? If I understand correctly (and I'm not sure I do), the term f (acker' f n) cannot be well-typed, there must be some "stratum" which prevents the final application of f.

So certainly the natural way to write this function is forbidden. What other natural things are forbidden in this framework? It's hard to say without asking a specialist, but my guess is that there will be a fair number of things. Linear type systems can be powerful frameworks, but they aren't very convenient or natural for writing programs.

It's also an important fact (but maybe this is asking for a lot) that $0\neq 1$ is directly provable in Coq, thanks to large elimination. Is adding this feature easy in your proposal?

Finally, there's something I'm always worried about when I hear about type systems with linear logic: how hard is it to write a type checker? Certainly the checker has to figure out which pieces of the context go where when performing checking. Also the user or the front-end has to figure out where to put all the !s, if you want to have any non-linear components (and you usually do!).

To summarize, my answer to the question "is EAL with dependent types simple, consistent and expressive?" is probably not: it is probably consistent, but I'm not sure it's simple, and I don't think it is sufficiently expressive.

However, there is a "simple" way to refute this claim: write down the system definition, ideally prove it consistent, and write down some simple functions using it, probably up to, say, red-black trees or something. If the fully detailed syntax and typing rules is large, then the system is complex, if it is very tough to write down the functions, then it is insufficiently expressive. If it is neither of those, then you've answered a tough open problem in type theory!


Here is a technical paper on the LMAX Architecture (I just followed a link found on the blog you linked here): http://disruptor.googlecode.com/files/Disruptor-1.0.pdf

An example of a multicast graph is on page 9 of the PDF. There are also examples of multicast graphs (compared to various other options) here: http://en.wikipedia.org/wiki/Multicast


Data processing inequality for interaction information

Since the interaction information can be either negative or positive, and a Markov chain that erases everything can be used to take the interaction information to $0$, without further conditions the answer is "no".


The following is according to Nick Pippenger:

The relevant references are as follows.  Steve described NC as Nick's Class in his paper "Deterministic CFL's Are Accepted Simultaneously in Polynomial Time and Log Squared Space" (ACM STOC, 11 (1979) 338-345)  on SC, and I described SC as Steve's Class in my paper "Simultaneous Resource Bounds'' (IEEE FOCS, 20 (1979) 307-311)  on NC.  But the names originated about a year-and-a-half earlier, when I visited the University of Toronto CS Department (January through June, 1978).  That's when the study of the two classes began, with Steve defining SC and me defining NC, and various people in the department (I think Allan Borodin was the first) using the two names.  The following fall, Steve submitted the paper cited above. I was on the program committee for that STOC, and not allowed to submit papers to it, so my paper appeared in the following FOCS conference.
Best wishes,
Nick


Calculating the instantaneous period of a wave

The instantaneous frequency of a wave is defined as $f(t) = \frac{1}{2\pi}\frac{d\phi}{dt}$ where $\phi$ is the instantaneous phase. See the Wikipedia page on Instantaneous Frequency.

Presumably you have discrete data, in which case you need to estimate $\phi$ and its derivative numerically.

This isn't an entirely meaningful measure, since it doesn't make very much sense to ascribe a frequency to a non-periodic function, but nonetheless there does seem to be a convention for it.

Let me close by saying that I don't consider this a TCS problem. It is firmly in signal processing territory, and so I wouldn't consider here the ideal venue for such questions.


Let me give a toy example of the relativization barrier. The canonical example is the time hierarchy theorem that ${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$. The proof (by diagonalization) is only a little more involved than the proof that the halting problem is undecidable: we define an algorithm $A(x)$ which simulates the $x$th algorithm $A_x$ on input $x$ directly step-for-step for $t(|x|)$ steps, then outputs the opposite value. Then we argue that $A$ can be implemented to run in $t(|x|)^2$ time.

The argument works equally well if we equip all algorithms with access to an arbitrary oracle set $O$, which we assume we can ask membership queries to, in one step of computation. A step-for-step simulation of $A_x^O$ can also be carried out by $A$, as long as $A$ has access to the oracle $O$ too. In notation, we have ${\bf TIME}^O[t(n)] \subsetneq {\bf TIME}^O[t(n)^2]$ for all oracles $O$. In other words, the time hierarchy relativizes.

We can define oracles for nondeterministic machines in a natural way, so it makes sense to define classes $P^O$ and $NP^O$ with respect to oracles. But there are oracles $O$ and $O'$ relative to which $P^O = NP^O$ and $P^{O'} \neq NP^{O'}$, so this kind of direct simulation argument in the time hierarchy theorem won't work for resolving $P$ versus $NP$. Relativizing arguments are powerful in that they are widely applicable and have led to many great insights; but this same power makes them "weak" with respect to questions like $P$ versus $NP$.

The above is, of course, a toy example -- there are many other more complicated examples of arguments in complexity which still relativize (i.e., hold up when arbitrary oracles are introduced).


MaxCut can be solved in polynomial time in $K_5$-minor-free graphs but is NP-hard in $K_6$-minor-free graphs (in particular, for apex graphs of planar graphs) [Barahona 1983].

See also this WG 2010 paper and slides by Marcin Kamiński.


What's the relationship between ASP-complete and #P-complete?

Let an ASP-complete problem Q be given.  There is an ASP-reduction from 3SAT to Q and all ASP-reductions are parsimonious, hence it serves as a parsimonious reduction from #3SAT to #Q.  Since #Q is in #P and #3SAT is #P-hard, #Q is #P-complete.


For such questions, you often get the right intuition by thinking of "flat" random variables. That is, think of $X$ as the uniform distribution over a set $A$ of size $2^{H(X)}$ and of $Y$ as the uniform distribution over a set $B$ of size $2^{H(Y)}$.

So, the question you're asking is (roughly speaking) what can you say about the size $|A+B|$ compared to $|A|$ and $|B|$. Generically (e.g., if they were random sets) then indeed you'll have $|A+B| \sim |A|\cdot |B|$ which corresponds to $H(X+Y) \sim H(X)+H(Y)$.

There are some special cases when $|A+B| \ll |A|\cdot |B|$, most notably when $A$ and $B$ are intervals (or more generally arithmetic progressions). There are some results that say that (at least under some conditions and if $|A+B|$ is almost as small as it can be) this is the only case. The area that studies such questions is known as "additive combinatorics", and some results have the flavor that in a group $(G,+)$ if $|A+B|=O(|A|+|B|)$ then $A,B$ are approximately subgroups of $G$ (as you mention in your question, Terence Tao's blog discusses some such results, generally speaking set size results can be transferred to the entropy setting).

The case you describe roughly corresponds to the case where $A$ is an integer interval $[a..b]$ and $B$ is an integer interval of the form $[0..c]$  (in fact, if don't try to take advantage of concentration and shoot for a $(1/2)\log n$ entropy bound, one would have $c=1$ and $a=0$ and $b=k$ for $k=1,...,n-1$ as you apply this repeatedly, however actually this will be more like $a \sim k-\sqrt{k}$ , $b \sim k+ \sqrt{k}$). Obviously in this case $|A+B| \leq |A|+c$, but I'm not sure if there is a more general bound this falls from as a special case.