Why was there a need for Martin-Löf to create intuitionistic type theory? I've been reading up on Intuitionistic Type Theory (ITT) and it does make sense. But what I'm struggling to understand is "why" was it created in the first place?

Intuitionistic Logic (IL) and Simply-typed $\lambda$-calculus (STLC) and type theory in general predates the very existence of Martin-Löf himself! It seems that one can do everything in STLC that is doable in ITT (I may be wrong, but at least it feels that way).

So what was "novel" about ITT and how exactly did (or does) it advance the theory of computation? From what I understand, he introduced the notion of "dependent types", but it seems they were already there in STLC, in a way. Was his ITT an attempt at abstraction to understand the underlying principles of STLC and IL together? But didn't STLC already held do that? So, just why was ITT created in the first place? What is/was the point?

Here's an excerpt from Wikipedia: But I still don't get the reason behind its creation that didn't already exist before.

  Martin-Löf's first draft article on type theory dates back to 1971.
  This impredicative theory generalized Girard's System F. However, this
  system turned out to be inconsistent due to Girard's paradox which was
  discovered by Girard when studying System U, an inconsistent extension
  of System F. This experience led Per Martin-Löf to develop the
  philosophical foundations of type theory, his meaning explanation, a
  form of proof-theoretic semantics, which justifies predicative type
  theory as presented in his 1984 Bibliopolis book...

It seems from the excerpt that the reason was to develop the "philosophical foundations of type theory" - I thought this foundation already existed (or maybe I assumed it did). Was this the main reason then?

Very briefly: the simply-typed $\lambda$-calculus does not have  dependent types. Dependent types were proposed by de Bruijn and Howard who wanted to extend the Curry-Howard correspondence from propositional to first-order logic. The key contribution of Martin-Löf's is a novel analysis of equality.
There are two main ways of giving Curry-Howard style account of equality.

Using Leibniz's rule of the identity of indiscernibles to encode propositional equality . This approach is used in the calculus of constructions, but it requires impredicative universes which were rejected by Martin-Löf for philosophical reasons.
A direct constructive characterisation of equality. Giving such a characterisation using identity types might be the main novelty of Martin-Löf's intuitionistic type theory.

Identity types appear deceptively simple today, but they refocussed the understanding of type-theory partly because they gave rise to intriguing semantical questions such as: are identity proofs unique? In some sense this question lead to homotopy type theory and the univalence axiom (which is incompatible with the uniqueness of identities). That the uniqueness of identity proofs is not derivable in Martin-Löf's intuitionistic type theory was shown
by Hofmann and Streicher in: "The groupoid interpretation of type theory". Incidentally, this result also shows that pattern matching is not a conservative extension of traditional type theory.


Finding the smallest DFA that separates two words without using brute force search? Given two strings x and y, I want to build a minimum size DFA that accepts x and rejects y.  One way to do this is brute force search.  You enumerate DFA's starting with the smallest.  You try each DFA until you find one that accepts x and rejects y.

I want to know if there is any other known way of finding or building a minimum size DFA that accepts x and rejects y.  In other words, can we beat brute force search?

More Detail:

(1) I really do want an algorithm to find a minimum size DFA, not a near minimum size DFA.

(2) I don't just want to know how large or small the minimum DFA is.

(3) Right here, I'm only focused on the case were you have two strings x and y.

Edit:

Additional information for the interested reader:

Suppose $x$ and $y$ are binary strings of length at most $n$.  It is a known result that there is a DFA that accepts $x$ and rejects $y$ with at most $\sqrt{n}$ states.  Notice that there are about $n^{\sqrt{n}}$ DFA's with a binary alphabet and at most $\sqrt{n}$ states.  Therefore, the brute force approach wouldn't require us to enumerate through more than $n^{\sqrt{n}}$ DFA's.  It follows that the brute force approach couldn't take much more than $n^{\sqrt{n}}$ time.

Slides that I found helpful: https://cs.uwaterloo.ca/~shallit/Talks/sep2.pdf

If I had to do this in practice, I would use a SAT solver.

The question of whether there is a DFA with $k$ states that accepts $x$ and rejects $y$ can be easily expressed as a SAT instance.  For instance, one way is to have $2k^2$ boolean variables: $z_{s,b,t}$ is true if the DFA transitions from state $s$ to state $t$ on input bit $b$.  Then add some clauses to enforce that this is a DFA, and some variables and clauses to enforce that it accepts $x$ and rejects $y$.

Now use binary search on $k$ to find the smallest $k$ such that a DFA of this sort exists.  Based on what I've read in papers on related problem, I would expect that this might be reasonably effective in practice.

Other encodings of this as SAT are possible.  For instance, we can use a trace encoding:

If $x$ is of length $m$, you could add $m\lg k$ boolean variables: let $s_0,s_1,\dots,s_m$ be the sequence of states traversed on input $x$, and represent each $s_i$ using $\lceil \lg k \rceil$ boolean variables.
Now for each $i,j$ such that $x_i=x_j$, you have the constraint that $s_{i-1}=s_{j-1} \implies s_i=s_j$.
Next, extend this to handle $y$: let $t_0,\dots,t_n$ be the sequence of states traversed on input $y$, and represent each $t_j$ using $\lg k$ boolean variables.  For each $i,j$ such that $y_i=y_j$, add the constraint that $t_{i-1}=t_{j-1} \implies t_i=t_j$.
Similarly, for each $i,j$ such that $x_i=y_j$, add the constraint that $s_{i-1}=t_{j-1} \implies s_i=t_j$.
Both traces must start from the same starting point, so add the requirement that $s_0=t_0$ (WLOG you can require $s_0=t_0=0$).
To ensure that the DFA uses only $k$ states, require that $0 \le s_i < k$ and $0 \le t_j <k$ for all $i,j$.
Finally, to encode the requirement that $x$ is accepted and $y$ is rejected, require that $s_m \ne t_n$.

All of these requirements can be encoded as SAT clauses.

As before, you'd use binary search on $k$ to find the smallest $k$ for which such a DFA exists.


Is $PP^{(PP^A)} = PP^A$ ? I've looked in the Zoo and it seems it is not true because $PH \subseteq P^{PP}$. Nonetheless I've passed by a paper that appears to have used a positive result. It was in the context that $f : \{0,1\}^* \mapsto \{0,1\}^*$ is a function, computable by probabilistic polynomial time oracle machine $M$ with access to an arbitrary oracle $A$. The authors say and I quote:

  Its also immediate that $G^f$ ≡
  $G^{M^A}$ is computable by a
  probabilistic polynomial time oracle
  machine with access to $A$.

where $G$ is a probabilistic polynomial time oracle machine.

They do it again also for $S^{N^A,M^A}$, $S,N$ being other probabilistic polynomial time oracle machine.

Update: the paper is "Notions of reducibility between cryptographic primitives" - 2004. It was in the proof of Lemma 1 of the part that "If there exists a fully-black-box reduction from a cryptographic primitive P to cryptographic primitive Q then there exists a relativizing reduction from P to Q as well." The definitions of fully-black-box and relativizing reduction is in the paper.

The question now, according to Lance Fortnow's answer that they are not equal, does that mean that this is a gap in the proof ?

Richard Beigel gives an oracle $A$ where $P^{NP^A}\not\subseteq PP^A$ which immediately gives $PP^{PP^A}\neq PP^A$.


Alphabet Reduction Step in PCP Proof I understand that the purpose of the alphabet reduction step in Dinur's proof of the PCP theorem is to reduce the alphabet after the graph powering stage. However, I don't see why the alphabet needs to be reduced- it is still a constant (though larger), and it seems that the graph powering step can be reapplied even with a larger alphabet size. Since the process is repeated logarithmically many times, the ending alphabet size will be polynomial in the input size. Please let me know what I am missing.

The alphabet size corresponds to the query complexity of the PCP verifier. So you need to make it a constant eventually so that the PCP has constant query complexity, as stated in the PCP theorem.

And if I am not mistaken, the alphabet size increases from $\left|\Sigma\right|$ to $\Omega(\left|\Sigma\right|^c)$ for some constant $c$ in each graph powering step. If you do not make the alphabet reduction in middle steps, the alphabet size will blow up exponentially within a logarithmic number of iterations.


Why do functional programming languages require garbage collection? What's stopping ghc from translating Haskell into a concatenative programming language such as combinatory logic and then simply using stack allocation for everything? According to Wikipedia, the translation from lambda calculus to combinatory logic is trivial, and also, concatenative programming languages can rely solely on a stack for memory allocation. Is it feasible to do this translation and thus eliminate garbage collection for languages such as Haskell and ocaml? Are there downsides to doing this?

EDIT: moved here https://stackoverflow.com/questions/39440412/why-do-functional-programming-languages-require-garbage-collection

All of the following comments are premised on the choice of a standard implementation strategy using closures to represent function values and a call-by-value evaluation order:

For the pure lambda calculus, garbage collection is not necessary. This is because it is not possible to form cycles in the heap: every newly-allocated value can only contain references to previously-allocated values, and so the memory graph forms a DAG -- so reference counting suffices to manage memory.
Most implementations do not use reference counting for two reasons.

They support a form of pointer type (eg, the ref type constructor in ML), and so true cycles in the heap can be formed.
Reference counting is much less efficient than garbage collection, since

it requires a lot of additional space to keep the reference counts, and
updating the counts is usually wasted work, and
the updates to the counts create a bunch of write contention which kills parallel performance.

Linearly-typed languages can eliminate the reference count (essentially because counts are 0-1: either the value has a single reference to it or it is dead and can be freed).
However, stack allocation still does not suffice. This is because it is possible to form function values which refer to free variables (i.e., we need to implement function closures), if you allocate things on the stack, then live values can be interleaved with dead values, and this will cause incorrect asymptotic space usage.
You can get the right asymptotics by replacing a stack with a "spaghetti stack" (ie, implement the stack as a linked list in the heap, so that you can cut out dead frames as needed).
If you want a real stack discipline, you can use type systems based on "ordered logic" (essentially linear types minus exchange).


What language $L \in NCM$ has $\overline{L} \not \in NCM$? $NCM$, the class of non-deterministic reversal-bounded counter machines, has a lot of interesting dependability and closure properties. It's known that, unlike the deterministic version, NCM is not closed under complement.

However, I've never seen a proof of this given explicitly. In Ibarra's paper,
the non-closure is implied because if NCM were closed under complement, subset would be decidable.

However, I've never actually seen an example of a language where $L$ is in $NCM$ but $\overline{L}$ isn't.

I'm wondering, can anyone provide such an example, and preferable, a source describing it that I could cite in a paper?

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).


Expressiveness of Büchi vs CTL(*) What is the relationship between the expressiveness of LTL, Büchi/QPTL, CTL and CTL*?

Can you give some references that cover as many of these temporal logics as possible (especially between linear- and branching-time)?

A Venn diagram with those temporal logics and some practical properties as examples would be perfect.

For instance:

Is it true that there are properties specifiable in Büchi but not in CTL*? Do you have a good example?
How about in Büchi and CTL but not in LTL?

Details:

The expressiveness of the logics is more relevant for me than the examples. The latter is just helpful for understanding and motivation.

I already know of the expressibility theorem between CTL* and LTL from [Clarke and Draghicescu, 1988], but do not like the usual example of fairness being in CTL and not in LTL since there are a plethora of fairness variants, some of which are expressible in LTL.

I also do not like the usual example of the evenness Büchi-property, given, e.g., in [Wolper83] about the restrictions of LTL, since adding another propositional variable would solve the problem ($even(p) \equiv q \wedge \Box ( q \implies X \neg q ) \wedge \Box ( \neg q \implies X q ) \wedge \Box ( q \implies p )$).

I do like the example of the evenness Büchi-property, given, e.g., in [Wolper83] about the restrictions of LTL, since it is simple and shows the necessity of PQTL for evenness (thanks for the note below).

Update:

I think the expressibility theorem between CTL* and LTL from [Clarke and Draghicescu, 1988] can be lifted to Büchi automata, resulting in:

Let $\phi$ be a CTL* state formula.
Then $\phi$ is expressible via Büchi automaton
         iff $\phi$ is equivalent to $A\phi^d$.

With this, Büchi $\cap$ CTL* = LTL, answering my questions above:

Is it true that there are properties specifiable in Büchi but not in CTL*? Yes, e.g. evenness.
How about in Büchi and CTL but not in LTL? No.

Has anyone lifted Clarke and Draghicescu's theorem already to Büchi automata, or stated a similar theorem? Or is this too trivial to be mentioned in a paper, since CTL*'s path quantifiers are obviously "orthogonal" to the criteria on accepted paths states by Büchi automata?

I'm not answering the full question but only part of it (I have no interest in branching time).

Your definition of $\mathit{even}$ would better read $\mathit{even}(p) \equiv \exists q.(q \land \Box ( q \leftrightarrow \mathsf{X} \lnot q ) \land \Box ( q \rightarrow p ))$.  You are introducing $q$ only to remember if you are on an odd or even position, but this $q$ information is not on your system so it should not be a free variable of your formula (otherwise your system and your formula are defined on different alphabets).  Such a formula is an Existentially-Quantified LTL formula (EQLTL for short).

EQLTL formula can only have $\exists$ quantifiers at the top-level.  And they are as expressive as Büchi automata.  For instance to translate
the EQLTL formula $\exists q.(q \land \Box ( q \leftrightarrow \mathsf{X} \lnot q ) \land \Box ( q \rightarrow p ))$ as a Büchi automaton, you would simply translate the LTL formula $q \land \Box ( q \leftrightarrow \mathsf{X} \lnot q ) \land \Box ( q \rightarrow p )$, and then erase the $q$ variable from everywhere in the automaton.   Conversely any Büchi automaton can be converted into an EQLTL formula easily: declare an existential variables for all the states $\exists s_1.\exists s_2\ldots$, and use these to encode transitions and acceptance states (e.g. $\exists s_1.\exists s_2.(s_1\land\Box(s_1\rightarrow a\land \mathsf{X}s_2)\land\Box(s_2)\rightarrow b\land\mathsf{X}(s_1))\land\Box\Diamond s_2\land\Box(\bigwedge_i (s_i\rightarrow\bigwedge_{j\ne i}\neg s_j)))$ if $s_1$ can go to $s_2$ with $a$, $s_2$ can go to $s_1$ with $b$, and $s_2$ is Büchi-accepting; the last conjunction of implications make sure you cannot be in two states at once).  You might want to read Stutter-Invariant Languages, ω-Automata, and Temporal-Logic on this subject.

Basically the $\exists q$ is used here like some second-order quantifier (there exist a set of states where $q$ hold and such that...).  EQLTL and Büchi automata are equalivent to S1S, and LTL is equalivent to F1S.  $even$ is the typical S1S formula that cannot be expressed by F1S.

QPTL, which you mentioned, adds $\exists$, $\forall$ (not only at the top-level), and past operators.  It contains EQLTL but is not more expressive (since QPTL can be converted to Büchi automata and Büchi automata can be converted to EQLTL).

CTL is about branching time, so it's a different world.  A CTL formula like $\mathsf{EF}\mathsf{AG}p$ which is reasoning on the tree of all possible futures have now equivalent in LTL which is reasoning on all possible scenarios.


Complexity of an edit distance problem Given an array $A[1...n]$ of non-negative integers,
we want to transform $A$ into $A'$ such that

$|A[I] - A[I + 1]| \leq 1$ in the minimum number of operations.

One operation consist of picking two adjacent elements and perform:

1) Add 1 to $A[I]$ and subtract 1 from $A[I + 1]$

2) Subtract 1 from $A[I]$ and Add 1 to $A[I + 1]$

E.g.: 1 3 5 2
1 4 4 2 (picking 3,5)
2 3 4 2 (picking 1,4)
2 3 3 3 (picking 4,2)

I give a rough idea to solve the problem in polynomial time.

In the optimal solution, the flow on each edge is unidirectional.
The final value of each element is not far from the mean. Also $\sum_{i<k}A'_i$, the prefix-sum of the optimal $A'$, is bounded in a range at most $O(n^2)$.
Let $T(k,R)$ be the optimal flow on the first $k$ edges such that $\sum_{i<k}A'_i=R$. Then $T(k,R)$ can be computed from $T(k-1,R')$ for all possible $R'$.

These imply a dynamic programming algorithm with polynomial time complexity.


Straight line complexity of monomials Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the monomials
which appear in $f$ with non-zero coefficient.

  Is it true that $ \forall m\in F:L(m)\le L(f)$?

Even some weaker upper bound for $L(m)$ is known?

If $$f=(\Sigma_{i=1}^n x_i)^{2^n}$$
then it has ${2^n+n-1\choose n-1} \approx 2^{n^2}$ monomials and $L(f)=O(n)$.
By a counting argument, there are $2^{O(n\log n)}$ straight-line programs of length $O(n)$.
As $f$ has more monomials, for some we need a longer program.
In fact this argument gives a monomial $m$ for which $L(m)=\widetilde\Omega(L^2(f))$.


Subspace-evasive set performance in the random case A subspace evasive set is defined as a large subset of a vector space which has small intersection with any $k$ dimensional affine space. That is, it "evades" all affine subspaces of small enough dimension.

Formally, for parameters $k$ and $\epsilon > 0$, a $(k,c)$-subspace evasive set $S \in \mathbb{F}_q^n$ is such that $|S| > |\mathbb{F}_q^{n}|^{1-\epsilon}$ and $|S \cap H| < c$ for all $k$-dimensional affine subspaces $H \in \mathbb{F}_q^n$.

The goal is to make the intersection $c$ as small as possible.

It is claimed (as trivial in most references) that a random set $S \in \mathbb{F}_q^n$ of size $|\mathbb{F}_q^{n}|^{1-\epsilon}$ has (whp) intersection $c = O(k/\epsilon)$.

Is there a way of showing this? It is supposed to be a simple application of a probabilistic method, but I am stuck and clueless.

Here's a quick calculation.

For a fixed affine subspace $H$ of dimension $k$, the probability that a random point falls in  $H$ is $1/q^{n-k}$. The probability that at least $c$ points in $S$ fall in $H$ is at most:
$${q^{(1-\epsilon)n} \choose c} \cdot \frac{1}{q^{(n-k)c}}\leq
 \frac{q^{(n-\epsilon n) c}}{q^{(n-k)c}} = \frac{1}{q^{(\epsilon n -k)c}}$$
A trivial bound on the number of subspaces of dimension $k$ is $q^{n(k+1)} < q^{2kn}$. So, by the union bound, the probability that there exists a subspace $H$ containing at least $c$ points of $S$ is at most:
$$q^{2nk} \cdot \frac{1}{q^{(\epsilon n -k)c}} < 1$$
if $c = 4k/\epsilon$ and $k<\epsilon n/3$.


What are some applications of computational geometry towards computer vision? I'm interested in both of these topics independently, and wondering some good applications of comp geom within the domain of vision.  What are some nice applications and potential projects of comp geom applied to vision?

Probably the most useful application of computational geometry within computer vision is in the realm of shape analysis/matching and image registration. There's a lot to google here, but you can start with Kendall's book on shape space, and also look at problems of measuring the distance between shapes.


Computationally bounded version of Nash equilibrium? I'm wondering if there is a computationally bounded version of the Nash equilibrium concept, something along the following lines.

Imagine some kind of two-player perfect information game which is played on an $n\times n$ board, and which is complex in the sense that optimal play is EXPTIME-hard.  Suppose also for simplicity that draws are not possible.  Imagine a pair $(A, B)$ of randomized polynomial-time Turing machines playing this game against each other.  For each $n$, let $p_{A,B}(n)$ be the probability that $A$ beats $B$ at the order-$n$ game.  (For concreteness, let's say that $A$ gets to play first with probability 0.5.)  What I think would be cool is if one could prove the existence of a pair $(A,B)$ with the property that no randomized polynomial-time Turing machine $A'$ dominates $A$ (where "$A'$ dominates $A$" means $p_{A',B}(n) > p_{A,B}(n)$ for all sufficiently large $n$), and similarly no randomized polynomial-time Turing machine $B'$ dominates $B$ (where "$B'$ dominates $B$" means $p_{A,B'}(n) < p_{A,B}(n)$ for all sufficiently large $n$).

Somehow, I suspect that this is too much to hope for, but is there any hope for something like this to be true, perhaps for a restricted class of games?

One motivation for this question is that I am looking for a way to formalize the notion that a given chess position is "advantageous for White."  Classically, a position is either a win for White or it isn't.  However, chess players, both human and computer, have an intuitive understanding of what it means for White to have an advantage.  It seems to have something to do with the probability that White will win, given that the players are computationally bounded and have to guess at the best move.  For a specific pair of randomized algorithms one can of course talk about the probability that White will win, but what I'm wondering is if there can be, in some sense, a canonical pair of computationally bounded players whose winning probabilities yield a value for the position that depends only on the game itself and not the idiosyncrasies of the players.

I can't think of any way there could be an easy, completely elegant/satisfying answer to this question, particularly because the ending payoff is so hard to compute; however, my thoughts are too lengthy to post as a comment.

The best idea I have is this:  In the case of chess, try approximating the probability that White will win based on White's material advantage (i.e., extra pawns, knights, etc.) for a given position by randomly selecting positions with that exact amount-of-material configuration.  Perhaps in the case of "all-rooks chess," we could say, "How likely is White to win with 8 rooks to Black's 17 rooks?"  Perhaps this probability is 4%; to calculate it, we would have to examine (say) 1000 different randomly generated chess positions that have 8 white rooks and 17 black rooks, and then look ahead (say) 10 moves deep in every case, and see what the new material configuration is.  Then, take the expected odds based on the material configuration at the end, and force each side to select the path that involves each side taking the best possible option at every turn, given the expected odds at the end.

Of course, it would be necessary to find the material configuration for every relevant possibility (M,N) of M white rooks to N black rooks...presumably starting at the lowest ordered pair (M=1,N=1) and working up from there.

For the original position, don't just go with the statistic you get (i.e., if the original position has (M=6,N=7) rooks, don't just assume that White has a 25% chance of winning because that's the expected odds of victory for (6,7)); instead, because you can be more precise, look 10 moves deep as usual with just this one position and find every possible ending position.  Then, find the right path (that involves optimal play by both sides) to a 10-moves-deep-configuration, and select this path's expected odds as the expected odds of the original position.

I think this process can be done in polynomial time.  Looking k moves deep for fixed k in chess is polynomial in the size of the board, and the total number of white and black rooks is expressed in unary (in a sense) because that number must be smaller than the size of the board.

If this sounds complicated and hard to explain, that's because it is.  A more succinct summary of what I'm describing is:  Use recursion and basic statistics to calculate the odds of victory for white given M white rooks and N black rooks on the board.  Then use these values to look k moves deep and ascertain the odds that White will win in the original position.

Final comment:  I think this problem is also interesting for non-EXPTIME-complete games, such as tic-tac-toe, which according to Wikipedia is PSPACE-complete.  Further, I believe a process like the one I described above could also be useful there too, although obviously it would be impossible to have a "material" advantage in tic-tac-toe; there would have to be some other basis for judging the superiority of X's or O's position.


Hamilton Decomposition Decision Problem Let $G=(V,E)$ be an undirected graph. A decomposition of $V$ into disjoint subsets $V_i$ is called a Hamilton decomposition of $G$ if the subgraph induced by each set $V_i$ is either a Hamilton graph or consists of a single edge with $|V_i|=2$.

Example: The complete bipartite graph $K_{m,n}$ possesses a Hamilton decomposition if and only if $m=n$.

I am looking for an algorithm that decides whether a given graph possesses a Hamilton decomposition. Is this decision problem NP-complete? If not, how can we find such a decomposition?

Note: In the literature a Hamilton decomposition often denotes a decomposition of the edges $E$ of $G$ such that the induced subgraphs are Hamilton. In contrast I am interested in a decomposition of the vertices.

If we request that each $|V_i| \ge 3$, then this is the 2-factor problem,
see the book Combinatorial Optimization by Schrijver. If you allow $|V_i| = 2$,
then we can solve this by replacing each undirected edge by two directed ones and compute what is called a cycle-cover. This can be done in polynomial time by reduction to bipartite matching.


Landauer's principle internals - how it works I attached a picture, where the energy dissipation (entropy increase) on information erasure is explained. Is the explanation correct?

"RESTORE TO ONE" - is it correct to identify the operation as "information erasure"? It looks like a negation, not like "information erasure".
I would say that the erasurement would be performed, when the "ball" (the black dot near "0" in the picture) would be returned to the meta-stable point between 0 and 1.
Maybe the intention of the author was to show, that "negation" has "erasurement" embedded in it? Then, he states that "computing depends on information erasure" - this statement is too strong? - we have reversible computation that do not erase information, correct?
The picture and point 2. (above) seem to be a very good metaphore of Landauer's principle. Does it match Landauer's principle closely, or maybe even perfectly - or is it just a picture to help only conceptually understand the principle?

(PS. A better title is welcomed..)

You're confused because the example didn't cover all possible cases, and you're extrapolating improperly.

Negation is the operation

  0 → 1,
    1 → 0.

This is reversible, and can theoretically be performed using an arbitrarily small amount of energy.

Restore to one is the operation

  0 → 1,
    1 → 1.

This is not reversible, and unavoidably  dissipates $k T \ln 2\;$ energy.


Parameters of energy function for TSP [This question was initially asked here. It went unanswered so I thought I should ask it in a different community.]

I am reading this paper by Hopfield et al. On page six, the authors defined the energy function of the Traveling-Salesman-Problem (TSP) mapped onto an artificial neural network as follows:

$$E = \frac{A}{2} \sum_X \sum_i \sum_{j \ne i} V_{Xi} V_{Xj} + \frac{B}{2} \sum_i \sum_X \sum_{X\ne Y} V_{Xi} V_{Yi} + \frac{C}{2} (\sum_X \sum_i V_{Xi} - n)^2 + \frac{1}{2D} \sum_X \sum_{Y\ne X} \sum_i d_{XY} V_{Xi} (V_{Y, i+1} + V_{Y, i-1})$$

Here the first three terms maintain correctness of the function while the final term calculate actual distance of the tour. Later on page seven, the authors picked the values of A, B, C and D for simulation.

I don't understand on what basis they choose those values. Any help?

There is no way to choose the parameters A, B, C, D properly;
as it is the case for most heuristics, the parameters are chosen ''by experience''.
Worse, there is no guarantee that the solution (the array of the outputs)
of this heuristic is indeed a feasible TSP tour!

In this context, perhaps interesting to read: Wilson and Pawley,
On the stability of the Travelling Salesman Problem
algorithm of Hopfield and Tank,
Biological Cybernetics 58 (1988) 63-70.

To your first comment: I don't think that this TSP energy function is useful for practical purposes.
If you want to solve TSP in practice, maybe here
is the right starting point.


Are there protein-based computational models? Is there a framework/formalism that defines computational models based on proteins other than Adleman's DNA model or this work by Cherry and Qian?

Edit 2020 (related models/ideas based on DNA):
DNA allows to store large amount of data, it seems to me that the combination of DNA-based memory methods and technologies like CRISPR as computational workers might be an interesting and relevant venue.

DNA-sequencing-based readers
DNA sequencing is the most direct way to extract information from DNA-based recording devices. Sanger sequencing can provide low-throughput but high-accuracy sequences of ~800 bp. Nucleotide polymorphism frequencies across a population at specific DNA addresses can also be determined from Sanger chromatograms88. Alternatively, NGS can determine the sequence of DNA addresses at a much larger scale, and progress in this arena14 has enabled analysis of many recent recording devices. Short-read sequencing-by-synthesis (from Illumina) can currently provide the highest throughput and read quality, albeit with a maximum read length of ~600 bp89. For DNA addresses with longer lengths (for example, large recombinase-targeted loci87,90), long-read sequencing technologies such as single-molecule real-time sequencing (SMRT; from Pacific Biosciences) or nanopore sequencing (from Oxford Nanopore Technologies) are necessary. Although long-read sequencing modalities currently have a relatively lower throughput and lower quality than more mature short-read NGS platforms, portable instruments such as the MinION nanopore sequencer offer exciting real-time readout of DNA data storage91.

Sheth, Ravi U., and Harris H. Wang. "DNA-based memory devices for recording cellular events." Nature Reviews Genetics 19.11 (2018): 718-732.
As mentioned in the answers, $\pi$-calculus and bioambinet calculus are relevant here as well:

An Abstract Machine for the Stochastic Bioambient Calculus by Andrew Phillip
The π-calculus as an Abstraction for Biomolecular Systems by Aviv Regev & Ehud Shapiro

Membrane Computing is a model that is based on the possibility or not of movement of molecules through membranes; also on possible reactions of these molecules inside a membrane compartment. While this is not specifically talking about proteins, in reality some of these molecules and the channels through which they pass would be proteins.

Here is an overview written by the creator of this model.

Another model possibly involving proteins is Computing by Observing which models the way that a person conducting an experiment extracts information from what she/he sees. The observed process may very well model protein interactions.


How is this graphical representation of SAT/CSP instances called? Given a CNF formula (SAT problem), we can construct the constraint/dependency graph, which contains a vertex for each variable and a hyperedge for each clause. Same goes for CSPs, where we have a hyperedge for each constraint.

But given a CNF formula, we could also define a (slightly larger) graph that has literals as vertices and clauses as hyperedges, where each edge is incident to each literal it contains. This can analogously be done for a CSP.

How is the latter graph called?

This has been called the microstructure complement when the edges represent the forbidden partial assignments.  I personally prefer the term clause structure.  The clause structure of a constraint satisfaction problem instance is obtained by applying the direct encoding of the instance to SAT, where each possible value $a$ of variable $v$ is represented by a literal $(v,a)$, the forbidden partial assignments are SAT clauses involving these literals, and a clause $\{(v,a),(v,b)\}$ is added for every variable $v$ and any values $a\ne b$.  (These clauses force a solution to be a function, assigning at most one value to each variable.)

If the edges represent the allowed partial assignments (with non-edges denoting forbidden partial assignments), this is called the microstructure.  This representation doesn't require the extra clauses.  However, one has to be careful of the semantics of missing edges.  One must decide whether only edges of a particular arity are covered by the stipulation that missing edges are forbidden, or whether the microstructure should contain all consistent partial assignments.  The semantics of the clause structure is much more straightforward.

The early work in constraint satisfaction only considered arity 2, when the microstructure and the clause structure are graphs.  But the definition was general (or unspecific) enough that it applies for any arity.

David A. Cohen, A New Class of Binary CSPs for which Arc-Consistency Is a Decision Procedure, CP 2003, 807–811.  doi:10.1007/978-3-540-45193-8_57
Eugene C. Freuder, Eliminating Interchangeable Values in Constraint Satisfaction Problems, AAAI 1991, 227–233.
P. Jégou, Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems, AAAI 1993, 731–736.
András Z. Salamon and Peter G. Jeavons, Perfect Constraints Are Tractable, CP 2008, 524–528.  doi:10.1007/978-3-540-85958-1_35


Choosing one number from each set so that the sum of squares of each distinct number counts is minimized Problem is as follows:
We are given $K$ subsets of $\{1,2,...,n\}$. We need to pick one number from each of these subsets such that $\sum_{i=1}^n p_i^2$ is minimized where $p_i$ is the number of times $i$ is repeated among picked numbers. Is there an efficient algorithm to do this?

Regarding the NP-hardness tag, your problem can be shown to be in $P$ (and thus likely not $NP$-hard) via a reduction to min-cost flow with $O(nK)$ vertices and $O(nK^2)$ edges.

It will help to have a visual to refer to for the construction. Below is a figure showing how we construct the min-cost flow instance with $n=K=3$, with the set family $A=\{1,2\}, B=\{1,2,3\}, C=\{2,3\}$.

All edges are directed rightwards. Red edges have cost 0 and capacity 1. Blue edges have cost 0 and capacity $K$. Black edges have capacity $1$ and cost indicated in the figure. We demand that $s$ route $K=3$ units of flow to $t$.

We refer to the nodes corresponding to $[n]$ (above labeled $1$, $2$, and $3$) as "number nodes" and those corresponding to the $K$ sets (above labeled $A$, $B$, and $C$) as "set nodes". The unlabeled nodes are called "central nodes", and we say that a given central node corresponds to the unique adjacent number node.

All costs and capacities are integral, so w.l.o.g. we can consider only integral feasible solutions to the problem. The capacity constraints on the red edges ensure that, in any feasible solution, each set node must send over exactly one unit of flow to $t$, corresponding to the constraint that we pick one element from each set. This unit of flow must have arrived from one of the $nK$ central nodes, which in turn must have arrived from its corresponding number node. Finally, this number node received its flow from $s$.

Thus, if we track the path taken by each unit of flow in a solution to the constructed flow instance, we see that it goes through both a number node $c$ and through a set node $S$, corresponding to a choice of a number $c$ from that set $S$ in the original instance. As for the costs, any solution that routes $p_i$ units of flow to a number node labeled $i$ must incur a cost of at least $\sum_{j=1}^{p_i}\left(2j-1\right) = {p_i}^2$ on the node's out-edges. In an optimal solution, this holds with equality. As all other edges have zero cost, optimal solutions to this flow problem thus have cost $\sum_{i=1}^{n}{p_i}^2$, as desired.

In general, $s$ has a blue edge to each of $n$ number nodes (labeled $1, 2, \cdots, n$), each of which is adjacent to its own distinct set of $K$ different central nodes. The edges connecting the number nodes to the central nodes all have capacity $1$ and varying costs equal to the first $K$ positive odd numbers. A central node corresponding to a number node with label $c$ is then connected with a blue edge to each of the set nodes for which the set contains $c$. The set nodes correspond to each of the $K$ sets. Finally, all set nodes are connected to $t$ with a red edge.

More generally, the same construction works with any convex cost structure, after the necessary modifications.


Positive topological ordering, take 3 Suppose we have an n by n matrix. Is it possible to reorder its rows and columns such that we get an upper-triangular matrix?

This question is motivated by this problem:
Positive topological ordering

The original decision problem is at least as hard as this one, so an NP-completeness result would solve that too.

Edit:
Laszlo Vegh and Andras Frank called my attention to an equivalent problem asked by Gunter Rote:
http://lemon.cs.elte.hu/egres/open/Graphs_extendable_to_a_uniquely_matchable_bipartite_graph

Edit:
The reduction to the original problem is as follows. Suppose that the DAG has only two levels, these will correspond to the rows and columns of the matrix. Also, we have one single node with weight +1. Everyone else in the lower level has weight -1 and on the upper level +1.

The problem turned out to be NP-complete. You can read more in detail here and here. Short summary:

The reduction is from a problem was shown to be NP-complete by Dasgupta, Jiang, Kannan, Li, and Sweedyk: given a bipartite graph G and an integer k, decide if G has an induced subgraph on 2k nodes that can be extended to be uniquely matchable. It was observed by Stéphane Vialette that this reduces to the bipartite unique matching version of this problem if we add n-k isolated nodes to both classes.


How exactly does lambda calculus capture the intuitive notion of computability? I've been trying to wrap my head around the what, why and how of $\lambda$-calculus but I'm unable to come to grips with "why does it work"?

"Intuitively" I get the computability model of Turing Machines (TM). But this $\lambda$-abstraction just leaves me confounded.

Let's assume, TMs don't exist - then how can one be "intuitively" convinced about $\lambda$-calculus's ability to capture this notion of computability. How does having a bunch of functions for everything and their composobility imply computability? What am I missing here? I read Alonzo Church's paper on that but I'm still confused and looking for a more "dummed down" understanding of the same.

You're in good company. Kurt Gödel criticized $\lambda$-calculus (as well as his own theory of general recursive functions) as not being a satisfactory notion of computability on the grounds that it is not intuitive, or that it does not sufficiently explain what is going on. In contrast, he found Turing's analysis of computability and the ensuing notion of machine totally convincing. So, don't worry.

On the other hand, to get some idea on how a model of computability works, it's best to write some programs in it. But you do not have to do it in pure $\lambda$-calculus, although it's fun (in the same sort of way that firewalking is). You can use a modern descendant of $\lambda$-calculus, such as Haskell.


Emptiness of complement of subspace arrangement Given $k$ affine subspaces in $\{0,1\}^n$, consider the problem of testing whether their union covers all of $\{0,1\}^n$. What's the complexity of this problem?

P.S.: It seems that this can be reduced to the computation of a characteristic polynomial, which looks like a hard problem. Is there another route?

Your problem is coNP-hard.
Take a 3SAT instance with variables $X$ and clause set $C$.

Set the dimension in your problem to $n:=|X|$.
For every clause $c\in C$, introduce a corresponding $(n-3)$-dimensional subspace $S(c)$ by restricting the three dimensions that correspond to the three variables in $c$.
If a variable occurrs positively in $c$, then fix the corresponding coordinate at 0.
If a variable occurrs negatively in $c$, then fix the corresponding coordinate at 1.
A 0-1 truth assignment (to the variables in $X$) violates clause $c$, if and only if the vector corresponding to the truth assignment lies in subspace $S(c)$.
A 0-1 truth assignment (to the variables in $X$) satisfies all clauses,
if and only if the vector corresponding to the truth assignment lies in none of the subspaces $S(c)$.


Worst case to average case reductions Are there problems whose average case complexity is the same as their worst case complexity? What are the underlying properties of these problems that makes reducing the worst case to the average case possible?

This type of problem has been the subject of quite a bit of study. You can find references by googling random self-reducibility, and the Wikipedia article is a good place to start reading. There are still a lot of associated open questions.


Upperbound for max degree of k-tree completion Definitions: For a graph $G$, a $k$-tree completion of $G$ is a $k$-tree obtained by adding edges to $G$ (if $G$ has a $k$-tree completion, $G$ is said to be a partial $k$-tree). The least integer $k$ such that $G$ has a $k$-tree completion is called the treewidth of $G$. The maximum degree of a graph $G$ is denoted by $\Delta(G)$.
Question: Suppose that $G$ has a $k$-tree completion.
Is there an upper bound $U$ in terms of $k$ and $\Delta(G)$ such that
there exist a $k$-tree completion $G'$ of $G$ with $\Delta(G')\leq U\,?$
(note: To be explicit, $U$ is a function of $k$ and $\Delta(G)$ )
Context: I have a graph parameter $x(G)$ such that $x(G)\leq \Delta(G)+p$ for every chordal graph $G$ where $p$ is a constant. Using this result, I am trying to give an upper bound for $x(G)$ in general graphs in terms of treewidth of $G$ and $\Delta(G)$.

It is known that a graph of treewidth $k$ and maximum degree $\Delta$ has tree partition width at most $O(k\Delta)$. See Wood, arXiv:math/0602507.
From a tree partition of width $O(k\Delta)$ a triangulation of width $O(k\Delta)$ and maximum degree $O(k\Delta^2)$ follows pretty directly (start with the tree partition, make every bag into a clique, make every vertex $v$ in $U$ adjacent to all vertices in all bags appearing together with neighbors of $v$).
So you get a (minimal) triangulation with the bounds above.
Note: I would not be surprised if you can get a better degree bound.. the additional $\Delta$ term feels unnecessary.


Complexity of permanent modulo prime Given $M\in\Bbb Z^{n\times n}$ with $O(n)$ bit entries (could be all in $\{0,1\}$), $p$ a prime of $O(n^\alpha)$ bits for some $\alpha\in(0,1]$ and a $c,d\in\Bbb Z$ with $0\leq c<d<p$, is 'Is $\mathsf{Perm}(M)\bmod p\in\{c,\dots,d\}$?' $\mathsf{PP}$-complete?

What if $p$ is $O(\log n)$ bits or even smaller?

Without the ${}\bmod p$ it is known to be $\mathsf{PP}$-complete.

First, the permanent of an $n\times n$ integer matrix with $O(n)$-bit coefficients is an integer with $O(n^2)$ bits, hence if we know it modulo an integer with $\Omega(n^2)$ bits (with the implied constant depending on the constant in the input bit size), we know it outright.

Your problem with $p$ allowed to have $O(\log n)$ bits is PP-hard under polynomial-time Turing reductions: in order to compute permanent, just compute it modulo every prime below $cn^2$, and use the Chinese remainder theorem to find its value modulo the product of these primes, which is roughly $e^{cn^2}$. By the above, this provides the true value of the permanent for suitable $c$.

There is a serious obstacle to using your problem for primes with $\omega(\log n)$ bits: any reduction to this problem must in particular produce a prime number, and we know of no provably correct deterministic way of computing large primes significantly faster than brute force.

But if you allow randomized reductions, or say, reductions with free access to solutions of the search problem “given $x$, find a prime $p$ such that $x\le p\le2x$”, then you can reduce the number of oracle queries in the reduction of permanent I gave above by using a smaller number of larger primes: if you allow primes $p$ with $m(n)$ bits, you can do away with about $n^2/m(n)$ oracle calls.

For $m(n)=n^\alpha$ with constant $\alpha$, you can use padding to reduce the number of queries to $1$, i.e., to get a randomized many-one reduction: given the input $n\times n$ matrix $M$, find a prime $p$ of at least $n^2$ bits, and let $M'$ be the matrix $M$ padded with diagonal $1$s to dimension $n'\times n'$, where $n'^\alpha\ge\log p$. Then ask for the permanent of $M'$ modulo $p$.


Solve the recurrence $f(n) = f(n-1) + f(n - \log n)$ How can I solve the following recurrence relation?
$$ f(n) = f(n-1) + f(n - \log n)$$

@Chandra, @Emil, and myself solved the question in the comments. The solution is $$f(n) = 2^{\Theta(n \log \log n / \log n)} \ .$$

To see the lower bound, apply the recurrence definition $\log n$ times, to get $$f(n) = 2f(n - \log n) + f(n - \log n - 1) + \ldots + f(n - 2 \log n) \ge \log n \cdot f(n - \log n) \ .$$
Use this inequality $n / \log n$ times, and we get that the solution is $2^{\Omega(n \log \log n / \log n)}$.

To get the upper bound, use the recurrence $\log n$ times and get that $$f(n) \le (\log n + 1) \cdot f(n - \log n) \ . $$
Use this inequality $n / \log n$ times, and we get that the solution is $2^{O(n \log \log n / \log n)}$.


Several papers appear to imply P=NP via chordal graphs, what is wrong? Several papers appear to imply P=NP via chordal graphs,
which suggests something is wrong.

As usual $\gamma(G)$ is the domination number and $i(G)$ and $\gamma^i(G)$
are the independence domination number.

According to VIZING’S CONJECTURE FOR CHORDAL GRAPHS, p.1

  Theorem 1.1. [2] In chordal graphs $\gamma(G)=\gamma^i(G)=i(G)$.

According to graphclasses.org

and a paper p. 55 of the document and 65 of the pdf:

  In chordal graphs Domination is NP-complete and Independent Domination is
  polynomial.

The equality in Theorem 1.1 appears to imply P=NP since we can compute
$\gamma(G)=i(G)$ in chordal graphs by the above result.

  What is wrong with this?

The problem is that you confused the definiton in the paper of Aharoni & Szabo and the normally used definition for the term "independence domination number". The former one refers to the largest size over all minimum set dominating an independent set, and the latter one is the smallest size of a dominating set which is also an independent set.

These two definitions are quite different, and as you noticed they have different symbols: $\gamma^i(G)$ and $i(G)$. The Theorem 1.1 you mentioned actually claims $\gamma(G)=\gamma^i(G)$ for chordal graphs $G$, and generally they are not equal to $i(G)$ even when $G$ is chordal. The following graph is a counterexample:

where $\gamma(G)=2$ and $i(G)=3$.

As a comment, Allan & Laskar showed that $\gamma(G)=i(G)$ when $G$ is claw-free, but there are no such conclusions for chordal graphs.


Surveys on Algorithmic Problems in Coding Theory Coding Theory has many algorithmic problems that enriched theoretical computer science. I want to learn specifically the connection between coding theory and the hardness of computational problems. I'm aware of the NP-completeness of Maximum likelihood decoding problem.

Are there recent surveys and tutorials of computationally hard problems in coding theory?

I'm more interested in surveys that do not assume strong background in coding theory.

There are known worst-case hardness results about ML decoding (for general and specific families of codes such as Reed-Solomon), computing or approximating minimum distance of codes, and so on. However there is a great room for improvement in these directions and several seemingly intractable problems are not analyzed yet.

There are coding theoretic problems that are conjectured to be intractable, such as problems related to decoding random ensembles of codes. Such intractability assumptions are related to hardness of learning noisy parities and also form the basis of coding-theoretic public key cryptography (which is a big area of research by itself). For a good account of the latter, see Lorenz Minder's thesis.

Finally, there's a survey on tractable algorithmic problems in coding, including recent developments in list decoding: Algorithmic Results in List Decoding. This is a good resource to quickly learn about basics of coding theory. Also for learning the basics, Luca Trevisan's article "Some Applications of Coding Theory in Computational Complexity" may be useful.


On definition of IP class I'm a little bit lost with the actual definition of IP, some sources define as interaction between algorithms starting with Verifier, another one does not any put restriction on who send the first message. This simple question turn things messy ahead, when take into account  the number of messages on definition of IP(k). Does matter who start the interaction?

In the definition of class IP(k), the interaction always ends with prover’s message.  Otherwise there is no use for the last message (why?).

The situation is different for the definitions of public-coin interactive proof systems (also known as Arthur-Merlin proof systems), where sending a message from the verifier to the prover is the only way for the verifier to generate a random bit string.  In Babai [Bab85], AM(k) is defined by the verifier (or Arthur) sending the first message and MA(k) is defined by the prover (or Merlin) sending the first message.

[Bab85] László Babai.  Trading group theory for randomness.  In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pp. 421–429, May 1985.  DOI: 10.1145/22145.22192.


Independent set size of a large girth graphs For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true

Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8d}\log_2d.$$

Where $n(G)$ is the vertex size of the graph, $d$ is the avg degree and $\alpha(G)$ is the size of maximum independent set.

My Question : Are there extensions of above result for graphs with girth $\geq l$ ?

Bollobas showed that for any $d$ and any $g$, there exists a $d$-regular graph $G$ of girth at least $g$ such that

$$
\alpha(G) < \frac{2n\log d}{d}.
$$

So you cannot hope for more than a factor 16 improvement. McKay gave somewhat sharper bounds.


Is the wording of Google's QC Supremacy valid? Quantum supremacy using a programmable superconducting processor was published today. Scott Aaronson posted a few weeks ago a post about this paper and it was clear we will see a Nature or Science paper soon.

The abstract’s wording is less extravagant:

  This dramatic increase in speed compared to all known classical
  algorithms is an experimental realization of quantum
  supremacy for this specific computational task...

Isn't supremacy a well-defined concept in complexity theory?
Wouldn't Shor's algorithm be considered a QC supremacy?
How can we define supermacy unless it's provable that there is no classical algorithm to solve the problem faster on "traditional" supercomputer besides brute force?

Note: this is an amazing paper and I am seriously asking to understand if the wording of the paper is acceptable by the QC community.

Related: IBM’s response.

You should read the new post by Aaronson, but until then the short answers:

No.
If you can realize it in a real world machine, then it would (if no one finds a fast, classical algorithm until then).
You don't prove anything. It's a practical fact, like AI playing chess better than humans. If a chess genius is born, (s)he might win back the crown for humanity!


Algorithm for ordering a list under a similarity function? While thinking about the best way to display confusion matrices, and I came up with the following problem:

You have a set of objects $A$, and a similarity function $s: A,A \rightarrow \mathbb{R}$ defined on every pair of objects.  You want to find an ordering $i: A \rightarrow [1..|A|]$ on the objects that minimizes:

$\sum_{a,b \in A} s(a,b) * (i(a) - i(b))^2$

That is, the ordering is penalized by the similarity of each pair times the square of the distance.

Any ideas on an algorithm to solve this?  Any of: a polynomial-time algorithm, an idea for an NP-hard reduction, or search keywords for similar problems would be greatly appreciated.  Thanks!

The variant of your problem where you DON'T square the distance is called the (weighted) Minimum Linear Arrangement problem. It's NP-hard and there are a number of different approximation methods for it. Here's one link that popped up that has code that you might find useful.

But fortunately for you, you squared the distance, which changes things quite a bit. Let's expand the expression:
$$
\begin{align*}
\sum_{a,b \in A} s(a,b) (i(a) - i(b))^2 &= \sum_{a,b \in A} s(a,b) (i^2(a) +i^2(b) - 2 i(a) i(b)) \\
&= \sum_a i^2(a) \sum_b s(a,b) + \sum_b i^2(b) s(a,b) - 2 \sum_{a,b} s(a,b)i(a)i(b) \\
&= 2 \sum_a S(a) i^2(a) - 2 \sum_{a,b} s(a,b)i(a)i(b) \\
&= 2 u^\top A u
\end{align*}
$$

where $u$ is the vector $i(a)$ and $A_{a,b} = -s(a,b), A(a,a) = \sum_b s(a,b)$.

All of this is a long-winded way of saying that you've essentially defined the Laplacian operator for the complete graph with weights given by your similarity function. At this point, minimizing the form is straightforward. You compute the decomposition of A in the form $A = V \Lambda V^T$, at which point your goal is to minimize the norm $\| u^T V \sqrt{\Lambda}\|$. But note that since $A$ is symmetric, $V$ is orthonormal, and is essentially a rotation matrix, and so what you really want to do is line up $u$ in reverse order of the eigenvalues of $A$ (the elements of $\Lambda$)


Determining the number of clusters using property testing algorithm We say a set of $n$ points in $R^d$ are $k$-clusterable, if all points are covered by k unit balls. We have a property testing algorithm (see section 5 of paper) which consider a promise version of the above problem. The algorithm samples $O(\frac{kd}{\epsilon}\log \frac{kd}{\epsilon})$ many points from the set, and distinguish between following two cases with probability at least $\frac{2}{3}$:

-algorithm ACCEPTS, if all the points are $k$-clusterable.

-algorithm REJECTS, if points are $\epsilon$-far from $k$-clusterable, i.e. any $k$ unit balls covers at most $(1-\epsilon)n$ points.

Now, using the above algorithm as a subroutine can we approximate the value of $k$ (number of clusters), i.e., if we can ignore at most $\epsilon n$ points (because now we don't have the promised version of the input) from the input,
then we need to determine the number of clusters in the input.

(I was thinking to do some kind of binary search over $k$, start with k=2, if algorithm ACCEPTS then k=2, if REJECTS then try for k=4 and so on.)

Pls let me know if there is any confusion in the problem.

First. One can do better as far as the sampling - at least if $d$ is large - $O(\frac{kd \log k}{\epsilon} \log \frac{1}{\epsilon})$ should follow easily from relative approximations http://sarielhp.org/p/06/relative/ and combining range spaces of bounded VC dimension (if you send me email I would email you a pdf containing this combining result you need - its well known, but i dont know a ref for that). Secondly, relative approximation sample in this case, guarantees that if the sample fails, then $k$ is too small. So, do exponential search for the right value of $k$, specifically, start with $k_i = 2^i$, and let $R_i$ be the the $i$th sample of size $n_i = O( \frac{kd \log k}{\epsilon} \log \frac{i}{\epsilon} )$ (the $i$ is not a typo).

Let $\alpha$ be the minimum $i$ for which the sample succeeds using the black box. Now, use brute force (on the sample) to find the minimum $k\leq k_\alpha$ for which the sample works. And this is your desired $k$. You need to carefully account for the probability of success, but thats why the $i$ is there - its one of these standard geometric summation stuff.

The $i$ can be avoided -- indeed, the probability that $\alpha$ is bigger by $\Delta$ than its correct value is smaller than $2^{-\Delta}$. If you do that, then the sample you are going to use is of the right size with good probability. That is, if the minimum $k$ for which you can cover more than $(1-\epsilon)n$ of the points is $\kappa$, then the sample the algorithm uses is $O\left( \frac{\kappa d \log \kappa}{\epsilon} \log \frac{1}{\epsilon} \right)$.

There is some added fuzzyness in the answer of this algorithm. The returned answer $\kappa$ is the minimum such that any value of $k < \kappa$, is say $(1-\epsilon/2)$-far from from being k-clustered. I assume this is OK.

In practice you would do something different. Hmm. Something to think about....


Adversarial Machine Learning, Learning with (Malicious) noise I am reading some old papers regarding Learning With Malicious Noise. In one of them, Learning in the presence of Malicious Errors, by Kearns and Li $[1]$ (https://www.cis.upenn.edu/~mkearns/papers/malicious.pdf), it is proved that in the case that an adversary may choose a fraction $\beta \in [0, \frac{1}{2})$ of the training set to poison with instances, such that no restriction is put on the poison instances, then the upper bound $\beta < \frac{\epsilon}{\epsilon+1}$ must be met, so that it is possible to learn an $\epsilon$-good hypothesis with a probability at least $1-\delta$ (in the PAC-learning setting, using the usual notations). This bound is, however, not reached everytime, but for some specific hypothesis classes, the bound is much lower than that.

However, in the paper Learning from Noisy Examples, by Angluin and Laird $[2]$ (http://homepages.math.uic.edu/~lreyzin/f14_mcs548/angluin88b.pdf), it is shown that in the case of Clasification Noise, i.e. the attacker doesn't modify the underlying distribution of the instances, but may flip the label of some instances, with a probability $\beta$, then for every $\beta < \frac{1}{2}$, it is possible to find an $\epsilon$-good hypothesis with a probability at least $1-\delta$ (in the PAC-learning setting, using the usual notations), using at least $m \geq \frac{2}{\epsilon^2(1-2\beta)^2}\ln{\Big( \frac{2 \cdot |\mathcal{H}|} {\delta} \Big)}$ instances, where $\mathcal{H}$ is the hypothesis class supposed to be learned.

The question is: why is not possible to apply the result of $[2]$ in the case of $[1]$? How is the hypothesis that the underlying distribution of instances stays the same in case of $[2]$ used to prove the correctness? I am not able to find that in the proof. Can you please point it out for me?

Thank you so much everyone!

In the proof of the positive result in [2] you are referring to, namely Theorem 2, the argument goes as follows. For every possible concept $L_i$ of the hypothesis class $\mathcal{H} = \{L_1,\dots, L_N\}$, let $p_i$ to be the distance (probability of disagreement) with the true concept $L^\ast$. Then, under a classification noise $\eta$, we have that the probability $p_i$ that a labeled example $\langle x,y\rangle$ disagrees with $L^\ast$ is exactly
$$
p_i =  d_i(1-\eta) + (1-d_i)\eta = \eta+d_i(1-2\eta) \tag{$\dagger$}
$$
where $d_i = \Pr[x\in L_i\triangle L^\ast]$ is the probability to hit the region where $L_i$ and $L^\ast$ disagree. In particular, for any "bad" concept $L_i$ which is $\varepsilon$-far from $L^\ast$, we have $p_i \geq \eta+\varepsilon(1-2\eta)$, while for $L_i=L^\ast$ we have $p_i = \eta$. The argument then goes by applying concentration bounds and a union bound over the (at most $N$) bad concepts to see how many examples are enough to ensure that, w.h.p., choosing the concept consistent with the maximum number of examples taken rules out all bad concepts. (In particular, the "gap" on expectation for $m$ examples between a bad concept and the true concept is at least $\varepsilon(1-2\eta)m$ by the above.)

Now, what changes under malicious noise? (Or, even, under the milder assumption that the adversary can, with probability $\eta$, decide to flip or not the label of a sample, instead of flipping it automatically as in the classification noise) Put it simply, $(\dagger)$ is no longer true.

For instance, the adversary could focus on a specific bad ($\varepsilon$-far) hypothesis, say $L_{i^\ast}$, and decide to only flip the label of a given example $x$ if that example falls into the region of disagreement $L_{i^\ast}\triangle L^\ast$ (and not if it doesn't). In that case, one gets
$$
p_{i^\ast} = d_{i^\ast}(1-\eta) + (1-d_i)\cdot 0 = d_{i^\ast}(1-\eta) \geq \varepsilon(1-\eta)
$$
instead of the previous expression. That is a huge drag for the analysis, and essentially kills it: now, in this possible scenario (which may not happen, but is a valid scenario) to have any hope of separating $L^\ast$ from this bad concept $L_{i^\ast}$ by looking at the disagreements, we need to separate the expected $\eta m$ (for $L^\ast$) from the expected $\varepsilon(1-\eta) m$ (for the bad concept $L_{i^\ast}$)... and to have any hope of doing so, we need
$$
\varepsilon(1-\eta) > \eta
$$
or equivalently $\eta < \frac{\varepsilon}{1+\varepsilon}$.

Note that this is by no means a formal proof of the negative result of [1], more a hand-wavy way to see that things are consistent.


Is there a PSPACE-intermediate language? Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete?

I encountered a language that is in PSPACE. The question is whether it's in PH. So far I don't have any success in either proving it's in PH or proving it's PSPACE-complete. I wonder if there is a languge that's not in PH and not PSPACE-complete given PH $\ne$ PSPACE.

This is corollary 13 in Uwe Schöning's paper "A uniform approach to obtain diagonal sets in complexity classes":

  Corollary 13:

  If $\mathsf{PSpace} \neq \mathsf{PH}$, then there exist sets in $\mathsf{PSpace}$ which are not $\mathsf{PSpace\text{-}complete}$ w.r.t. $\leq^{\mathsf{P}}_T$ and which are not in the polynomial hierarchy.

  Proof:

  If $\mathsf{PSpace} \neq \mathsf{PH}$, then QBF is not in the polynomial hierarchy.
  Hence $A_1 = \emptyset$, $A_2 = QBF$, $C_1 = \{\mathsf{NP\text{-}complete} \text{ w.r.t. } \leq^{\mathsf{P}}_T \}$, $C_2 = \mathsf{PH}$, satisfy the hypothesis of the main theorem.

  Main theorem:

  Let $A_1$, $A_2$ be recursive sets and $C_1$, $C_2$ be classes of recursive sets with the following properties:

  $A_1 \notin C_1$, $A_2 \notin C_2$
  $C_1$ and $C_2$ are recursively presentable,
  $C_1$ and $C_2$ are closed under finite variations.

  Then there exists a recursive set $A$ such that:

  $A \notin C_1$, $A \notin C_2$,
  if $A_1 \in \mathsf{P}$ and $A_2\notin \{ \emptyset, \Sigma^* \}$, then $A \leq^{\mathsf{P}}_m A_2$.

(note: I updated the names to current ones)

There are two interpretations for monotone QBF:

QBFs where the quantifier free part is monotone in all variables. Then this is in $\mathsf{P}$ as Ryan noted. Because the quantifier-free part is monotone in quantified variables we can remove the quantifiers and replace the existentially quantified variables with 1 and universally quantified variables with 0, the original quantified formula is true iff this modified quantifier-free formula is true, and this reduces the problem to monotone formula evaluation which is in (and complete for) $\mathsf{NC^1} \subseteq \mathsf{P}$. (If we are taking supremum of a function over a variable and the function is monotone in that variable we only need to compute the value of the function over the maximal values for that variable.)
QBFs which are monotone in the input variables. This is $\mathsf{PSpace}$ under $\mathsf{AC^0}$ reductions, the reduction of the QBF to this version is simple and is similar to the proof for monotone boolean formula evaluation being complete for $\mathsf{NC^1}$ or monotone circuit value being complete for $\mathsf{P}$.


Alternatives to Normalization by Evaluation Reading about lambda calculus I got the impression that normalization is evaluation.
So I don't understand what is meant by Normalization by Evaluation (used e.g. in several publications of A. Abel).
Can you explain what are the alternative paths to the goals achieved by NbE?

NbE really has 2 goals:

As an evaluation mechanism for $\lambda$-terms. In this regard there are many many alternatives, basically any interpreter, virtual machine or compiler is a possible approach. NbE is just a way to get the host language to do the compilation for you!

As a proof technique to show the decidability of convertability for typed lambda calculi. E.g. it is decidable to prove $t =_{\beta\eta} u$ if $t$ and $u$ are simply typed terms of the same type. The obvious alternative is: proving that $\beta\eta$-reduction is strongly normalizing and confluent. It's not clear whether you're lumping this in with NbE, because they (usually) both use logical relations at their core. Certainly there are systems for which SN does not hold, but for which we can carry out NbE though.


Fast sparse boolean matrix chain product So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually stay as sparse at each step.

Are there any matrix chain product algorithms that work particularly fast in this case?

On a higher level, the problem is to compute the composition of a series of one-to-many mappings on a reasonably small graph (transition functions of an NFA), where most elements map to no more than 0-3.

(please note that this is not the usual "matrix chain product" problem, because all matrices are of the same size and I don't have to choose the optimal parenthesizing)

This was too long to be a comment -- I wonder if those matrices have structure that make them behave differently from random matrices. Products of random sparse matrices go to zero or become non-sparse quickly.
Here's a simple experiment -- take 200 random binary 50x50 matrices, and plot number of non-zeros as a function of number of matrices multiplied. Plots below show standard deviation over 2000 runs. First plot is for 2% sparsity, second plot is for 3%

(source: yaroslavvb.com)

(source: yaroslavvb.com)
this took 3 minutes on my laptop using standard matrix multiplication


Proof of Nullstellensatz certificate degree Discalimer:

The approach below may be usefull to prove P=NP. I would understand down-voting.

Many NP-complete problems can be encoded in the system of polynomial equations. Some examples are in the introduction here. Basically the idea is to encode binary variables in the equations $f_k= x_k^2-1= 0$, or $f_k = x_k^2-x_k=0$, and add one or more equations ($g_k=0 $) encoding satisfiability problem. Since the system can have exponentially many solutions finding them is hard. On the other hand, we can try to figure out if the system has solutions at all. One of the approaches is to use Nulstellensatz certificate, e.g. find the set of polynomials $P_k, P'_k  \in \mathbb{K}[x_1,...x_n]$, where $\mathbb{K} $ is an algebraically closed field, for example $\mathbb{C} $ such that the following equation is satisfied $1= \sum_k P_k f_k +\sum_m P'_m g_m$. The problem with this approach is that one need very high degree polynomials $P_k, P'_k $ and the certificate has exponentially many monomials. The intuition here is following. The problem is hard since all variables are influencing other variables, otherwise the problem can be split into independent subproblems. Since all of them are important the term with monomial $x_1 ... x_n$ has to appear in the certificate. That lead to the certificate of degree $n$, which has too many monomials.There is no clear way of selecting right monomials, and we need to use all of them. So the problem is that by increasing the degree of certificate the "mixing" of variables is too slow - we introduce too much noise - too many problem irrelevant tautologies!!! And we need a way to speed-up mixing of the variables.

We do usual trick of linearizing quadratic equations in terms of quadratic monomials (for 3-SAT we need cubic monomials), e.g. $y_{x_k,x_m}= x_k x_m,\ k, m = 0..n,\ x_0=1 $. This linear system has $\approx n^2$ linear variables (monomials), and $\approx n$ equations, e.g. highly under-complete. The solution of this (homogenised) linear system is $\approx n^2 $ dimensional projective space. The original system has a solution iff there is a point $c \in \mathbb{C}^{\approx n^2}$ in this projective space such that all corresponding equations on $y_{x_k,x_m} = y_{x_0,x_k} y_{x_0, x_m}, y_{0,0}=1$  are satisfied. These are quadratic equations on $c$, so we can write all the quadratic in $c$ constraints $y_{x_k,x_m} y_{x_p,x_q}= y_{x_k,x_p} y_{x_m,x_q}= y_{x_k,x_q} y_{x_p,x_m}$ (tautologies). Therefore, we have $\approx \frac{2}{3} n^4 $ quadratic equations with $\approx n^2 $ indeterminates $c_k$. Now we have equivalent, in terms of satisfiability, system of quadratic equations with $O(n^4)$ equations and $O(n^2)$ variables $c_k$, In other words, now we have $O(1)$ equations in terms of the number of quadratic in monomials, and the system is almost complete.

Now we can write Nulstellensatz certificate for the new system of tautologies in terms of $c_k$.

Q1. Does anyone see a simple way of proving fixed certificate degree for the new "almost complete" system?

Any relevant references are appreciated.

The research area relevant to your question is propositional proof complexity, more specifically algebraic proof systems. Nullstellensatz is in fact only one of a family of proof systems which includes also the polynomial calculus (PC), polynomial calculus with resolution (PCR), and a proof system which has received some notice from a surprising directions, the sum of squares (SoS) system.

Unfortunately, I wasn't able to find a recent survey of algebraic proof systems. Toni Pitassi has an old survey, but there are many results not mentioned there. There is some material in the more general survey by Paul Beame and Toni Pitassi. Some more recent results are referenced in a lecture by Pavel Pudlák.


Polynomial method for complexity results Polynomial methods, say Combinatorial Nullstellensatz and Chevalley–Warning theorem are powerful tools in additive combinatorics. By representing a problem with proper polynomials, they can guarantee the existence of a solution, or the number of solutions to the polynomials. They have been used to solve problems like restricted sumsets or zero-sum problems, and some of the theorems in this area can be proved only by such methods.

To me the non-constructive manner of these methods are truly amazing, and I'm curious about that how we can apply these methods to prove any interesting inclusions and separations of complexity classes (even if the result can be solved by other methods).

  Are there any complexity results known that one can prove them by polynomial methods?

Some classic examples of the use of the polynomial method are:

Razborov-Smolensky's proof of "Parity not in $AC^0$" (lots of expositions available online, here is one)
Beigel-Reingold-Spielman's proof of "PP is closed under intersection"
Bazzi's result for fooling DNFs, and Braverman's proof of "Polylog independence fools $AC^0$"

Also, fourier analysis of boolean functions (here is a great course by Ryan O'Donnell)  has a HUGE collection of awesome results, my favourite being the Kushilevitz-Mansour-Nisan's proof of the Goldreich-Levin theorem.

Scott Aaronson had in fact given a tutorial at FOCS'08 on the "The Polynomial Method in Classical and Quantum Computing (ppt)".

Hope this helps.


Termination checking for Scott-encodings in System F with positive-recursive types Is there any research on termination analysis on Scott-encodings in System F with positive-recursive types.
All papers I have found use languages with constructors and case analysis (for example foetus).
But given that we can encode any ADT as pure lambdas, by defining an ADT as it's case analysis function, is it still possible to do termination checking similar to how it is done for ADTs?

For example we can encode the natural numbers as:

type Nat = forall t. t -> (Nat -> t) -> t
zero = \z s -> z
succ n = \z s -> s n

and then define addition like:

add n m = n m (\n' -> succ (add n' m))

Is it still possible to analyze the recursive calls for termination?
I am aware of Church-encodings but I am interested in structural recursion specifically.

I'll first point you to Types for the Scott Numerals by Plotkin, Cardelli and Abadi, where they show how to encode Scott numerals in plain old system F. This at least shows that you can write the "natural" recursion principles on Scott numerals, and because they correspond to recursors in this encoding, they are guaranteed to terminate.

However, if you want to work directly with the recursive type formulation, you can apply the classical theory of termination of system F augmented with the theory of positive inductive types, comprehensively treated in Ralph Matthes' dissertation, admittedly a technical read.

I'm not 100% sure those techniques apply here though. I think the recursor you'd get for the Scott encoding would be something like

recNat : forall P. ((forall t. t -> (P -> t) -> t) -> P) -> (Nat -> P)

For fixing ideas I wrote a definition in Haskell which was a bit tedious:

rectNat f n = f $ \z s -> n z (\ n' -> s (recNat f n'))

Of course in a Matthes like system, the recursor is primitive and the Haskell definition is simply the operational semantics of the recursor.

and you would write addition by specializing P to Nat -> Nat and implementing the first argument of recNat by:

\n -> n (\m -> m) (\add_n m -> succ $ add_n m)

which I think works out to the correct addition when applied to the recursor.

If you're really adverse to recursors, you can apply standard termination analysis techniques in system F or Calculus of constructions, see e.g. Abel's dissertation which is a real tour-de-force.

Finally, I must caution you against a strange counter example in the realm of recursion with positive inductive types: consider the type

I = (forall t. (t -> t)) -> I

which is positive, since a fortiori it does not even contain recursive arguments! Then one might be tempted to accept the recursive function:

Y :: I -> I
Y i = i Y i

There is no obvious reason to reject this program, since Y is not being recursively applied to any smaller arguments. However, applying Y to the identity function will loop.

All this to say that there are strange counter-examples when dealing with positive inductive types in impredicative settings. However, Scott encodings with structural recursive functions do not seem to trigger these counter-examples, and I believe that they are handled by the standard theory of termination from the literature.


Does the simply typed lambda calculus have general iteration? In more expressive calculi such as System F, the Church numerals, by virtue of their design, allow for iteration over an arbitrary type.  Can this effect be replicated in the simply typed case?

To be precise, consider the simply typed lambda calculus with a single base type $0$, giving the Church numerals the type $\mathsf{N} := (0 \rightarrow 0) \rightarrow 0 \rightarrow 0$.  For any type $\sigma$, can we find a closed term $\mathsf{it}_\sigma : \mathsf{N} \rightarrow (\sigma \rightarrow \sigma) \rightarrow \sigma \rightarrow \sigma$ with the property that

$$
\mathsf{it}_\sigma \underline{n} f x \rightsquigarrow f^nx
$$

?

Assuming the given type and standard definition of Church numerals this indeed seems possible if we assume the existence of computable bijective mapping between instances of given types.

Note that the main issue is the type mismatch of $\mathsf{it}_\sigma$ and $\mathsf{N}$, otherwise $\mathsf{it}_\sigma$ could be equal to the identity function. One way of solving this issue is to have a way of uniquely converting between the types $\sigma$ and $0$. More specifically, if we have a way of encoding instances of type $\sigma$ into $0$ (which should encode natural numbers, thus have infinitely countable number of instances), we could encode the argument before applying it to $f$ and then decoding back the result. That is, if $e: \sigma \rightarrow 0$ and $d: 0 \rightarrow \sigma$ (which are inverses, thus define a bijection), we can define:

$$\mathsf{it}_\sigma \; n \; f \; x = n \; (\lambda y. e \; (f \; (d \; y)) \; x$$

Of course, this assumes the existence of $f$ and $g$, which might be easily realizable if, for examples, we had ways to enumerate instances of corresponding types. (E.g. for Church numerals, zero and increment should suffice.)

Note that bounded iteration is not as expressive as general iteration. In addition, note that Church numerals are definable by typeable terms in simply typed lambda calculus, together with operations like addition, but not predecessor (for which stronger mechanisms, like polymorphism in System F, are needed). (Short writeup about this can be found here.)


Isomorphism between algebraic data-types I have two types of trees in Haskell, defined as the least solution of the following equations:

$T_1(A) \cong 1 + A + T_1(A) \times T_1(A)$

$T_2(A) \cong 1 + A \times T_2(A) + T_2(A) \times T_2(A)$

In Haskell it would be something like

data T1 a = Leaf | Data a | Node (T1 a) (T1 a)

data T2 a = Leaf' | Data' a (T2 a) | Node' (T2 a) (T2 a)

How could I prove or disprove that $T_1$ and $T_2$ are isomorphic? I'd like to know which tools are used to prove the non-existence of isomorphisms.

Spoiler: the types are isomorphic.

First let me clarify what might be meant by "isomorphic". Say that two datatypes $S$ and $T$ are isomorphic if there are maps $f : S \to T$ and $g : T \to S$ such that $f(g(v)) = v$ for every value $v : T$ and $g(f(u)) = u$ for every value $u : U$.

Let us fix a type $A$. We can then write your equations without the parameter $A$ as
$$T_1 = 1 + A + T_1 \times T_1$$
and
$$T_2 = 1 + A \times T_2 + T_2 \times T_2.$$
(We really want to consider the types polymorphic in $A$, and we shall do so, but for the moment I'd like to get rid of $A$ as a parameter, so let us consider it temporarily fixed.) If we define "polynomial" type constructors $P_1(X) = 1 + A + X \times X$ and $P_2(X) = 1 + A \times X + X \times X$ then the above definitions become fixed-point equations
$$T_1 = P_1(T_1)$$
and
$$T_2 = P_2(T_2).$$
We can consider either the inductive solution (the initial algebra for the polynomial functor) or the coinductive solution (the final coalgebra). The former is what you get in ML-style language and the latter in Haskell. Let's do inductive, as that is algebra, while coinductive gets us into topology (which is cooler but a bit trickier).

Now, we would like to know whether the initial algebras for $P_1$ and $P_2$ are isomorphic parametrically in $A$, by which we mean that we want isomorphisms that are parametrically polymorphic in $A$. Beware, non-isomorphic functors may produce isomorphic initial algebras: lists of $A$'s are the initial algebra for both $X \mapsto 1 + A \times X$ and $X \mapsto 1 + A \times X + A \times A \times X$! So for instance it is not sufficient to find $Y$ such that $P_1(Y) \not\cong P_2(Y)$. But since we want isomorphisms that work for all $A$'s it is sufficient to find a single instance of $A$'s for which $T_1 \not\cong T_2$ (although that might be a bit hard to find...)

I am going to take it for granted that there are no isomorphisms between $A^n$ and $A^m$ for $n \neq m$ that are parametric in $A$. (Consider $A = \mathtt{bool}$.)

We can think of $T_1$ as an "infinite" nesting $P_1(P_1(P_1(\cdots)))$, so it makes sense to look at a finite approximation. Let us compute $P_1^n(X)$ for some $n$. The result is a polynomial in $A$ and $X$, which we express as $Q_n(A) + X \times R_n(A,X)$. For $n = 1$ we get (using Mathematica and expanding as a power series in $X$):
$$(A+1)+O\left(X^2\right),$$
for $n = 2$ we get
$$\left(A^2+3 A+2\right)+O\left(X^2\right)$$
for $n = 6$ we get
$$\left(A^{32}+48 A^{31}+1112 A^{30}+16568 A^{29}+178484 A^{28}+1481816
   A^{27}+9867676 A^{26}+54160004 A^{25}+249844422 A^{24}+982869432
   A^{23}+3333905572 A^{22}+9834052604 A^{21}+25390949338 A^{20}+57672050948
   A^{19}+115666688826 A^{18}+205373975070 A^{17}+323359748527
   A^{16}+451792820168 A^{15}+560048078060 A^{14}+615271918604
   A^{13}+597813614038 A^{12}+512098495020 A^{11}+385051162322
   A^{10}+252634062394 A^9+143508813439 A^8+69855202828 A^7+28739884958
   A^6+9808926186 A^5+2705141303 A^4+579784870 A^3+90704955 A^2+9224803
   A+458330\right)+O\left(X^2\right)$$
So it seems that we get a whole lot of every power of $A$. A similar thing happens with $T_2$, for instance $P_2$ unfolded 6 times is
$$
\left(256 A^{16}+6656 A^{15}+80768 A^{14}+607488 A^{13}+3171408 A^{12}+12191008
   A^{11}+35710688 A^{10}+81347056 A^9+145690452 A^8+205905596 A^7+228957512
   A^6+198261418 A^5+131104690 A^4+64020678 A^3+21778198 A^2+4612401
   A+458330\right)+\left(3072 A^{17}+80128 A^{16}+975744 A^{15}+7366080
   A^{14}+38598592 A^{13}+148916448 A^{12}+437720280 A^{11}+1000231448
   A^{10}+1796273100 A^9+2544344160 A^8+2833851236 A^7+2456339273 A^6+1624706942
   A^5+792912172 A^4+269323336 A^3+56895232 A^2+5632640 A\right)
   X+O\left(X^2\right)$$
In the "infinity" these coefficients on $A$'s will be infinite. We will get something that looks like
$$T_1 = P_1^\infty(X) = \infty + \infty A + \infty A^2 + \infty A^3 + \cdots
= \infty \times (1 +A + A^2 + A^3 + \cdots) = \infty \times \mathtt{List}(A)$$
and the same for $T_2$. So we form a hypothesis:

Theorem: Both $T_1$ and $T_2$ are isomorphic (parametrically in $A$) to the type $\mathtt{nat} \times \mathtt{List}(A)$.

Proof. The best proof would be actual implementations of the isomorphisms in question, but I do not have the time to do that. Perhaps a nice soul can volunteer to write these. Let me sketch an outline of the proof. Think of the elements of $T_1$ as trees which store some $A$'s in their leaves. To each value $v : T_1$ we assign a list $\ell_v = [a_1, \ldots, a_{n_v}]$ of the $A$'s stored in $v$, in left-to-right traversal order. There are infinitely many $v$'s which share the same $\ell_v$ because we can have arbitrarily many empty leaves. Order all $v$'s with the same $\ell_v$ in a canonical order of some sort, so that to each $v$ with a given $\ell_v$ we assign a number $n_v$ in this order. The mapping $v \mapsto (n_v, \ell_v)$ is the isomorphism from $T_1$ to $\mathtt{nat} \times \mathtt{List}(A)$. A similar construction works for $T_2$. QED.


Path in a graph with durations I have the following problem:

given

a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ (here $\mathbb{Q}_0^+$ denotes the set of non-negative rationals and $\mathcal{I}(\mathbb{Q}_0^+\cup\{+\infty\})$ the set of intervals, bounded or unbounded above, with non-negative rational bounds) is a function associating with each vertex $v\in V$ a "minimum/maximum duration" $d(v)=[a,b]$ for some $a\in \mathbb{Q}_0^+,b\in \mathbb{Q}_0^+\cup\{+\infty\}$ and $a\leq b$,
two vertices $s,t\in V$ and
an integer $h$ encoded in binary,

we have to decide whether or not there exist

a path in $G$, possibly with repeated vertices and edges, $v_0 \cdot v_1 \cdots v_{n-1}\cdot v_n$, with $v_0=s$ and $v_n=t$ and
a list of values $d_0,\ldots,d_n\in\mathbb{Q}_0^+$,
such that $\sum_{i=0}^n d_i = h$ and for all $i=0,\ldots, n$, $d_i\in d(v_i)$.

Intuitively, we have to find a path in $G$, possibly where we get to the same vertices/edges also more than once, and where we remain in each vertex a non-negative rational amount of time allowed by the minimum/maximum duration function, such that the overall time of the path equals $h$.

This can be solved easily in PSPACE.
We conjecture it to be in NP (we already know it is NP-hard!). This is not trivial to prove, as we may have $h\in\Theta(2^n)$, for instance. Thus the required path may have length exponential in both $|V|$ and in the binary encoding of $h$.

Have you ever seen a similar problem? Can you come up with an NP algorithm? Or do you know some connected literature?

This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP,
we provide a polynomial-size certificate,
and then we show how to check it in deterministic polynomial time.

The certificate is just the following:
a set of integers $\{x_{u,v}\mid (u,v)\in E\}$.
Intuitively, $x_{u,v}$ is the number of times the solution path
traverses $(u,v)$.

We now describe the
verification algorithm.

We consider the subset $E'$ of edges of $G$, $E':=\{(u,v)\in E\mid x_{u,v}>0\}$. We check whether $E'$ induces a strongly (undirected)
connected subgraph of $G$.
We check whether

$\sum_{(u,v)\in E'} x_{u,v}=\sum_{(v,w)\in E'} x_{v,w}$, for all $v \in V\setminus\{s,t\}$;
$\sum_{(u,s)\in E'} x_{u,s}=\sum_{(s,w)\in E'} x_{s,w}-1$;
$\sum_{(u,t)\in E'} x_{u,t}=\sum_{(t,w)\in E'} x_{t,w}+1$.

For all $v \in V\setminus\{s\}$, we define $y_v:=\sum_{(u,v)\in E'} x_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover,
$y_s := \sum_{(s,u)\in E'} x_{s,u}$.
We check whether there exist real values $z_v$, for every $v \in V$, such that

$d_{min}(v)\cdot y_v \leq z_v \leq d_{max}(v)\cdot y_v$ (here $d_{min}(v)$ and $d_{max}(v)$ denote resp. the lower and the upper
bound of the rational interval $d(v)$), and
$\sum_{v \in V} z_v = h$.

We now sketch the correctness:

Steps 1. and 2. together check that the values $x_{u,v}$ for the arcs specify
a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4.
form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).


Reducing redundant edges from a dependency graph I have a DAG of dependencies that contains lots of redundant edges (see example below). I want a "quick" algorithm (ie. can handle a graph with several thousands of nodes/edges) that finds a minimal sub graph.

For example:

A -> B -> C
A -> C

in words A is prerequisite to B, and B is prerequisite to C, and also A is prerequisite to C. In this case A -> C is redundant (since B is already necessary to reach C, and A is necessary to reach B).

Its been a while since I studied algorithms, and I'm not sure where to start.

By the way, its not critical that the algorithm finds the global minimum, local minimum is fine (the edge reduction is only a runtime optimization for next stage of processing).

Also, I realize this is a CS QA and not programming, but my program is written in Python, so I would be extra happy to learn of a python module or open source for doing this reduction, just in case you know of it.

thanks in advance!

The Transitive Reduction of a Directed Graph
A. V. Aho, M. R. Garey, and J. D. Ullman

According to wikipedia, this algorithm is used by tred which is tool for transitive reduction available in GraphViz package. You can run it on your graph and get reduced graph.

This question is duplicate of this stackoverflow question.

code here graphviz/tools/src/tred.c does use DFS. ;-)


Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$) I would like to check a sort of SMT formulas with two quantifiers where universal variables range over finite/bounded integer domains. An example formula is
$$\exists x \forall y ((y \ge 1 \land y \le 2) \implies ((\neg x)\land(y * y \ge 1)).$$
I found that Z3 can handle the sort of formulas. However, the heuristics for handling quantifiers in Z3 seem not tuned for problems where universal variables range over finite/bounded domains. Are there any other efficient tools for checking the sort of formulas?
This question describes tools for 2QBF, but 2QBF only supports SAT formulas (i.e., only supports Boolean variables). The formulas in my question include integer variables.

Since your integer variables are from a finite domain, you could "bit-blast" to SAT, then use a 2QBF solver.
In other words, you translate formulas over these int variables into formulas over boolean variables, by building a boolean circuit to represent each of the operations (multiplication and comparison, in your example), and then using the Tseitin transform.

Another approach is to apply one of the methods for 2QBF to your problem directly.  You'd have to implement this yourself.  For example, here is a naive approach.  Suppose your formula is $\exists x \forall y \varphi$:

Let $b_1,\dots,b_n$ be some values.

Testing the satisfiability of $\varphi[b_1/y] \land \dots \land \varphi[b_n/y]$.  If this is not satisfiable, then you can terminate, as it implies that $\exists x \forall y \varphi$ is not satisfiable.  If it is satisfiable, suppose it is satisfied by $x=a$.

Then try to satisfy $\neg \varphi[a/x]$.  If it cannot be satisfied, then you can terminate, as it implies that $\exists x \forall y \varphi$ is satisfiable with $x=a$.  If it can be satisfied, say by $y=b$, let $b_{n+1}=b$, increment $n$, and go back to step 2.

You could implement each of these steps in Z3, and this would take advantage of Z3's SMT theories, without requiring you to "bit-blast" to SAT.  Note that in this procedure, you only invoke Z3 to test satisfiability of singly-quantified formulas; there are no nested quantifiers.  You might even be able to use Z3's incremental solving abilities for better performance.


An upper bound for chi-square divergence in terms of KL divergence for general alphabets In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ defined over a general alphabet $\mathcal{X}$, if $P\ll Q$, then
$$\chi ^2(P||Q):=\int_{\mathcal{X}}\Big(\frac{dP}{dQ}\Big)^2dQ$$ and
$$D(P||Q):=\int_{\mathcal{X}}dP\log\frac{dP}{dQ}.$$

I am looking for an upper bound of $\chi^2(P||Q)$ in terms of $D(P||Q)$ which works wven if $\mathcal{X}$ is uncountable.
What I need is a special case where $P=P_{XY}$ and $Q=P_X\times P_Y$, for two random variables with joint and product distributions are $P_{XY}$ and $P_X\times P_Y$, respectively. Noticing that in this case KL divergence is equal to the mutual information , I need an upper bound of chi-square divergence in terms of mutual information.

Your definition of $\chi^2$ divergence is missing a term; namely,
$$
\chi^2(P\|Q) = \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ} - 1\right)^2
= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1
$$
(see e.g. this Wikipedia article on $f$-divergences).

With this in hand, recall that by concavity of the logarithm, we have
$$
\log x \leq x-1, \qquad \forall x >0
$$
(where $\log$ denotes the natural logarithm), and thus
$$\begin{align}
D(P\| Q) &=  \int_{\mathcal{X}} dP\log\frac{dP}{dQ}\\
&\leq  \int_{\mathcal{X}} dP\left(\frac{dP}{dQ} - 1\right) \\
&= \int_{\mathcal{X}} dQ\left(\frac{dP}{dQ}\right)^2 - 1
\end{align}$$
showing that the inequality holds:
$$
D(P\| Q) \leq \chi^2(P\|Q)\,,\qquad \forall P\ll Q
$$


Calculation of Recursive Spawning I'm reading the book Introduction to Algorithms (Cormel et al., 2009) on the chapter about multithreaded algorithms, and I'm confused about the following:

  We must also account for the overhead of recursive spawning when analyzing the
  span of a parallel-loop construct. Since the depth of recursive calling is logarithmic in the number of iterations, for a parallel loop with $n$ iterations in which the $i$th iteration has span $iter_{\infty}(i)$, the span is $$T_\infty(n)=\Theta(\lg n)+\max_{1\leq i\leq n}iter_\infty(i).$$

I agree that if there are a fixed number of processor, say $2$, then the depth is indeed $\log n$. But what if there are a huge number of processors, so that it can handle even large values of $n$? Wouldn't the depth of recursive calling be $\Theta(1)$ in that case?

$T_\infty$ means you have as many processor as you need (theoretically an infinite number). The strategy to assign each iteration to one processor is base on Divide and Conquer. So, at first, one processor split the number of iterations in two, spawn a new thread with the first half and recursively processes the other half. Then this two processors split each half in two chunks each. And so on until you have one iteration on each chunk, so you can compute it in $iter_\infty (i)$ time. Given that you have an infinite number of processors you can recruit twice the number of processors on each new level of this recursion, so each level can be executed in $O(1)$, but still you need to executed each level after the other. In order to have $n$ iterations (leaf on the recursion tree) you will need $O(\log n)$ levels.


Existence of "colouring matrices" Edit: there is now a follow-up question related to this post.

Definitions

Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$.

A $c \times c$ matrix $M = (m_{i,j})$ is said to be a $c$-to-$k$ colouring matrix if the following holds:

we have $m_{i,j} \in [k]$ for all $i, j \in [c]$,
for all $i,j,\ell \in [c]$ with $i \ne j$ and $j \ne \ell$ we have $m_{i,j} \ne m_{j,\ell}$.

We write $c \leadsto k$ if there exists a $c$-to-$k$ colouring matrix.

Note that the diagonal elements are irrelevant; we are only interested in the non-diagonal elements of $M$.

The following alternative perspective may be helpful. Let $R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$ be the set of non-diagonal elements in row $\ell$, and similarly let $C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$ be the set of non-diagonal elements in column $\ell$. Now $M$ is a $c$-to-$k$ colouring matrix iff $$R(M,\ell) \subseteq [k], \quad C(M,\ell) \subseteq [k], \quad R(M,\ell) \cap C(M,\ell) = \emptyset$$ for all $\ell \in [c]$. That is, row $\ell$ and column $\ell$ must consist of distinct elements (except, of course, at the diagonal).

It may or may not be helpful to try to interpret $M$ as a special kind of hash function from $[c]^2$ to $[k]$.

Examples

Here is a $6$-to-$4$ colouring matrix: $$\begin{bmatrix}
-&2&2&1&1&1\\
3&-&3&1&1&1\\
4&4&-&1&1&1\\
3&2&2&-&3&2\\
4&2&2&4&-&2\\
3&4&3&4&3&-
\end{bmatrix}.$$

In general, it is known that for any $n \ge 2$ we have $${2n \choose n} \leadsto 2n.$$ For example, $20 \leadsto 6$ and $6 \leadsto 4$. To see this, we can use the following construction (e.g., Naor & Stockmeyer 1995).

Let $c = {2n \choose n}$ and let $k = 2n$. Let $f$ be a bijection from $[c]$ to the set of all $n$-subsets of $[2n]$, that is, $f(i) \subseteq [2n]$ and $|f(i)| = n$ for all $i$. For each $i,j \in [c]$ with $i \ne j$, choose arbitrarily $$m_{i,j} \in f(i) \setminus f(j).$$

Note that $f(j) \setminus f(i) \ne \emptyset$. It is straightforward to verify that the construction is indeed a colouring matrix; in particular, we have $R(M,\ell) = f(\ell)$ and $C(M,\ell) = [k] \setminus f(\ell)$.

Question

Is the above construction optimal? Put otherwise, do we have $${2n \choose n} + 1 \leadsto 2n$$ for any $n \ge 2$?

It is well-known that the above construction is asymptotically tight; necessarily $k = \Omega(\log c)$. This follows, e.g., from Linial's (1992) result or from a straightforward application of Ramsey theory. But to me it is not clear whether the construction is also tight up to constants. Some numerical experiments suggest that the above construction might be optimal.

Motivation

The question is related to the existence of fast distributed algorithms for graph colouring. For example, assume that we are given a directed tree (all edges oriented towards a root node), and assume that we are given a proper $c$-colouring of the tree. Now there is a distributed algorithm that computes a proper $k$ colouring of the tree in $1$ synchronous communication round if and only if $c \leadsto k$.

The construction is optimal in the sense that $\binom{2n}{n}+1 \leadsto n$ cannot hold.  Indeed, it is easy to see that c-to-k coloring matrix exists if and only if there are c subsets A1, …, Ac of the set {1, …, k} such that no distinct i and j satisfy Ai ⊆ Aj.  (For the “only if” direction, take Ai = R(M, i) for a c-to-k coloring matrix M.  For the “if” direction, set mij ∈ Ai ∖ Aj.)  A family of sets none of which contains another is called a Sperner family, and it is Sperner’s theorem that the maximum number of sets in a Sperner family on the universe of size k is $\binom{k}{\lfloor k/2\rfloor}$.  This implies that $c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$.