What language $L \in NCM$ has $\overline{L} \not \in NCM$?

Letting $L$ be the complement of the language of copies $\{ww \mid w \in \{a, b\}^*\}$, you get your statement.  First, it is indeed recognized by a NCM — as is the complement of the language of palindromes.  The NCM simply ensures that two positions in the input word chosen non deterministically hold different letters, and checks that they are separated by exactly half the length of the input.

Now Parikh Automata were introduced by Klaedkte and Rueß in ICALP'03.  The technical report version, available on Klaedkte's webpage, states the equivalence of Parikh Automata and NCM as Theorem 29 and 31.

Relying on a combinatorial argument, they show that the complement of $L$ is not recognizable by a Parikh automaton, Lemma 26.  Further lemmata have been developed to show that some languages are outside this class (we present a few in this journal paper).


I would amend your definition of second quantization.  It is not a procedure that is applied only to the electromagnetic field.  It is more properly a process in which something like the Schrodinger equation is re-interpreted as a classical field, which is then quantized.  This is the standard old-fashioned way to move from single-particle quantum systems to multi-particle quantum systems in which particle creation and annihilation can be described via unitary operators.

I'm not sure that the paradigm of second-quantization makes sense in the context of quantum computation.  To do so, one would need to interpret the "first-quantized" theory as a system which conserves something like particle number.  The "second-quantized" theory allows for a description of systems with different particle numbers.  Qubits obey neither Bose-Einstein nor Fermi-Dirac statistics and thus there is nothing analogous to "particle-number" in a qubit system.  From this point of view it is hard to see that "second-quantizing" a qubit system would lead to something sensible.


Lower Bound for the Parity Learning Problem

The question is about recovering with membership queries for which it is well known that O( k log n) queries suffice (via BCH codes see Hoffmeister's paper or my COLT 2005 paper). In terms of lower bounds \Omega(k log n) trivially follows from counting the number of parities and using the fact that they are all completely uncorrelated (basic packing-based lower bound).


Is solving systems of equations modulo $k$ in $\mathsf{coMod}_k\mathsf L$ for $k$ composite?

I'm happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete.

We can actually reduce this problem to the special case of prime powers. One may show that:

  Normal Form. The class coModkL consists of langauges L of the form L = Lp1 ∩ Lp2 ∩ ... ∩ Lpr , where Lpj ∈ coModpj L and where pj ranges over the prime factors of k.

By the Remainder Theorem, any solution to a system of equations modulo each of the prime powers $p_{\!j}^{e_j}$ dividing k gives rise to a solution to the same system, mod k.
So if solving systems of linear equations over $p_{\!j}^{t_j}$ is contained in coModpj L, it follows that solving systems of equations mod k is contained in coModkL.

There's a standard algorithm, described by McKenzie and Cook for reducing linear congruences modulo a prime power to constructing a spanning set for its nullspace (namely, for Ax = y over a given ring, construct a basis for the nullspace of [ A | y ] and see if any solutions exist with a final coefficient of −1); and subsequently for reducing the construction of nullspaces modulo prime powers to constructing nullspaces modulo primes, and matrix multiplication modulo prime powers. Both of the latter tasks are problems which are feasible for coModkL, provided that you can construct the matrices involved.

It turns out that the matrices involved in the reduction of McKenzie and Cook can themselves be computed by matrix multiplication, and (crucially) division by a constant factor. Fortunately, for prime powers, the coefficients of the matrices involved can be computed on the work-tape using an oracle for coModpL-machines; and the division by a constant can be performed in NC1, which is again feasible in coModpL. So it turns out that the whole problem is ultimately doable in coModkL.

For complete details, see [arxiv:1202.3949].


These are interesting open problems. Your second question effects a Karp-Lipton collapse.

Note that Toda's theorem gives you $NP\subseteq P^{PP}$, but that does not suffice for our purposes. We want to know whether $NP^{PP}\subseteq P^{PP}$, which makes this a funny question in my opninion.

1: Note that $NP^{PP}=NP^{\#P}$ and $P^{PP}=P^{\#P}$, so your first question has already been asked and answered here. Your are asking whether the polynomial hierarchy collapses relative to a $PP$ oracle (or equivalently relative to a $\#P$ oracle). According to this answer, that is an open question. If $P^{PP}=NP^{PP}$ then clearly the hierarchy does collapse relative to that oracle.

2: I think it is an open problem, and would be answered if we know whether the polynomial hierarchy collapses relative to a $PP$ oracle. Because, note that you get a Karp-Lipton collapse:

$$NP^{PP}\subset P^{PP}_{/poly} \text{ implies }{\Sigma_2^P}^{PP}={\Pi_2^P}^{PP}$$
Here I have only used the fact that the Karp-Lipton theorem relativizes. Whether you see this as evidence against the conjecture depends on whether you think the polynomial hierarchy collapses relative to $PP$, because if you think it collapses all the way down to $P$ relative to this oracle, then yes, $NP^{PP}=P^{PP}\subset P^{PP}_{/poly}$.

Going further, keep in mind that $$PP\subseteq P^{PP}\subseteq NP^{PP}\subseteq PP^{PP}=C_2^P,$$ and we do not have an oracle which separates $PP\subsetneq PP^{PP}$, so an oracle separation towards your first question, $P^{PP}\subsetneq NP^{PP}$, is more ambitious than that, and would be a nice result in its own right. Currently we do not even have an oracle relative to which $P^{PP}\subsetneq PSPACE$.

Personally I'd love to see the flipside: is $PP\subseteq NP_{/poly}$? We already know $PP$ is not contained in $P_{/n^k}$ for any fixed $k$. Can we show the same for $NP_{/n^k}$?


Is the 3-sphere recognition problem NP-complete?

If it's NP-complete, then wouldn't you have proved that no set of (uniformly) polynomial-time computable invariants of 3-manifolds distinguishes 3-spheres from other 3-manifolds. I would be very surprised if this is known.


Nondeterminism is on average useless for circuits?

1) Realize that nondeterminism is a red herring here. You could have used alternation or circuits that have gates that solve the halting problem. It boils down to a simple counting argument that once you fix the model, you can only compute $2^k$ functions that have a $k$ bit description.

2) For uniform classes like P this is more challenging, as there is no clear definition of "average function in P" and the counting arguments no longer work so cleanly. It's consistent with current knowledge that everything in P can be solved in nondeterministic linear time.


There is no Zoo-style reference yet, but a recent automata-theoretic survey of Giovanni Pighizzini has been useful to me, especially the slides from his talk.

Giovanni Pighizzini, Investigations on Automata and Languages over a Unary Alphabet, CIAA 2014.  doi:10.1007/978-3-319-08846-4_3


Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard?

Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question.

Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)


The probability by which Bloom filters preserves the order relation given a similarity measure on sets

This is not a direct answer to your question,  but it's related. The probability you want is precisely what is provided by min-wise hashing schemes. In particular, a min-wise hash takes a set and produces a single element, with the property that the probability of the two elements being identical is precisely the Jaccard similarity between the sets (intersection/union).


The map $f$ is not a contraction.  To see why, let's take for concreteness $R = 100$.  Suppose $w$ is a word and $A,B$ are two machines such that $t_A(w) = 200$ and $t_B(w) = 400$.  Then $d(A,B) = 100$.  Now $t_{f(A)}(w) = 100 + |w| + 2$ and $t_{f(B)}(w) = 200 + |w| + 2$, so $|t_{f(A)}(w) - t_{f(B)}(w)| = 100$ and $d(f(A),f(B)) = 100$ also.  But to have a contraction in the sense of the Banach fixed point theorem (also called a strict contraction) you need to have a constant $c < 1$ such that $d(f(A), f(B)) \le c d(A,B)$, so this can't be achieved.


Efficient algorithm for near-optimal edge-colourings of hypergraphs

The answer below breaks your condition that you don't want serious restrictions placed on your hypergraph, but it might be of interest if only as related work.

Your hypergraph (which I'll rename as a range space) has a corresponding dual range space (hypergraph) by interchanging the roles of vertices and edges. Your problem then amounts to coloring the elements of this range space so that a range of cardinality $r$ has $r$ colors. Let's call such a range colorful.

There's been some recent work on such "colorful coloring" problems for geometric range spaces, motivated partly by problems in sensor networks. A standard question that's asked is:

  Given a parameter $k$ and range space
  $S$, determine the function $c_S(k)$
  such that a $c_S(k)$ coloring of the
  elements of S guarantees that each
  range $r$ of $S$ has $\min(|r|, k)$
  colors.

Thus, $c_S(\Delta)$ is the quantity you're looking for (where $\Delta$ is the maximum cardinality of a range).

A related question is to determine $c_\tilde{S}(k)$, where $\tilde{S}$ is the dual range space (in effect, your original hypergraph). One example of the kind of results obtained is that:

  For $S$ being the space of halfplanes
  in $\Re^2$, $c_S(k) \le 3k-2$

A good reference for this body of work is the DCG paper by Aloupsis et al, and the references therein.


Complexity to calculate a full set of eigenvectors over a finite field

There will generally not exist a set of $n$ linearly independent vectors $x$ such that $Ax = x$; this can only happen for $A$ being the identity matrix. On the other extreme, there may be no such vectors at all. For example, the matrix
$$
A = \left(\begin{array}{cc} 0 & 1\\ 1 & 1 \end{array}\right)
$$
has full rank, but there are no nonzero vectors $x$ such that $Ax = x$. This is consistent with the fact that the characteristic polynomial of $A$ is $\lambda^2 + \lambda + 1$, which is irreducible over GF(2).

If you want to find the maximum number $k$ of linearly independent vectors $x$ such that $Ax=x$, compute the nullspace of $A - I$. This can be done using Gaussian elimination in time $O(n^3)$. Several other algorithms for this task also exist, and are described in textbooks on computational linear algebra.


When $m = O(\log n)$, you can use dynamic programming to find the optimum in polynomial time. The table contains Boolean-valued cells $T_{\ell,X}$ for each $\ell \in \{0,\ldots,k\}$ and $X \subseteq \mathcal{U}$, indicating whether there are $\ell$ sets which cover the elements in $X$.

When $m = O(\sqrt{n})$, say $m \leq C\sqrt{n}$, the problem remains NP-hard. Given an instance of SET-COVER, add $m$ new elements $x_1,\ldots,x_m$ and $(2C^{-1}m)^2$ new sets, consisting of non-empty subsets of the new elements, including $\{x_1,\ldots,x_m\}$ (when $m$ is large enough, $(2C^{-1}m)^2 < 2^m$). Also increase $k$ by one. The new $m,n$ are $m' = 2m$ and $n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$.


Approximation algorithm for graph problem

The problem you specify is called Uniform Labeling Problem and often arises in the field of computer vision. Kleinberg & Tardos give the LP-based 2-approximation you are looking for.

This problem also appears in the Williamson & Shmoys book as exercise 5.10.


PLANAR NAE $k$-SAT is in P for all values of $k$ .

Reason is that we can reduce PLANAR NAE $k$-SAT to PLANAR NAE $3$-SAT. Let $\phi$ be an instance of PLANAR NAE $k$-SAT, and suppose $\phi$ contains a clause $C$ with literals $\ell_1, \ell_2, \dots, \ell_k$. Introduce a new variable $v_C$, and replace $C$ with two NAE clauses $C_1$ and $C_2$. $C_1$ contains $3$ literals $\ell_1$, $\ell_2$, and $v_C$, while $C_2$ contains $k-1$ literals $\bar{v}_C, \ell_3, \ell_4, \dots, \ell_k$. It's easy to see that $C$ is satisfiable iff $C_1 \wedge C_2$ is and that the transformation preserves planarity. Now, we can repeatedly apply this procedure on the clauses to eventually obtain an instance $\phi'$ of NAE $3$-SAT as desired.


What is FO(REGULAR)? (The descriptive complexity equivalent of NC1)

Professor Immerman kindly answered this by email:

  The definition of FO(REGULAR) is the set of all decision problems that are reducible to some regular language via first-order reductions.

Additionally, since the word problem for $S_5$ (which is a regular language) is complete for $\mathsf{NC}^1$ under FO reductions, this means that FO(REGULAR) can be defined equivalently as the set of decision problems that are reducible to $S_5$.

Other logics equivalent to $\mathsf{NC}^1$:

FO with monoidal quantifiers (Barrington, Immerman, Straubing, 1990: On uniformity within NC1)
FO with "relational primitive recursion" and the BIT relation (Compton, Laflamme, 1990: An algebra and a logic for NC1)
FO with width-5 transitive closure (Immerman, 1987: Expressibility as a Complexity Measure: Results and Directions)


Maybe.

Becker, Coron, and Joux [EUROCRYPT 2011 describe an algorithm to solve random hard instances of Subset Sum (in fact, the more general Knapsack problem) in $\tilde{O}(2^{0.291n})$ time, beating the "meet in the middle" time bound $\tilde{O}(2^{n/2})$ by Shamir and Schroeppel [SICOMP 1981].  (Here, $\tilde{O}(f(n))$ is standard shorthand for $O(f(n)\operatorname{polylog} f(n))$.)

More recently, Dinur, Dunkelman, Keller, and Shamir [Crypto 2012], which establish better time-space tradeoffs (but do not improve worst-case running times) for a general class of cryptography problems that includes Knapsack.  Becker's techniques rely crucially on the observation that addition is both commutative and associative, but Dinur's techniques do not; for example, they also derive faster algorithms for solving random hard instances of permutation puzzles like the Rubik's cube.

It seems likely that Dinur's techniques would imply faster algorithms for (at least random hard instances of) your problem.


Is a theoretically secure key exchange possible?

I believe you are talking about the existence of information-theoretically (unconditionally) secure key agreement schemes. You can prove that such schemes cannot be achieved with only authenticated channels from Alice to Bob and Bob to Alice.

Nevertheless, if Alice, Bob, and Eve are in possession of some sort of correlated randomness, then it may be possible to construct such a scheme.

One such example is when a satellite broadcasts several random bits, and Alice, Bob, and Eve receive the bits through different binary symmetric channels with certain error probabilities. One can prove that, in this case, information-theoretical key agreement is possible, even when Eve's error probability is much lower than Alice's and Bob's.

A classic paper on this topic is "Secret Key Agreement by Public Discussion from Common Information" by Ueli Maurer.


Easy decision hard counting Parametrized

Finding $k$-path (simple paths of length $k$) in a graph is in $FPT$ and can be done in $O^*(2^k)$ with a randomized algorithm or $O^*(2.62^k)$ deterministically.

This is while Counting $k$-paths is $\#W[1]$-hard.

A more interesting example (decision is even in $P$ while counting is parameterized-hard) would be counting $k$-matchings in bipartite graph.
Not only that the problem is $\#P$-complete, it was recently shown to be $\#W[1]$-hard as well !


Terminology for games with incomplete information and no prior beliefs

Uncertainty in the absence of a prior distribution is sometimes called Knightian Uncertainty in economics. There are a couple of recent papers studying how to deal with knightian uncertainty in mechanism design. See for example:

The Knightian Truthfulness of Classical Mechanisms

Knightian Auctions


A practical multi-word compare-and-swap operation

In a concurrent runtime environment simple things can seem weird ... hope this can help.

We have a BUILT-IN ATOMIC CAS1 having this semantic:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

We need to define an ATOMIC RDCSS function using CAS1 and having the following semantic:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Intuitively: we need to CONCURRENTLY change the value at addr2 only if *addr1 == oldval1 ... if another thread is changing it we can help the other thread to complete the operation, then we can retry.

RDCSS function will be used (see article) to define CASN. Now, we define a RDCSS Descriptor in the following way:

RDCSSDESCRI
int *addr1
int oldval1
int *addr2
int oldval2
int newval2

Then we implement RDCSS in the following way:

int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);
}

STEP1: first we try to change the value of *addr2 to our (own) descriptor d, if CAS1 succeeds then res == d->oldval2 (i.e. res is NOT a descriptor)
STEP2: check if res is a descriptor i.e. STEP1 failed (another thread changed addr2) ... help another thread completing the operation
STEP3: retry the STEP1 if we didn't succeed in storing our descriptor d
STEP4: if we fetched our expected value from addr2 then we succeeded in storing our descriptor (pointer) in addr2 and we can complete our task storing newval2 to *addr2 iif *addr1 == oldval1

ANSWER TO YOUR QUESTION

If we omit STEP4 then the if(... && *addr1==oldval1) *addr2=newval2 part of the RDCSS semantic will never be executed (... or better: it can be executed in an umpredictable way by other threads helping the current one).

As pointed out by you in your comment the condition if(res == d1->oldval2) at STEP4 is unnecessary: even if we omit it, both CAS1 in Complete() will fail because *(d->addr2)!=d. Its only purpouse is avoid a function call.

Example T1=thread1, T2=thread2:

remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)


Need a term for a graph-theoretic/metric concept

Sloan calls this the "covering radius" when distributing points on a sphere.  http://www2.research.att.com/~njas/coverings/


Law of excluded middle does not make intuitionistic logic inconsistent; intuitionistic logic is in many regards a subset of classical logic (of course classical logic can't have proof objects and there are other diffrences). In Agda you can use the postulate keyword for such things. The following could be added to your postulates.

$LEM : \{A : Set\} \to A \lor \neg A$

I was doing some proofs out of a book on first order logic where I found it more useful to have double negation elimination than LEM.

$\neg\neg E : \{A : Set\} \to \neg\neg A \to A$

One of course implies the other so take your pick.

edit:
One of your previous questions gives some insight here as well. cody made mention of Agda being predicative. Martin Lof type theory is predicative (as well as Agda which is basically MLTT). Agda still has large elimination and adding LEM does not make the logic inconsistent. Martin Lof originally tried to base MLTT off of System-F but its impredicative nature kept getting in the way of such things. This is part of the reason why MLTT is predictive.


Resolution augmented with the rule of symmetry or the rule of extension

First, ER p-simulates SR: for example, ER is p-equivalent to the extended Frege proof system (EF) which is p-equivalent to the substitution Frege proof system (SF), and it is easy to see that SF p-simulates SR (the symmetry rule amounts to substitution of a special kind).

On the other hand, Urquhart [1] proves an exponential lower bound on SR refutations of Tseitin tautologies for certain graphs. Since Tseitin formulas have polynomial-size ER (or extended Frege) refutations, this shows that ER is exponentially more powerful than SR.

Reference:

[1] Alasdair Urquhart: The symmetry rule in propositional logic, Discrete Applied Mathematics 96–97 (1999), pp. 177–193, doi: 10.1016/S0166-218X(99)00039-6.


The question has been resolved by Chris Godsil on Maths Overflow. I repost it here for completeness:

What follows is all quite standard, iirc it's in Aigner's book "Combinatorics" but my copy's out on loan....

Let $B$ be the vertex-edge incidence matrix of the graph. (Nothing's gained by deleting a row.) We want a subspace of codimension two in $GF(2)^{m+2}$ containing no column of B. If a and b are distinct non-zero vectors indexed by the vertices of $G$ and $x$ is a column of $B$, we have a map $\rho _{a,b}$ that sends $x$ to $(a^Tx,b^Tx)$ and $a^⊥∩b^⊥$ is a subspace of codimension two that does not contain a column if and only if $0$ is not in the image of $ρ_{a,b}$.

If we identify $V(G)$ with the standard basis for $GF(2)^{m+2}$ then the map that assigns the vector $ρ_{a,b}(ei)$ to the vertex $i$ is a proper 4-colouring of the vertices of $G$, as you can easily check. Hence a necessary condition is that $G$ be 4-colourable.

On the other hand, if $G$ is 4-colourable then we can colour it with the four elements of $GF(2)^2$. Let $a$ be the vector such that $a_i$ is the first coordinate of the colouring of the vertex $i$ and let $b$ be the vector such that $b_i$ is the second coordinate. The $ρ_{a,b}(e_i+e_j)≠0$ if $ij∈E(G)$ and so the kernel of $ρ_{a,b}$ is a subspace of codimension two that does not contain a column of $B$. (If $a=b$ we have a 2-colouring, which is impossible.)

So your question is equivalent to the 4-color theorem.


Looking for papers and articles on the Tarskian Möglichkeit

Rob, I didn't know this was called the Tarskian Möglichkeit, but Martin Escardo and I have been studying this operator (A -> B) -> A, in the more general case when falsity is an arbitrary formula B, for the past few years, mainly in connection with computational interpretations of classical theorems. If we let B be fixed, then we define

J A = (A -> B) -> A

It is easy to show that this is a strong monad. We call it the "selection monad" or the "Peirce monad", as J A -> A is Peirce's law. In fact, the seemingly absurd theorem you mentioned in your post is the cornerstone for our work on interpreting ineffective principles such as the Tychonoff theorem, for instance. Have a look at some of our papers, e.g.

Martín Escardó and Paulo Oliva. Sequential games and optimal strategies. Proceedings of the Royal Society A, 467:1519-1545, 2011.

Martín Escardó Paulo Oliva, The Pierce translation. Annals of Pure and Applied Logic, 163(6):681-692, 2012.

Or others found on our webpages: http://www.eecs.qmul.ac.uk/~pbo/

Any paper which mentions "selection functions" or "game" is related to the operator you are asking about.

I must warn we have been studying this operator in the setting of intuitonistic (minimal) logic. But I find it very interesting that you are looking at this in the more refined (substructural) settings of linear logic and Lukasiewicz logic.

Best regards, Paulo.


Subset of a bipartite graph with maximal number of minimal unmatched vertices

The problem is in $P$ by reducing the problem to submodular minimization.

Let $v(A)$ be defined as the size of the maximum matching in $G_{|A}$. $v$ is submodular. One way to see this is convert the problem to a max flow problem, and use the fact that the set function $c(U)=$ max flow from $U$ to $t$ defined over $V\setminus \{t\}$ is submodular.

I will use $f(A)$ to mean the $f(G_{|A})$ in your notation.

$f(A) = |A| + |V| - 2v(A)$. $|V|$ is a constant, so we can maximize over $f(A)-|V| = |A| - 2v(A)$, which is the same as minimize $g(A) = 2v(A)-|A|$. $g$ is a submodular function(difference of submodular and modular function), and you can apply any polynomial time submodular function minimization algorithm.

This can be extended to weighted case if weighted analogue of $v(A)$ is submodular.


Is it possible to compute whether two functions are extensional equal?

Yes. If you can verify that they are the same, then so can a computer.

Here's a quick specification for an integer sort in Coq:

Inductive natlist : Type :=
| nil : natlist
| cons : nat → natlist → natlist.

Fixpoint is_sorted (l : natlist ) : bool :=
    match l with
    |  nil => true
    |  (cons x nil) => true
    |  (cons x (cons y r)) => if x <= y then is_sorted (cons y r) else false
    end.

...

Theorem sort_spec : forall l, is_sorted (sort_list l).

A specification can be directly encoded into the declaration of sort using dependent types.

For this particular problem, John Darlington demonstrated in the 70s that 6 families of sorting algorithms can be derived by mechanically transforming the specification of a sort into an implementation; I believe this goes under the name "semantics-based program derivation."

In the software-engineering world, finding extensionally equivalent functions is known as "semantic clone detection."

Dave Clarke also gave a good answer to this question on the CS StackExchange: https://cs.stackexchange.com/questions/2059/how-do-you-check-if-two-algorithms-return-the-same-result-for-any-input

This all falls under the umbrellas of formal methods and programming languages. Denotational semantics are one class of techniques for modeling semantics, but they've fallen out of favor for being difficult to use compared to operational semantics.


State-of-the-art unification for associative-commutative functions

Here are the standard references on unification:

Franz Baader and Tobias Nipkow. Term Rewriting and All That. Cambridge University Press, United Kingdom, 1998. (Book homepage)
Franz Baader and Wayne Snyder. Unification Theory. In J.A. Robinson and A. Voronkov, editors, Handbook of Automated Reasoning, pages 447-533. Elsevier Science Publishers, 2001. (Online copy here)


Simple and cache-oblivious tries on fixed-length strings

Update: An idea very similar to this one is described in "Digital Access to Comparison-Based Tree Data Structures and Algorithms".

Here's an idea for a structure that might meet these bounds.
It uses an balanced binary search tree where each node is annotated with a pair of integers in $[-1,k-1]$ to indicate how much of the prefix of the key does not need to be compared again with the search key.

Notation

A shared prefix pair is a pair of integers associated with a key, called the focus, and a set of string keys not containing the focus, called the context.
For a focus $f$ and context $c$, if $\forall y \in c, f < y$, then the left shared prefix (the left value in the shared prefix pair) of $f$ and $c$ is $-1$.
Otherwise, let $g$ be the largest key in $c$ such that $g < f$.
This is called the left neighbor of $f$ in $c$.
Then the left shared prefix $i$ is the largest integer such that $f[i] > g[i]$ and $\forall j < i, f[j] = g[j]$.
The right shared prefix and right neighbor are defined symmetrically.

Search

Annotate each node in a balanced binary search tree with a shared prefix pair, using the key at that node as the focus and they keys of its ancestors in the tree as the context.
I'll first describe how to search for a string key (the needle, as in "needle in a haystack") in an annotated tree, then describe insertion and deletion.

During search, maintain a shared prefix pair with the needle as the focus and the keys of the nodes inspected during the search as the context.
By the definition above, we start with a shared prefix pair of $(-1,-1)$.

Assume we are searching for the needle $d$ with shared prefix pair $(i,j)$ in a tree with root $v$ with key $z$ and shared prefix pair $(p,q)$.
Since the search proceeds from parent to child, the prefix pairs share the same context and the same left and right neighbors, $a$ and $b$.

Now, if $i < p$, then $z[i] = a[i] < d[i]$, and $z < d$.
In this case, the search proceeds recursively to the right child of $v$.
$z$ is the new left neighbor of $d$ and $d$'s prefix pair stays the same.

If $i > p$, then $d[p] = a[p] < z[p]$, and $d < z$.
In this case, the search proceeds recursively to the left child of $v$.
$z$ is $d$'s new right neighbor and $p$ is the new right shared prefix of $d$.

For $j \neq q$, proceed similarly.

In the remaining case, $i = p$ and $j = q$.
Assume w.l.o.g., that $i \geq j$.
Find the first $i^{\prime} > i$ such that $d[i^{\prime}] \neq z[i^{\prime}]$ but $\forall n < i^{\prime}, d[n] = z[n]$.
If $d[i^{\prime}] < z[i^{\prime}]$, then $d < z$, so proceed to the left child of $v$.
The new right neighbor of $d$ is $z$ and the new right shared prefix of $d$ is $i^{\prime}$.
If $d[i^{\prime}] > z[i^{\prime}]$, then $d > z$, so proceed to the right; $z$ is the new left neighbor of $d$, and $i^{\prime}$ is $d$'s new left shared prefix.
The $j > i$ case is symmetric.

Search Performance

Letters are not compared unless $i=p$ and $j=q$.
At each step in which letters are compared, either the sum of the shared prefix pair increases or only one letter comparison is made.
We will discuss these two separately.

If only one letter comparison is made, a child pointer is immediately followed.
Since paths from the root to leaves are $O(\lg n)$ and $n \leq A^k$, fewer than $O(k \lg A)$ single-letter-comparison steps are taken.

If $p > 1$ letter comparisons are made in a step, the sum $i+j$ of the shared prefix pair increases by at least $p-1$.
Since the maximum possible sum is $2k$, $O(k)$ letter comparisons are made in comparisons that result in larger shared prefix pair sums.
However, shared prefix pair sums may seemingly decrease in non-letter-comparison steps when $i > p$ and $j$ is replaced by $p$ or $j > q$ and $i$ is replaced by $q$.
This is not the case, though:
If $i > p$ then $d < z$, so $j \leq q$.
If $j < q$, then $d$'s new right shared prefix is $j$, so $j = p$ and the shared prefix pair sum is not decreased.
Similarly, if $j = q$, then $d$'s new right shared prefix is $\geq j$, and the sum is not decreased.

Similarly, each step requires $O(1+p/B)$ block transfers if it makes $p-1$ letter comparisons.

Insertion and Deletion

To perform an insertion, first locate where the node with the key $d$ would be found if it were in the tree.
After modification, perform the necessary $O(\log n)$ restructuring necessary to restore balance.
Rotations might invalidate shared prefix pairs.

Consider the case of a left rotation:

  B
 / \
A   D
   / \
  C   E

    D
   / \
  B   E
 / \
A   C

The shared prefix pairs at A, C, and E all remain valid.
The left shared prefix of B and the right shared prefix of D also remain valid.
The right shared prefix at B is the left shared prefix at D from before the rotation.
The left shared prefix of D is the minimum of the left shared prefixes of D and B from before the rotation.

The right rotation and deletion cases are the same, mutatis mutandis.


Your question is somewhat ill-posed: given $n$ and $k$, it is easy to construct a Tanner graph with a 4-cycle and column weight at most 2.

Instead, you can ask the question of what is the maximum column weight of a Tanner graph, given that is has no 4-cycle. Assuming uniform column weights, then the maximum column weight is $O(\sqrt{k})$. This is known as the Kővári–Sós–Turán theorem (see e.g. here), which states that the number of edges in an $(n,k)$-bipartite graph without 4-cycle is at most
$$
(n-1)\sqrt{k} + k.
$$
If the Tanner graph has uniform column weights $d$, then it has $nd$ edges, which gives the bound on $d$.

This is tight up to constants for the case where $k = n$ (see e.g. here).


A counting subset sum problem with fixed subset size and bounded weights

Even if $s$ is not constant, a dynamic programming algorithm similar to that for the knapsack problem would work.  For this to be polynomial time, we need each $w_i$ to be polynomial in $n$ (implying that $k \leq \sum w_i$ is polynomial in n).

The idea is that $T(j,i)$ is the number of subsets of weight $j$ and cardinality $i$.  Start with all $T(j,i) = 0$ except $T(0,0) = 1$

Then:

For i = 1 to $n$
For j = 0 to $k$
For h = 1 to $s$
T(w_i + j,h+1) += T(j,h)

Then your answer is $\sum_{j \leq k} T(j,s)$

$s$, $n$, and $w_i$ (and therefore $k$) are all polynomial so all of this is polynomial.  Specifically this is at worst $O(n^2k)$ time.


Proof that the calculus of constructions extended with recursive types isn't strongly normalizing?

With general recursive types you can define the type

type T = T -> T

With that type you can type self-application -- and in fact, every term of the untyped lambda calculus, including any of the well-known fixed-point operators. For example, the Y operator:

Y = \f:T. (\x:T. f (x x)) (\x:T. f (x x))


There is a famous example of Cai, Fürer and Immerman, which shows that the $\mathcal{C}_{\infty\omega}^k$-hierarchy is strict and in particular that $\mathcal{C}_{\infty\omega}^\omega$ cannot express every query on finite structures. The paper is quite famous because it disproved a conjecture that IFP+C captures PTIME. Your proof that $\mathcal{L}_{\infty\omega}\equiv\mathcal{C}_{\infty\omega}$ is correct.


Complexity of a variant of partition problem

The problem of finding a maximum cardinality discrepancy partition (or determining that one doesn't exist) is solvable in pseudo-polynomial time even if a balanced partition is not given.

Suppose that the input is a multiset of positive integers $S = \{x_1, \ldots, x_N\}$. Let $K = \sum_{i = 1}^Nx_i$. Below I demonstrate a dynamic programming algorithm for finding a maximum cardinality discrepancy partition of $S$.

Suppose $s$, $i$, and $c$ are variables with $0 \le s \le K$ and $0 \le c \le i \le N$. Then define $p(s, i, c)$ to be true if and only if there exists a multiset $T \subseteq \{x_1, \ldots, x_i\}$ whose cardinality is $c$ and whose sum is $s$.

We can define a recurrence:

$p(s, 0, 0)$ is true iff $s = 0$.
$p(s, i, c)$ is true if either $p(s, i-1, c)$ or $p(s - x_i, i-1, c-1)$ is true.
$p(s, i, c)$ is false otherwise.

Using this recurrence we can compute the value of $p$ on all valid $s$, $i$, and $c$ in time polynomial in $N$ and $K$.

Furthermore, the predicate $\phi(c) = p(\frac{K}{2}, N, c)$ can be interpreted as "does there exist a subset of $S$ of cardinality $c$ whose sum is half of the sum of $S$?" or equivalently as "does there exist a partition of $S$ with cardinality discrepancy $|N-2c|$?". Thus, after finding all the values of $p$, we can simply look through all the values of $\phi(c) = p(\frac{K}{2}, N, c)$ and select the value of $c$ with $\phi(c)$ true for which the cardinality discrepancy $|N-2c|$ is largest. Call this value $c_0$. If $\phi(c)$ is never true then there is no partition of $S$.

All that's left is to actually find the partition of $S$ one of whose sets has size $c_0$. Here's an algorithm for doing this:

initialize P_1 and P_2 to be empty lists
initialize (s, c) to (k/2, c_0)
for i = N, N-1, ..., 1
| if p(s, i-1, c) is true:
| | add x_i to P_1
| else:
| | add x_i to P_2
| | set (s, c) to (s - x_i, c-1)
output P_1 and P_2

Notice that this algorithm is just following the recurrence of $p$ back from $p(\frac{K}{2}, N, c_0)$ to $p(0,0,0)$. That is, the algorithm maintains the invariant that $p(s, i, c)$ is always true at the start of the loop (this is easy to prove by induction). The invariant even continues to hold after the last iteration of the loop; that is, $p(s, 0, c)$ is true after the loop. Since $p(s, 0, c)$ is only true if $s = c = 0$, we can deduce that $s$ and $c$ decrease from $\frac{K}{2}$ and $c_0$ to $0$ over the course of a loop. Looking at the only line where $s$ and $c$ change, this clearly implies that list $P_2$ ends up containing exactly $c_0$ elements whose total sum is $\frac{K}{2}$. In other words, $P_1$ and $P_2$ form a partition of $S$ whose cardinality discrepancy is $|N - 2c_0|$, which by definition of $c_0$ is exactly the largest possible cardinality discrepancy for any partition of $S$.


What are good books for learning grammar ( BNF )?

For just learning about BNF grammars, a good reference is this.

However, since you mentioned its with the interest of developing a compiler, the dragon book is probably the best reference possible.


How easy is it to switch the area of research in CS (going from M.Tech to PhD)?

I recently served on the TCS grad admissions committee of MIT, and I can give you my angle on things: When I'm reading applications, what I'm looking for is excellent people who strongly want to pursue research in TCS. The combination of intrinsic ability and strong desire is, in my opinion, the best way to predict success.
After all, it is our job, once someone becomes a grad student, to help them transform their potential into actual achievements, through courses, advising, etc.

Here are some important points :

Before grad school is a very early stage to change fields. Many
people shift then. It's acceptable and expected.
In your application, explain your changing fields (so the readers understand why the rec letter writers are not from TCS, why you took lots of non-theory courses, etc). Talk about how you learned TCS, what appeals to you in TCS, demonstrate that you know the basics of the field.
If you have strong letters from your supervisors, it still counts for you, even if they are from a different field (strong = from a professor who knows you well and has great things to say about you).
If you have research experience (especially if there's some theoretical angle to it), it still counts for you, even if it's in a different field.
If you have good grades, it still counts for you, even if they are for courses from a different field. For TCS, math classes are important.


Are There Highly Symmetric NP- or P-complete Languages?

For NP, this seems hard to construct. In particular, if you can also sample (nearly) uniform elements from your group - which is true for many natural ways of constructing groups - then if an NP-complete language has a poly-time group action with few orbits, PH collapses. For, with this additional assumption about sampleability, the standard $\mathsf{coAM}$ protocol for Graph Isomorphism also works for testing whether two strings are in the same $G_n$-orbit. We then would have $\mathsf{NP} \subseteq \mathsf{coAM/poly} = \mathsf{coNP/poly}$, so PH collapses to $\mathsf{ZPP}^{\mathsf{NP}}$. So, to avoid collapsing PH, any such construction for NP would need the groups to not have an efficient nearly-uniform sampler.


Your problem is NP-hard. I show this by a reduction from the shuffle problem: given words $w, w_1, \ldots, w_k$ over the alphabet $\{a, b, c\}$, decide whether $w$ can be obtained as an interleaving (aka "shuffle") of $w_1, \ldots, w_n$. This problem is NP-hard: see Warmuth & Haussler, On the complexity of iterated shuffle, JCSS, 1984, Theorem 3.1.

Given an instance $w, w_1, \ldots, w_n$ of this problem, and writing $l_i := |w_i|$ for all $1 \leq i \leq n$, we build the DAG $G$ as a union of path graphs $L_1, \ldots, L_n$, where each $L_i$ for $1 \leq i \leq n$ has $l_i$ vertices written $v^i_1, \ldots, v^i_{l_i}$. Now, we define the cost function $f$ as follows: for each $1 \leq i \leq n$ and $1 \leq j \leq l_i$, for each $1 \leq k \leq |w|$, we set $f(v^i_j, k)$ to be $0$ if the $j$-th character of $w_i$ is the same as the $k$-th character of $w$, and $1$ otherwise.

This reduction is clearly in PTIME, and it is clear that the minimum cost of a topological sort is 0 iff there is an interleaving of the path graphs realizing exactly the word $w$, showing that the reduction is correct.

(Shameless ad: If you're interested in NP-hard variants of topological sorting, you may be interested about a recent preprint of mine which studies the complexity of finding topological sorts that fall into fixed regular languages.)


On finding a chain decomposition of a Partial Order

Your access to $A$ (which is $P$ in the paper) is through an oracle, and you're charged for each query. But in terms of the query count, your accesses to $A'$ (which is $P'$ in the paper and is an "induced sub-poset" of $A$) are free. So the answer is that a chain decomposition of $A'$ is built without asking any new queries to $A$, only based on the relations in $A'$, which are already known. Then a new element is inserted by performing a binary search on each chain of the chain decomposition, and this is where $w\log n$ queries are performed.

Note that Theorem 6 relates to Figure 2 and not Figure 1. There the number of queries is decreased by querying asymptotically optimally, rather than blindly doing a binary search independently on each chain (which would ignore relations going between chains).


What is the fastest deterministic algorithm for incremental dynamic tree reachability?

The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder.

There are several data structures that can maintain a list of items, allowing insertions immediately before or after one particular item, deletions, and constant time ordering queries, in constant time per operation; see e.g. http://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf. Record for each node which tree it belongs to, and use one of these structures for the preorder and postorder of each tree. If these structures do not already do this for you, also use a linked list so you can read off the tree nodes in either order.

To add an edge from a node $x$ to a node $y$ (where prior to the addition, $y$ is the root of a tree) we need to merge the orderings for two trees. Do so by finding which of the two trees is smaller, adding its vertices into the ordering structures for the tree that is larger, and changing the node labels on the nodes in the smaller tree to point to the larger one. In this way, each vertex participates in $O(\log n)$ updates over the lifetime of the structure (every time it is part of the smaller tree, the size of the tree it is in doubles). More precisely, each tree with $k$ edges takes total time $O(k\log k)$ to build, so the amortized time per edge is logarithmic.


Shortest cycle with a specific number of vertices

The problem of finding the shortest tour that covers a given number k of nodes is usually referred to as k-TSP. Searching Google scholar for that term will find some relevant literature. It is NP-hard but can be approximated within a constant factor. So finding an exact solution may be out of reach, unless you're prepared to use sophisticated branch and bound methods extending what Concorde does for the usual TSP.


Deciding whether an interval contains a prime number

Disclaimer: I'm not an expert in number theory.

Short answer: If you're willing to assume "reasonable number-theoretic conjectures", then we can tell whether there is a prime in the interval $[n, n+\Delta]$ in time $\mathrm{polylog}(n)$. If you're not willing to make such an assumption, then there is a beautiful algorithm due to Odlyzko that achieves $n^{1/2 + o(1)}$, and I believe that this is the best known.

Very helpful link with lots of great information about a closely related problem: PolyMath project on deterministic algorithms for finding primes.

Long answer:

This is a difficult problem, an active area of research, and seems to be intimately connected to the difficult question of bounding gaps between the primes. Your problem is morally very similar to the problem of finding a prime between $n$ and $2n$ deterministically, which was recently the subject of a PolyMath project. (If you want to really dive into these questions, that link is a great place to start.) In particular, our best algorithms for both problems are essentially the same.

In both cases, the best algorithm depends heavily on the size of gaps between the prime. In particular, if $f(n)$ is such that there is always a prime between $n$ and $n + f(n)$ (and $f(n)$ can be computed efficiently), then we can always find a prime in time $\mathrm{polylog}(n) \cdot f(n)$ as follows. To determine whether there is a prime between $n$ and $n + \Delta$, first check if $\Delta \geq f(n)$. If so, output yes. Otherwise, just iterate through the integers between $n$ and $n + \Delta$ and test each for primality and answer yes if you find a prime and no otherwise. (This can be done deterministically, which is why deterministically finding a prime between $n$ and $2n$ is so closely related to determining whether there is a prime in a certain interval.)

If the primes behave like we think they do, then this is the end of the story (up to $\mathrm{polylog}(n)$ factors). In particular, we expect to be able to take $f(n) = O(\log^2 n)$. This is known as Cramér's conjecture after Harald Cramér, and proving it seems very far out of reach at the moment. But, as far as I know, it is widely believed. (One arrives at this conjecture, e.g., from the heuristic that the primes behave like the random set of integers obtained by including each integer $n \geq 3$ independently at random with probability $1/\log n$.)

There are many conjectures that imply the much much weaker bound $f(n) \leq O(\sqrt{n})$, such as Legendre's conjecture. (I'm not aware of any conjectures that are known to imply an intermediate bound, though I imagine that they exist.) And, the Riemann hypothesis is known to imply the similar bound $f(n) \leq O(\sqrt{n} \log n)$. So, if you assume these conjectures, you essentially match Odlyzko's algorithm (up a factor of $n^{o(1)}$) with a much simpler algorithm.

I believe that the best unconditional bound right now is $\widetilde{O}(n^{0.525})$ due to Baker, Harman, and Pintz. So, if you assume nothing, then Odlyzko's algorithm beats the obvious algorithm by roughly a factor of $n^{0.025}$.


The complexity of decomposing a bi-stochastic matrix

Summary. Using your favourite $O(n^d)$ algorithm for finding a matching in graphs on $O(n)$ vertices, there is a simple algorithm using  $O(\max\{n^{d+2},n^4\})$ operations over the reals for decomposing doubly-stochastic matrices. The run-time bound comes from $O(n^2)$ iterations of a procedure in which each iteration involves finding a matching, and modifying coefficients of an $n \times n$ matrix. (There are undoubtedly ways of streamlining these operations, at least in the case of the time required to modify the matrix coefficients.)

Details.
The following proof of the Birkhoff–von Neumann theorem can be found e.g. in [1], and leads to an efficient algorithm for decomposing doubly-stochastic matrices.

We consider matrices $A$ whose rows and columns all sum to the same value (which for a doubly-stochastic input is initially 1). Let $N$ be the number of non-zero entries in your $n \times n$ doubly-stochastic matrix: in decomposing the matrix, we will reduce the number of non-zero entries while keeping the invariant of having constant line-sums. Thus at each stage, we have either $N \geqslant n$ or $N = 0$, by the invariant of having equal line-sums.

Set $t \gets 0$.
While $N > 0$:

Set $t \gets t + 1$.
For each $i \in [n]$: let $S_i = \bigl\{ j \in [n]: A_{ij} > 0 \bigr\}$.
Find a bijection $\sigma: [n] \to [n]$ such that $\sigma(i) \in S_i$(such a bijection exists, and can be found efficiently, by Hall's Marriage criterion).
Let $u^{(t)} = \min\,\bigl\{A_{i,\sigma(i)} : i \in [n]\bigr\}$, and let $P^{(t)}$ be the permutation matrix for which $P^{(t)}_{i,\sigma(i)} = 1$ for each $i \in [n]$.
Update $A \gets \bigl(A - u^{(t)} P^{(t)}\bigr)$, and update $N$ to the number of non-zero elements of $A$(which is smaller by at least $1$).

Return $\bigl(u^{(1)},P^{(1)}\bigr)$, ... $\bigl(u^{(t)},P^{(t)}\bigr)$, representing the decomposition $\sum_{i\in[t]} u^{(i)} P^{(i)}$ of the input.

[1] Extremal Combinatorics: With Applications in Computer Science by Stasys Jukna


Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$ is an (ordered) DAG and two digraphs $D_1$ and $D_2$ are isomorphic iff their corresponding ordered dags $D_1’$ and $D_2’$ are (ordered) isomorphic.
If you need to order both outgoing and incoming edges there is a simple polynomial time algorithm: if $D_1$ and $D_2$ are connected then fixing $f(u) = v$ (for $u \in V(D_1)$ and $v \in V(D_2)$) uniquely determines $f$.


Sorted dictionary structure supporting efficient merges?

If you have a balanced binary search tree data structure with the finger search tree property (a search for an item $d$ positions away takes time $O(\log d)$), such as for instance a splay tree, then if you insert a sorted sequence of $k$ items into it the total time for the insertion will be $O(k\log(n/k))$.

Now, suppose that you want to support insertions, destructive merges, and searches. For the insertions and searches, just use the existing search tree operations. For a merge, always merge the smaller tree into the larger one, and use an inorder traversal of the smaller tree to get its sorted order in linear time. Then, insert the elements of the smaller tree one at a time into the larger tree in this sorted order.

If an element $x$ is inserted then merged into a sequence of larger trees with sizes $n_1, n_2,\dots$ then the amount of time for the insertion and merges (counting only $x$'s fraction of the total merge time) will be $O(\log n_1)$, $O(\log(n_2/n_1))$, $\dots$, which add in a telescoping sequence to $O(\log n)$. So if one uses an amortization scheme in which this logarithmic total time for a potential sequence of merges is charged to the insertion operation for $x$, then we still get $O(\log n)$ amortized time per insertion or search, and only $O(1)$ amortized time per merge.

Deletions complicate this analysis, but not much. One way to handle them would be to do a semi-lazy deletion, where a deleted item is removed from its tree but not removed from the count of items in this tree, so that when we decide which of two trees is smaller or larger we count all the items that were ever in the tree. Then, the $n$ in the $O(\log n)$ time per operation should be the total number of items ever inserted or deleted rather than the number currently present. If these two numbers ever grow too far apart you can make an update that re-adjusts all the counts to their actual numbers, resetting the data structure to a state with no lazy-deleted items; the amortized time for this update can be charged against the deletion operations you had to perform to get the numbers so far apart. Or possibly you can make the merge amortization work directly with non-lazy deletions, but I haven't worked out the details of that part.


Is Escardó's metric semantic for PCF+timeouts fully abstract ?

Regarding your second question, I seem to remember that for higher-order types the question was linked closely to whether PCF+timeout was equivalent to Type Two Effectivity (Turing machines with infinite inputs and outpus), i.e., Kleene's second partial combinatory algebra. John Longley claimed for a while that Kleene's second algebra was equivalent to PCF+timeout+catch, but in the end he never published a detailed result.

On the other hand, I am pretty sure that John Longley opus magnum "On the ubiquity of certain total type structures" (Mathematical Structures in Computer Science 17(5) (2007), 841--953) implies that the higher-order functionals definable in PCF+timeout are precisely the hereditarily effective ones.


How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?

Short answer: probably not (1), definitely not (2), and possibly (3).

This is something I have been thinking about off-and-on for a while now.  First, in a sense GCT is really aimed at giving lower bounds on computing functions, rather than decision problems. But your question makes perfect sense for the function class versions of $L$, $P$, $PSPACE$, and $EXP$.

Second, actually proving the boolean versions -- the ones we know and love, like $FP \neq FEXP$ -- is probably incredibly difficult in a GCT approach, since that would require the use of modular representation theory (representation theory over finite fields), which is not well understood in any context.

But a reasonable goal might be to use GCT to prove an algebraic analog of $FP \neq FEXP$.

To get to your question: I believe that these questions can be formulated in a GCT context, though it's not immediately obvious how. More or less, you need a function that is complete for the class and characterized by its symmetries; extra bonus if the representation theory associated to the function is easy to understand, but this latter is usually quite difficult.

Even once the questions are formulated in a GCT context, I have no idea how difficult it will be to use GCT to prove (algebraic analogs of) $FP \neq FEXP$ etc.  The representation-theoretic conjectures that will arise in these contexts will likely have a very similar flavor to the ones arising in $P$ vs $NP$ or permanent vs determinant.  One might hope that the classical proofs of these separation results might give some idea of how to find the representation-theoretic "obstructions" needed for a GCT proof.  However, the proofs of the statements you mention are all hierarchy theorems based on diagonalization, and I do not see how diagonalization will really give you much insight into the representation theory associated with a function that is complete for (the algebraic analog of) $FEXP$, say.  On the other hand, I haven't yet seen how to formulate $FEXP$ in a GCT context, so it's a little early to say.

Finally, as I mentioned in that blog post, Peter Burgisser and Christian Ikenmeyer have attempted to re-prove the lower bound on the border-rank of $2 \times 2$ matrix multiplication (which was proven to be 7 in 2006 by Joseph Landsberg).  They were able to show the border-rank is at least 6 by a computer search for GCT obstructions. Update April 2013: they have since managed to re-prove Landsberg's result using a GCT obstruction, and to show an asymptotic $\frac{3}{2}n^2 - 2$ lower bound on matrix multiplication using such obstructions. Although GCT has not so far reproduced the known lower bound on matrix multiplication, it does enable a computer search more efficient than the alternative (which would involve Grobner bases, which are doubly-exponential time in the worst case).  In their talks at the workshop, both Peter and Christian pointed out (correctly, I'd say) that what we really hope to get of computing small examples is not re-proving known lower bounds, but some insight that will let us use these techniques to prove new lower bounds.

The nice thing about GCT in the context of matrix multiplication is that the technique easily generalizes from $2 \times 2$ to $3 \times 3$ matrix multiplication (although computing the obstructions with the current techniques obviously gets more expensive), whereas Landsberg's approach seems very difficult to implement even for the $3 \times 3$ case.  A similar thing could be said about the complexity class separations you mention: GCT is general enough that it may apply not only to known results like $FP \neq FEXP$, but also to unknown ones like $P \neq NP$, whereas we know diagonalization does not.


Complexity of finding automorphism group of code

By taking direct sum of codes (given their two generator matrices $G_1, G_2$, consider the block matrix $G_1 \oplus G_2 = \begin{bmatrix} G_1 & 0 \\ 0 & G_2 \end{bmatrix}$), finding the automorphism group is at least as hard as testing isomorphism of codes (also called code equivalence). The current best upper bound for testing equivalence of linear codes is $2^{O(n)}$ (see Babai-Codenotti-G-Qiao, SODA '11), and this algorithm can in fact give you generators for the automorphism group.

(For the above reduction I'm assuming that each code is indecomposable in the sense that neither code is itself a nontrivial direct sum, but I think this is true of (a) most/all codes people ever study and (b) most codes, ie a random code.)


Reference request: Classical analog of quantum threshold theorem

The classical theory of fault tolerance was pioneered by John von Neumann. I think this is the original reference:

von Neumann, J. (1956). "Probabilistic Logics and Synthesis of Reliable Organisms from Unreliable Components", in Automata Studies, eds. C. Shannon and J. McCarthy, Princeton University Press, pp. 43–98


Complexity of deciding whether a matrix is totally regular

The paper Vandermonde Matrices, NP-Completeness, and Transversal Subspaces [ps] by Alexander Chistov, Hervé Fournier, Leonid Gurvits and Pascal Koiran may be relevant to your question (though it does not answer it).

They prove the $\mathsf{NP}$-completeness of the following problem: Given an $n\times m$ matrix over $\mathbb Z$ ($n\le m$), decide whether there exists a $n\times n$ submatrix whose determinant vanishes.


Is black box parallel quantum speedup ever nontrivial?

Methinks, you do not understand the black-box magic of quantum processors.

It shall cover all n elements of a task by its cubits, otherwise, there would not be happen collapse of superposition over all input's elements and you would not even calculate anything.

For example, factorization algorithm: There shall be n + k cubits, where n - is a dimension of input, and k is support engine.

If your processor can not reach this dimension, you are not able to split input in n/p parts and feed p different processors to summarize result after, on exit...

Super-position of sum of p processors will be much lesser then super-position of one big n dimension processor. And quantum magic is exactly hidden in this dimension, means - number of cubits.

E.g. 3 CPU x 3 cubits each; This will give us such fields:

1st 2nd 3rd
000 000 000
001 001 001
010 010 010
011 011 011
100 100 100
101 101 101
110 110 110
111 111 111

This is how superposition will looks like. Three small quantum registers. And this field - is our calculation power here.

But, when you'll take One Big CPU with 9 cubits, this will give you 2^9 dimension = 512 different boolean vectors. And system will be in all of its while in super-position.

The "memory" of such quantum computer in super position will be much bigger:

000000000 000000001 000000010 000000011 000000100 000000101 000000110 000000111
000001000 000001001 000001010 000001011 000001100 000001101 000001110 000001111
000010000 000010001 000010010 000010011 000010100 000010101 000010110 000010111
000011000 000011001 000011010 000011011 000011100 000011101 000011110 000011111
000100000 000100001 000100010 000100011 000100100 000100101 000100110 000100111
000101000 000101001 000101010 000101011 000101100 000101101 000101110 000101111
000110000 000110001 000110010 000110011 000110100 000110101 000110110 000110111
000111000 000111001 000111010 000111011 000111100 000111101 000111110 000111111
001000000 001000001 001000010 001000011 001000100 001000101 001000110 001000111
001001000 001001001 001001010 001001011 001001100 001001101 001001110 001001111
001010000 001010001 001010010 001010011 001010100 001010101 001010110 001010111
001011000 001011001 001011010 001011011 001011100 001011101 001011110 001011111
001100000 001100001 001100010 001100011 001100100 001100101 001100110 001100111
001101000 001101001 001101010 001101011 001101100 001101101 001101110 001101111
001110000 001110001 001110010 001110011 001110100 001110101 001110110 001110111
001111000 001111001 001111010 001111011 001111100 001111101 001111110 001111111
010000000 010000001 010000010 010000011 010000100 010000101 010000110 010000111
010001000 010001001 010001010 010001011 010001100 010001101 010001110 010001111
010010000 010010001 010010010 010010011 010010100 010010101 010010110 010010111
010011000 010011001 010011010 010011011 010011100 010011101 010011110 010011111
010100000 010100001 010100010 010100011 010100100 010100101 010100110 010100111
010101000 010101001 010101010 010101011 010101100 010101101 010101110 010101111
010110000 010110001 010110010 010110011 010110100 010110101 010110110 010110111
010111000 010111001 010111010 010111011 010111100 010111101 010111110 010111111
011000000 011000001 011000010 011000011 011000100 011000101 011000110 011000111
011001000 011001001 011001010 011001011 011001100 011001101 011001110 011001111
011010000 011010001 011010010 011010011 011010100 011010101 011010110 011010111
011011000 011011001 011011010 011011011 011011100 011011101 011011110 011011111
011100000 011100001 011100010 011100011 011100100 011100101 011100110 011100111
011101000 011101001 011101010 011101011 011101100 011101101 011101110 011101111
011110000 011110001 011110010 011110011 011110100 011110101 011110110 011110111
011111000 011111001 011111010 011111011 011111100 011111101 011111110 011111111
100000000 100000001 100000010 100000011 100000100 100000101 100000110 100000111
100001000 100001001 100001010 100001011 100001100 100001101 100001110 100001111
100010000 100010001 100010010 100010011 100010100 100010101 100010110 100010111
100011000 100011001 100011010 100011011 100011100 100011101 100011110 100011111
100100000 100100001 100100010 100100011 100100100 100100101 100100110 100100111
100101000 100101001 100101010 100101011 100101100 100101101 100101110 100101111
100110000 100110001 100110010 100110011 100110100 100110101 100110110 100110111
100111000 100111001 100111010 100111011 100111100 100111101 100111110 100111111
101000000 101000001 101000010 101000011 101000100 101000101 101000110 101000111
101001000 101001001 101001010 101001011 101001100 101001101 101001110 101001111
101010000 101010001 101010010 101010011 101010100 101010101 101010110 101010111
101011000 101011001 101011010 101011011 101011100 101011101 101011110 101011111
101100000 101100001 101100010 101100011 101100100 101100101 101100110 101100111
101101000 101101001 101101010 101101011 101101100 101101101 101101110 101101111
101110000 101110001 101110010 101110011 101110100 101110101 101110110 101110111
101111000 101111001 101111010 101111011 101111100 101111101 101111110 101111111
110000000 110000001 110000010 110000011 110000100 110000101 110000110 110000111
110001000 110001001 110001010 110001011 110001100 110001101 110001110 110001111
110010000 110010001 110010010 110010011 110010100 110010101 110010110 110010111
110011000 110011001 110011010 110011011 110011100 110011101 110011110 110011111
110100000 110100001 110100010 110100011 110100100 110100101 110100110 110100111
110101000 110101001 110101010 110101011 110101100 110101101 110101110 110101111
110110000 110110001 110110010 110110011 110110100 110110101 110110110 110110111
110111000 110111001 110111010 110111011 110111100 110111101 110111110 110111111
111000000 111000001 111000010 111000011 111000100 111000101 111000110 111000111
111001000 111001001 111001010 111001011 111001100 111001101 111001110 111001111
111010000 111010001 111010010 111010011 111010100 111010101 111010110 111010111
111011000 111011001 111011010 111011011 111011100 111011101 111011110 111011111
111100000 111100001 111100010 111100011 111100100 111100101 111100110 111100111
111101000 111101001 111101010 111101011 111101100 111101101 111101110 111101111
111110000 111110001 111110010 111110011 111110100 111110101 111110110 111110111
111111000 111111001 111111010 111111011 111111100 111111101 111111110 111111111

You can factorize number lesser than 2^9, for example 465 on such QCPU, but you can not factorize this number on bunch of little QCPU with 3 cubits per each.

465 - it is 111 010 001. So, how do you plan to split it, to feed by parts to each little QCPU? First will factorize 111, second 010, third 001? And how to sum such result on exit? There is no way.

As you can see, 3 QCPU x 3cubits - is not the same as 1 QCPU x 9cubits.
And each new cubit increase power of QCPU by multiplying its calculation field on two. x2, x2, x2, x2... so, you could fast reach the number of stars in the visible universe or even atoms, or quarks,.. photons... and even exceed it... Simply, knot more and more cubits in superposition. But you can not achieve the same, by printing more and more small quantum computers, because the effect will be linear, not exponential.


Choosing a research topic using game theory

I'm going to try to answer you question by proposing an alternate model for the question.  I typically ask more questions than I answer on here, so I hope you'll be forgiving if my answer isn't optimal, although I'm doing my best.

I think that the way to phrase the question that would be optimal for allowing game theory to be useful would be to assume a more competitive scenario.  I.e., there needs to be competition among a variety of different actors.  So, I would assume the following:

There is a large but finite number n of other researchers attempting to pursue the same set of available research questions, which I call Q, that you are interested in.
Each research problem is defined by the following characteristics:

Time investment, or I, required to achieve visibility on whether or not you'll be able to solve the problem
Probability of success, or S, at solving the problem; once you reach the "moment of truth" and have invested enough time, Nature will decide randomly if you're going to be able to solve the problem or not
Benefit to your career, or U (as in utility), provided success is achieved

Each of these researchers have different levels of the following quantities:

Time available for investment in research, t
Talent at research, r
Interpersonal skills and other career-assisting qualities, l (as in likable), which will determine how well the researcher will capitalize on their research successes for their career advancement

Now, assuming no cooperation on any problem is possible, consider what I'm going to refer to as a "dynamic iterated game."  This is a game that is played repeatedly, but that changes slightly each time it is played.

Let M be the number of moves, or turns, in the game.  The initial manifestation of the game could be represented as a list that contains every actor (researcher) and every problem that they could work on, in addition to all of the values associated with each actor and each problem that I listed above.  (I'm assuming, of course, that every researcher knows everything presently known about all of the problems, and about all other researchers, making this a game of perfect information.)

During each iteration of the game, a given actor chooses a research question to work on.  Each actor is permitted to switch questions at any time, and if a problem is solved, the benefit to career U gets dropped to 0 for all other players.  If a player invests sufficient time and fails to solve the problem, then that particular player is prohibited from trying to solve that problem again...although any other player is allowed to continue working on the problem, and another actor may be able to solve it successfully.  The game ends after all M turns have been taken.

Each turn that a researcher has selected a problem will cause that player to get closer to reaching the "moment of truth," and possibly solving the problem, Nature permitting.  A problem, once solved, adds a certain benefit to the researcher's career based on l.  Research talent amplifies the probability of success, while free time amplifies the ability to make progress in a given turn.

I doubt that there is any polynomial time algorithm for solving this; I see no reason why researchers should be restricted to playing pure-strategy Nash equilibria, so the problem would involve mixed-strategy Nash equilibria and thus be at worst PPAD-complete, if you consider "solving the problem" to mean "finding a Nash equilibrium for the problem."  (One could imagine that if you are the most proactive researcher around, you might go ahead and calculate your favorite Nash equilibrium and then signal it to all other players...thus giving you some confidence that no one will change strategies away from the strategy profile you've signaled.)

At any rate, this is the most involved answer I've ever posted.  I hope it is of at least some value.  Please let me know if anyone has any response or to it or recommendations for improving it.


Their result is not optimal. First, it was improved upon by Yannet Interian. She obtained a 20/19 approximation (if I recall correctly). See the reference:

  Y. Interian. Approximation algorithm for Random MAX-kSAT. Theory and Applications of Satisfiability Testing (SAT 2004), Revised Selected Papers. LNCS 3542, 2005.

Her result has apparently been improved further by Fernandez de la Vega and Karpinski to 1.0957, but I cannot find an online preprint of this paper.

Given such a low approximation ratio, I wonder if it is reasonable to conjecture that there is a PTAS.


To be clear that I understand the context, I'm going to first reproduce you situation worded differently.

  Consider a sequence of sets, $C_i$, and a target function, $f$. Let $\cup C_i=C$. We wish to find a subset $S\subseteq C$ that maximizes $f(S)$ under the constraint that $\forall i, |S\cap C_i|<k_i$ and $|S|<k$.

I would agree with the commenter that this should be referred to as a cardinality constraint or a collection of cardinality constraints. I might also call it a "structural constraint," but I would specifically avoid calling it a "group carnality constraint" as "group" already has a meaning. In general, I would advocate for avoiding referring to a collection as a "group," "set," or "class" unless your object actually satisfies the required axioms. "Collection" is a good, general word that doesn't have a mathematical meaning.

If you don't want to use the term "carnality constraint" you can always introduce a term to refer to this specific restriction in your context. This can be helpful because it allows you to highlight the context-sensitive meaning of the constraint in a way that a more general term doesn't. For example, I have a paper with a constraint of this form that I refer to as an "isolation condition" because, when $S$ satisfies it, $S$ is isolated from the structure of the rest of the graph in a relevant way. This gives me a simple and intuitive way to refer to the condition, while simultaneously telling the reader what is important about the condition every time it comes up.


Are all turing machines paths predictable?

This is another way to prove that not all Turing machines are predictable.

First it's easy to note that:

all halting machines are predictable;
all machines that loop forever on a finite portion of the tape are predictable;
all machines that expand towards both sides of the tape are predictable ($N=M, Q' = \emptyset$).

The interesting case is when a machine runs forever and visits an infinite number of cells expanding only in one direction.

The following $M_{u}$ that expands rightwards is unpredictable.

at the beginning it writes $\# \langle M_0 \rangle$ on the tape;
if the rightmost part of the tape contains  $...\#\langle M_i \rangle$ then it shift it on the right adding a $H:$ before it:

$$...H:\#\langle M_i \rangle$$

($...$ is the old untouched content of the tape)

then it simulates $M_i$ on empty tape (using the rightmost part of the tape) and check if it halts in $2^{ |M_i|^i}$ space (number of cells);
if it halts in $2^{|M_i|^i}$ space it returns back to $H$, otherwise it never visits $H$ again;
at the end it clears the right part of the tape and leaves

$$...H:\# \langle M_{i+1} \rangle$$

and jump back to step 2.

Suppose that $M_u$ (possibly padded with some dummy states to increase its size) is predictable by $N_u$.

There exists $M_k$ that simulates the whole computation of $M_u$ up to $...\# \langle M_k \rangle$ (recursion theorem) and in parallel simulate $N_u$ using no more than $2^{2|M_{k-1}|^{k-1}}$ space. Indeed $N_u$ has the same path of $M_u$ by hypothesis, so after processing every $M_u(\#\langle M_i \rangle)$, $M_k$ can shift the whole tape to the leftmost cell and continue with $M_u(\#\langle M_{i+1} \rangle)$ (both $M_u$ and $N_u$ will never use space on the left of $\#$ again). Finally it can discover if $M_k$ (itself) halts in space $2^{|M_k|^k}$ immediately after step 2: it's enough to examine whether $N_u$ is in a $Q'$ state when the simulated $M_u$ writes the $H$ or not.

If it uses less than $2^{|M_k|^k}$ space then $M_k$ can loop right and never halt, otherwise it halts; this leads to a contradiction ($M_k$ would be able to diagonalize itself).


How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?

This is a standard minimum-cost circulation problem.  Give each directed edge capacity $1$ and cost $-1$.  Then a feasible circulation is a sum (ie, union) of edge-disjoint directed cycles, and the cost of the circulation is the negation of the number of edges.

Because all the costs and capacities are bounded by constants, a simple cycle-cancelling algorithm will find the required circulation in polynomial time.  This is almost the same as the obvious greedy algorithm:

while G has any negative-cost directed cycles
    γ = arbitrary negative-cost directed cycle
    reverse every edge in γ
    negate the cost of every edge in γ
return the subgraph of reversed edges

Here, the cost of a cycle is the sum of the costs of its edges.  Negative-cost cycles can be found using the Bellman-Ford shortest-path algorithm in $O(VE)$ time.  Each iteration reduces the cost of the current circulation by at least 1.  The initial (empty) circulation has cost $0$, and the final circulation has cost at least $-E$.  Thus, the algorithm ends after at most $E$ iterations, so its total running time is at most $O(VE^2)$.

This is not the fastest algorithm known.


Here is a list of several hierarchies of interest, some of which were already mentioned in other answers.

Concatenation hierarchies

A language $L$ is a marked product of $L_0, L_1, \ldots, L_n$ if
$L = L_0a_1L_1 \cdots a_nL_n$ for some letters $a_1, \ldots, a_n$.
Concatenation hierarchies are defined by alternating Boolean operations and polynomial operations (= union and marked product).
The Straubing-Thérien hierarchy (starting point $\{\emptyset, A^*\})\ $ and the dot-depth hierarchy (starting point $\{\emptyset, \{1\}, A^+, A^*\})\ $ are of this type, but you can take other starting points, notably the group languages (languages accepted by a permutation automaton).

Star-height hierarchies

The general pattern is to count the minimal number of nested stars needed to express a language starting from the letters, but several variants are possible, depending on the basic operators you allow. If you only allow union and product, you define the restricted star-height, if you allow union, complement and product, you define the (generalised) star-height and if you allow union, intersection and product you define the intermediate star-height. There are languages of restricted star $n$ for every $n$ and on can effectively compute the star-height of a given regular language. For the star-height, star-height $0$ is decidable (star-free languages), there exist languages of star-height $1$, but no language of star-height $2$ is known! No result is known on the intermediate star-height. See this paper for an overview.

Logical hierarchies

There are many of them, but one of the most important one is the so-called $\Sigma_n$ hierarchy. A formula is said to be a $\Sigma_n$-formula if it is equivalent to a formula of the form $Q(x_1,...,x_k)\varphi$ where $\varphi$ is quantifier free and $Q(x_1,...,x_k)$ is a sequence of $n$ blocks of quantifiers such that the first block contains only existential quantifiers (note that this first block may be empty), the second block universal quantifiers, etc. Similarly, if $Q(x_1,...,x_k)$ is formed of $n$ alternating blocks of quantifiers beginning with a block of universal quantifiers (which again might be empty), we say that $\varphi$ is a $\Pi_n$-formula. Denote by $\Sigma_n$ (resp. $\Pi_n$) the class of languages which can be defined by a $\Sigma_n$-formula (resp. a $\Pi_n$-formula) and by $\mathcal{B}\Sigma_n$ the Boolean closure of $\Sigma_n$-languages. Finally, let $\Delta_n = \Sigma_n \cap \Pi_n$.
The general picture looks like this

One needs of course to specify the signature. There is usually a predicate $\mathbf{a}$ for each letter (and $\mathbf{a}x$ means there is a letter $a$ in position $x$ in the word). Then one can add a binary symbol $<$ (the corresponding hierarchy is the Straubing-Thérien hierarchy) and also a successor symbol (the corresponding hierarchy is the dot-depth hierarchy). Other possibilities include a $Mod$ predicate, to count modulo $n$, etc. See again this paper for an overview.

Boolean hierarchies

The general pattern (which is not specific to regular languages) is due to Hausdorff. Let $\mathcal{L}$ be a class of languages containing the empty set and the full set, and closed under finite intersection and finite union. Let
$\mathcal{D}_n(\mathcal{L})$ be the class of all languages of the form
\begin{equation}
   X = X_1 - X_2 + \cdots \pm X_n
\end{equation}
where $X_i\in \mathcal{L}$ and $X_1 \supseteq X_2\supseteq X_3 \supseteq \cdots \supseteq X_n$. Since $\mathcal{D}_n(\mathcal{L}) \subseteq \mathcal{D}_{n+1}(\mathcal{L})$, the classes $\mathcal{D}_n(\mathcal{L})$
define a hierarchy and their union is the Boolean closure of $\mathcal{L}$. Again, various starting points are possible.

Group complexity

A result of Krohn-Rhodes (1966) states that every DFA can be simulated by a cascade of reset (also called flip-flop) automata and automata whose transitions semigroups are finite groups.
The group complexity of a language is the least number of groups involved in such a decomposition of the minimal DFA of the language. Languages of complexity $0$ are exactly the star-free languages and there exist languages of any complexity. However, no effective characterisation of the languages of complexity $1$ is known.

Hierarchies inherited from circuit complexity

The starting point is the nice article $[1]$ which show in particular that the class $AC^0 \cap Reg$ is decidable. Let $ACC(q) = \{ L \subseteq \{0,1\}^* \mid L \leqslant_{AC^0} MOD_q\}$, where $MOD_q = \{u \in \{0,1\}^* \mid |u|_1 \equiv 0 \bmod q\}$. If $q$ divides $q'$, then $ACC(q) \subseteq ACC(q')$. An interesting question is to know whether $ACC(q) \cap Reg$ is decidable for any $q$.

$[1]$ Barrington, David A. Mix; Compton, Kevin; Straubing, Howard; Thérien, Denis. Regular languages in $NC^1$. J. Comput. System Sci. 44 (1992)


The name “#Monotone-2SAT” usually refers to the problem of counting the satisfying assignments of a given monotone 2CNF formula, without a restriction on the number of variables set to true.  The stated “Monotone 2SAT” problem, or the Vertex Cover problem as is usually called, is not the decision version of #Monotone-2SAT because of the additional restriction on the number of variables set to true.  (This is certainly unfortunate.)  Therefore, Vertex Cover (or “Monotone 2SAT”) is not reducible to #Monotone-2SAT in the same way as 3SAT is reducible to #3SAT.

Note that Vertex Cover is clearly in NP and that #Monotone-2SAT is known to be #P-complete (see my answer to your previous question for the reference) and hence NP-hard.  Therefore, Vertex Cover is reducible to #Monotone-2SAT.  (Note that this does not require the fact that Vertex Cover is NP-complete.)  To construct an actual reduction, you can simply composing several reductions as always.  There may be a simpler reduction than this, but I do not expect that seeking for a simpler reduction gives much insight into either problem.


What else (besides the usual) can be said about a Scott Information System if the constructed domain is required to be Hausdorff?

Since the least element $\bot$ of any Scott domain is a compactification point $-$ the only open set containing it is the whole space $-$ the Scott topology is never Hausdorff, unless it is trivial.

An information system $(A,Con,\vdash)$ induces a trivial domain iff it is itself trivial: $Con = \{\emptyset\}$.  Otherwise, there exists at least one point above $\bot$.

The total elements of the Scott domain can indeed be given their own topology sometimes, which may be $T_2$ or even metrizable.


Why isn't the Charikar algorithm for finding the densest subgraph optimal?

Suppose you have a complete graph on four nodes and then next to it a graph with five nodes comprising a degree four hub and four degree 3 satellites. The greedy algorithm might start by removing one of the satellites and thus spoil the optimum which is 1.6

o-------o    o-------o
| \   / |    | \   / |
|   X   |    |   o   |
| /   \ |    | /   \ |
o-------o    o-------o

For the sake of completeness: given a graph $G=(V,E)$ the task is to find a subset $S\subseteq V$ maximising the quantity $|E(S)| / |S|$ where $E(S)\subseteq E$ is the set of edges with endpoints in $S$. The greedy algorithm operates by successively removing vertices of minimal degree and then searching for the optimal $S$ among the successively shrinking set of remaining vertices.


A full proof (based on superconcentrators) can be found in chapter 24 "The pebble game" of the book

  Uwe Schöning and Randall Pruim:
  Gems of Theoretical Computer Science
  Springer, 1998

  ISBN 978-3-642-64352-1
  https://link.springer.com/book/10.1007%2F978-3-642-60322-8


Research about geometry negotiation in widget layout

I would suggest looking at these survey papers and tracking down the citations in the bibliography, and digging up subsequent papers which cited these.

Walter Hower, and  Winfried Graf. Research in constraint-based layout, visualization, CAD, and related topics : a bibliographical survey, 1995.
Simon Lok and Steven Feiner, A survey of automated layout techniques for information presentations, 2001.

If you're more interested in the engineering aspects, you should look at Brad Myers' work (from the late 80s/early 90s) on the Garnet and Amulet toolkits. They have a TOPLAS paper, Lessons learned about one-way, dataflow constraints in the Garnet and Amulet graphical toolkits, which summarizes what they learned.


Approaches for Theoretical Analysis of Estimates of Probability Distributions

Disclaimer: I am biased, in that I will suggest a survey which I have written.

What you seem to be looking for can be captured under the field of distribution testing, a subfield of Property Testing initiated in TCS by the work(s) of Batu, Fortnow, Rubinfeld, Smith, and White in 2000.

Most of the works in this field answers questions of the following sort:

  Given i.i.d. sample from one (or several) unknown propbability distribution(s) over a known discrete domain, and a parameter $\varepsilon > 0$, how to distinguish between (i) the distribution has some prespecified property of interest $\mathcal{P}$ and (ii) it is at distance at least $\varepsilon$ (in total variation distance/statistical distance/$\ell_1$ distance) from every distribution that has this property?

For instance, defining the property to be the singleton $\{p\}$ (where $p$ is a known, fixed distribution of interest) you get the identity testing problem.

People have considered many variants, including varying the metric ($\ell_2$, Hellinger, Earthmover, $f$-divergences). It dates back to last year, but here is a list of references (from the second survey below).

There has been a lot of work in this area: I would suggest the following pointers and surveys:

Chapter 11 of the upcoming Introduction to Property Testing book by O. Goldreich
A Survey on Distribution Testing: Your Data is Big. But is it Blue?
(C. Canonne, 2015)
http://eccc.hpi-web.de/report/2015/063/
Taming Big Probability Distributions (R. Rubinfeld, 2012)
https://people.csail.mit.edu/ronitt/papers/xrds-rr-dist.pdf

(There are others -- see e.g. the surveys referenced by Ronitt Rubinfeld here for property testing in general, and some discussion of distribution testing.)

Some slides:
http://www.cs.columbia.edu/~ccanonne/files/talks/candidacy-2015-04-20-columbia.pdf

Now, this is trying to address the question "after coming up with a (set of) hypotheses, how to test whether they are good. (Hence the testing and tolerant testing focus.) You may also want to start from the start, and ask how to learn the distribution itself, or the relevant parameter (i.e., learning instead of testing). Not surprisingly, this becomes distribution learning (or density estimation), with all its variants (proper learning, agnostic learning, etc.). I am a bit more out of my depth there, but if that's what you are after you may want to have a look at

Learning Structured Distributions (I. Diakonikolas, 2016)
Invited Book Chapter, Handbook of Big Data, Chapman and Hall/CRC.
http://www.iliasdiakonikolas.org/distribution-learning-survey.pdf

and things like this (slightly outdated) workshop from STOC'12.


Non-interesting numbers via resource-bounded properties?

This might be cheating, because I am reinterpreting your notion of "number" as "countable ordinal."  However, there is an extensive theory about exactly what you are asking about in your question -- which ordinals can be defined, with which definition-strengths.  I looked at Wikipedia, and the large countable ordinal page has a lot of information.  In particular, the "smallest number that is interesting because the system can't even prove it's a number" corresponds to the unrecursable ordinals, if we require nothing other than computability as the resource bound.


Learnability of constraint satisfaction problems CSPs?

You are probably looking for this paper:

Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003.  doi:10.1016/S0304-3975(03)00342-6

In short, the learning complexity of a family of quantified formulas over a finite domain of values is determined by its clone of polymorphisms.  This includes CSPs as a special case of more general quantified formulas (since a CSP instance is just an existentially quantified conjunctive formula).

For the Boolean case and also for two broad classes of non-Boolean formulas, there is a dichotomy between polynomially learnable (via the Generating Set algorithm, if the clone contains a "nice" operation) and not, subject to the hypothesis that there exists a public key cryptosystem secure against chosen ciphertext attacks.


Interesting functions on graphs that can be efficiently maximized.

Whenever $f(S)$ counts the number of edges $(u,v)$ satisfying some Boolean predicate defined in terms of $u\in S$ and $v\in S$, then what you wrote is just a Boolean 2-CSP. The objective function asks to maximize the number of satisfied clauses over all assignments to the variables. This is known to be NP-hard and the exact hardness threshold is also known assuming UGC (see Raghavendra'08).

There are many natural positive examples when you want to maximize over subsets of edges, e.g, Maximum matching is one example of a polynomial time problem in this case.


Lambda-Calculus terms that reduce to themselves

First, note that the result states that the only beta redex where the right-hand side is equal (modulo alpha-conversion) to the left-hand side is $(\lambda x. x x) (\lambda x. x x)$. There are other terms that reduce to themselves, having this redex in a context.

I can see how most of Lercher's proof work, though there are points where I can't get past without modifying the proof slightly. Suppose that $(\lambda x. A) B = [B/x] A$ (I use $=$ for alpha equivalence), and as per the variable convention suppose that $x$ does not occur free in $B$.

Count the number of $\lambda$'s in the left-hand side and the right-hand side. The reduction removes one from the redex, plus those of $B$, and adds as many as there are in $B$ times the number of occurrences of $x$ in $A$. In other words, if $L(M)$ is the number of $\lambda$'s in $M$ and $\#_x(M)$ is the number of free occurrences of $x$ in $M$ then $1 + L(B) = \#_x(A) \times L(B)$. The only solution to that Diophantine equation is $\#_x(A) = 2$ (and $L(B)=1$ but we won't use that fact).

I don't understand Lercher's argument for the paragraph above. He counts the number of $\lambda$'s and atomic terms; let's write this $\#(M)$. The equation is $\#(B) + 1 = \#_x(A) \times (\#(B) - 1)$, which has two solutions: $\#_x(A)=2, \#(B)=3$ and $\#_x(A)=3, \#(B)=2$. I don't see an obvious way to eliminate the second possibility.

Let us now apply the same reasoning to the number of subterms equal to $B$ on both sides. The reduction removes one near the top, and adds as many as there are substituted occurrences of $x$ in $A$, i.e. 2. Hence one more occurrence of $B$ must disappear; since the ones in $A$ remain (because $B$ contains no free $x$), the extra occurrence of $B$ on the left-hand side must be $\lambda x. A$.

I don't understand how Lercher deduces that $A$ does not have $B$ as a subterm, but this is not in fact relevant for the proof.

From the initial hypothesis, $[(\lambda x. A)/x] A$ is an application. This cannot be the case if $A = x$, therefore $A$ itself is an application $M N$, with $\lambda x.M N = [(\lambda x. M N)/x] M = [(\lambda x. M N)/x] N$. Since $M$ can't have itself as a subterm, $M$ cannot have the form $\lambda x.P$, so $M = x$. Similarly, $N = x$.

I prefer a proof with no counting arguments. Suppose that $(\lambda x. A) B = [B/x] A$.

If $A = x$ then we have $(\lambda x. A) B = B$, which is not possible since $B$ cannot be a subterm of itself. Thus, since the right-hand side of the hypothesis is equal to an application, $A$ must be an application $A_1 A_2$, and $\lambda x. A = [B/x] A_1$ and $B = [B/x] A_2$.

From the former equality, either $A_1 = x$ or $A_1 = \lambda x. [B/x] A$. In the second case, $A_1 = \lambda x. (\lambda x. A_1 A_2) B$, which is not possible since $A_1 cannot be a subterm of itself.

From the latter equality, either $A_2 = x$ or $A_2$ has no free $x$ (otherwise $B$ would be a subterm of itself). In the latter case, $A_2 = B$.

We have shown that $A = x x$. The right-hand side of the initial hypothesis is thus $B B$, and $B = \lambda x. A$ = $\lambda x. x x$.