Can type inference be classified in two groups: unification-based and control-flow-based?

Perhaps an even better way to see type inference is as a specialization of a single framework: Abstract Interpretation (abbreviated AI).  The hallmark of most unification-based type inference algorithms is that they generate the principal type for a term; translated into AI terms, this means that you never need to widen, nor do you need to go to power domains to find the answer.  Unification turns out to be the 'join' operation -- there is also a nice categorical interpretation of unification which is even more enlightening.

Several comments shed light on this as well: all algorithms can be better understood in terms of generating then solving systems of constraints.  Unification is indeed eager, and constraint-solving (and that includes control-flow based approaches) tend to be lazier.

Perhaps an even better way to see type inference is as an alternate interpreter for a program: rather than producing values, it produces types.  It is very easy to see type inference as a form a partial evaluation.  Perhaps an easy introduction to that circle of ideas is via Aaron Stump's A rewriting view of simple typing.


This exact question is answered in this paper: https://arxiv.org/abs/1807.01804


Here is one way to generate a Unique $k$-SAT instance, given a SAT instance $\varphi$ that you know is satisfiable.  Consider the formula $\psi(x)$ given by

$$\varphi(x) \land h(x)=y,$$

where $h$ is a hash function that maps an assignment $x$ to a $k$-bit value (for some small value of $k$), and $y$ is a random $k$-bit value.  If $\varphi$ has about $2^k$ satisfying assignments, then (heuristically) we assume that $\psi$ will have exactly one satisfying assignment (with constant probability).  We can test whether this is the case using a SAT solver (namely, test whether $\psi$ is satisfiable; if it is, and $x_0$ is one satisfying assignment, test whether $\psi(x) \land x \ne x_0$ is satisfiable).  If $k$ is not known, you can find $k$ using binary search or just by iterating over each candidate value $k=1,2,\dots,n$ (where $n$ is the number of boolean variables in $x$).

You can choose the hash function freely.  You'll probably want to make it as simple as possible.  One extremely simple construction is to have $h$ pick out a random subset of $k$ bits from $x$.  A slightly more sophisticated construction is to have the $i$th bit of $h(x)$ be the xor of two randomly chosen bits from $x$ (choosing a separate pair of bit positions for each $i$, independently).  Keeping $h$ simple will keep $\psi$ relatively simple.

This kind of transformation is sometimes used/suggested, as part of a scheme for estimating the number of satisfying assignments to a formula $\varphi$; I've adapted it for your particular need.

You can find many testbeds of SAT instances on the Internet, and you could apply this transformation to all of them, to obtain a collection of Unique $k$-SAT instances.

Another possibility would be to generate Unique $k$-SAT instances from cryptography.  For instance, suppose $f:\{0,1\}^n \to \{0,1\}^n$ is a cryptographic one-way permutation.  Let $x$ be a randomly chosen element of $\{0,1\}^n$, and let $y=f(x)$.  Then the formula $\varphi(x)$ given by $f(x)=y$ is a Unique $k$-SAT instance.  As another example, pick two large prime numbers $p,q$ randomly, and let $n=pq$.  Then the formula $\varphi(x,y)$ given by $x \cdot y = n \land x>1 \land y>1 \land x \le y$ (with the obvious correspondence between bit-strings and integers) is a Unique $k$-SAT instance.  However, these constructions do not seem like a useful way to benchmark or optimize your solver.  They all have a special structure, and there is no reason to believe that this structure is representative of real-world problems.  In particular, SAT instances drawn from cryptographic problems are known to be extremely hard, much harder than SAT instances drawn from many other real-world applications of SAT solvers, so they aren't a very good basis for benchmarking your solver.

In general, all of the techniques mentioned in this answer have the drawback that they generate Unique $k$-SAT instances with a particular structure, so they might not be what you are looking for -- or, at least, you might not want to rely solely upon formulae generated in this way.  A better approach would be to identify applications of Unique $k$-SAT (who do you think is going to use your solver, and for what purpose?), and then try to obtain some realistic examples from those application domains.

For a related topic, see also Generating interesting combinatorial optimization problems


Boolean formula balancing in $\mathsf{AC^0}$

I am not sure if this is very relevant but in Log-Space Algorithms for Paths and Matchings in k-Trees (building on a long history of past work and specifically on Arithmetizing classes around NC1 and L by Limaye-Mahajan-Rao) we show how to find recursive balanced separators for a tree in Logspace. This bound may very well be improvable to $\mathsf{NC}^1$ if the input tree is directly given in the string representation.

The basic idea is to represent the tree as a parenthesis expression and find balanced separators for these. Notice that we find leaf separators i.e. subtrees which are balanced w.r.t. number of leaves.


What logic correponds via Curry-Howard to a Monad?

The two papers to look at it are Benton, Bierman and de Paiva's Computational Types from a Logical Perspective, which directly gives a proof theory for Moggi's computational lambda-calculus; and Rowan Davies and Frank Pfenning's A Judgmental Reconstruction of Modal Logic, which gives a constructive proof theory for S4 modal logic with box and diamond, and then translates Moggi's metalanguage into it.

Both papers note that the axioms of a strong monad were originally introduced by Curry in 1952, which was independently re-invented by Fairtlough and Mendler as lax logic. Giving the action on types and contexts below, we see:

$$
\begin{array}{lcl}
( \to )^+ & =& ◻^+ \to ^+ \\
(◯)^+ & = & ◊◻^+ \\
^+ & =&  \;\;\mbox{for atomic}\;  \
\end{array}
$$

The translation of Davies and Pfenning is very similar to Gödel's embedding of intuitionistic logic into classical logic, and to Girard's embedding of intuitionistic logic into linear logic.


You can do this with SAT4J, simply by iterating over all models: http://www.sat4j.org/howto.php#models. I imagine that most SAT solvers have this ability.


The meaning of  simpler in your question is unclear. Kripke structures have a labelling function on states. LTSes have labels on transitions, which can be viewed as a labelling function on transitions. Why is one simpler than the other? In the context of your question, using acronyms like "ACTL" is ambiguous because the "A" could mean all paths or action-based.

The difference, in my opinion, between Kripke structures and LTSes is based on modelling convenience and not simplicity. There is a lot of work comparing and contrasting the two. Here are a few starting points for chasing down related work.

De Nicola and Vaandrager have a few papers on translating between Kripke structures and LTSes and how this affects logical properties. They introduce doubly labelled transition systems to move between the two types of representations and semantic interpretations.

Action versus state based logics for transition systems , De Nicola and Vaandrager, 1990

Three logics for branching bisimulation, De Nicola and Vaandrager, 1995
If the goal is verification of event-based systems, one option is to translate the LTS into a Kripke structure and use a Kripke structure model checker. The translation has to preserve the interpretation of CTL over the LTS.

An action-based framework for veryfying logical and behavioural properties of concurrent systems, De Nicola, Fantesi, Gnesi, Ristori
Translating between representations involves a blowup. For the case of LTL, there are cases when this blowup can be avoided. Here is a recent paper on the topic.

State/event-based software model checking, Chaki, Clarke, Ouaknine, Sharygina, Sinha


I will answer for the general setting. Assume a directed graph $G=(V, E)$ with costs as assumed in the question, that is the costs for entering a node depend on which edge it is left on and vice versa.

Let $v \in V$ arbitrarily; the following construction can be performed iteratively for all nodes in any order. Let $e_1, \dots, e_k \in (V \times \{v\}) \cap E$ (incoming edges) and $f_1, \dots, f_l \in  (\{v\} \times V)\cap E$ (outgoing edges).

Now create for all pairs of $e_i =: (u,v)$ and $f_j =: (v,x)$ a node $v_{ij}$ and edges $(u, v_{ij})$ as well as $(v_{ij}, x)$. Assign the costs as per the described model: costs for edge $(u, v_{ij})$ are the costs for entering $v$ from $u$ when leaving in direction of $x$; costs for edge $(v_{ij}, x)$ are the costs for leaving $v$ to $x$ when having come from $u$.

Add all thusly created $v_{ij}$ and their incident edges to $G$ and remove $v$ and its incident edges from it. Iterate for all nodes.

The resulting graph has $\mathcal{O}(|E|\cdot d^2)$ many edges ad $\mathcal{O}(|V| \cdot d^2)$ many nodes, $d$ the maximum node degree in $G$. It can be reduced by merging (or not splitting) those combinations that have the same costs.

The original problem is equivalent to finding a path with exactly one from each $\{v_{ij} \mid v \in V \}$.


Looking for easy applications of fractional cascading

Chazelle and Guibas wrote a paper describing some of the good applications that can be made with Fractional Cascading: Link

Some of the most interesting applications are:

Intersection of a polygonal path $P$ and a line. Given the path $P$, pre-process it and allow queries of the form: Given a line $l$, report all the intersections of $P$ and $l$.
Orthogonal Range Search. Given points in $R^d$, and a $d$-orthotope. Return the points that lie in the orthotope.
Planar point Location. Locate a point in a planar subdivision.

You do have to give a bit more background as this problems tend to be geometrical in nature. Fractional Cascading is really only good when tackling higher dimensional problems.


1)$\bf FNP$ is contained in $\bf FPH$, which is called the "functional polynomial hierarchy", where every function in $\bf FPH$  is polynomial time 1-Turing reduciable to some function in $\bf \#P$.
2)We know from the Valiant Vazirani theorem that $\bf NP$ $\subseteq$ $\bf RP^{PromiseUP}$. We also know that $\bf UP$ $\subseteq$ $\bf \oplus P$. Therefore, we have $\bf NP$ $\subseteq$ $\bf RP^{\bf \oplus P}$.


Classical Matrix-Vector multiplication Complexity of standard matrices

Essentially, your are asking why people believe that DFT or DHT do not have linear size arithmetic circuits. First, researcher tried to find such circuits for decades but did not succeed. Second, there are superlinear lower bounds (Morgenstern's theorem, see the book by Bürgisser, Clausen, Shokrollahi) in restricted models. From Morgenstern's theorem, in follows that in linear arithmetic circuits of linear size over the complex numbers  for the DFT, the absolute values of the constants used in the circuit go to infinity as $n$ goes to infinity.


The Problem:

Input: $\;\;$ a tuple that parses as $\:\langle \hspace{.04 in}p,\hspace{-0.03 in}y,\hspace{-0.03 in}i\hspace{.02 in}\rangle$

Output:

if $p$ is prime and $y$ is a quadratic residue modulo $p$, $\;$ then the $\hspace{.02 in}i\hspace{.03 in}$th$\hspace{.01 in}$ bit of the

non-negative integer $x$ that satisfies $\;\;\; x^{\hspace{.02 in}2} \equiv y \; \pmod p\;\;\;$ and $\;\; 2\hspace{-0.04 in}\cdot \hspace{-0.04 in}x \: \leq \: p \;\;$,

else 0

According to the wiki article, that problem is in ZPP but is not known to be in P.


What are those deterministic algorithms for k-SAT that are not derandomization of random algorithms like PPSZ and Schöning's local search?

If I may interpret your question as a reference request: Donald Knuth recently finished the part of TAOCP that deals with satisfiability:

Donald E. Knuth, The Art of Computer Programming, Volume 4 Fascicle 6, Satisfiability (2015), xiii+310pp. ISBN 978-0-13-439760-3.

Although I did not work through it yet (no pun intended), it is well known that Don Knuth usually puts a clear emphasis on the structure of the different algorithmic approaches, and he gives a very detailed account on the history of ideas. My bet is that you'll find the answer to your question in the fascicle. (Maybe someone else who is more knowledgeable about SAT can give a less indirect answer )


How to start learning formal language theory

Theory of computation by M. Sipser is interesting per se. For introduction you have to practice and go in following sequence.

Regular language and automata
Context free grammar and expressions
Pushdown automata
Non context free grammar
Lr(k) grammar
Turing Machines

If interest level drops keep reading a fun book
https://en.wikipedia.org/wiki/A_New_Kind_of_Science


You can refer Roger Wattenhofer's Lecture note on PODC.

Here I mentioned some other courses on distributed algorithms.


Is this greedy algorithm for vertex cover studied before?

Unfortunately, the algorithm can be arbitrarily bad.  In the following example, each vertex $u_i$ has $d$ disjoint neighbors, of which only four are drawn. The optimal solution is $\{u_1, \ldots, u_p, w_1, \ldots, w_d\}$, while the greedy algorithm returns its complement.  The ratio is $\frac{d p}{p + d} \approx d$ with $p\to 0$.


Is Isomorphism of bounded degree hyper-graphs in P?

It depends on whether the uniformity of your hypergraphs is bounded.

Bounded uniformity In this case, you can represent each hypergraph with a colored bipartite graph which has vertices on one side (colored blue) and hyperedges on the other side (colored red). A vertex and a hyperedge are connected if the hyperedge connects the vertex. We can get rid of the colors in any number of ways, for example attach to each red a vertex a very long path which will force any isomorphism between two such graphs to match vertex colors. These graphs have bounded degree, and so GI for this class of graphs is in P.

Unbounded uniformity In this case the problem is GI-complete. Given a graph $G$, create a bounded degree hypergraph whose vertices are the edges of $G$ and whose hyperedges correspond to vertices of $G$; a hyperedge contains a vertex if the corresponding vertex of $G$ belongs to the corresponding edge of $G$. This hypergraph has maximum degree 2. Two graphs are isomorphic if and only if the corresponding hypergraphs are isomorphic (this requires some argument but seems correct).


How to translate the axiom schema of induction by Curry-Howard?

First a correction. The statement
$$\forall P \,.\, (P(0) \Rightarrow (\forall n . P(n) \Rightarrow P(S n)) \Rightarrow \forall m . P(m)),$$
is not the schema of induction, but rather induction written in second-order arithmetic.
To get the schema you need to avoid $\forall P$. This is done by saying that there are infinitely many axioms of the form
$$P(0) \Rightarrow (\forall n . P(n) \Rightarrow P(S n)) \Rightarrow \forall m . P(m),$$
one for each formula $P(x)$. That is, whereas in your axiom $P$ refers to arbitrary subsets of $\mathbb{N}$, in the schema it refers to sytnactic entities, namely formulas with parameter $x$. It is called a "schema" because it prescribes a shape from which infinitely many axioms may be generated by plugging in all possible syntactic entities $P$.

To answer your question, we just have to look at the Curry-Howard correspondence to see what a predicate $P(x)$ correspond to. The answer is type family or dependent type. Because you wrote your axiom in second-order arithmetic, it became unclear how to quantify over dependent types. This is possible by using universes, for instance Daimano in his answer used $\mathsf{Prop}$, the universe of propositions. However, under the pure Curry-Howard there is no $\mathsf{Prop}$, there are only types.

We have two options. If we translate the schema, then it is this: for every dependent type $$x : \mathbb{N} \vdash P(x) \, \mathsf{type}$$ we get the type
$$\textstyle P(0) \to (\prod_{n:\mathbb{N}} P(n) \to P(S n)) \to \prod_{m:\mathbb{N}} P(m)$$
If we translate the second-order formulation of induction, we need to use a type universe $\mathsf{Type}$, and then we get
$$\textstyle
\prod_{P : \mathbb{N} \to \mathsf{Type}}
P(0) \to (\prod_{n:\mathbb{N}} P(n) \to P(S n)) \to \prod_{m:\mathbb{N}} P(m)$$

What are these types inhabited by? In the case of schema, they are inhabited by primitive recursors $\mathsf{rec}_P$ which satisfy the equations
\begin{align*}
\mathsf{rec}_P \; z \; f \; 0 &= z \\
\mathsf{rec}_P \; z \; f \; (S n) &= f \; n \; (\mathsf{rec}_P \; z \; f \; n)
\end{align*}
Depending on the details of your formalism we may be able to drop the subscript $P$ on $\mathsf{rec}_P$, and just write $\mathsf{rec}$ -- but secretly there is a different $\mathsf{rec}$ for each $P$.

In the case of the second-order induction we would get a single primitive recursor $\mathsf{rec}$ satisfying
\begin{align*}
\mathsf{rec} \; P \; z \; f \; 0 &= z \\
\mathsf{rec} \; P \; z \; f \; (S n) &= f \; n \; (\mathsf{rec} \;P \; z \; f \; n)
\end{align*}

If I spoke to a Haskell programmer I would say that in the case of schema each $\mathsf{rec}$ was obtained from $P$ using a "deriving" clause, whereas in the second-order case there is a single polymorphic $\mathsf{rec}$.


Is Kolmogorov complexity quasi-surjective?

Suppose $L_0$ is an essentially-optimal description language, and consider the identity function, which is a computable partial function from $\{0,1\}^*$ to itself. According to the definition, there is a computable function $f$ and a constant $C$ such that $|f(x)| \leq |x| + C$ and $L_0(f(x)) = x$.

Take now a Kolmogorov random string $x$ of length $n$. On the one hand, $K(x) \geq n$. On the other hand, we have seen above that $K(x) \leq n + C$.


Are linear feedback shift registers being generally discouraged by cryptologists?

There are many types of cryptanalytic attacks: Linear approximations, Algebraic attacks, Time-memory-data-tradeoff attacks, fault attacks.

For example you can read the survey: "Algebraic Attacks On Stream Ciphers (Survey)"

Abstract: Most stream ciphers based on linear feedback shift registers (LFSR)
are vulnerable to recent algebraic attacks. In this survey paper, we describe
generic attacks: existence of algebraic equations and fast algebraic attacks. ...

At the end you can find other relevant references.

Another good paper about fault attacks to stream ciphers is: "Fault Analysis of Stream Ciphers"

Abstract: ... Our goal in this paper is to develop general techniques which can be used to attack the standard constructions of stream ciphers based on LFSR’s, as well as more specialized techniques which can be used against specific stream ciphers such as RC4, LILI-128 and SOBERt32. While most of the schemes can be successfully attacked, we point out several interesting open problems such as an attack on FSM filtered constructions and the analysis of high Hamming weight faults in LFSR’s.

For time-memory-data tradeoffs attacks you can read: "Cryptanalytic Time/Memory/Data tradeoffs for stream ciphers".


Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture

Here's just a couple of observations I couldn't fit in a comment:

0) Added because the first answer was deleted: there is an interpretation of $H_n$, namely, indexing the rows and columns by $\{0,1\}^n$, the entry corresponding to $(x,y)$ is $1$ if the Hadamard product $x\odot y=(x_1y_1,\ldots,x_n y_n)$ has even parity, and $-1$ if it has odd parity.

1) In general, the spectrum of block matrices can be very complicated and not obviously related to the spectra of the individual blocks, as the characteristic polynomial will look awful. But for a symmetric block matrix $M=\begin{pmatrix} A & B\\ B^T & C\end{pmatrix}$ that might arise via a recursive construction like the $A_n$ and $H_n$ above, where each matrix is square, one of the only simplifications occurs when $B^T$ and $C$ commute, in which case one has $\det(M)=\det(AC-BB^T)$. Then the characteristic polynomial of $M$ will be $$\det((\lambda I-A)(\lambda I-C)-BB^T)=\det(\lambda^2I-\lambda (A+C)+AC-BB^T).$$
For this to lead to nice recursive formulas for the eigenvalues, one basically needs $C=-A$ to kill the linear $\lambda$ term. If further $A$ and $B$ are symmetric and commute, we get
$$
\det(\lambda I-M)=\det(\lambda^2 I-(A^2+B^2)),
$$
from which one easily reads off the eigenvalues using the fact symmetric commuting matrices admit a common eigenbasis. This might be obvious, but all of this is to say that as far as getting good, recursive formulas for the eigenvalues, it is basically essential to require the lower right block to be $-A$ and hope that lower left and upper right blocks are symmetric and commute with $A$, which is the case for the $A_n$ (with $B=I$) and $H_n$ matrices (with $B=H_{n-1}=A$).

2) On the random sign question: the signing of the adjacency matrix given in the paper is optimal in the sense of maximizing $\lambda_{2^{n-1}}$, which is needed for the lower bound via Cauchy interlacing, and can be seen from elementary means. For an arbitrary signing $M_n$ of the adjacency matrix of the $n$-dimensional hypercube, one immediately gets
$$
\text{Tr}(M_n)=\sum_{i=1}^{2^n} \lambda_i(M_n)=0,\quad \text{Tr}(M_n^2)=\sum_{i=1}^{2^n} \lambda_i(M_n)^2=\|M_n\|_F^2=n2^n,
$$
where $\lambda_1(M_n)\geq \lambda_2(M_n)\geq\ldots\geq \lambda_{2^n}(M_n)$. If for some signing $M_n$ one has $\lambda_{2^{n-1}}(M_n)>\sqrt{n}$, then
$$
\sum_{i=1}^{2^{n-1}} \lambda_i(M_n)>\sqrt{n}2^{n-1},\quad \sum_{i=1}^{2^{n-1}} \lambda_i(M_n)^2>n2^{n-1}.
$$
One can then see it is not possible to satisfy the trace equalities above: the negative eigenvalues must sum to strictly more than $\sqrt{n}2^{n-1}$ (in absolute value), and their squares must sum to strictly less than $n2^{n-1}$. Minimizing the sum of squares while keeping the sum constant happens when they are all equal, but in this case will make the sum of squares too large anyway. So for any signing, one can see via elementary means that $\lambda_{2^{n-1}}(M_n)\leq \sqrt{n}$ without knowing the magic signing in the paper, where equality holds iff the values are $\sqrt{n},\ldots,\sqrt{n},-\sqrt{n},\ldots,-\sqrt{n}$. That there actually exists such a signing attaining it is pretty amazing. The eigenvalues of the normal adjacency matrix are $-n, -n+2,\ldots,n-2,n$, where the $i$th eigenvalue has multiplicity ${n\choose i }$, so it's very interesting (to me, anyway) how the all-$+1$ signing maximizes $\lambda_1$, while this signing maximizes $\lambda_{2^{n-1}}$.

As far as would a random signing work, it's harder to say because I think most non-asymptotic bounds on eigenvalues focus on spectral norm. One expects random signings to smooth out the extreme usual eigenvalues, and indeed, using the noncommutative Khintchine inequality and/or recent tighter bounds like in here, a uniformly random signing has $\mathbb{E}[\|M_n\|_2]=\Theta(\sqrt{n})$. It's hard for me to imagine the middle eigenvalues would be on a similar polynomial order as the leading one in expectation (and asymptotic results like the semi-circular law for different matrix ensembles suggest similarly, I think), but maybe it's possible.


I received an email last February from a Spanish undergraduate, Nil Mamano, with a proof that this problem is indeed NP-complete, by reduction from Hamiltonian path in grid graphs. I don't know that it has been published anywhere yet. The reduction replaces each vertex of the grid graph by a 2x2 block of 1's, and each edge, face, or missing vertex by a 2x2 block of 0's. The input sequence alternates between subsequences of four 1's and four 0's for as many times as is needed to cover all the vertices, then fills out the rest of the sequence with 0's. To match the input sequence, a path through the grid must align the subsequences of four 1's with the 2x2 blocks of 1's from the reduction, forming a Hamiltonian path; if such a path exists, it's always possible to do this in a way that allows the rest of the matrix to be covered by the remaining zeros at the end of the sequence.


Maximum common subgraph of two planar graphs of bounded degree k

Maybe I misunderstood the question, but it seems it's NPC and this is trivial. Finding hamiltonian cycle in planar graphs of max degree $3$ is NPC. Therefore this problem is also NPC (input: A planar graph of max degree $3$ on $n$ vertices and a cycle on $n$ vertex.


At the level of precision used in the nlab page, values are global elements -- i.e., a value of type $A$ corresponds to a morphism $1 \to A$.

If you want to be serious about this, there are some technicalities to account for:

First, actual Haskell does not actually form a category in the sense that we would hope -- the seq operator breaks a lot of the program equivalences we need. However, if it were removed, then the pure fragment of Haskell would form a category (basically corresponding to the category of domains and continuous functions).
However, global elements in "Hask" (how I hate this terminology!) are not precisely values, since the nonterminating computation is an inhabitant of every type, and so for every type $A$ there is a map $\mathsf{loop}_A : 1 \to A$ which just runs forever.

If you want to distinguish between values and nonterminating computations, then you need a somewhat more complicated setup, corresponding to the models of Paul Blain Levy's call-by-push-value.

There, you work with two categories -- one, a category of values, and the other, a category of computations, with an adjunction which gives you two functors, one embedding values into computations and the other embedding computations into values.


What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

This is an (interesting) open problem, as far as I know. Rahul Santhanam and I explicitly mention the problem of proving Permanent is not in LOGSPACE-uniform TC0 in our CCC'13 paper (On Medium-Uniformity and Circuit Lower Bounds).


Strongly normalizing type theory beyond induction-recursion

Yes. System F is probably the simplest example. As far as I know, you can’t prove normalisation for it in a dependent type theory with induction-recursion — you need at least impredicative prop to do so.


Number of equivalence classes in regular languages as a function of DFA size

Answer to Question 1,

  What is the smallest $n$ for which $|T/{\sim}|=|T|$?

We have $$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x)$$
where $\mathrm{sep}(w,x)$ is the smallest number of states in any DFA that accepts one of $w$ and $x$, but not the other.
The best known upper bound on $n$ is then (see some slides by Jeffrey Shallit)

  $n=O(s^{2/5}(\log s)^{3/5})$.

which was obtained in

Robson, J. M., Separating strings with small automata, Inf. Process. Lett. 30, No. 4, 209-214 (1989). ZBL0666.68051.


Minimum offset while measuring TSP paths

It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known.

Let us assume that a Euclidean TSP instance is given by a collection of points in $(\mathbb{Z} \cap [-N, N])^2$ (i.e. points with integer coordinates bounded in absolute value by $N$). It is not known how to decide the following problem in polynomial time: given two tours $T_1$, $T_2$ over the same set of points, is the cost $c(T_1)$ of $T_1$ less than the cost $c(T_2)$ of $T_2$. To solve this problem it is sufficient to upper bound $-\log |c(T_1) - c(T_2)|$ by a polynomial in n and $\log N$, which is equivalent to your question.

The even more basic problem of deciding if $\sum_{i = 1}^n{\sqrt{a_i}} < \sum_{i = 1}^n{\sqrt{b_i}}$, for $a_i, b_i \in \mathbb{Z} \cap [1, N]$ (i.e. positive integers bounded by $N$) in time polynomial in $n$ and $\log N$ is also open, see http://cs.smith.edu/~orourke/TOPP/P33.html.

If all distances between points are rational, i.e. $\|v_i - v_j\| = a_{i,j}/b_{i,j}$ for integers $a_{ij}$, $b_{i,j}$, then
$$
|c(T_1) - c(T_2)| >= \frac{1}{\text{LCM}(\{b_{i,j}\}_{i, j \in [n]})},
$$
where LCM is the least common multiple function.


For company $A$/the firm/giant corporation/"big pharma"/"THE MAN", the strategy does not change from the symmetric version:

Consider a round where the probability of seeing only lesser candidates thereafter is $> .5$.  If company $A$ keeps the candidate, then it has a chance of winning $> .5$.  If $A$ does not keep the candidate, then company $B$ can hire the candidate and company $A$ has a chance of winning $< .5$.  So, obviously, company $A$ would hire (and company $B$ would attempt to hire) in this situation.

For a candidate with winning odds of exactly $.5$, $A$ may or may not choose to hire, but $B$ would choose to hire because $B$ can never get odds better than $.5$.

If company $A$ hired before it saw a candidate with winning chance $>= .5$, then the odds of a better future candidate existing (and hence $B$ winning) would be $> .5$.  So $A$ will not hire until it sees a candidate of winning odds $>= .5$.

Therefore, $A$'s strategy is identical to the symmetric case: hire the first candidate that yields winning odds of $> .5$.

$B$'s strategy, then, is formed with $A$'s strategy in mind.  Obviously, if $A$ hires (at or) before $B$, then $B$'s strategy is to hire the next candidate that is better than $A$'s, if any.  Also, if a candidate comes by with winning odds $> .5$, $B$ should try to hire, even though $A$ will also try to hire (and force $B$ to keep looking).

The only question left is: is it ever beneficial for $B$ to hire when the odds of winning is $<= .5$.  The answer is: yes.

Intuitively, say there is a round where the odds of winning with the candidate is $.5 - \epsilon$.  Also, there is "likely to be" (explained later) a future candidate with winning odds $> .5 + \epsilon$.  Then it would benefit $B$ to choose the earlier candidate.

Let $d_r$ be the candidate interviewing in round $r$ for all $1 <= r <= N$.

Officially, $B$'s strategy is: "hire $d_r$ if doing so yields better odds of winning than if not".  The following is how we calculate such a decision.

Let $p_{r,i}$ be the probability of winning after interviewing and hiring $d_r$ given $d_r$ is the $i$th best interviewed candidate.  Then:

$p_{r,i} = $ probability that $d_s < d_r$ for $s > r$

$ = (1-\frac{i}{r+1})(1-\frac{i}{r+2})\times ... \times (1-\frac{i}{N})$

...

$ = \frac{(N-i)!r!}{(r-i)!N!}$

Notably, $p_{r,i}$ is easily computable to constant accuracy.

Let $P_{B,r}$ be the probability that $B$ wins given that neither company hired in rounds $1$ through $r-1$.

Then $B$ would hire $d_r$ if the probability of winning after hiring $d_r$ is better than $P_{B,r+1}$.

Note that $P_{B,N} = 0$, because if it is the last round, then $A$ is guaranteed to hire and $B$ will not hire anyone and loose.

Then, in round $N-1$, $B$ is guaranteed to try to hire and will succeed unless $A$ hires as well.  So:
$$
P_{B,N-1} = \sum_{i=1}^{N-1}\frac{1}{N-1}
\left\{
\begin{array}{lcl}
p_{N-1,i}   & : & p_{N-1,i} < .5 \\
1-p_{N-1,i} & : & p_{N-1,i} >= .5
\end{array}
\right.
$$

Which leads to the recursive function:

$$
P_{B,r} = \sum_{i=1}^{r}\frac{1}{r}
\left\{
\begin{array}{lcl}
1-p_{r,i} & : & p_{r,i} >= .5 \\
p_{r,i}   & : & P_{B,r+1} < p_{r,i} < .5 \\
P_{B,r+1} & : & \text{else}
\end{array}
\right.
$$

It's pretty obvious that $P_{B,r}$ can be calculated to constant accuracy in polynomial time.  The final question is: "what is the probability of $B$ winning?"  The answer is $P_{B,1}$ and varies with $N$.

As to the question of how often does $B$ win?  I have not calculated exactly, but looking at $N$ from 1 to 100, it appears that as $N$ grows, that $B$'s winning rate approaches .4 or so.  This result may be off as I just did a quick python script to check and did not pay close attention to rounding errors with floating numbers.  It may very well end up that the real hard limit is .5.


How to define eta-equivalence for F-omega types?

The first approach is subsumed by the second, sort of (because the first approach is slightly broken).

One should never consider expressions with free variables without explicitly specifying a context in which they appear (this is a lesson one learns as soon as one wants to formalize $\forall$ and $\exists$ that are allowed to range over possibly empty types or sets).

In a single-sorted theory, equations without context $t_1 = t_2$ can always be equipped with a context $\Gamma \vdash t_1 = t_2 : S$ where $S$ is the single sort and $\Gamma = x_1 : S, \ldots, x_n : S$, with $x_i$ being the free variables in $t_1$ and $t_2$.

Leaving the context implicit like that is not quite right. For example, what if I want to write down an equation that involves $x_1$ and $x_2$ in a context which also mentions $x_3$? You might think that sort of thing is going to be useless, but it isn't, not if $x_3$ could come from an empty type.

Also, as soon as you think about categorical semantics you will see that it makes little sense to have bare equations without contexts.

So I would advise you to put your equations in contexts, and then use the shorter form as an abbreviation. One reference where everything is done explicitly in a context all the time is Bart Jacob's "Categorical Logic and Type Theory", Chapter 8 is about polymorphic type theory and might be of particular interest to you.


Template Metaprogramming and Turing Completeness

The article you want is C++ Templates are Turing Complete by Todd Verhuizen. It explains how things work in sufficient details. If you can faithfully encode a Turing machine and its behaviour in C++ templates, then this is sufficient to demonstrate Turing completeness.


Finding the identity with permutation chains

Just a note: if the $K$ permutations can be arbitrary, and if you want to find the shortest possible solution, a quick reduction from the Pancake flipping problem shows that finding the shortest possible sequence is NP-hard.

The reduction: Given an instance of the Pancake flipping (i.e. a permutation of $[1..n]$), add to the list the $K = n$ possible prefix permutations.
The application of a $P_i$ corresponds to a pancake flip, and $U$ of them can generate the identity permutation if and only if the pancake of the original problem can be sorted using $U$ flips.

However, this doesn't apply directly to the problem as you stated it.  If we don't need the shortest possible solution, it's easy to find a solution of length $O(n)$ to the pancake flipping problem.  Since this question asked for any solution (rather than the shortest possible solution), there's no proof that this problem is NP-hard.


How to show that ECTL* is more expressive than CTL* $\cup$ Büchi (with an example)

I think the simpler example is your property, which can be written for instance $E(((a+b)a)^\omega))$.
A simple way to show that is is not in CTL* is to show that this would imply that the word language $((a+b)a)^\omega$ is in LTL (because CTL* on linear structures is LTL).

This fact is a classical result.
To show it, it suffices (for instance) to use the theorem stating LTL<=>aperiodic $\omega$-semigroup. So we just need to compute the minimal $\omega$-semigroup of this language, and observe that it contains the group $\mathbb{Z}/2\mathbb{Z}$, so it is not aperiodic.


What are the parameters that one should look for?
Number and quality of the faculty working in your area of choice or related areas, ease of finding an advisor, opportunities to collaborate with different people in the program, how well funded the program is, quality of the students, how successful are graduates in finding jobs/positions that you would be interested in after graduating, etc.
What are credible sources other than institute website/provided materials to get information about the course or program?
Other students in the program are one of the best sources of information. Most schools should have an Open House for admitted students. Highly recommend you go to them.
Do brand names really matter? (As in if you had to choose between one with a global and better brand name and other with a strong research focus)
The story I've heard is that brand names matter in the sense that you'll likely find an excellent and diverse faculty body making it easier to find an advisor and do good work in your field. In addition, on average, the quality of students at such universities is likely to be higher which can be important as at least in my experience, I tend to learn a lot from my peers and work harder if people around me are working hard too.
You'll also have an easier time getting a good CS job and can also help when looking for a postdoc/faculty position if only because it would be easier to collaborate with a well known faculty member who could write you a great rec.


Reducing threshold questions to finiteness questions

Sipser proved that no infinite parity can be computed by an (infinite) circuit of any constant depth, which you can view as a warm-up to the result that PARITY is not in $AC^0$.

There are also some results and attempts at proofs of lower bounds in proof complexity using nonstandard models (some results of Ajtai and Krajicek. See esp. Krajiceks' "Forcing with Random Variables and Proof Complexity," available from Cambridge Press, but also a draft available online) . The basic idea is to build a nonstandard model of arithmetic in which a statement is false in the model (rather than "true, but without short proofs"), and then, from the properties of the model, infer that a corresponding sequence of finite statements does not have polynomial-size proofs in some proof system.

I'm not sure, but my impression is that often these results sort of "hide the asymptotics under the hood" so that it's not so much a reduction from threshold to finiteness as it is a new mathematical language in which "false" in the new language corresponds to "without short proofs" in the old language. That's not to say that the new language doesn't provide a useful new viewpoint, but I'm not quite sure if it's what you're looking for.


I don't know if there is a suitable approximation algorithm for this problem, but I can provide a counter-example for your heuristic algorithm:
Assume G has 2*n vertices with weights
$$W(v_i) = w - \epsilon * i$$
Which in your algorithm will be sorted by this order:
$$v_1, v_2, ... v_{2n}$$
And there's an edge between $v_i$ and $v_j$ iff $\exists k : i-j = 2*k$
The resulting graph is the union of 2 cliques with size n
The algorithm alternates between these two, which means in every step a clique with exactly one vertex will be returned, yielding a final answer with weight:
$$2*n*w - \epsilon * n * (2*n+1)$$
But we know that the optimum weight is just $2*w - 3*\epsilon$
So the approximation factor can be as big as $n/2$ (assuming that the graph has $n$ vertices) which is not very interesting because the obvious algorithm "Pick each vertex as a clique" has an approximation factor of $n$


Oncina-Garcia RPNI algorithm for learning DFAs

The algorithm is named RPNI, not RNPI.

Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., minimal) DFA for that language. If the generating language is not regular, the automaton may grow unboundedly with the set of inputs.

Since the algorithm merges states, the output automaton has at most |p| states. Therefore, the output is bounded by the sum of input lengths in p.

A proof appears in "Inferring regular languages in polynomial update time".
There are more details about the algorithm in the "Grammatical Inference" book by Colin de La Higuera.


Let $A_k$ be the inverse of $\alpha_k$. $A_1(x) = 2x, A_2(x) = 2^x, \dots$. I claim that $k^{-1}(x) = A_x(x)$.

Since $x = \alpha_x(A_x(x))$, and since $\forall z, \alpha_y(z) > \alpha_x(z)$, $\alpha_y(A_x(x)) > \alpha_x(A_x(x)) = x$. As a result $k(A_x(x)) = x$.

Now consider the value of $\alpha(k^{-1}(n)) = \alpha(A_n(n))$. By definition of $\alpha$, this is $\min_z \{\alpha_z(A_n(n)) \leq 3\}$. We know that $\alpha_n(A_n(n)) = n$, so $\alpha(A_n(n)) > n$. I claim that $\alpha(A_n(n)) \leq n+2$. $\alpha_{n+1}(A_n(n)) = 1+\alpha_{n+1}(n)$. Now $\alpha(n) = \min_z\{\alpha_z(n) \leq 3\}$, so $\alpha_{\alpha(n)}(n) \leq 3$. Since $n+1 > \alpha(n)$, $\alpha_{n+1}(n) \leq 3$, so $\alpha_{n+1}(A_n(n)) \leq 4$. Thus, $\alpha_{n+2}(A_n(n)) = 1 + \alpha_{n+2}(\alpha_{n+1}(n)) \leq 1 + \alpha_{n+2}(4) \leq 3$.

So, we have $n < \alpha(k^{-1}(n)) \leq n+2$, so $k$ and $\alpha$ are essentially equal.


Some problems about arrow's theorem and social choice

Unanimity and transitivity do no imply IIA.

For example, consider the Borda-count voting mechanism. There is an example of the violation of IIA here.


Notable examples of the square root idea in complexity analysis

There are $O(m^{3/2})$ triangles in any $m$-edge graph and that they can be found in $O(m^{3/2})$ time. There are many ways of doing this but I think one of the earliest is Itai and Rodeh (STOC 1977) who provide an algorithm that goes through a sequence of linear-time iterations, each of which removes a spanning forest from the graph. In the early iterations when the remaining forest has at least $n-k$ components, the algorithm removes at least $k$ edges per step, and in the late iterations when it has at most $n-k$ components, the maximum degree is $k$ and shrinks by at least one in each step. So the total number of iterations is at most $m/k+k$ and choosing the right tradeoff gives the overall bound of $O(\sqrt m)$ on iterations and $O(m^{3/2})$ on time.


Reference for Dudley's chaining integral

I think the proper reference is:

@article{Dudley1967290,
    Author = {R.M Dudley},
    Doi = {http://dx.doi.org/10.1016/0022-1236(67)90017-1},
    Issn = {0022-1236},
    Journal = {Journal of Functional Analysis},
    Number = {3},
    Pages = {290 - 330},
    Title = {The sizes of compact subsets of Hilbert space and continuity of Gaussian processes},
    Url = {http://www.sciencedirect.com/science/article/pii/0022123667900171},
    Volume = {1},
    Year = {1967},
    Bdsk-Url-1 = {http://www.sciencedirect.com/science/article/pii/0022123667900171},
    Bdsk-Url-2 = {http://dx.doi.org/10.1016/0022-1236(67)90017-1}}

See Theorem 3.1. for the relevant result, although stated in terms of continuity of Gaussian processes.


The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound $m+n$.
In the case of $(s,t)$-flows, we may note that during decomposition the nodes $s$ and $t$ becomes balanced at the same time. This gives the already the bound $m+1$ on the number of paths and cycles. If we look at the flow decomposition, when finding the final path flow (this is where the balance of $s$ and $t$ becomes balanced), if no flow on some arc is made 0, it means that we will still find a cycle flow. Now the final cycle flow will make at least two arcs have flow 0 at the same time. This sharpens the bound to $m$ in case of $(s,t)$-flows.
P.S. The proofs of the notes you link are not quite correct, see the comments.


resolution based theorem prover for temporal logic

Your translation goes into Presburger arithmetic, which is decidable.

You could take your translated formula, do quantifier elimination on it, and then hand it over to a proof-producing SMT solver. Since pretty much all SMT solvers are (fancy extensions of) DPLL, I would guess you can turn those proofs into resolution proofs without too much difficulty.

I'm pretty sure that CVC4 can directly give you the resolution proofs, and would be surprised if Z3 couldn't.


$L_\mathcal{D}(A(S)) \le 0.1$ with prob at least $0.9$ implies PAC learnability

The end of the proof of Theorem 7.2 explicitly states "Using the fundamental theorem of statistical learning, this implies that the VC dimension of $\mathcal{H}_n$ must be finite, and therefore $\mathcal{H}_n$ is agnostic PAC learnable."
Now, this is confusing, since looking at this "fundamental theorem of statistical learning" (Theorem 6.7 in this book), it looks like we want to use the implication $(4) \Rightarrow (6)$, namely PAC learnability implies finite VC dimension. But, as you point out, instead of PAC learnability we only have the seemingly weaker guarantee you wrote:

With probability at least $6/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S))\leq 1/8$

using the notation of the book. However, if you look at the proof of Theorem 6.7, $(4) \Rightarrow (6)$ follows from the No-Free-Lunch theorem (Theorem 5.1), or rather its implication in terms of VC dimension (Corollary 6.4, and then Theorem 6.6). I'll let you check the details, but essentially it proves the stronger-looking statement you need:

Let $\mathcal{H}$ be a class of infinite VC dimension. Then, for every $m$, and every learning algorithm $A$, there exists a distribution $\mathcal{D}$ and a predictor $h\in\mathcal{H}$ such that (i) $L_{\mathcal{D}}(h) = 0$; but (ii) with probability at least $1/7$ over $S\sim \mathcal{D}^m$ we have $L_{\mathcal{D}}(A(S)) > 1/8$.


I think there may be multiple instances of such graphs. One pathological case that can be constructed is as follows

Consider three disjoint vertex sets S,T,O. S is a single vertex of degree d+1 with all of edges going into the set O, i.e. there are no edges between S and T. Let O be a very large set and let the edges inside O be such that O is a clique. Now the idea is that we will set edges such that T has smaller expansion than S but T will have greater sparsity. So essentially such that S is the smallest sparsity set and T is the smallest expansion. Set up edges such that T is a clique and every vertex in T has d edges going into O. Suppose that |O| and |T| >> d

Now clearly T is the set with smallest expansion (of expansion d) (this is not hard to see because subsets of T and O have a lot of edges going out). Once again the smallest sparsity sets would be either T or S. Sparsity of S = d+1 / |O| + |T| and Sparsity of T = d / |O| + 1 . Given our chosen set of parameters. Sparsity of T > Sparsity of S


What is the theoretical basis of imperative programming?

In general, when mathematics is used to study some X, one first needs a model of X, and then develops a theory, a set of results about that model. I guess that theory may be said to be a "theoretical basis" for X. Now set X=computation. There are many models of computation, many involving "state". Each model has its own "theory" and it is sometimes possible to "translate" between models. I believe it's hard to say which model is more "basic"---they are simply designed with different goals in mind.

Turing machines were designed to define what is computable. So they make a good model if you care about whether there exists an algorithm for a certain problem. This model is sometimes abused to study the efficiency of algorithms or the hardness of problems, under the pretext that it's good enough, at least if you only care about polynomial/non-polynomial. The RAM model is closer to a real computer and therefore better if you want a precise analysis of an algorithm. To put lower bounds on the hardness of problems it is better to not use a model that resembles too much today's computers because you want to cover a wide range of possible computers, while still being more precise than just polynomial/non-polynomial. In this context, I saw for example the cell-probe model used.

If you care about correctness, then still other models are useful. Here you have operational semantics (which I'd say is the analogue of lambda calculus for statefull computations), axiomatic semantics (developed in 1969 by Hoare based on Floyd's inductive assertions from 1967, which are popularized by Knuth in The Art of Computer Programming, volume 1), and others.

To summarize, I think you are after models of computation. There are many such models, developed with various goals in minds, and many have state, so they correspond to imperative programming. If you want to know if something can be computed, then look at Turing machines. If you care about efficiency look at RAM models. If you care about correctness look at models that end in "semantics", such as operational semantics.

Finally, let me mention that there is a big book online only about Models of Computation by John Savage. It is mostly about efficiency. For the correctness part I recommend you start with the classic papers of Floyd (1967), Hoare (1969), Dijkstra (1975), and Plotkin (1981). They are all pretty cool.


Balls and Bins analysis in the m >> n regime.

Not really a full answer (nor a useful reference), but just a rather an extended comment. For any given bin, the probability of having exactly $B$ balls in the bin will be given by $p_B = \binom{m}{B} \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$. We can use an inequality due to Sondow, $\binom{(b+1)a}{a}<\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$, to yield $p_B < \left(\frac{(r+1)^{r+1}}{r^r}\right)^B \left(\frac{1}{n}\right)^B \left(\frac{n-1}{n}\right)^{m-B}$, where $r=\frac{m}{B}-1$. Note that this bound is fairly tight, since a $\binom{(b+1)a}{a}>\frac{1}{4ab}\left(\frac{(b+1)^{b+1}}{b^b}\right)^a$.

Thus we have $p_B < e^{B(r+1)\ln(r+1) - Br\ln r - m\ln n + (m-B)\ln (n-1)}$. Now, since you are interested in the probability of finding $B$ or more balls in a bin we can consider $p_{\geq B} = \sum_{b=B}^{m} p_b < \sum_{b=B}^{m} e^{b(r+1)\ln(r+1) - br\ln r - m\ln n + (m-b)\ln (n-1)}$. Rearranging the terms, we get $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \sum_{b=0}^{m-B} e^{b(r+1)\ln(r+1) - br\ln r - b\ln (n-1)}.$$

Note the summation above is merely a geometric series, so we can simplify this to give $$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)^{m-B+1}}{1-\left(\frac{(r+1)^{r+1}}{r^r (n-1)}\right)}.$$ If we rewrite $\frac{(r+1)^{r+1}}{r^r (n-1)}$ terms using exponentials, we get
$$p_{\geq B} < e^{-m\ln \frac{n}{n-1}} \times e^{B(r+1)\ln(r+1) - Br\ln r - B\ln (n-1)} \times \frac{1-\left(e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right)^{m-B+1}}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}},$$ which then becomes $$p_{\geq B} < \frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}}.$$

Now, I take it you care about finding some $B$ such that $p_{\geq B} < \frac{C}{n}$ for some constant $C$, since this gives the total probability of any bin having $B$ or more balls as bounded from above by $C$. This criteria is satisfied by taking $$\frac{e^{-m\ln \frac{n}{n-1}} \times \left(e^{B((r+1)\ln(r+1) - r\ln r - \ln (n-1))} -e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}} = \frac{C}{n},$$ which can be rewritten as $$B = \frac{\ln\left(\frac{C}{n} e^{m\ln \frac{n}{n-1}} \left(1-e^{(r+1)\ln (r+1) - r \ln r - \ln(n-1)}\right) + e^{(m+1)((r+1)\ln (r+1) - r \ln r - \ln(n-1))}\right)}{(r+1)\ln(r+1) - r\ln r - \ln (n-1)}.$$

I'm not entirely sure how useful this comment will be to you (it's entirely possible I've made a mistake somewhere), but hopefully it can be of some use.


Is algorithmic information theory still evolving?

A modern tweak on algorithmic information theory is algorithmic randomness which was developed intensively in the 2000s (2009-2009) and is still quite active.

The most notorious open problem there may be whether Kolmogorov-Loveland randomness (in which martingales are computable but are allowed to bet on bits out of order) is the same as Martin-Löf randomness (in which martingales are only semicomputable, i.e., the capital function is computably approximable from below). This is known to be almost true, e.g. if $A\oplus B=\{2n:n\in A\}\cup \{2n+1:n\in B\}$ is KL-random then either $A$ or $B$ is ML-random.

An example of a recent paper in this area:

Bienvenu, Laurent, Kolmogorov-Loveland stochasticity and Kolmogorov complexity, Theory Comput. Syst. 46, No. 3, 598-617 (2010). ZBL1204.68110..


Problem 1 is known as SET PACKING. Like other packing problems, it's annoyingly hard. The best known bound is a $O(\sqrt{|S|})$ approximation and it is indeed APX-hard.


Task Multithreading analysis for a Divide and Conquer algorithm

Since you know that you must process each element and tasks are independent, i.e., the algorithm is embarrassingly parallel, in the Dynamic Multithreading model you should simply use a parallel for instead of spawning threads as you do, and let the compiler implement this optimally.

The work (sequential time) is $T_1 = O(nk)$ because you need to process each element and each element requires O(k) time. The span is $T_\infty = O(log n + k)$, and the parallelism is $T_1 / T_\infty = nk / (log n + k)$. In general, you know that, regarding $T_p$, we can only say that:

$T_1/p \leq T_p \leq T_1/p +  T_\infty$

$T_\infty \leq T_p \leq T_1/p + T_\infty$

This is because $T_p$ is a function of the work, span, size $n$ and scheduler behavior. And $T_\infty$ actually means for your algorithm $p = n$.

Now, let's analyze what happens to the speedup by using the Generalized Amdahl's law (derived by Lee). This law describes the speedup of parallel applications in which the computation is made of phases and in each phase a different number of processors is actually used. Think about each level of the directed acyclic graph corresponding to the computation as a phase.

Let $q_i$ be the percentage of a parallel application executed simultaneously by $i$ processors; then, we have:

${T_1} = \sum\limits_{i = 1}^p {{q_i}} {T_1}$

${T_p} = \sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} {T_1}$

Therefore, the speedup is

$\frac{{{T_1}}}{{{T_p}}} = \frac{{\sum\limits_{i = 1}^p {{q_i}} {T_1}}}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} {T_1}}} = \frac{{\sum\limits_{i = 1}^p {{q_i}} }}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }}$

Why is this useful? Because in general it allows you to derive useful bounds. For instance, assuming $q_i = 1/p$ then we can derive an upper bound for the speedup as follows:

$\frac{{{T_1}}}{{{T_p}}} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\frac{1}{p}\sum\limits_{i = 1}^p {\frac{1}{i}} }} = \frac{p}{{\sum\limits_{i = 1}^p {\frac{1}{i}} }} \leqslant \frac{p}{{\log p}}$

In your algorithm, $q_i$ is different from zero only for values of $p$ which are powers of 2; i.e.,  $q_i = 2^i, i = 0,...,\log p$. In the corresponding summation $q_i$ will be divided by $2^i$, giving rise to a summation in which each term is 1. As an example, for $p=16$ the nonzero $q_i$ values are 1,2,4,8,16 and these values must be divided respectively by 1,2,4,8,16 so the sum is 5 and the speedup is 1/5. In general, the speedup of your algorithm is:

$\frac{{{T_1}}}{{{T_p}}} = \frac{1}{{\sum\limits_{i = 1}^p {\frac{{{q_i}}}{i}} }} = \frac{1}{{\sum\limits_{j = 0}^{\log p} {\frac{{{2^i}}}{{{2^i}}}} }} = \frac{1}{{(\log p) + 1}}$

Now compare this with the performances you can obtain in the message passing model, in which your algorithm is executed on $p$ processors. Since the algorithm is embarrassingly parallel, $T_p = O(\frac{n}{p} k)$ (domain decomposition is trivial and requires O(1) time) and the speedup is (as expected for an embarrassingly parallel algorithm) $T_1/T_p = p.$


3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I recommend reading Sections 7 and 14 in the excellent book  by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh.

In short, Gu and Tamaki give a quadratic time algorithm which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then Robertson and Seymour in (5.1) give a tree-decomposition of width less than $\frac{9\sqrt{n}}{2}$. Then the classical dynamic programming algorithm (see, e.g., Marx) solves $3$-Coloring in time $3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)<141^{\sqrt{n}}$.

On the other hand, it is known (Lichtenstein) that under the Exponential Time Hypothesis (ETH), the Planar $3$-SAT problem is $2^{\Omega(\sqrt{n})}$-hard. And a reduction from Planar $3$-SAT to Planar $3$-Coloring implies that under ETH there is no algorithm solving Planar $3$-Coloring in time $2^{o(\sqrt{n})}$.


What is the motivation behind defining Deterministic Looping Automata?

In a looping automaton, the transition function is not assumed to be total. That is, for a state $q$ and a letter $\sigma$, it could be the case that $\delta(q,\sigma)$ is undefined.
Intuitively, this is the same as having a transition to a rejecting sink.

So they are "deterministic" in the sense that there is no non-determinism. But still, this means that for every word either there is a single run, or there are no runs. Thus, saying that a word is accepted iff it has a run on it is not a trivial acceptance condition.

The reason for studying these automata is that they correspond to safety properties. A safety property is a language $L$ such that for every word $w\notin L$, there exists some prefix $x$ of $w$ such that for every suffix $y$, $x\cdot y\notin L$. That is, once you read $x$, there is no way to get in the language.
These properties are useful in practice, as they correspond to "system failure", in a way. That is, once something really bad happens, you can't recover.

Technically, these autoamta are useful because of their simple acceptance condition.

As for references, start here. Also, Orna Kupferman has several papers using these objects (but I suspect you already know that... :) )


NIZK proofs: Why is the prove function necessary?

Prove$\:\:$is needed to convince the verifer(s) that $y$ is true.
Sort of; the verifier(s) will have almost as much control as the prover over the choice of $\sigma$.

The verifier(s) can convince (every) other verifier by forwarding $\pi$ to the other verifier(s).

Unlike ZK protocols in the standard model, which have

deniability, NIZK proofs instead have transferability.

Related to NIZK but not otherwise related to your question:

multi-string NIZK uses a weaker setup
assumption.


Can a two counters machine decide $n^2$?

The problem has been solved in:

Oscar H. Ibarra, Nicholas Q. Trân, A note on simple programs with two variables, Theoretical Computer Science, Volume 112, Issue 2, 10 May 1993, Pages 391-397, ISSN 0304-3975, http://dx.doi.org/10.1016/0304-3975(93)90028-R.

Let $TV$ be the class of languages recognized by two-counter machines.

Theorem 3.3: For any fixed integer $k \geq 2$, $L_k = \{ n^k \mid n \geq 0 \} \notin TV$

Note: it's strange that in the Ibarra&Tran's paper

Theorem 3.4 Let $f$ be a total function with infinite range and such that the relation $f(a + bn)=f(a)+cn$ for all $n \geq 0$ does not hold for any triple $(a,b,c)$; then $f$ cannot be computed by any two-counter machine.

is proved and the authors say that it has been derived in a slightly different form in:

I.M. Barzdin, Ob odnom klasse machin Turinga (machiny Minskogo), Russian, Algebra i Logika 1 (1963) 42-51

but don't cite Rich Schroeppel's paper (1972) in which the theorem is also derived ... :-)


Decomposing complete graphs into clique-free graphs of certain size

This question is about Ramsey theory.  In the case of the complete graphs, you can take a=1 by considering partitioning into only two sets.

The Ramsey number R(k,k) is the minimum integer m such that however you partition the edges of the complete graph Km into two sets, at least one of the sets contains Kk as a subgraph.  This immediately implies that if m < R(k,k), then the edges of the complete graph Km can be partitioned into two sets so that neither set contains Kk as a subgraph.

Erdős proved that R(k,k) grows exponentially: R(k,k) > k⋅2k/2/(e√2).  This means that if m is sufficiently large, then m < R(k,k) for k = ⌈2 log2m⌉ = O(log m).  In other words, you can take a=1 with two sets.


Complexity of computing the parity of read-twice opposite CNF formula ($\oplus\text{Rtw-Opp-CNF}$)

It turns out that every opposite-read-twice formula has an even number of satisfying assignments. Here's a nice proof of it, though one could probably eliminate the graph-theoretic terminology.

Let $\phi$ be an opposite-read-twice CNF formula. Without loss of generality, no clause contains both a variable and its negation.

Consider the graph $G$ whose vertex set is the clauses of $\phi$, and for each variable $x$, we add an (undirected) edge that is incident on the two clauses containing $x$. Our WLOG assumption in $\phi$ says this graph has no self-loops. Moreover, think of labeling each edge by the variable defining it; this way we can distinguish between parallel edges.

An orientation of $G$ is a directed graph whose edges are formed by assigning a direction to each edge in $G$. Call an orientation of $G$ admissible if every vertex of $G$ has an outgoing edge. It's easy to see that satisfying assignments to $\phi$ are in bijective correspondence with admissible orientations of $G$.

Now I claim that the number of admissible orientations of $G$ is even. The argument is "by involution": I construct a map $\Phi$ with the following properties:

$\Phi$ is totally defined (every admissible orientation is mapped somewhere)
$\Phi$ sends admissible orientations to admissible orientations
$\Phi$ is an involution ($\Phi \circ \Phi$ is the identity)
$\Phi$ has no fixed points

Once these are established, we can observe that the orbits of $\Phi$ have size 2 and partition the admissible orientations of $G$. It follows that the number of admissible orientations is even.

To define $\Phi$, let $\vec{G}$ be an admissible orientation, and consider breaking $\vec{G}$ into it's strongly connected components. $\Phi$ then sends $\vec{G}$ to the orientation formed by reversing all the edges within the strongly connected components. The properties are then straightforwardly checked:

Every directed graph can be partitioned into strongly connected components.
Consider the "DAG of strongly connected components" in $\vec G$; call it the quotient graph. Note that $\Phi(\vec G)$ will have the same quotient structure, since $\Phi$ doesn't affect the edges between SCCs, and strongly connected graphs remain strongly connected when reversing all their edges. Additionally, if a SCC has more than one vertex, then all its constituent vertices have an incoming edge. If an SCC has just a single vertex and isn't a source in the quotient, then all its constituent vertices have an incoming edge. So to show $\Phi(\vec G)$ is admissible, it suffices to show that the SCCs which are sources in the quotient have multiple vertices. But this follows by the fact that every vertex in the component has an incoming edge, which must come from another vertex in the component since $G$ has no self-loops and the component is a source in the quotient.
This follows from the fact that the quotient structure of $\Phi(\vec G)$ coincides with the quotient structure of $\vec G$.
By admissibility, $\vec G$ has a cycle, and hence some SCC with an edge inside it.


Exact exponential-time algorithms for 0-1 programs with nonnegative data

if the number of non-zero coefficients in $A$ is linear in $n$, there is an algorithm that solves this problem in less than $2^n$ time.

Here's how it works.  We use the standard connection between an optimization problem and its corresponding decision problem.  To test whether there exists a solution $x$ where $Ax\le b$ and $c^T x \ge \alpha$, we will form a decision problem: we will adjoin the constraint $c^T x\ge \alpha$ to the matrix $A$, and test whether there exists any $x$ such that $Ax \le b$ and $-c^T x \le -\alpha$.  In particular, we will form a new matrix $A'$ by taking $A$ and adding an extra row containing $-c^T$, and we will form $b'$ by taking $b$ and adjoining an extra row with $-\alpha$.  We obtain a decision problem: does there exist $x \in \{0,1\}^n$ such that $A' x \le b'$?  The answer to this decision problem tells us whether there exists a solution to the original optimization problem of value $\alpha$ or greater.  Moreover, as explained in the answer to your prior question, this decision problem can be solved in less than $2^n$ time, if the number of non-zero coefficients in $A'$ is linear in $n$ (and thus if the number of non-zero coefficients in $A$ is linear in $n$).  Now we can use binary search on $\alpha$ to solve your optimization problem in less than $2^n$ time.

My thanks to AustinBuchanan and Stefan Schneider for helping to debug an earlier version of this answer.


Major unsolved problems in theoretical computer science?

Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations?

The exponent of the best known upper bound even has a special symbol, $\omega$. Currently $\omega$ is approximately 2.376, by the Coppersmith-Winograd algorithm.  A nice overview of the state of the art is Sara Robinson, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News, 38(9), 2005.

Update: Andrew Stothers (in his 2010 thesis) showed that $\omega < 2.3737$, which was improved by Virginia Vassilevska Williams (in a July 2014 preprint) to $\omega < 2.372873$.  These bounds were both obtained by a careful analysis of the basic Coppersmith-Winograd technique.

Further Update (Jan 30, 2014): François Le Gall has proved that $\omega < 2.3728639$ in a paper published in ISSAC 2014 (arXiv preprint).


Choosing one number from each set so that the difference between maximum and minimum is minimized

It's not really a graph problem, I think. Problems in which you try to choose some objects to minimize the difference between the min and max chosen object are called "minimum range" problems — e.g. look up "minimum range cut", which is a graph problem — but this one looks like you're trying to find the minimum range basis of a partition matroid with one partition set for each of your groups.

In general minimum range matroid basis problems can be solved in $O(n\log n)$ time, plus $O(n)$ steps of a subroutine that finds a basis of a set with corank one: sort the elements from smallest to largest and then process the elements one by one. While you process the elements maintain an independent set $I$; when you process an element $e$, add $e$ to $I$ and, if that addition causes $I$ to become dependent, kick out the minimum weight element in the unique circuit of $I$. The minimum range basis is one of the sets $I$ that you found in this process: the one that has full rank and has as small a range between min and max as possible.

For your partition matroid special case it's easy to find the circuit in $I$ when it becomes dependent: a circuit happens when $e$ belongs to the same group as an element $f$ that you previously added, and $f$ is the element you should kick out of $I$. So the whole algorithm takes $O(n\log n)$ time, or possibly faster depending on how much time it takes to do the sorting step.


Does PSPACE-completeness imply approximation hardness?

As there is no answer yet, I turn my comment to answer, Marathe et al. in their ICALP93 paper, defined some problems which are PSPACE complete but they admit constant factor approximations, they also provide some inapproximability results. For this particular question, consider MAX3SAT, corresponding decision problem is PSPACE-complete even if the corresponding SAT graph has hierarchical structure as they defined in their paper, but this problem has a 2-approximation guarantee algorithm in hierarchical structure.


Constructive proof of the Halting Problem

I think if we want to answer this problem constructively, then we should be able propose problem constructively.
Let language of arithmetic be $L=\{0,S,+,\cdot \}$ and $\phi(n,x,y)$ be kleene predicate in $L$. Now the first problem is:

  Is there any $m\in \mathbb{N}$ such that $$H_1(m):=\forall x\in\mathbb{N}:\forall y \in \mathbb{N} \neg \phi(x,x,y)\leftrightarrow \exists z\in \mathbb{N} \phi(m,x,z)$$
  ?

Proof. Suppose there exists such $m$, so by above definition we have:
$$\forall y \in \mathbb{N} \neg \phi(m,m,y)\leftrightarrow \exists z\in \mathbb{N} \phi(m,m,z)$$
and this leads to a contradiction, therefore there does not such $m$. (note that $\neg \exists A(x)\rightarrow \forall x \neg A(x)$ has a constructive proof.)

Define $$H_2(m):=\forall x\in \mathbb{N}\exists ! y\in\{0,1\} \phi(m,x,y) \land \forall x\in\mathbb{N}:\exists u \in \mathbb{N}\phi(x,x,u)\leftrightarrow \phi(m,x,1)$$

  Is there any $m$ such that $H_2(m)$ satisfied in natural numbers?

proof. If there exists such m, we can construct number $m'$ from $m$ such that  $H_1(m')$ satisfied in natural numbers and this lead to a contradiction, therefore we have $\forall n\in \mathbb{N}\neg H_2(n)$.

We can see that $H_2(n)$ means that "partial recursive function with code $n$ is a solution for halting problem". Actually we can not deduce constructively that $$\neg H_2(n)\leftrightarrow \neg(\forall x\in \mathbb{N}\exists ! y\in\{0,1\} \phi(n,x,y)) \lor \neg(\forall x\in\mathbb{N}:\exists u \in \mathbb{N}\phi(x,x,u)\leftrightarrow \phi(n,x,1))$$, but $\neg H_2(n)$ means
there exists a time in tmeline that we figure out $\neg\forall x\in \mathbb{N}\exists ! y\in\{0,1\} \phi(n,x,y)$ or $\neg\forall x\in\mathbb{N}:\exists u \in \mathbb{N}\phi(x,x,u)\leftrightarrow \phi(n,x,1)$ although maybe we don't know which of them is true this moment.


Can three stacks be implemented in one array, with O(1) push/pop time?

Fredman and Goldsmith showed in "Three Stacks" (Journal of Algorithms, 1994) that $\Theta(n^\varepsilon)$ bits of wasted space is achievable. It is also the minimum needed for arrays of size at least 16 quattuordecillion yottabytes. I described a simple algorithm wasting $\Theta(\sqrt{n})$ words of space in my StackOverflow answer to this question. As @dmitri-urbanowicz mentioned in the comments, this is basically just treating the array as $\sqrt{n}$ blocks of size $\sqrt{n}$, where each block is used for exactly one stack and contains a single pointer to the next block in that stack.


Quantum circuit simulation divergence in results

Peter Shor nailed the reason. This is because OpenQASM and Quirk have different conventions for how the order of wires maps into the order of bits shown in the kets. The simplest way to check this is to use a circuit that toggles only the top qubit.

Quirk considers the top qubit to be the least significant qubit, and labels kets in big endian order (i.e. the ordering humans use; why 12 represents twelve instead of twenty-one). So the 4-output chance display is showing outputs in the following order: probability of top=bottom=0; probability of top=1 and bottom=0, probability of top=0 and bottom=1; probability of top=bottom=1.

The reason I chose this order when making Quirk is because it makes the displays behave better when resizing. If you resize the chance display from 2-qubits to 3-qubits, and the third qubit is off, the original four outputs stay together in the top half instead of being spread apart. Also it's just the natural thing to do when programming: the wire at index k has weight 1<<k. Quirk's tendency to expand circuits and gates downward pushed it towards a "down means more/bigger" convention in other places as well, e.g. in the arithmetic circuits.


If there exists a solution for $(n,c)$, there exists a solution for $(4n,2c)$ (assuming $n \ge 4$): e.g., take $T = \{x||x||y||y : x,y \in S\}$, where $S$ is the solution for $(n,c)$.  This works since $n^2 \ge 4n$ for $n \ge 4$.

This implies that $c = \Omega(n^{1/2})$ should be a sufficient condition to imply existence of such a set (and this is constructive; i.e., there is an algorithm to construct such sets that achieves this bound).

More generally, if there is a solution for $(n,c)$ and $n$ is even, there is a solution for $(n^2,cn/2)$.  Here we let $T = \{x||\cdots ||x||y||\cdots || y : x,y \in S\}$, where we repeat $x$ $n/2$ times and repeat $y$ $n/2$ times.

This implies that, asymptotically, $c = \Omega(n/\lg n)$ is sufficient to ensure the existence of such a set (and again this is constructive).

I don't know whether $c = \Omega(n)$ is sufficient to ensure the existence of such a set.


What is an accessible introduction to Percolation Theory?

I can't give you a comparison of different options but I can at least tell you that I (having that background) really liked Grimmett's book.

As an aside: would this have been better as a comment?  I was debating with myself and could not decide.


Counting words of length $n$ in an inherently ambiguous CFG?

It seems that this problem is NP-hard, if both the grammar and $n$ (in unary notation) are considered to be parts of the input.
There is a classical construction that is used to show that universality of a CFG is undecidable. The construction takes a Turing machine $M$ and outputs a grammar $G_M$, such that all strings in $L(G_M)$ are not valid accepting computations of $M$ in some encoding.
Sections 1 and 3 of this overview do a decent job of explaining the main ideas, though they skip over a lot of details (how to deal with tape extensions, e.t.c.).
Said construction should work for non-deterministic Turing machines as well (the construction does not use determinism anywhere, I think). Now, consider a polynomial time non-deterministic Turing machine $M$ that solves SAT by guessing a satisfying assignment. Construct a grammar $G_M$ that corresponds to $M$.
I claim that a polynomial time algorithm to compute the number of strings in $G_M$ with a given length yields a polynomial time algorithm for solving SAT. Indeed, consider a given SAT-formula $\varphi$, it corresponds to some initial configuration $x_\varphi$ of $M$. Then, the language $L' = L(G_M) \cup \overline{(x_\varphi\#)(\Gamma \cup Q \cup \{\#\})^*}$ is the language of all strings that are either not valid accepting computations of $M$ or valid accepting computations of $M$ that do not start in configuration $x_\varphi$.
Hence, if $\varphi$ is satisfiable, there is a string of polynomial length from $(\Gamma \cup Q \cup \{\#\})^*$ that does not belong to $L'$. This string correspond to $M$ guessing some satisfying assignment correctly. On the other hand, for unsatisfiable $\varphi$, there are no accepting computations of $M$, hence there will be no short strings (or any strings, really) that do not belong to $L'$.
The last thing to note is that $L'$ is a union of a CFL $L(G_M)$ and a regular language $\overline{(x_\varphi\#)(\Gamma \cup Q \cup \{\#\})^*}$. Therefore, it is recognised by a grammar $G_M'$ of size $|G_M| + O(|\varphi|)$. Hence, computing the number of strings with a given length in $G_M'$ is NP-hard, because SAT can be reduced to this problem.
UPD. In fact, this problem is #P-complete, because every satisfying assignment of $\varphi$ corresponds to exactly one short string not in $L'$, yielding a reduction from #SAT.


Storing a bit vector in uninitialized memory and minimal space

Yes, this can be done through bucketing. The representation in Briggs and Torczon can be used to store not just bits, but values associated with any set bits, by storing them next to the values in the dense array. For $k$-bit values, this leads to a total storage cost of $(2n+1)\lceil \lg n \rceil + kn$.

Now pick $k=\lceil \lg n \rceil$. Each $k$-bit value will represent a set of $\lceil \lg n \rceil$ contiguous bits in the bit array. We thus only need to track $\lceil n/\lceil \lg n \rceil \rceil$ of them with the dense and sparse arrays. This leads to a total cost of $\Theta(n)$ bits of storage, with $\Theta(\lg n)$ initialized bits.

Like the basic solution, this requires $O(1)$ operations on words of length $\Theta(\lg n)$ to set a single bit.


Are string palindrome questions practically interesting?

I had a use for palindromes as follows:

A string of length $n$ and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal.

Now after identifying you may ask how many equivalence classes have certain properties. And then the number of equivalence classes is directly related to the number of palindromes. If there  are $p_n$ palindromes then there are
$$p_n+(2^n-p_n)/2$$
equivalence classes of binary strings.


It seems that there are no recent books or survey papers on online algorithms.


The question is a bit ill-posed, since you did not specify that equivalent automata should be counted as a single object. Without that restriction (or the reachability one), the set of all $n$-state DFAs over a binary alphabet and with starting state $s=1$ has exactly $n^{2n}2^n$ elements, and it is trivial to sample from this set uniformly, as indicated in the link in my comment,
https://dl.acm.org/citation.cfm?id=3064434

Now the linked paper gives sharp bounds on the expected size of the minimal equivalent DFA, when the original one is drawn from the naive uniform distribution. For binary alphabets, this quantity is concentrated about $0.7968n$. That suggests that if you naively sample DFAs on $n/0.7968$ states and then minimize them, you'll get automata with roughly $n$ reachable states. Of course, no claim is being made about this sampling procedure being uniform. See, however, references in the linked paper -- especially
https://dl.acm.org/citation.cfm?id=782472
and
http://www.sciencedirect.com/science/article/pii/S0304397507002861?via%3Dihub
-- the latter seems most relevant to your question.


Question about "typical set" in Shannon's source coding theorem

$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set.

The only reason to use the typical set instead of $S_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with the asymptotic equipartition property makes it easy to count the size of the typical set and to put bounds on the probability of each element in the set. This is not so easy to do when working with $S_δ$


What separates easy global problems from hard global problems on graphs of bounded treewidth?

Most algorithms for graphs of bounded treewidth are based on some form of dynamic programming. For these algorithms to be efficient, we need to bound the number of states in the dynamic programming table: if you want a polynomial-time algorithm, then you need a polynomial number of states (e.g., n^tw), if you want to show that the problem is FPT, you usually want to show that the number of states is some function of treewidth. The number of states typically corresponds to the number of different types of partial solutions when breaking the graph at some small separator. Thus a problem is easy on bounded-treewidth graphs usually because partial solutions interacting with the outside world via a bounded number of vertices have only a bounded number of types. For example, in the independent set problem the type of a partial solution depends only on which boundary vertices are selected. In the Hamiltonian cycle problem, the type of a partial solution is described by how the subpaths of the partial solution match the vertices of the boundary to each other.
Variants of Courcelle's Theorem give sufficient conditions for a problem to have the property that partial solutions have only a bounded number of types.

If a problem is hard on bounded-treewidth graphs, then it is usually because of one of the following three reasons.

There are interactions in the problem not captured by the graph. For example, Steiner Forest is NP-hard on graphs of treewidth 3, intuitively because the source-destination pairs create interactions between nonadjacent vertices.

Elisabeth Gassner: The Steiner Forest Problem revisited. J. Discrete Algorithms 8(2): 154-163 (2010)

MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dániel Marx: Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM 58(5): 21 (2011)

The problem is defined on the edges of the graph. Then even if a part of the graph is attached to the rest of the graph via a bounded number of vertices, there could be many edges incident to those few vertices and then the state of a partial solution can be described only by describing the state of all these edges. This is what made the problems in [3,4] hard.
Each vertex can have a large number of different states. For example, Capacitated Vertex Cover is W[1]-hard parameterized by treewidth, intuitively because the description of a partial solution involves not only stating which vertices of the separator were selected, but also stating how many times each selected vertex of the separator was used to cover edges.

Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Capacitated Domination and Covering: A Parameterized Perspective. IWPEC 2008: 78-90


Yes, this has been studied. It was called the multiple intents re-ranking problem by Azar, Gamzu, and Yin who gave a $\log n$ approximation using a cleverly modified greedy algorithm (the point is being greedy with respect to a clever metric). Bansal, Gupta, and Krishnaswamy had the good sense to rename the problem to generalized min-sum set cover and gave a constant approximation via LP rounding. The constant is very large, more than 400. Skutella and Williamson improved this to 28.

BTW you state the problem as finding an ordering on the sets to satisfy a coverage requirement on the elements. Some of the above papers state the problem in the equivalent dual form: find an ordering on the elements to satisfy hitting requirements on the sets.


Why is "topological sorting" topological?

The earliest reference I could find for topological sort is from [Lasser61]:

  A network of directed line segments free of circular elements is assumed. The lines are identified by their terminal nodes and the nodes are assumed to be numbered by a non-topological system. Given a list of these lines in numeric order, a simple technique can be used to create at high speed a list in topological order.

I don't have access to this article right now but I would wager that the "topology" in "topological sort" does not come from the mathematical notion of topology (e.g.: open sets, compactness, etc...) but rather from the "network topology" sense.

[Lasser61] Lasser, Daniel J. "Topological ordering of a list of randomly-numbered elements of a network." Communications of the ACM 4, no. 4 (1961): 167-168.


P vs NP: Instructive example of when Brute Force search can be avoided

I recommend Jenga!

Assuming you have two perfectly logical, sober, and dextrous players, Jenga is a perfect-information two-player game, just like Checkers or Go.  Suppose the game starts with a stack of $3N$ bricks, with 3 bricks in each level.  For most of the game, each player has $\Theta(N)$ choices at each turn for the next move, and in the absence of stupid mistakes, the number of turns is always between $N$ and $6N$.  So crudely, the game tree has $N^{\Theta(N)}$ states.  If you explored the game tree by brute force, you might spend exponential time to find a winning move or convince yourself that you can't win.

But in fact, Uri Zwick proved in 2005 that you can play Jenga perfectly by keeping track of just three integers, using a simple set of rules that you can easily fit on a business card.  The three numbers you need are

$m =$ the number of levels (not counting the top level) with three bricks.
$n =$ the number of levels (not counting the top level) with two bricks side by side.
$t =$ the number of bricks in the top level (0, 1, 2, or 3).

In fact, most of the time, you only have to remember $n\bmod 3$ and $m\bmod 3$ instead of $n$ and $m$.  Here is the complete winning strategy:

Here I-I means you should move the middle brick from any 3-layer the top, II- means you should move a side brick from a 3-layer to the top, -I- means you should move a side brick from a 2-layer to the top, and the bob-omb means you should think about death and get sad and stuff.  If there's more than one suggested move in a box, you can choose any one of them.  It's trivial to execute this strategy in $O(1)$ time if you already know the triple $(m,n,t)$, or in $O(N)$ time if you don't.

Moral: Jenga is only fun if everyone is clumsy and/or drunk.


Homoiconic languages which are not Turing complete

You can turn every programming language $L$ into a homoiconic language $L_{hom}$ by adding a suitable representation of programs, such as ASTs (abstract syntax trees) or quasi-quoted programs, together with some operations that mediate between $L$ and the representation of $L$-syntax (e.g. evaluation or splicing instructions). The details of this depend on your precise rendering of homoiconicity (e.g. compile-time as in Template Haskell vs run-time as in the MetaML family of languages or Javascript).

One extreme example is the empty language $L^{\emptyset}$ that has no programs. Clearly its  homoiconic variant $L^{\emptyset}_{hom}$ isn't Turing complete. For more interesting examples, you can take any of the usual type theories such as the simply typed $\lambda$-calculus, System F or the Calculus of Constructions. Of course one would have to prove that the homoiconified version of such type-theories doesn't allow us to encode recursion somehow. I doubt that this has been done. Cody's comment below suggests that this might not be possible.


Relating univalence for a theory of cateogries to the skeleton concept

I refer you to Chapter 9 of the HoTT book. In particular, a category is defined in such a way that isomorphic objects are equal, see Definition 9.1.6. As Example 9.1.15 points out, there really isn't a reasonable notion of "skeletality" in HoTT. This is so because equality is so weak that it already means "isomorphic".

Furthermore, Theorem 9.4.16 says

  Theorem 9.4.16: If $A$ and $B$ are categories then the function $$(A = B) \to (A \simeq B)$$ (defined by induction on the identity functor) is an equivalence of types.

The theorem tells us that the Univalence Axiom gives us a sort of cateory theorist's dream: equivalent categories are equal.

You ask whether you can reduce the Univalence axiom to a statement about categories. Attempts using skeletons won't work because there isn't a good way to say "skeletal". We could ask whether Theorem 9.4.16 implies the Univalence axiom. This is not going to be the case, as far as I can see, because a category has a $1$-type (groupoid) of objects and a $0$-type (set) of morphisms, so theorem 9.4.16 amounts to something like the Univalence axiom for 1-types, only.


Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

In practice, if you want to extract randomness from a source $S$, you don't use an extractor.  Instead, you use a cryptographic hash function and hash the data from the source.  (This is how cryptographic-strength pseudo-random number generators distill randomness from many non-uniformly distributed sources of randomness.)  This can be proven safe in the random oracle model.

Of course, if you care mostly about theoretical bounds, extractors are better because they provide provable bounds without requiring cryptographic assumptions, so theoretical work will naturally focus on extractors -- but if you want to do this in practice, that consideration is less important.  If you want to do this in practice, I recommend you use a cryptographic hash function, as the assumptions are reasonable and you get something that does not waste any entropy.  (And before you reject the idea of depending upon cryptographic assumptions: Hey, if it's good enough to protect e-commerce and banks and classified documents, it's probably good enough for your purposes.)

If you use a cryptographic hash function, the bottom line (essentially) is that all of the entropy of the source is preserved (up to the security level of the cryptographic hash function).  So, quantifying the amount of extracted randomness comes down to quantifying how much randomness is present in the source.

There is no good black-box way to determine the min-entropy of the source distribution.  So, in practice, you don't try to determine the min-entropy of a source through observational methods (e.g., observing many samples and then doing something).  Instead, you need to have a model of how the source works, and to derive estimates of its entropy based upon that model.  That model might be based upon the physics of the source or other domain-specific assumptions.  This is not a question that algorithms can help you with much.

Why is it hard to estimate the min-entropy of a source?  Consider two sources: $S_1$ outputs a random $1000$-bit value $x$ (distributed uniformly at random); $S_2$ picks a random $128$-bit value $k$, then uses AES in CTR mode (a secure pseudorandom generator) to stretch $k$ to a $1000$-bit value $y$, and outputs $y$.  Notice that, assuming AES is secure, there is no feasible way to distinguish source $S_1$ from source $S_2$ by just observing their outputs: any algorithm for distinguishing the two sources would require something like $2^{128}$ steps of computation.  However, the min-entropy of $S_1$ is very different from the min-entropy of $S_2$ ($1000$ bits vs $128$ bits).  This example shows that computing the min-entropy of a source is a difficult in general, so you should not expect to find any efficient algorithm to do that for you based solely on observing some outputs from the source.

For a more rigorous treatment of the complexity of estimating the min-entropy, see e.g. the following paper:

The Complexity of Estimating Min-Entropy.  Thomas Watson.  CC 2015.

The bottom line is that it's hard.  (Thanks to epsfooling for pointing me to this paper.)

The literature on cryptographic pseudorandom number generators has lots more on this topic.


Complexity class of phase information in Gauss sum

See Efficient Quantum Algorithms for Estimating Gauss Sums by Wim van Dam and Gadiel Seroussi.

They have a nice introduction to the computational problem of estimating Gauss sums over finite fields and finite rings. They carefully explain how the computational problem is specified, how the characters are specified in the input and what the input size is.

They show how to estimate the phase of a Gauss sum to inverse polynomial accuracy in polynomial time on a quantum computer. They then show that this problem is classically hard assuming discrete log is hard.


general statement what kinds of problems can be solved more efficiently

My limited understanding is that problems in which cyclic groups or their products play a central role usually have very good (exponential to polynomial complexity) speedups when quantum algorithms are used.

This is due to the fact that the complex Fourier transform plays a central role in the representation of quantum states.

The fact that Grover's search doesn't have this impressive speedup is also due to the fact that it is not tightly related to cyclic groups.


What's the "real" reason that IP=PSPACE is non-relativizing?

Any answer to a question of the form, "What is the real reason that..." will necessarily be somewhat subjective.  However, for the particular case of IP = PSPACE, I think that a pretty good case can be made that arithmetization is indeed the key, by observing that while IP = PSPACE does not relativize, it does algebrize in the sense of Aaronson and Wigderson.  As they explain in their paper, roughly speaking, a complexity class inclusion ${\cal C} \subseteq {\cal D}$ algebrizes if ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ for all oracles $A$ and all low-degree extensions $\tilde A$ of $A$.  In particular, they show that the inclusion PSPACE $\subseteq$ IP algebrizes, even though it doesn't relativize.

  The intuition that I've developed is that non-relativizing results are ones that poke around with the nitty gritty of Turing Machines

This is not a bad intuition, but I think that the Aaronson-Wigderson result shows that the IP = PSPACE proof pokes around in a rather limited way, and certainly not in a sophisticated enough way to prove P $\ne$ NP, since Aaronson and Wigderson also show that non-algebrizing techniques will be required to separate P from NP.


Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

The obvious approach is:

(1) Compute an approximation to $\log_2(3^n)$. You can approximate it to within an additive error of 1 by counting the number of bits in the given binary representation, and to within an additive error of $\epsilon$ by additionally looking at the top $O(\log\frac{1}{\epsilon})$ bits of the input. It should suffice to choose a constant value of $\epsilon$, so that (after combining with the error in step (2)) the final result ends up within an additive error of $1/2$ of correct.

(2) Compute an approximation to $\log_2(3)$. I'm not familiar with the algorithms for this but I expect they take time polynomial in the number of bits of precision you need, and you only need $O(\log n)$ bits of precision.

(3) Divide the answer to (1) by the answer to (2), and round to the nearest integer.

So the first step takes linear time (in most models of computation although maybe not for some underpowered ones like single-head Turing machines) and the remaining steps should be polylogarithmic.


When can be used the "uncompute garbage" trick in quantum computing?

I think I finally figured out what the answer was :) It seems that the "uncomputation trick" was first used for quantum computing in this paper: Strengths and Weaknesses of Quantum Computing (proof of Theorem 4.14). So basically I was right when I said that it only works for "exact" computation (i.e. the output register that contains $f(x)$ is not in superposition) but it can also be used when the error probability of the algorithm is low (in this case the uncomputation is not perfect, but the amplitude of the error term is low).

Let me explain how it works: we have a quantum algorithm $\mathcal{Q}$ that takes an input $|0\rangle |0\rangle$ and produces a state $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle$ where $y$ is the working space and $b_y \in \{0,1\}$ is the output register (the result of the computation). If the computation is "exact" then all the $b_y$ are equal to a same value $b$, i.e. the state is $\sum_y \alpha_y |y\rangle |b\rangle$. We now add an extra register in which we CNOT the result: $\sum_y \alpha_y |y\rangle |b\rangle |b\rangle$. Finally, we can apply $\mathcal{Q}^{-1}$ on the first two registers so as to obtain $|0\rangle |0\rangle |b\rangle$. The uncomputation is exact.

Assume now that there is some error probability $\varepsilon$, i.e. the probability of correctly measuring $b$ is $\sum_{y : b_y = b} |\alpha_y|^2 = 1 - \varepsilon$. Let's add the extra register to CNOT the result and denote $|\phi\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b_y\rangle $ (in which some $b_y$ are different from $b$) and $|\phi'\rangle = \sum_y \alpha_y |y\rangle |b_y\rangle |b\rangle$. If we apply $\mathcal{Q}^{-1}$ on the first two registers of $|\phi'\rangle$ we obtain $|0\rangle |0\rangle |b\rangle$ which is what we want. Unfortunately, we only know how to compute $|\phi\rangle$ (in which the last register is a superposition of $b$ and $1-b$). However, note that $\langle \phi | \phi' \rangle = \sum_{y : b_y = b} |\alpha_y|^2 = 1-\varepsilon$. Consequently, the inner product between $\mathcal{Q}^{-1} |\phi\rangle$ and $\mathcal{Q}^{-1} |\phi'\rangle = |0\rangle |0\rangle |b\rangle$ is also $1-\varepsilon$ (inner product is preserved by unitaries), which means that the amplitude of $|0\rangle |0\rangle |b\rangle$ in $\mathcal{Q}^{-1} |\phi\rangle$ is $1 - \varepsilon$. Thus, if $\varepsilon$ is small, then $\mathcal{Q}^{-1} |\phi\rangle$ is close to the correct uncomputed state $|0\rangle |0\rangle |b\rangle$. The uncomputation is almost exact.

I think this is the underlying reasoning in Aaronson's paper when he talks about "uncompute garbage". His circuit $\mathcal{Q}^{\star}$ has a very low error probability (due to an amplification step he performed before) and thus he does not care about the error part in the uncomputation.

There is also this paper: Quantum Entanglement and the Communication Complexity of the Inner Product Function (section 3) for another detailed use of uncomputation.


The complexity of enumerating maximal independent sets in graphs is the same as in bipartite graphs, so bipartiteness does not bring anything new.

You have an algorithm (with exponential space) in $O(|C|\cdot n^2)$, but no polynomial space algorithm that acheives this time complexity is known. The following paper http://www.sciencedirect.com/science/article/pii/S0166218X08004563 is a good survey.


If I understand your problem correctly, it seems like you're looking to examine a furthest-point weighted Voronoi diagram under the Manhattan ($\ell_1$) distance. The transformation is as follows.

For each point $p_i$ on the grid, define the distance function $$d_i(x) = \max(0, \|x - p_i\|_1 - (t_{n+1}-t_i))$$ Then $d_i(x)$ is the (truncated) distance of $x$ from the ball of radius $t_{n+1}-t_i$ around $p_i$ under the $\ell_1$ distance.

You want to find
$$ x^* = \arg \min \max_i \ d_i(x) $$
which can be obtained by computing the furthest-point weighted Voronoi diagram under the $\ell_1$ distance (the weighted part is because of the offset associated with the $t_i$).

If you want code, then I'm not sure where you might find it, but this site has an amazing collection of Voronoi demos written in Java (including furthest point Manhattan distance) and you might be able to adapt it for for your needs.