Reference for (odd-hole,antihole)-free graphs?

In fact, it is relatively easy. Instead for studying independent set problem in (odd-hole,antihole)-free graphs, we take complement of the graphs and try to find a maximum clique in it. Thus it becomes maximum clique problem in (hole, anti-odd-hole)-free graphs.

In section 2 of the paper "Triangulated Neighborhoods in Even-hole-free Graphs" by da Silva and Vuskovic, they stated that Farber first shows

  There are $O(n^2)$ maximal cliques in any 4-hole free graphs.

Then their main theorem stated that

  There are $O(n + m)$ maximal cliques in even-hole-free graphs, and all the maximal cliques can be found in time $O(n^2m)$.

Since we are dealing with (hole, anti-odd-hole)-free graphs which is clearly even-hole-free, finding a maximum clique takes at most $O(n^2m)$ time.

4-hole-free are critical to these kind of results like a poly-time algorithm for $\overline{K_{2,m}}$-free graphs, so the real challenge may be studying independent set problem in (hole, anti-odd-hole)-free graphs instead, which becomes the maximum clique problem in (odd-hole, anti-hole)-free graphs.

Edit:

Oh, another thought came out. (hole, anti-odd-hole)-free graphs are almost weakly chordal in the following sense: since 4-hole-free implies there are only anti-holes with size 4~7 remains (any k-anti-hole with size > 7 contains a 4-hole), and it is also anti-odd-hole-free which restrict the size of anti-holes down to 4 and 6, it is almost no holes/antiholes in the graph! Thus a poly-time algorithm seems plausible for such graphs.


Lower bound for enumerating k closest pair of points

This is only a partial answer.

I think it is not complex to show that if question 1 can be done in $o(n^2 \log n)$, then so can be question 2. So according to the comment by Willard Zhan in the OP's question, your first question should be open as well.

A reduction could be as follows:

Assume your input to question 2 is $\{x_i\}_{1 \leq i \leq n}$. Then construct an input for question 1 as follows:

$\{T + x_i\}_{1 \leq i \leq n} \cup \{- x_i\}_{1 \leq i \leq n}$ for a sufficiently large constant T.

Then the answer to question 1 with these $2n$ points could be easily translated to an answer to question 2, as pairs of the form $(T + x_i, -x_j)$ in the answer to question 1 are easily differentiated from the rest, and correspond directly to the answer of question 2, taking into account that:

$|(T + x_i) - (- x_j) | = |T + x_i + x_j | = T + x_i + x_j > T / 2$
$|(T + x_i) - (T + x_j) | = |x_i - x_j | < T / 2$
$|-x_i - (-x_j) | = |- x_i + x_j | < T / 2$


Redundancy and Structure of computational problems

Actually, I think that the phenomenon here is that GI in some sense has too much structure. It is in some ways the group-theoretic nature of its witnesses which leads to the $\mathsf{coAM}$ algorithm for GI and is one of the pieces of technical evidence why people believe GI is not $\mathsf{NP}$-complete. My thinking here is that there is so much structure that the problem is "too rigid" to encode arbitrary $\mathsf{NP}$ problems.

Another way to capture this is the fact that the counting and decision versions of GI are equivalent, whereas for all known $\mathsf{NP}$-complete problems this is not the case unless the polynomial hierarchy collapses. This can also be viewed as capturing some aspect of structure/redundancy: for unstructured, general problems, counting solutions seems to be much harder than telling if one exists, whereas the extensive structure of GI allows one to show that counting and decision are equivalent.

(On the other hand, group isomorphism seems even more structured than GI, yet no counting-to-decision reduction is known for group iso. Perhaps this says that GI is in sort of a "just right" level of structure - too structured to be NP-complete, but unstructured enough to allow a counting-to-decision reduction.)


Erdos conjecture, number of cliques, Turan`s graph

Isn't the conjecture in the paper that the number of $(k+1)$-cliques in this case is at least $c^{k-1}$? That's the number you get by adding a single edge to the Turan-graph. I think it's proved in 1969-10. Also relevant: 1983-28.
Recently, there has been significant progress on bounding the number of cliques as a function of the quadratic term of the number of edges: arxiv:1212.2454.


the number of rational points of a curve modulo 2

This language belongs to P. See Corollary 7.4 at
"Algorithmic theory of zeta functions
over finite fields"
by Daqing Wan. (There $n$ is the number of variables of a hypersurface, $d$ is the total degree of it, and  $q$ is the cardinality of the corresponding finite field.)


Why colon to denote that a value belongs to a type?

The main reason to prefer the colon notation $t : T$ to the membership relation $t \in T$ is that the membership relation can be misleading because types are not (just) collections.

[Supplemental: I should note that historically type theory was written using $\in$. Martin-Löf's conception of type was meant to capture sets constructively, and already Russell and Whitehead used $\epsilon$ for the class memebrship. It would be interesting to track down the moment when $:$ became more prevalent than $\in$.]

A type describes a certain kind of construction, i.e., how to make objects with a certain structure, how to use them, and what equations holds about them.

For instance a product type $A \times B$ has introduction rules that explain how to make ordered pairs, and elimination rules explaining that we can project the first and the second components from any element of $A \times B$. The definition of $A \times B$ does not start with the words "the collection of all ..." and neither does it say anywhere anything like "all elements of $A \times B$ are pairs" (but it follows from the definition that every element of $A \times B$ is propositionally equal to a pair). In constrast, the set-theoretic definition of $X \times Y$ is stated as "the set of all ordered pairs ...".

The notation $t : T$ signifies the fact that $t$ has the structure described by $T$.

A type $T$ is not to be confused with its extension, which is the collection of all objects of type $T$.  A type is not determined by its extension, just like a group is not determined by its carrier set. Furthermore, it may happen that two types have the same extension, but are different, for instance:

The type of all even primes larger than two: $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{iseven}(n) \times (n > 2)$.
The type of all odd primes smaller than two: $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{isodd}(n) \times (n < 2)$.

The extension of both is empty, but they are not the same type.

There are further differences between the type-theoretic $:$ and the set-theoretic $\in$. An object $a$ in set theory exists independently of what sets it belongs to, and it may belong to several sets. In contrast, most type theories satisfy uniqueness of typing: if $t : T$ and $t : U$ then $T \equiv U$. Or to put it differently, a type-theoretic construction $t$ has precisely one type $T$, and in fact there is no way to have just an object $t$ without its (uniquely determined) type.

Another difference is that in set theory we can deny the fact that $a \in A$ by writing $\lnot (a \in A)$ or $a \not\in A$. This is not possible in type theory, because $t : T$ is a judgement which can be derived using the rules of type theory, but there is nothing in type theory that would allow us to state that something has not been derived. When a child makes something from LEGO blocks they proudly run to their parents to show them the construction, but they never run to their parents to show them what they didn't make.


What is the actual time complexity of Gaussian elimination?

I think the answer is $\widetilde O(n^3 \log( \|A\| + \|b\|))$, where
we omit the (poly)logarithmic factors.  The bound is presented in
"W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann,
G. Villard. Solving sparse integer linear systems. Proc. ISSAC'06,
Genova, Italy, ACM Press, 63-70, July 2006", but it is based on a
paper by Dixon: "Exact solution of linear equations using P-adic
expansions, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Number 1,
137-141".


The book introduces two concepts, and warns not to confuse them with each other:

Encryption schemes: Which can have varying key lengths; and
Block ciphers: Which have fixed-length black and key lengths.

Chapter 3 of the book mainly speaks about encryption schemes. For instance, take a look at the proof of CPA-security of the CTR mode (Theorem 3.29, and Figure 3.8): The permutation $F_k$ used at the heart of the CTR construct can have varying key lengths.

However, chapter 5 mainly discusses block ciphers. These are practical constructs based on the theoretical ideas of encryption schemes (as the chapter title implies). The security of block ciphers (DES, AES, etc.) cannot be formally proved (at least at the present), since there exists no notion of concrete security, in contrast to asymptotic security.

That said, there has been some attempts at defining security notions for concrete security as well. Rogaway, for instance, has written a nice paper on defining security for "ordinary" hash functions (in contrast to "families" of hash functions).

A related question on CSTheory is Hardness Guarantees for AES, where the OP asked about provable measures for the AES block cipher.


Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

There are a (growing) number of parameterized complexity results where the existence of a polynomial-sized kernelization implies the collapse of the PH to the third level. The central technique is given in [1], building on prior work (referenced in [1]).

As a simple example, the $k$-Path problem is the parameterized version of the Longest Path problem:

  $k$-Path
  Instance: A graph $G$ and integer $k$.
  Parameter: $k$.
  Question: Does $G$ contain a path of length $k$?

This problem is in FPT (with somewhat practical algorithms), but in [2] they show that if it has a polynomially sized kernel (in $k$), then the PH collapses to $\Sigma^{P}_{3}$. (The current presentation is typically phrased as a negative kernalization result unless NP $\subseteq$ coNP/poly or coNP $\subseteq$ NP/poly, so searching for something like "no polynomial kernel unless" nets a lot of results.)

References

H. L. Bodlaender, B. M. P. Jansen, and S. Kratsch, "Kernelization lower bounds by cross-composition", SIAM J. Discrete Math., 28 (2014), pp. 277–305. [arXiv version]
H. L. Bodlaender, R. G. Downey, M. R. Fellows, D. Hermelin, "On problems without polynomial kernels", Journal of Computer and System Sciences, 75(8):423-434. 2009. [Stanford hosted version]


Implication of Exponential Time Hypothesis falseness?

One such result is by Megiddo and Vishkin. They proved that minimum dominating set in tournaments is in $QP$. Additionally, they showed that tournament dominating set has P-time algorithm if and only if SAT has subexponential time algorithm. Therefore, ETH falseness implies that tournament dominating set is in $P$ which seems unlikely.


Regularity of language with finite number of right derivatives

See Janusz Brzozowski's 1964 paper Derivatives of Regular Expressions. This is theorem 5.2 in the paper, and the proof is in Appendix 2.


An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002).

In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($r$ part of the input). A certain $\Sigma_3^p$-complete problem called "Minimum block decoder" can be found on p. 28 (see also $\Sigma_2^p$-complete "Minimal block encoder and decoder", p. 25).

I guess following the references should help in digging out more related problems.


any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

There are lots of overlaps between small world and scale-free, but I think much less so between those two and expanders.

The terms "small world" and "scale-free" are often used informally, but formal definitions are  often along the lines of:

Small-world means short average (or maximum) path length (typically $O(\log n)$, with $n$ vertices) and highly clustered (meaning that for any vertex $v$, the fraction of pairs of neighbors of $v$ which are adjacent is high)
Scale-free is often taken to mean that the degree distribution follows some variant of a power-law (e.g. power-law with cutoff, etc.), but more generally/informally is used to mean that the degree distribution is long-tailed, in contrast to, say, Erdos-Renyi random graphs which have a degree distribution that is exponentially concentrated around its mean.

Expander, of course, has a formal definition that is almost 100% standardized.

Expanders by their nature have logarithmic diameter, similar to small-world networks. Beyond that, however, as far as I know there is little overlap between the concepts.

In practice, expanders are often bounded-degree or even regular of bounded degree, whereas "real-world" graphs typically have a long-tailed degree distribution, with a small (but surprisingly large - e.g. not exponentially small) number of high-degree "hubs" (as they are usually called). Furthermore, scale-free graphs (almost by definition, depending on your definition) have a large number of vertices of very low degree - in most "real-world" graphs there are a large number of vertices of degree 1 or 2. This makes real-world graphs very unlike expanders, in that it is very easy to disconnect real-world graphs by removal of targeted edges, whereas expanders are by their nature highly connected. (Real-world graphs often also have the property that removal of random edges is very bad at disconnecting them.)

I'm sure there is something to be said about the use of spectral techniques for things like community detection, etc. in real-world networks, and from that viewpoint there may or may not be a little more overlap with expanders, but I'm not an expert in that area (maybe we can get Mark Newman to join cstheory.SE to comment...)


Why does Huffman coding eliminate entropy that Lempel-Ziv doesn't?

This was originally a comment, but it got too long.

If you look at DEFLATE, what is being compressed by Huffman is the output of LZ77; LZ77 works by (when this takes fewer bits than the raw data) sending an pointer earlier into the string being compressed, and a match length that tells how many symbols to take after the pointer. The theory shows that, even without additional compression, this technique eventually converges to the source entropy. However, in data compression, any time you have a distribution that isn't completely random, you might as well compress it. There's no reason to believe that the output of LZ77—the pointers and the match lengths—are completely random. They have to converge to complete randomness in the asymptotic limit, since LZ77 is asymptotically optimal, but in practice you only use a finite dictionary, so they presumably stay far enough away from being completely random that you win by doing further compression on them. Naturally, you use one Huffman code for the pointers and another for the match lengths, since these two processes have different statistics.

Why use Huffman rather than LZ for the second round of compression? The big advantage LZ has over Huffman is in treating dependencies between symbols. In English, if one letter is a 'q', the next is extremely likely to be a 'u', and so on. If the symbols are independent events, then Huffman is simpler and works just as well or better for short strings. For the output of LZ77, my intuition is that the symbols should be fairly independent, so Huffman should work better.


What type of mathematical problems interesting for TCS researchers?

Let us say I am able to give an algorithm which classifies all modules (algebraic structure) of some rank. Will that be interesting to TCS researchers?

Roughly speaking...

It will be interesting to applied mathematicians if they find that the algorithm is fast enough in practice in some sense.
It will be interesting to pure mathematicians if the algorithm gives new insight into the structure of modules or lets them compute examples that can be used to test conjectures.
And will be interesting to TCS researchers if there are also lower bounds on how fast an algorithm for this problem can possibly be, or if this problem is related to algorithms for other problems such as classifying rings, module isomorphism etc.

An example that was interesting to all three to varying degrees is Tarski's theorem on the real field.


Size of cuts in graphs drawn from $ G_{n,1/2}$

Perhaps what's implicit after "there are" is "asymptotically almost surely", which means that the property holds with probability tending to 1 as n tends to infinity; this is stronger than "in expectation".  You might want to check out a standard textbook on random graphs (e.g. by Alon-Spencer, Bollobas, or Janson-Luczak-Rucinski).


Ensemble of tree decompositions for all-pairs problem

I would simply do as follows:

Start with a tree decomposition $T$ of $G$. Each time you would like to compute the number of self avoiding walks on $G$ passing through $u$ and some other node, do dynamic programming on the tree decomposition $T'$ obtained from $T$ by adding $u$ to each bag of the tree decomposition. The width of $T'$ is at most the width of $T$ plus one, and you cannot hope for anything better in general.


Multidimensional knapsack STRONGLY NP-complete

In the paper titled "ON MULTIDIMENSIONAL PACKING PROBLEMS" that appeared in SODA and then in SICOMP (http://epubs.siam.org/doi/abs/10.1137/S0097539799356265) we considered several packing problems where items are d-dimensional vectors. We discuss PIPs which are the same as as multidimensional knapsack (we mention this) and their approximability when d is not fixed. You can find hardness results as function of d in that paper.


Is solving the following system of boolean equations NP-hard?

[Now that the question's been clarified I'll post my previous comment as an answer.]
It's in $\mathsf{P}$. Start with unit propagation. Afterwards, what's left on the right-hand sides will be monotone, so will be satisfied by setting all remaining variables to True.
(If you want to count the number of solutions, on the other hand, that might be harder.)


Suresh asked me to assemble my comments above into an answer, so here it is. I'm not really sure it's an answer to the original question, though, since it's not obvious how to make it polynomial time when the dimension of the input Euclidean space is non-constant. It does at least have the advantage of avoiding any problem with large $1/\epsilon$ as the original question asks, because it doesn't involve any approximation, and it looks polynomial for constant $d$.

Anyway: from integral geometry, there is a standard measure on sets of hyperplanes in $d$-dimensional Euclidean space that is invariant under Euclidean congruences. It has the property that the length of any bounded-length curve $C$ is proportional to the measure of the hyperplanes that cross $C$ (with multiplicity, meaning that if a hyperplane crosses $C$ twice then it contributes twice to the total measure of the hyperplanes crossing $C$). In particular if $C$ is a line segment then the multiplicity complication doesn't arise and we can normalize the measure on the hyperplanes crossing $C$ to be exactly the length of $C$. (The hyperplanes containing $C$ have measure zero, so don't worry about infinite multiplicity.)

Now, given a set of n points in d-dimensional space, make an $\ell_1$ coordinate for each of the partitions of the points into two subsets induced by a hyperplane that doesn't pass through any of the points. Give the points on one side of the partition coordinate value zero and the points on the other side of the partition coordinate value equal to the measure of the set of hyperplanes inducing that partition.

If $p$ and $q$ are any two of the $n$ points, let $K$ be the set of hyperplanes crossing line segment $pq$, and let $K_i$ be the subsets of $K$ formed by each possible hyperplane partition that has $p$ on one side and $q$ on the other. Then $K$ is the disjoint union of the $K_i$, and the coordinate differences between $p$ and $q$ are just the measures of the subsets $K_i$. Therefore, the $\ell_1$ distance between the coordinatizations of $p$ and $q$ (the sum of the measures of the $K_i$) is the measure of $K$, which is just the original $\ell_2$ distance between $p$ and $q$.

For computational geometers, an alternative description of the same construction may be helpful: use projective duality to transform the $n$ input points into $n$ hyperplanes, and separating hyperplanes into points. The integral geometry measure on sets of hyperplanes is then transformed into a more standard measure on sets of points, the distance between $p$ and $q$ dualizes to the measure of the double wedge between two hyperplanes, and the hyperplane arrangement partitions this double wedge into smaller cells. The coordinate value for a point is either the measure of one of the cells in the arrangement (if the dual hyperplane is below that coordinate's cell) or zero (if the dual hyperplane is above the cell). Therefore, the $\ell_1$ distance between $p$ and $q$ is just the sum of the measures of the cells in the double wedge, which is the same as the measure of the whole double wedge. This dual point of view also makes it easy to calculate the dimension of the embedding found in this way: it's just the number of cells in the hyperplane arrangement, which is $O(n^d)$, or more precisely at most $\sum_{i=0}^d{n\choose i}$.

So far, this gives a completely deterministic and exact embedding in $\ell_1^{O(n^d)}$. But we wanted a smaller dimension, $\ell_1^{n\choose 2}$. Here's where Luca's comment about Carathéodory's theorem comes in. The set of $\ell_1$-representable metrics forms a polyhedral cone in the $n\choose 2$-dimensional space of all functions from unordered pairs of points to real numbers, and the geometric argument above says that the Euclidean metric belongs to this cone. The points on the extreme rays of the cone are one-dimensional $\ell_1$ pseudometrics (in which the points are split into two sets, all distances within a single set are zero, and all distances across the split are equal), and Carathéodory says that any point within the cone (including the one we care about) can be represented as a convex combination of points on extreme rays whose number is at most the dimension of the ambient space, $n\choose 2$. But a convex combination of at most $n\choose 2$ one-dimensional $\ell_1$ metrics is a $\ell_1^{n\choose 2}$ metric.

Finally, how can we go about actually computing the $n\choose 2$-dimensional embedding? At this point we have not just a point in the $n\choose 2$-dimensional convex cone of $\ell_1$ metrics (the distance metric we started with), but we also have a set of $O(n^d)$ extreme points of the cone (corresponding to the partitions of the input into two subsets induced by hyperplanes) such that our metric is a convex combination of these extreme points — for small $d$, this is a big improvement over the $2^n-2$ extreme rays that the cone has overall. Now all we need to do is apply a greedy algorithm that gets rid of extreme points from our set, one by one, until only $n\choose 2$ of them are left. At each step, we need to maintain as an invariant that our metric is still inside the convex hull of the remaining extreme points, which is just a linear programming feasibility problem, and if we do this Carathéodory will ensure that there always remains a set of $n\choose 2$ extreme points whose convex hull contains the input metric.


Non constructible functions and anomalous results

Borodin's Gap Theorem: For every total computable function $g(n) \geq n$, there is a total computable function $t$ such that $DTIME[g(t(n))] = DTIME[t(n)]$.

In fact, this holds for any Blum complexity measure in place of $DTIME$.

See also the wikipedia page and references therein.


Small graph with gap between chromatic and vector chromatic number?

I make my comment an answer.
If we don't require that $\chi_v(G)$ is an integer then the smallest example is $G=C_5$ (a cycle on 5 vertices):
$$\chi_v(C_5) = \sqrt{5} < 3 = \chi(C_5) . \qquad\text{[Lovász]}$$

It's not hard to transform this example to an example where $\chi_v(G)$ is integer. Let $G_1$ be a union of two 5-cycles $C_5^{(1)}$ and $C_5^{(2)}$ in which every vertex from $C_5^{(1)}$ is connected to every vertex in $C_5^{(2)}$. Let $G_2=K_5$. Finally, let $G$ be the union of $G_1$ and $G_2$. Then
\begin{align*}
\chi(G) &= \max(\chi(G_1), \chi(G_2)) = \chi(G_1) = 6.\\
\chi_v(G) &= \max(\chi_v(G_1), \chi_v(G_2)) = \max(2\cdot \sqrt{5}, 5) = 5.
\end{align*}


Approximating max degree $3$ perfect matching count?

Dagum and Luby show (using a construction credited to Dahlhaus and Karpinski) how to construct, given a bipartite graph $G$, a bipartite graph $G'$ of maximum degree $3$ such that $G'$ has exactly as many perfect matchings as $G$ (see Theorem 6.2.). Then from $G'$ you can construct a graph $G''$ with average degree arbitrarily close to $2$ and twice as many perfect matchings as $G'$, as I explained here. Both constructions are in polynomial time. Therefore, the best polytime deterministic approximation to the number of perfect matchings of a graph of maximum degree 3, and average degree in $[2,3]$ is equal to the best polytime deterministic approximation to the permanent of a 0-1 matrix. As far as I know, this is the factor $2^n$ approximation achieved by Gurvits and Samorodnitsky.

(It may be helpful to note that a $\exp(n^\varepsilon)$ approximation for $\varepsilon < 1$ would imply an FPTAS.)


Version control for collaboration (with word-level diffs)?

I've used git to collaborate on some documents written in latex. You'll have to adhere to some rules:

Start each sentence on a new line, latex ignores these newlines as long as there is no blank line
Use the same configuration for formatting (tab/spaces/max text width)
For best results, create a .gitattributes file in your repository and add the line *.tex    diff=tex. This makes diff aware of the tex syntax and leads to more meaningful output.

You can then use git diff --color-words and gitk --color-words to see word differences (also see this article Word-by-word diffs in Git on how to configure git to always use word-diff algorithm for displaying the git diff/git log).

To reduce the manual merges, I can recommend using separate files for sections and subsections (depending on the size of your document).


Vector Addition Systems with finite "obstacles"

The idea is based on a discussion I got with Grégoire Sutre this afternoon.

The problem is decidable as follows.

A Petri net $T$ is a finite set of pairs in $\mathbb{N}^d\times\mathbb{N}^d$ called transitions. Given a transition $t=(\vec{u},\vec{v})$, we denote by $\xrightarrow{t}$ the binary relation defined on the set of configurations $\mathbb{N}^d$ by $\vec{x}\xrightarrow{t}\vec{y}$ if there exists a vector $\vec{z}\in\mathbb{N}^d$ such that $\vec{x}=\vec{u}+\vec{z}$ and $\vec{y}=\vec{v}+\vec{z}$. We denote by $\xrightarrow{T}$ the one step reachability relation $\bigcup_{t\in T}\xrightarrow{t}$. The reflexive and transitive closure of this relation is denoted by $\xrightarrow{T^*}$.

Let $\leq$ be the classical componentwise partial order over $\mathbb{N}^d$ and defined by $\vec{u}\leq \vec{x}$ if there exists $\vec{z}\in\mathbb{N}^d$ such that $\vec{x}=\vec{u}+\vec{z}$. The upward closure of a set $\vec{X}$ of $\mathbb{N}^d$ is the set ${\uparrow}\vec{X}$ of vectors $\{\vec{v}\in\mathbb{N}^d \mid \exists \vec{x}\in\vec{X}.\,\vec{x}\leq\vec{v}\}$. The downward closure of a set $\vec{X}$ is the set ${\downarrow}\vec{X}$ of vectors $\{\vec{v}\in\mathbb{N}^d \mid \exists \vec{x}\in\vec{x}.\,\vec{v}\leq\vec{x}\}$.

Notice that if $\vec{U}={\uparrow}\vec{B}$ for some finite set $\vec{B}$ of $\mathbb{N}^d$ and if $T$ is a Petri net, we can compute a new Petri net $T_{\vec{B}}$ such that for every configurations $\vec{x},\vec{y}$, we have $\vec{x}\xrightarrow{T}\vec{y}$ and $\vec{x},\vec{y}\in\vec{U}$ if, and only if, $\vec{x}\xrightarrow{T_{\vec{B}}}\vec{y}$. In fact, if $t=(\vec{u},\vec{v})$ is a transition, then for each $\vec{b}\in\vec{B}$, let $t_{\vec{b}}=(\vec{u}+\vec{z},\vec{v}+\vec{z})$ where $\vec{z}$ is the vector in $\mathbb{N}^d$ defined componentwise by $\vec{z}(i)=\max\{\vec{b}(i)-\vec{u}(i),\vec{b}(i)-\vec{v}(i),0\}$ for every $1\leq i\leq d$. Notice that $T_{\vec{U}}=\{t_{\vec{b}} \mid t\in T\,\vec{b}\in\vec{B}\}$ satisfies the requirement.

Now, assume that $T$ is a Petri net, $\vec{O}$ the set of obstacle. We introduce the finite set $\vec{D}={\downarrow}\vec{O}$. Observe that we can compute effectively a finite set $\vec{B}$ of $\mathbb{N}^d$ such that ${\uparrow}\vec{B}=\mathbb{N}^d\backslash\vec{D}$. Let $R$ be the binary relation defined over $\mathbb{N}^d\backslash \vec{O}$  by $\vec{x} R \vec{y}$ if $\vec{x}=\vec{y}$, or there exists $\vec{x}',\vec{y}'\in \mathbb{N}^d\backslash \vec{O}$ such that $\vec{x}\xrightarrow{T}\vec{x}'\xrightarrow{T_{\vec{B}}^*}\vec{y}'\xrightarrow{T}\vec{y}$.

Now, just observe that if there exists a run from the initial configuration $\vec{x}$ to the final one $\vec{y}$ that avoid the obstacle $\vec{O}$, then there exists one that avoid the obstacle in $\vec{O}$ and that passes by configurations in $\vec{D}\backslash \vec{O}$ at most the cardinal of that set. Hence, the problem reduces to select non-deterministically distinct configurations $\vec{c}_1,\ldots,\vec{c}_n$ in $\vec{D}\backslash \vec{O}$, fix $\vec{c}_0$ as the initial configuration $\vec{x}$, $c_{n+1}$ as the final one $\vec{y}$, and check that $\vec{c}_j R \vec{c}_{j+1}$ for every $j$. This last problem reduces to classical reachability questions for Petri nets.


Why it's impossible to declare an induction principle for Church numerals

The question you are asking is interesting and known. You are using the so-called impredicative encoding of the natural numbers. Let me explain a bit of the background.

Given a type constructor $T : \mathsf{Type} \to \mathsf{Type}$, we might be interested in the "minimal" type $A$ satisfying $A \cong T(A)$. In terms of category theory $T$ is a functor and $A$ is the initial $T$-algebra. For example, if $T(X) = 1 + X$ then $A$ corresponds to the natural numbers. If $T(X) = 1 + X \times X$ then $A$ is the type of finite binary trees.

An idea with long history is that the initial $T$-algebra is the type
$$A \mathrel{{:}{=}} \prod_{X : \mathsf{Type}} (T(X) \to X) \to X.$$
(You are using Agda notation for dependent products, but I am using a more traditional mathematical notation.) Why should this be? Well, $A$ essentially encodes the recursion principle for the initial $T$-algebra: given any $T$-algebra $Y$ with a structure morphism $f : T(Y) \to Y$, we get an algebra homomorphism $\phi : A \to Y$ by
$$\phi(a) = a \, Y \, f.$$
So we see that $A$ is weakly initial for sure. For it to be initial we would have to know that $\phi$ is unique as well. This is not true without further assumptions, but the details are technical and nasty and require reading some background material. For instance, if we can show a satisfactory parametricty theorem then we win, but there are also other methods (such as massaging the definition of $A$ and assuming the $K$-axiom and function extensionality).

Let us apply the above to $T(X) = 1 + X$:
$$\mathsf{Nat} =
  \prod_{X : \mathsf{Type}} ((1 + X) \to X) \to X =
  \prod_{X : \mathsf{Type}} (X \times (X \to X)) \to X =
  \prod_{X : \mathsf{Type}} X \to (X \to X) \to X.
$$
We got Church numerals! And we also understand now that we will get a recursion principle for free, because the Church numerals are the recursion principle for numbers, but we will not get induction without parametricity or a similar device.

The tehcnical answer to your question is this: there exist models of type theory in which the type SimpleNat contains exotic elements that do not correspond to numerals, and moreover, these elements break the induction principle. The type SimpleNat in these models is too big and is only a weak initial algebra.


Directed graph with bounded in-deg can be partitioned in a balanced way

This is a special version of the Beck-Fiala theorem.
Define a set system on the vertices whose sets are the out-neighborhoods of the vertices.
The in-degree condition will give that every element is in at most $n$ sets.
The theorem states that in this case the elements can be colored with red and blue such that the difference of the red and blue elements in any set is at most $2n-1$.
This means that in your digraph the out-degree of each vertex $v$ in the corresponding subgraph is between $d(v)/2-n$ and $d(v)/2+n$, so for your specific question $c(n)\ge 6n$ is sufficient.


For the latter, this discussion is a good starting point.  For the former, I guess finding a random point in the ball, rounding it to a grid point, then checking that grid point is in the ball.


Proof of Nullstellensatz certificate degree

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

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


Difficulty in understanding the quantum algorithm for the abelian hidden subgroup problem

This classical post-processing exploits several non-trivial group theoretical properties of Abelian groups. I wrote a didactic explanation of how this classical algorithm works here [1]; other good sources to read about are [2, 3, 4].

So, measuring at the end of the algorithm in the standard basis will give you elements of $H^{*}$ uniformly at random. It is not hard to check that the set $H^{*}$ is a (finite Abelian) subgroup of the character group $G^{*}$; due to, after $O(\log{|G|})$ measurement rounds a generating set of $H^{*}$ is obtained with probability exponentially close to one.

The most technical part is how to reconstruct $H$ given a generating set of $H^{*}$. Let us focus on this problem from now on. For this, we will need some rudiments from character theory.

Character Theory

First of all, remember that, when $G$ is finite Abelian, characters form a group isomorphic to $G$ and that they can be written as
\begin{equation}
\chi_g(h)=\exp{\left(2\pi i \sum_{i=1}^{m} \frac{g(i)h(i)}{d_i}\right)}.
\end{equation}
The label $g$ of the character $\chi_g$ is an element of $G$. The map $g\rightarrow \chi_g$ defines an isomorphism between $G^*$ and $G$, so that we can identify both groups.

Now, given $H$, the set $H^*$ you describe is calle the orthogonal subgroup of $H$ or, depending on the source, the annihilator of $H$. This subgroup has some important mathematical properties:

First of all, $H^*$ is also subgroup of $G$;
It is dual to $H$, in the sense that, if we consider the
double annihilator subgroup $H^{**}$, this subgroup is isomorphic to
$H$: i.e., $H\cong H^{**}$. This guarantees that the solutions to the system of equations $$\chi_g(h)=1,\quad \textrm{ for every } g\in H^*$$
are precisely the elements of the subgroup $H$ that you want.

Linear Equations over Groups

Now, a key observation that we can use is the following (I will follow  [1] for this part): the former systems of equations can be re-written as a ''system of linear equations over finite Abelian groups''. By that, I mean a problem where the input are to finite Abelian groups $X$, $Y$; an element $b\in Y$; a group homomorphism$ \alpha:X\rightarrow Y$ and the task is to find the solutions of the equation $$\alpha(x)=b$$ You can show that any homomorphisms can be written as a matrix $A$, in such a way that the problem above can be re-expressed as
\begin{equation}
A x=
\begin{pmatrix}
a_1(1) & a_2(1) & \cdots & a_n(1)\\
a_1(2) & a_2(2) & \cdots & a_n(2)\\
\vdots & \vdots & \cdots & \vdots\\
a_1(m) & a_2(m) & \cdots & a_n(m)
\end{pmatrix}
\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d_1\\
\mod d_2\\
\vdots\\
\mod d_m
\end{matrix}
= b
\end{equation}
where we assume $Y=\mathbb{Z}_{d_{1}}\times\cdots\times \mathbb{Z}_{d_{m}}$.

The final key observation is that there exist efficient classical algorithms to decide whether these systems admit solutions, count them and find them (we survey some in [1]). The set of solutions is always of the form $x_0+\ker{\alpha}$, where $x_0$ is a particular solution and $\ker{\alpha}$ is the kernel of $\alpha$ (a subgroup of $X$). These classical algorithms can find a particular solution of the system and compute a generating set of $\ker{\alpha}$. These classical algorithms make crucial use of Smith Normal Forms to rewrite the system in an almost diagonal form (some other intermediate steps are necessary, but that should give you the intuitive picture).

The system of equations that you obtain in your case encodes the hidden subgroup $H$. In particular is of the form $\Omega x = 0$, for some group homomorphism $\Omega$. The kernel of $\Omega$ is precisely the hidden subgroup. A particular solution in that case is 0, the trivial one.


The answer depends on $k$, $m$, and $n$. Exact counts are generally not known, but there is a "threshold" phenomenon that for most settings of $k$, $m$, $n$, either nearly all $k$-SAT instances are satisfiable, or nearly all instances are unsatisfiable. For example, when $k=3$, it has been empirically observed that when $m < 4.27 n$, all but a $o(1)$ fraction of 3-SAT instances are satisfiable, and when $m > 4.27n$, all but a $o(1)$ fraction are unsatisfiable. (There are also rigorous proofs of bounds known.)

One starting point is "The Asymptotic Order of the k-SAT Threshold".

Amin Coja-Oghlan has also done a lot of work on these satisfiability threshold problems.


This is hard for planar graphs, at least for six colours or more. See
"Inapproximability of the Tutte polynomial of a planar graph" by Goldberg and Jerrum


The worst-case scenario(s) for MAX3E SAT

In fact, we are able to perform "clause counting".  The total number of satisfied clauses for all remaining truth assignments is proportional to the expected number of satisfied clauses for a random truth assignment, which is the sum of the probabilities $P(C_i | \{x, y, ...\})$, where $C_i$ is the $i$-th clause, and $\{x,y,...\}$ are the literals that have been assigned to be true.  In particular, if there are three distinct literals per clause, and we are promised a satisfying truth assignment (so a variable and its negation never occur in the same clause), and a single literal $x$ has been assigned to be true, then the probability that a particular clause is satisfied by a random assignment of the remaining variables is $3/4$ if the clause contains $\neg{x}$, or $7/8$ if the clause contains neither $x$ nor $\neg{x}$, or $1$ if the clause contains ${x}$.  That is,
$$P(C_i | \{x\}) = \frac{7}{8} + \frac{1}{8}n_i(x),$$
where $n_i(x) \in\{-1, 0,1\}$.  So the literal picked out by "clause counting" will be the one that maximizes $\sum_{i}n_i(x)=N(x)$, where the sum is over all clauses, and $N(x)$ is the (net) number of occurrences of the literal $x$ in the entire formula.

To use this to construct a counterexample, we need a literal that is false (say) in all satisfying assignments, but that maximizes the above count.  We can force a literal to be false with four occurrences of its negation, as follows:
$$
\begin{eqnarray}
\neg{a} &\equiv& \neg{a} \wedge (b \vee \neg{b}) \wedge (c \vee \neg{c}) \\
&\equiv& (\neg{a} \vee b \vee c) \wedge (\neg{a} \vee b \vee \neg{c}) \wedge (\neg{a} \vee \neg{b} \vee c) \wedge (\neg{a} \vee \neg{b} \vee \neg{c}) \\
&\equiv& \Phi(\neg{a};b,c),
\end{eqnarray}
$$
for any additional literals $b$ and $c$; this subformula has $N(a)=-4$ and $N(b)=N(c)=0$.  We then need to include enough occurrences of $a$ in the rest of the formula to make $N(a)$ the largest count.  This can be done using
$$
\Omega(a;d,f) \equiv (a \vee d \vee f) \wedge (a \vee d \vee \neg{f}) \wedge (a \vee \neg{d} \vee f),
$$
which is equivalent to $a \vee (d \wedge f)$, and has $N(a)=3$ and $N(d)=N(f)=1$.  So a counterexample with four variables and ten (unique) clauses is
$$
\Phi(\neg{a}; x_1, x_2) \wedge \Omega(a; x_1, x_3) \wedge \Omega(a; x_2, x_3),
$$
which has $N(a)=2$ and $N(x_1)=N(x_2)=N(x_3)=1$, and a unique satisfying assignment: $\{\neg{a}, x_1, x_2, x_3\}$.


Shortest string containing all fixed-length substrings

This is called a de Bruijn sequence ( http://en.wikipedia.org/wiki/De_Bruijn_sequence ).  You can generate it by taking an Euler tour of a de Bruijn graph, but there are also other ways.  You can use de Bruijn sequences to break into 1990s-era cars efficiently ( http://everything2.com/title/Weak+security+in+our+daily+lives ) among many other applications.


The query complexity used in this paper is $O(1)$ and $O(poly(logn))$.

For Lemma 3.1 there is a note that the query complexity used is $O(1)$.

If the question is how Lemma 3.1 generalizes to non-constant query complexity, this does present a problem outside of $O(poly(f(n)))$.

This problem is sidestepped by composing a verifier that reduces query complexity to $O(1)$ (Lemma 4.4).


Is there software for graph product calculation and visualization?

I think that Sage is the right thing for this task.

Example.

sage: G = digraphs.Circuit(40)
sage: G = G.lexicographic_product(G)
sage: G.show()

Other graph products and algorithms are available as well.


Is there a 'very fast growing' hierarchy that would capture System F?

Typically, fast growing hierarchies are characterized by ordinal notations, which are really just ways to express fast-growing functions (but it's sometimes convenient to see them as ordinals in the mathematical sense).

There is a somewhat generic way of assigning an ordinal (notation) to a consistent theory, though it is very non-constructive. For various technical reasons, the ordinal for $\mathrm{PA}_2$ corresponds to the fast growing functions expressible in system $F$.

So the question really is:

  Is there an ordinal notation for $\mathrm{PA}_2$?

As far as I am aware, we do not know the answer to this question, and it is a very important open question in proof theory/ordinal analysis.

The following mathoverflow question explains this idea in more detail:

https://mathoverflow.net/questions/144041/proof-theoretic-ordinal-of-zfc-or-consistent-zfc-extensions


Does Dirac's theorem on Hamiltonian cycles only apply to undirected graphs?

While Dirac's theorem wasn't intended/proved for directed graphs, it was extended to directed graphs by GHOUILA-HOURI in 1960 ("Une condition suffisante d’existence d'un circuit hamiltonien").

Their requirements, however, were that each vertex should have both out-degree and in-degree of at least $n/2$, which is not the case in your graph.

One of the original conditions of GHOUILA-HOURI, as Saeed mentioned, is that the graph is strongly connected. In fact, the degree conditions are strong enough for only diameter $\leq 2$ graphs to be considered.


Topological properties of Delaunay triangulations

Yes. See

Dillencourt, Michael B.; Smith, Warren D. Graph-theoretical conditions for inscribability and Delaunay realizability. Discrete Math. 161 (1996), no. 1-3, 63–77.

However, if a topological triangulation has no separating triangles, and no chords connecting pairs of vertices on its outer face, then it is always realizable as a Delaunay triangulation.


Well, here's a not-horrible upper bound over $\mathbb{C}$: $\mathsf{PSPACE}$, or assuming the Riemann Hypothesis, $\mathsf{AM}$. This is because for any given patterns of zeros for $A,B$, checking whether one can make $AB=I_n$ is checking whether a certain system of $n^2$ integer polynomial equations has a solution in $\mathbb{C}$, and this can be done in these upper bounds, by Koiran.

Another approach is to try to leverage the fact that this is in fact a system of bilinear equations. Solving bilinear equations is equivalent to finding "rank 1" solutions to linear equations. I've been trying to determine if there are better upper bounds for solving bilinear systems in general, but with no luck so far. It's also possible that one could leverage the particular structure of these bilinear equations to get something better than what's known in general...


What relation is between constraint satisfaction problems and constraint programming?

First of all, I cannot help but point out a practice I consider bad in the way you defined your question. You are comparing a class of algorithms with a class of problems. Although closely related, they are not the same. As an example, consider the halting problem. It is a very well defined problem. However, we know that no Turing Machine can diagnose it. Given the Church-Turing thesis, this is the same as saying that there is no algorithm for this problem.

However, one can rephrase the question such that the items compared are of the same nature. Consider constraint programming (CP) as the computational model A and
boolean formulas as the computational model B. I chose boolean formulas because SAT is probably the most known CSP and furthermore boolean formulas have a nice property, which I will use below.

Although I have programmed in Prolog, I cannot say I have a good knowledge of constraint programming. However, I am almost certain that they are Turing-complete. Since they use constraints, one could use them to "simulate" head moves,e.g. if [constraint] then move to this cell . Furthermore, one could write contents into that tape. Therefore, constraint programming is as powerful as Turing Machines. Since all programs in CP are algorithms, they can be simulated by a universal TM. Thus CP and TM have the same expressibility.

One might think at this point that CP is a stronger model that boolean formulas. However, in Arora and Barak's book "Computational Complexity:A Modern Approach", in chapter 2, a proof is given that any boolean function has an equivalent boolean formula ( the theorem is labeled "Universality" of AND,OR and NOT). On a given input, the formula is satisfied if and only if the boolean function is true for this input.  As an informal proof, consider that those 3 operators can express any piece of hardware. Furthermore, every other input can be translated into a boolean one. Therefore, every TM can be simulated as a boolean formula. Thus boolean formulas are Turing-complete. Furthermore, there is a TM that can diagnose the satisfiability of a boolean formula. Therefore, boolean formulas and TMs are equivalent.

It follows that the two models have the same expressibility.


Over lunch in Brussels we proved this problem is NP-Hard by a fairly short reduction from 3SAT. Our proof doesn't lead to an inapproximability result (yet). We'll think more about it.

Roughly, you transform a 3-SAT instance (with n variables and c clauses) into a series of permutations structured as follows:

1...n for numbering the n variables
n+1 used by the variable gadget
n+2, n+3 representing the 1st clause
...
n+2j, n+2j+1 representing the jth clause
n+2c+2 used by the garbage collector

variable xi is represented by the permutation
1,...,i-1,n+1,i+1,...,n,i,...
and swapping n+2j+1, n+2j for every clause where j where xi appears;
and  the permutation
1,...,i-1,n+1,i+1,...,n,i,...
and swapping n+2j+1, n+2j for every clause where j where -xi appears.

Then we use the garbage collector to place each number in a position where it could not appear otherwise. To place x in position y, we put y in position n+2c+2 and n+2c+2 in position x. We will have exactly n+2c-1 such garbage collectors for each variable and 2(n+2c-1) for each clause. The 3SAT is satisfiable iff we can choose exactly one of the 2 permutations for each variable, iff the permutation set cover has a solution of size n+(n+2c-1)(n+2c).

There are probably some minor details missing for small instances.

Stefan.


Minimizing the gaps with incremental capacity

Here's a poly-time dynamic-programming algorithm.
Lemma 1. The problem in the post has a poly-time dynamic-programming algorithm.
Proof sketch. Fix an input $(\zeta, c)$ over time slots $\{1,2,\ldots, n\}$.
For each $t, p\in \{0, 1,\ldots, n\}$, define subproblem $M(t, p)$ as follows.  Consider the problem restricted to the first $t$ time slots.  (That is, the problem over time slots $\{1,2,\ldots, t\}$, with $\zeta$ and $c$ restricted to those time slots.)  For this restricted problem, consider just those solutions that have total penalty $p$ and (if $t\ge 1$) do use slot $t$.  Define $M(t, p)$ to be the maximum, over all such solutions, of the capacity $C(t)$ achieved by that solution.  (Or $-\infty$ if there are no such solutions.)
The desired answer is $\min \{ p + \lfloor (n-t)/2\rfloor : t,p\in\{0,\ldots,n\},\, M(t, p) \ne -\infty\}$.
Then $M(0, 0) = 0$ and $M(0, p) = -\infty$ for $p>0$.  For $t>0$,  the following recurrence relation holds.
$M(t, p)$ is the maximum, over $s\in\{0,1,\ldots,t-1\}$, of
$$\begin{cases}
M(s, p-\lfloor(t-s-1)/2\rfloor) -c(t) + \sum_{i=s+1}^t \zeta(i)
& \scriptsize\textit{ (if that quantity is well-defined and non-negative)} \\
-\infty & \scriptsize\textit{ (otherwise). }
\end{cases}
$$
Here's the intuition.  Consider the possible solutions for the first $t$ time slots that use slot $t$ and achieve total penalty $p$.  Partition these solutions according to their last slot used, say, slot $s$, before slot $t$.  (Or $s=0$ if slot $t$ is the first slot used.)  Given $s$, such a solution consists of some solution $S_s$ for slots $1,2,\ldots, s$ (with slot $s$ used if $s>0$), followed by unused slots $s+1,s+2,\ldots, t-1$, followed by the used slot $t$.
The penalty incurred for the size-$(t-s)$ block of unused slots $s+1,\ldots, t-1$ is $\lfloor (t-s)/2\rfloor$.  So the cumulative penalty incurred by $S_s$ must be $p$ minus this.  The capacity $C(t)$ at time $t$ must be the capacity $C(s)$ achieved by $S_s$ at time $s$ plus the additional capacity added for unused slots $s+1,\ldots, t$, minus $\zeta(t)$ for using slot $t$.  So $C(t)$ will be maximized when $C(s)$ is maximized (over all solutions $S_s$ with appropriate penalty).  This is why the recurrence relation holds.
There are $O(n^2)$ subproblems, and for each the right-hand side of the recurrence can be evaluated in time $O(n)$ (with appropriate preprocessing), so this yields an $O(n^3)$-time dynamic-programming algorithm. $~~\Box$.


Have imperative programs been defined like this?

Short answer: yes.

Longer answer -- there probably isn't a unique reference but control flow graphs (essentially what you describe) and their precursors, flowcharts are Old. Here are three random references from antiquity to something very recent that use minor modifications of the model. The latter two define the model fairly precisely. You'll find a lot of lattices in the second paper.

Assigning Meaning to Programs, Robert Floyd, 1967.
Systematic Design of Program Transformation Frameworks by Abstract Interpretation, Patrick Cousot and Radhia Cousot, POPL 2002.
Assertion Checking Unified, Sumit Gulwani and Ashish Tiwari, VMCAI 2007.


Is there a PSPACE-intermediate language?

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

  Corollary 13:

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

  Proof:

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

  Main theorem:

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

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

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

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

(note: I updated the names to current ones)

There are two interpretations for monotone QBF:

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


Every instance of Q can be transformed into an instance of the Multiple Set Cover Problem, where the locations are the intervals $[l_i,r_i]$, covering a consecutive sequence of demand points (=integers $d_i$).


Worst number of questions needed to learn a monotonic predicate over a poset

This is not a complete answer, but it's too long to be a comment.

I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight.

Consider the following poset.  The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable.  (The Hasse diagram is a $4$-cycle).

Let me identify the monotone properties with the upsets of the poset.  This poset has seven upsets: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$, and this poset has seven antichains since the antichains are in one-to-one correspondence with the upsets.  So, $\lceil \log_2 N_X \rceil=\lceil \log_2 7 \rceil = 3$ for this poset.

Now, by adversary argument I'll show that any strategy needs at least four queries (so needs to query all elements).  Let's fix an arbitrary strategy.

If the strategy first queries $a_1$, then the adversary answers "$P(a_1)$ doesn't hold."  Then, we are left with five possibilities: $\emptyset$, $\{b_1\}$, $\{b_2\}$, $\{b_1,b_2\}$, $\{a_2,b_1,b_2\}$.  Thus, to determine which is the case, we need at least $\lceil \log_2 5\rceil = 3$ more queries.  In total, we need four queries.  The same argument applies if the first query is $a_2$.

If the strategy first queries $b_1$, then the adversary answers "$P(b_1)$ holds."  Then, we are left with five possibilities: $\{b_1\}$, $\{b_1,b_2\}$, $\{a_1,b_1,b_2\}$, $\{a_2,b_1,b_2\}$, $\{a_1,a_2,b_1,b_2\}$.  Therefore, we need at least three more queries as before.  In total, we need four queries.  The same argument applies when the first query is $b_2$.

If we take $k$ parallel copies of this poset, then it has $7^k$ antichains, and thus the proposed bound is $\lceil \log_2 7^k \rceil = 3k$. But, since each of the copies needs four queries, we need at least $4k$ queries.

Probably, there is a larger poset with larger gap.  But this argument can only improve the coefficient.

Here, the problem looks to be a situation where no query partitions the search space evenly.  In such a case, the adversary can force the larger half to remain.


The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms.

Context free languages live in the complexity class $LOGCFL.$ This class is equivalently characterized by log depth semi-unbounded circuits. These are polynomial sized circuits wherein OR gates have unbounded fan-in and AND gates have bounded fan-in (say 2). By increasing depth by a log factor, we can replace every unbounded fan-in OR gate with bounded fan-in ORs. This put the problem in $NC^2.$ It is not difficult to see how $NC^2$ can be evaluated by a $DSPACE(\log^2(n))$ by say a depth first search that maintains the left/right sequence of children at the gates explored thus far. The result goes back to the Lewis-Hartmanis paper. And while this improves David's space bound,  this can take $n^{\log n}$ time. We do not know any better.

The traditional way to understand time space tradeoff is to use pebble games. There have been a few papers on CYK; a more recent attempt is in the first part of this presentation. Here it is shown that (a) linear space can be achieved at exponential time and (b) if time is restricted to $O(n^2)$, then CYK would use at least $n^2$ space.

Certainly a very interesting problem worthy of a look.


Complexity of finding Exact Size Cut-Sets in Bipartite Graphs

The problem of bipartite exact cuts is NP-Complete, as shown here by a reduction from exact cuts in general graphs.


No, such an algorithm cannot exist.

Assume $t$ comparisons per element are allowed.

For a start, consider the situation of merging two lists, one of size
one, and the other of size $2^t$.
There are $2^t+1$ possible results, and an easy adversarial argument
shows that the element in the small list needs to participate in $t+1$ comparisons,
and this element has to go to the trash.

From this it is easy to construct an instance with two lists of size $n$
that consists of $n/2^t$ such small situations, and hence $n/2^t$ elements
have to go to the trash.

Hence, as long as $t$ is constant, it is impossible to have a trash of
$o(n)$.

On a side note, it seems that it is possible to match this bound by an algorithm where every element is compared with roughly log of the size of the surrounding part of the other list.  If this is of interest, I will try to work out the details.


Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?

The problem of determining whether a sentence of Presburger arithmetic is true is in between 2-NEXP and 2-EXPSPACE. When the number of quantifier alternations is fixed and at least two, the problem is in between NEXP and EXPSPACE. The existential fragment is NP-complete. For more details, see e.g. Christoph Haase, Subclasses of Presburger Arithmetic and the Weak EXP Hierarchy, CSL/LICS 2014.


Why is intuitionistic negation nonconstructive?

Intuitionistic negation is perfectly constructive, because $\lnot A$ is simply an abbreviation for $A \to \bot$ (i.e., "A implies false"). You may be thinking of the principle of double-negation elimination (i.e, $\lnot\lnot A \to A$). This principle is indeed nonconstructive.

The reason we call intuitionistic logic constructive is that existentials and disjunctions are "constructive". Concretely, this means that:

if you have a proof of $\exists x.\;A[x]$, then you can find a specific value $v$ such that $A[v]$ is provable.
if you have a proof of $A \vee B$, then you can either find a proof of $A$, or a proof of $B$

The axiom of the excluded middle is not constructive, because it asserts $A \vee \lnot A$ for any $A$, without giving a procedure for deciding which of $A$ or $\lnot A$ is provable.

Double-negation elimination lets you derive the excluded middle. This is because $\lnot\lnot(P \vee \lnot P)$ is derivable in intuitionistic logic. Here's a proof, given as a lambda-term:

f : ¬¬(P ∨ ¬P)
f : (((P ∨ (P → ⊥)) → ⊥) → ⊥ )
f = λk : (P ∨ (P → ⊥)) → ⊥.
     let g : P → ⊥ = λp:P. k (inl p) in
     let h : (P → ⊥) → ⊥ = λn : P → ⊥. k (inr n) in
     h g

We can combine this with double-negation elimination to conclude that $P ∨ ¬P$ holds generally. Hence it follows that double-negation elimination is not a constructive principle in general.


Stochastic Gradient Descent with integer arithmetics

see eg Neural network training with constrained integer weights
Plagianakos, V.P.;   Vrahatis, M.N.;

An Integer Recurrent Artificial Neural Network
for Classifying Feature Vectors
Roelof K Brouwer PEng, Ph

the general idea in various implementations is to represent/approximate real numbers $x \in[0..1]$ as integers in the form $x \cdot 10^m$ where $m$ is some integer exponent.


Finding a permutation $p$ of $x_1, x_2, \dots, x_n$ which maximises $\sum_{i=1}^{n-1}|x_{p_{i+1}}-x_{p_i}|$

I found that the problem has been used in a student programming contest.

... if you still want to try to solve it by yourself don't move the mouse over the area below !!! :-)

  The programmingn contest is the Bubble Cup 7DC, Belgrade 2012.The key idea to solve it is to consider the middle element of the given array after sorting it in increasing order (if the number of elements is even then pick the value between the two middle elements); it splits the set in two halves $A$ and $B$.Then it is easy to prove that an optimal solution cannot contain three consecutive elements in increasing (or decreasing) order $... x_i < x_j < x_k ...$ because it is enough to move the middle element at the end of the array and the sum cannot decrease after the trasformation. So an optimal solution must proceed in a zig-zag style. Then we can prove that the optimal solution cannot contain two consecutive elements from the same side. Suppose that we have somewhere $... x_i, x_j, x_k ...$ with $x_i> x_j < x_k$ and $x_i, x_j, x_k \in B$. Then then the remaining sequence must contain three consecutive elements from $A$  $...x'_i,x'_j,x'_k...$ ordered as $x'_i < x'_j > x'_k$. Then $A \ni x'_j < x_j \in B$ can be swapped preserving the inequalities and strictly increasing the value of the sum.For the detailed proof see: Bubble Cup 7DC - Problem C: MaxDiff(it contains other nice problems)


Are there hypothesis classes that are hard to learn but easy to test?

Take the class  $\mathcal{M}$ of monotone boolean functions under the uniform distribution on $\{0,1\}^n$:

it is known that $O(\sqrt{n}/\varepsilon^2)$ queries are sufficient to test it (even with non-adaptive testers) [KhotMinzerSafra15].
learning $\mathcal{M}$ under the uniform distribution, even allowing membership queries, requires $2^{\Omega(\sqrt{n}/\varepsilon)}$ queries ([BshoutyTamon96,BlaisCOST15]).


Inferring an LP cost vector from its solution

I guess that you want the set of optimal solutions of the LP as small as possible.  (Otherwise, c=0 certainly makes x* one of the optimal solutions but probably that is not what you want.)

One way to obtain such c is as follows.  If x*i=0, then let ci be any strictly negative number.  If x*i>0, then let ci=0.

If you want to know all the vectors c with the required property, you can add any linear combination of rows of matrix A to cT.  It is not hard to prove that no other vectors c satisfy the condition.

Edit: Entirely rewritten in revision 2 to make it simpler.


Smallest vertex cover which is also an independent set

This is the "Independent Vertex Cover" problem. It is solvable in polynomial time. To see this, note that for every edge, exactly one endpoint of the edge must be in a vertex cover. We can reduce the problem to 2-SAT, as follows:  make a variable $x_i$ for each vertex $i$, and for each edge $(i,j)$, include clauses of length two of the form $x_i \oplus x_j = 1$.

See also https://stackoverflow.com/questions/10769971/algorithm-for-independent-vertex-cover


What is the relation/difference between axiomatic and denotational semantics one one side, and the data flow analysis(DFA) on the other sied?

The textbook that might be most relevant to your question is Principles of Program Analysis
by Nielson, Nielson and Hankin. It does cover dataflow analysis and its relationship to denotational semantics. It does not deal with axiomatic semantics though.


I don't know how you can get or see the bound of $\sqrt{(t+1)(n-t+1)}$ from the original bound $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$ but here is the proof that this bounds are asymptotically equal up to a constant factor:

First see that (I exclude $t = 0$ because the threshold function is always $1$)
$$ n(n-\vert (2(t-1) -n+1 \vert) = \left\lbrace
\begin{array}{ll}
n(2t-1) & 1 \leq t \leq n/2+1/2\\
n(2n-2t+1) & n/2+1/2 \leq t \leq n-1
\end{array} \right. $$

Define $f_1(t) = n(2t-1)$, $f_2(t) = n(2n-2t+1)$ and $g(t) = (t+1)(n-t+1)$.

Now you have to calculate the maximal value (according to $t$ within the defined intervalls) of the fractions $f_1(t)/g(t)$, $f_2(t)/g(t)$, $g(t)/f_1(t)$ and $g(t)/f_2(t)$. You can do this with differential calculus or approximation with the help of the graph (with $n$ large enough):

$f_1(t)/g(t) \leq f_1(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$f_2(t)/g(t) \leq f_2(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$g(t)/f_1(t) \leq g(1)/f_1(1) = \dfrac{2n}{n} = 2$

$g(t)/f_2(t) \leq g(n-1)/f_2(n-1) = \dfrac{n/2}{n/3} \leq 3/2$

This gives you
$$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$$
and also the wanted result
$$\sqrt{n(n-\vert 2(t-1)-n-1 \vert)} = \Theta(\sqrt{(t+1)(n-t+1)}).$$

Is there an easier way to see/get this result?


I think the answer to you first question is negative: A circuit has a fixed number of inputs, and thus, IMO, we can only talk about "families" of circuits, rather than just one uniform circuit.

Regarding your second question, you may note that there are "uniform families of circuits," whose description is generated by a Turing machine. That is, let $\{C_n\}$ be a uniform family of circuit, and let $M$ be a Turing machine. Then, for each $n$, $[C_n] = M(1^n)$, where $[C_n]$ denotes the description of $C_n$.

There are several complexity classes below P, defined by uniform families of circuits. For example:

$\mathbf{NC}^i$ is the class of decision problems decidable by uniform boolean circuits with a polynomial number of gates and depth $O(\log^i n)$.


Distinguishing a biased coin with a small set of tests

Yes. Such families are called "averaging samplers", and there are plenty of constructions for them. You can find a more information about them (and about the more general notion of sampler) in this survey.

The notion of averaging samplers was introduced in this paper, which also showed that they are equivalent to randomness extractors. There are many constructions of extractors, and you can use any of them to construct samplers.

Here are a few relatively simple ways to construct such families:

Take a random family, as pointed out by Emil Jerabek in the comments.
Construct a family using a $k$-wise independent hash function, as pointed out in the comments by D.W.
Construct a family by considering an expander graph over the vertex set [n] and taking the neighborhood of radius $r$ around every vertex (for some sufficiently large values of $r$) - see for example this lecture. Alternatively, take the family obtained from the set of random walks of length $r$ on the graph. -- see for example this lecture  .


How to formally model the “hesitation” in the hat-guessing puzzle and prove it by mathematical induction?

This isn't really an answer to your questions, but I think it would help in understanding the problem (or the way to answer your questions is) to write out a formal statement and proof of the solution. The proof you've presented doesn't say what is being proven, and as written is certainly incorrect. It states (final bullet point) that the inductive hypothesis is that $k$ people with $k-1$ black hats and $> k$ white hats can tell that they all have white hats without any hesistation, but it proves that $k+1$ people with $(k, >k+1)$ hats can tell with hesitation.

Writing out a more formal proof would also make it clear what modeling assumptions you require for it to work. For example, you would probably end up needing to prove "$k$ people with $(k-1,>k)$ hats can all tell if they have white hats after $k$ moments of hesistation". If so, that means you would need some formal, common-knowledge notion of "moment of hesitation".

I hope that helps a little bit with question #1. (Also, the answers at math.stackexchange seem very good on this topic as well....) It might also help with #2, but I'm not sure what exactly you're asking -- I think the proof by induction would take care of this?


Efficient tools for checking SMT formulas with two quantifiers ($\exists\forall$)

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

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

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

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

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

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


Questions about algebraic effects and handlers, decomposed handlers

That's three questions.

Can handlers be decomposed?

No, a handler cannot always be decomposed because the operations may interact. It is false that you can decompose get and set into separate handlers because they have to handle a shared state. You can try these examples online in Eff. First, the ordinary state handler:

type 'a state = effect
  operation get: unit -> 'a
  operation set: 'a -> unit
end

let r = new state

let state_handler x = handler
  | val y -> (fun s -> (y, s))
  | r#get () k -> (fun s -> k s s)
  | r#set s' k -> (fun _ -> k () s')
  | finally f -> f x

;;

with state_handler 30 handle
   let x = r#get () in
   let () = r#set 20 in
   let y = r#get () in
     (x,y)
;;

The above example returns (30, 20), as it should. Now let's separate the handler into two handlers and apply them, as you suggested:

type 'a state = effect
  operation get: unit -> 'a
  operation set: 'a -> unit
end

let r = new state

let get_handler x = handler
  | val y -> (fun _ -> y)
  | r#get () k -> (fun s -> k s s)
  | finally f -> f x

let put_handler x = handler
  | val y -> (fun _ -> y)
  | r#set s' k -> (fun _ -> k () s')
  | finally f -> f x

;;

with put_handler 30 handle
with get_handler 30 handle
   let x = r#get () in
   let () = r#set 20 in
   let y = r#get () in
     (x,y)
;;

The result is (30, 30) which is unexpected. The problem is that each handler put_handler and get_handler is rolling its own state, so get takes state from one place and put places it into another place.

Why do handlers have special types?

In a language with operations and handlers we distinguish values from computations. A value is an inert piece of data which cannot trigger any effects and needs not be computed (such as a constant true, a tuple (42, false), or a function fun x => ...). A computation is an expression which must still be evaluated, and it may trigger an effect, produce a value, or diverge. Now:

functions map values to computations,
handlers map computations to computations.

The difference is visible in the types: $\alpha \to \beta$ is the function type, but $\alpha \Rightarrow \beta$ is the handler type. In operational semantics there is also a difference: we must apply a function to a value, and we must apply a handler to a computation. Thus, instead of writing

(fun x => print "Hello"; x + 3) (print "world" ; 8)

we must write

let v = (print "world"; 8) in (fun x => print "Hello"; x + 3) v

Of course this is quite annoying and the programmer doesn't have to do it by hand, at least not in Eff. Eff will perform the transformation automatically. Also note that here print "world"; 8 is evaluated first, and then the function is applied to v.

You can think of a handling construct as an application of a handler to a computation:

with H handle C

means "apply H to the computation C". Note that we do not evaluate C first, contrary to how we evaluated v above before we applied the function.

Why are computation types used?

The computation types are part of an adjunction between value types and computation types. We have a category $\mathcal{V}$ of value types and a category $\mathcal{C}$ of computation types, with two functors
$$F : \mathcal{V} \to \mathcal{C} \qquad\text{and}\qquad
  U : \mathcal{C} \to \mathcal{V}$$
such that $F$ is left-adjoint to $U$. It is a general fact that such an adjunction determines a monad $T = U \circ F : \mathcal{V} \to \mathcal{V}$. By passing from the adjunction $F \dashv U$ to the monad $T$ we lose a little bit of information (but not much, since every monad can be decomposed into an adjunction in a canonical way).

The use of computation types is thus largely a matter of mathematical setup. It is quite natural to use value and computation types when we consider handlers. This is so because operations and handlers arise from a similar picture that occurs in algebra: there is a category of sets $\mathsf{Set}$ and the category of algebras $\mathsf{Alg}$ (for the given operations), together with functors
$$F : \mathsf{Set} \to \mathsf{Alg} \qquad\text{and}\qquad
  U : \mathsf{Alg} \to \mathsf{Set} $$
where $F(X)$ is the free algebra generated by the set $X$ and $U(A)$ is the underlying set of the algebra $A$. This again is an adjunction. (In fact, handlers were discovered starting from these two functors. We massaged them until algebra became programming.) In this instance value types are sets and computation types are free algebras. For example, a computation which returns a natural number, and may trigger put and get operations, is the free algebra $F(\mathbb{N})$ for the operations put and get. A handler for such an operation has the form

handler
  put x k => P
  get x k => G
  val n => V(n)

and corresponds to an algebra homomorphism $\phi : F(\mathbb{N}) \to A$ where $A$ is an algebra with operations $P$ and $G$, and $\phi$ maps a generator $n$ to the element $V(n) \in A$.

Could we rephrase all of this in terms of the monad $T = U \circ F$? Probably, but it would be ugly, and it would start to look like we're trying to hack things in Haskell, rather than do them from foundations up.


All recursive algorithms are inherently NOT-inplace, isn't it?

Recursion is an abstract concept. Talking about whether or not it has in-place semantics is nonsense. (Unless of course the language specifies recursion semantics.) This idea is related to how it is nonsense to talk about the speed of a language.

How recursion is implemented is another question. For example, a compiler might perform tail call optimization where recursion can be converted to a loop under the hood among other things. In this case, recursion maintains constant stack space (assuming your architechure uses stacks :D)

EDIT: What does this all mean? It means that there exist recursive algorithms that are in-place when implemented in certain fashions. Thus the statement "All recursive algorithms are inherently not in-place" is false.


Why does ML's Value Restriction stop you from capturing parametric values?

Your C# example doesn't trigger the value restriction at all. Here it is in OCaml:

# let foo f init acc =
    let cur = ref init in
    (fun () -> cur := f !cur acc ; !cur) ;;
val foo : ('a -> 'b -> 'a) -> 'a -> 'b -> unit -> 'a = <fun>

# let my_bar_a = foo (+) 0 1 ;;
val my_bar_a : unit -> int = <fun>
# let my_bar_b = foo (^) ":" "-" ;;
val my_bar_b : unit -> string = <fun>

# my_bar_a () ;;
- : int = 1
# my_bar_a () ;;
- : int = 2
# my_bar_b () ;;
- : string = ":-"
# my_bar_b () ;;
- : string = ":--"
# my_bar_a () ;;
- : int = 3
# my_bar_b () ;;
- : string = ":---"

Note that your initial example shouldn't trigger it either:

let f = fun x -> x in f "plop", f 2 ;;
- : string * int = ("plop", 2)

f here is a non mutable value, it can be safely generalized.

The ML value restriction doesn't stop you from capturing parametric values as long as, given a unique reference, it will only be instantiated with a unique type. This is the case in your C# example: the reference cell is created for each new function.

I'm not extremely fond of the MLTON manual. You can read Real World OCaml for a decent introduction to the value restriction here. OCaml also has extensions to the value restriction when type parameters are in covariant position, which you can read about in Jacque Garrigue's paper.


An upper bound for chi-square divergence in terms of KL divergence for general alphabets

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

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


Note that the paper considers strongly Byzantine agents and weakly Byzantine agents.
From the abstract:

  For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f+2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f+2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f+1, then they are not able to gather deterministically with termination in some networks.

So for $f$ weakly Byzantine agents any number of good agents will do if the network size is known. Alternatively if it is not known, $\ge f+2$ good agents is a lower bound and they also show the matching upper bound.

  For strongly Byzantine agents, we give a lower bound of f+1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2f+1 good agents when the size of the network is known and for at least 4f+2 good agents when it is unknown.

In the strongly Byzantine case, they show that $f+1$ is a lower bound on the number of good agents required when the network size is known, which implies that this is true when the network size is unknown. These lower bounds aren't tight it seems as their best algorithms require $\ge 2f+1$ good agents in the case where the network size is known, or $\ge 4f+2$ good agents if the network size is unknown.


It looks fairly similar to

  Coloring random graphs online without creating monochromatic subgraphs (Reto Spöhel, Torsten Mütze, and Thomas Rast)
  Proceedings of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA '11), PR 137, 145-158.

SODA PDF
Journal version
Conference proceedings


expected number of sets generated by greedy set cover ?

Given that a cover exists, greedy will return a cover of expected size $O(p^{-1}\log n)$.
As long as $k$ is not too large, with high probability every cover has size $\Omega(p^{-1}\log n)$

This implies that (for $k$ not too large) greedy gives an $O(1)$-approximation with probability $1-\delta$, for any constant $\delta>0$.

Here is the upper bound, followed by the lower bound.

Upper bound

Conditioning on the event that there exists a set cover,
the greedy set-cover algorithm returns a set cover with expected size
$O(p^{-1}\log n)$.

Proof of upper bound.
Condition on the event that a set cover exists.

Assume without loss of generality that $k\ge (12/p)\ln(n)$
(otherwise, since greedy chooses at most $k$ sets, we are done).

We prove that there is a fractional set cover $X$ of expected size at most
$$\frac{2}{p} + n\exp(-pk/12).$$
By the assumption on $k$ this is $$O(1/p).$$

The upper bound will follow, because
(as is well-known) greedy returns a cover of size $O(\log n)$
times the size of any fractional set cover (and so, here, $O(p^{-1}\log n)$)
(see here or Chvatal).

Define the fractional cover $X$ in two stages.

Give each set $s$ weight $X_s = 2/pk$.
For each element $e$ such that $\sum_{e\in s} X_s < 1$,
choose any set $s$ containing $e$ and raise $X_s$ enough to fully cover $e$.

This clearly gives a fractional set cover.  (Step 2 is well defined,
because we are conditioning on the event that there is a set cover,
that is, that each element is in some set.)

To finish we bound the expected total weight of $X$, that is, $\sum_s X_s$.

Stage 1 contributes exactly $k 2/pk = 2/p$ to the total weight.

Stage 2 contributes, in expectation, at most $n\exp(-pk/12)$,
because each of the $n$ elements has probability at most
$\exp(-pk/12)$ of being covered with weight less than 1
by stage 1.

(To verify this, fix any element.
The element is left insufficiently covered
iff it is contained in fewer than $kp/2$ sets.
The expected number of sets covering the element
is $kp$, so by a standard Chernoff bound the
probability that the number falls below $kp/2$
is at most $$\exp(-(1/2)^2 k p/3) = \exp(-kp/12).$$
This ignores the conditioning, but the conditioning
only decreases the chance that the element is contained
in fewer than $kp/2$ sets.)
QED

As an aside, note that if $k$ is large enough, then greedy will almost certainly return a cover of constant size.  (E.g. if $k$ is $2n2^n$ and $p=1/2$, then won't all possible subsets be present with high probability? And in that case greedy will return just one set of course.)

Lower bound

Assuming  $p\le 1/2$, $k\le \exp(n^{1-\epsilon})$ for some $\epsilon\in [0,1/2]$,
and $s = \min((\epsilon/4p)\ln n, n^{\epsilon/2})$,
then the probability that there exists a set cover of size $s$ or less is $o(1)$.

Of course this implies that greedy does not return a set cover of size less than $s$.

The proof is probabilistic, using direct calculation and the naive union bound.
Hopefully there are no mistakes in the calculations.

Proof.
Fix $p$, $k$, $s$, $\epsilon$ as above.

The number of ways of choosing $s$ sets from the $k$ sets available
is ${k\choose s}$.

For any fixed collection of $s$ sets, the chance that it covers all
$n$ elements is $(1-(1-p)^s)^n$.

Combining these two observations, the expected number of size-$s$ covers among the $k$ sets is
$${k\choose s} (1-(1-p)^s)^n
~\le~ k^s \exp(-n(1-p)^s)
~\le~ \exp\big(s\ln(k) - n e^{-2sp}\big).$$

To complete the proof, one shows that the right-hand side above is $o(1)$
(under the assumptions on $k$ and $s$).

To do that, it suffices to show that

$n e^{-2sp} \rightarrow \infty$, and
$s\ln k \le (1/e) n e^{-2sp}$.

The first of these follows from the assumption on $s$.
The second reduces (taking logarithms) to
$$1+2ps + \ln s \le \ln(n) - \ln\ln k.$$
By the assumption on $k$ this reduces to
$$(1+2ps) + \ln s \le \epsilon \ln n.$$
This holds because the assumptions on $s$ imply that each of the two summands
on the left is at most $(\epsilon/2)\ln n$.
QED


Is there a well-defined division operation on finite automata?

Take a look at this MFCS 2013 paper, which studies compositionality in automata. Perhaps it will help.


Find Shortest Pairwise Distance of Points in o(n log n)?

There is a randomized linear expected time algorithm by Rabin; see e.g. Rabin Flips a Coin on Lipton's blog.


Membership problem for certain class of unrestricted grammars

This class of grammars is undecidable. Here is a rough idea about how to use it to emulate Turing machines.

At each point, the current partially expanded word would look like

$$[\mbox{tape to the left}][\mbox{head}][\mbox{tape to the right}]$$

Here:

$[\mbox{tape to the left}]$, after applying $P$, only contains characters $\overline0$ and $\overline1$.
$[\mbox{tape to the right}]$, after applying $P$, only contains characters $0$ and $1$.
$[\mbox{head}]$ is a single nonterminal, which encodes both the head state and the character at the head position.

Suppose that the head is in state $S$, and the character under the head is $i\in\{0,1\}$. Then the head is represented by nonterminal $S_i$. If it needs to transition to state $T$, replace the current character with $j$, and move to the left, there are two transitions $S_i\rightarrow0T_0j$ and $S_i\rightarrow1T_1j$. If it needs to move to the right instead, there are two transitions $S_i\rightarrow\overline jT_0\overline0$ and $S_i\rightarrow\overline jT_1\overline 1$. In some sense, the head has to "guess" the character in the direction it is moving to by producing the matching character. If the guess is wrong, the invariant on $[\mbox{tape to the left}]$ or $[\mbox{tape to the right}]$ would be violated, and it would never recover.

When the machine halts, the head should "consume" its tape on both sides by "guessing" and producing matching characters. After that, it should produce empty word. As a result, empty word would be a member of such grammar if and only if the corresponding Turing machine halts.


Natural complete problems in higher levels of the $\mathsf{W}$-hierarchy

I believe the title of this paper is self-explanatory and answers your question:
On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]


Edit distance algorithms that depend on alphabet

The answer is certainly yes. Assume for simplicity that the two strings are of equal length $n$. If the "induced" alphabet of each string is also of size $n$, then both strings are permutations, and the problem degenerates to the classical longest increasing subsequence (LIS) problem: it is easy to see that the edit distance between a given permutation $\pi$ and the sorted permutation $1,2,\ldots,n$ is $n-LIS(\pi)$. The LIS problem was studied as early as 1930s by Erdos and Szekeres, and by Robinson. The best algorithms for LIS run in time $O(n \log n)$ or $O(n \log\log n)$, depending on the computation model. Such algorithms were (re)discovered dozens of times (or perhaps hundreds of thousands, considering that the problem makes a good programming exercise), often with various twists. It is easy to find the relevant papers, since most of them cite previous work. The most recent result I am aware of, and a good point to start exploring the references, is the $O(n \log\log LIS(\pi))$ algorithm by Crochemore and Porat:

M. Crochemore and E. Porat. Fast computation of a longest increasing subsequence and application. Information and Computation, 208(9):1054--1059, 2010. http://dx.doi.org/10.1016/j.ic.2010.04.003

The same paper also describes how to interpolate between this extreme case and the general edit distance problem, taking the total number of character matches as a parameter. This is relevant when your "induced" alphabet size is large, but not exactly equal to $n$. For smaller "induced" alphabet sizes (say $n/2$), it is easy to construct examples that are essentially binary over a significant part (say, one half) of each input string, so a large "induced" alphabet over the whole string won't help more than by a constant factor.


Assuming that the coefficients of $f$ are integers or rationals and that you want integer roots, the simplest approach is to use the integer or rational root theorem. See http://en.wikipedia.org/wiki/Rational_root_theorem
As noted by D.W., this might be problematic if the constant coefficient is hard to factor (see also https://math.stackexchange.com/questions/123018/polynomial-and-integer-roots)

In any case, the Sage documentation clearly explains how they are doing the root search: "The next method, which is used if K is an integral domain, is to attempt to factor the polynomial. If this succeeds, then for every degree-one factor a*x+b, we add -b/a as a root (as long as this quotient is actually in the desired ring)."
See http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html.

So your question becomes How do they efficiently factor polynomials with integer coefficients ?  Apparently, Sage is calling NTL to do that (see http://www.shoup.net/ntl/doc/ZZXFactoring.txt for NTL details).

If you want an asymptotically efficient method, you could refer to the method of Lenstra, Lenstra and Lovasz (https://openaccess.leidenuniv.nl/handle/1887/3810).


Curious about computer-assisted NP-completeness proofs

As for question 2, there are at least two examples of $NP$-completeness proofs that involve computer-assistant.

Erickson and  Ruskey provided a computer-aided proof that Domino Tatami Covering is NP-complete. They gave a polynomial time reduction from planar 3-SAT to tatami domino covering. A SAT-solver (Minisat) was used to automate gadgets discovery in the reduction. No other $NP$-completeness proof is known for it.

Ruepp and Holzer proved that pencil puzzle Kakuro is $NP$-complete. Some parts of the $NP$-completeness proof were generated automatically using a SAT-solver ( again Minisat).


Large classes which contain LOGSPACE for which strict inclusions are unknown

This is a favorite question of mine.

Fortnow showed, in his paper "Time-Space Tradeoffs for Satisfiability", that $NL$ is properly contained in $\Sigma_{a(n)} P$, where $a(n)$ is any unbounded function. That is, nondeterministic logspace is properly contained in alternating polynomial time with $a(n)$ alternations.

Showing that $NL$ is not in $\Sigma_k P$ for a fixed constant $k$ would imply that $NL \neq NP$. (To see this, consider the contrapositive.)

It is open whether $NL = P^{\#P}$. The last time I seriously attempted to prove this, it resulted in the paper "Time-Space Tradeoffs for Counting NP Solutions Modulo Integers". I was trying to find some simulation of every language in logspace that would take $n^k$ time for some fixed $k$ when one has access to an oracle for counting satisfying assignments to a given formula. (This would imply $LOGSPACE \neq P^{\#P}$.) My approach didn't work, but I ended up using the same approach to prove time-space lower bounds for solving $Mod_6 SAT$ and other related results.

Uniform-$TC^0$ is properly contained in $P^{\#P}$. The proof is in Allender, "The Permanent Requires Large Uniform Threshold Circuits". Any improvement on this separation is open. (For example, proving uniform-$NC^1 \neq P^{\#P}$ is open, and proving uniform-$TC^0 \neq NP$ is also open.)


Social choice, arrow's theorem and open problems ?

Your question is very well timed, because the most recent issue of the CACM has an article      that does exactly this: http://cacm.acm.org/magazines/2010/11/100640-using-complexity-to-protect-elections/fulltext

In brief, there's a lot of work by Conitzer, Tovey and others on the actual hardness, both worst-case and under distributional assumptions, of cracking voting mechanisms that are in principle breakable via Arrow's theorem.


Implementation of surreal numbers for games

I don't have an answer to your question of whether the theory of Conway games has been used in building game-playing programs, but still you might be interested in the Combinatorial Game Suite, "an open-source program to aid research in combinatorial game theory" (which I first learned about here).  It includes an implementation of various standard operations on Conway games in canonical form, as well as a scripting language for describing new games.


Derive logitboost using the logistic loss function

Originally, Logitboost was derived by Friedman, Hastie, and Tibshirani (paper) -- their algorithm internally used a numerical procedure, via Newtons method to solve a regression problem.

Later, Collins, Schapire, and Singer (paper) found an equivalent formulation, with a single-line modification from AdaBoost, setting
$$D(i) \propto \frac{1}{1+e^{y_i f_{t-1}(x_i)}}.$$

Schapire has a nice summary of boosting here, which also discusses Logitboost.


P-complete decision problems about integers

Not quite what you're looking for, but the iterated mod problem is a P-complete number-theoretic decision problem.


Is the problem "MIN-SET-PARTITION" an NP-hard problem?

Take $S_i$ to be the edges of a graph $G$. Then, a partition $F$ of size $k$ corresponds to an edge-coloring of $G$; the minimum such $k$ corresponds to the chromatic index of $G$. Edge-coloring is known to be NP-complete: "The NP-Completeness of Edge-Colouring".


Minimising the root-set of a spanning hyperforest of a hypergraph

This answer addresses the NP-hardness of the SPANNING SYMMETRIC HYPERFOREST ROOT SET (SSHRS) problem (given an undirected hypergraph $G$ and a number $k$, is there a spanning hyperforest with root set of size at most $k$ in the symmetric directed hypergraph $D_G$).

We prove that this problem is hard by reduction from the MAXIMUM UNIQUELY RESTRICTED BIPARTITE MATCHING (MURBM) problem (see https://link.springer.com/article/10.1007/s00453-001-0004-z for hardness). A uniquely restricted matching in a graph $B$ is a matching $M$ such that the induced subgraph of $B$ over the vertices of $M$ has exactly one perfect matching ($M$ itself). The MURBM problem asks for a given bipartite graph $B$ and a given number $n$ whether there exist a uniquely restricted matching in the graph with at least $n$ edges.

Note that a matching is uniquely restricted if and only if there exists no cycle in the graph whose edges alternate between being in the matching and not being in the matching. (This is easy to show, so the proof will not be included here).

The reduction from MURBM to SSHRS is simple: we are given a MURBM instance consisting of bipartite graph $B$ and number $n$. Suppose $B$ has vertex parts $V_1$ and $V_2$. Define $N(v)$ to be the set of neighbors of $v$ in $B$. Then define a hypergraph $G = (V, E)$ with vertices $V = V_1$ and edges $E = \{N(v)~|~v\in V_2\}$. Next, define $k = |V_1| - n$. In other words, construct the hypergraph $G$ whose bipartite graph model is $B$. Output $G$ and $k$ as the SSHRS instance output of the reduction.

The logic behind the reduction is this:

Choosing a spanning hyperforest in $D_G$ is equivalent to choosing a set of edges in $D_G$ subject to certain constraints. But choosing a set of edges in $D_G$ (subject to certain constraints) is equivalent to choosing a set of edges in $G$ and choosing a vertex to be the head from each (subject to certain constraints). Since a hyperforest allows no cycles, the same edge of $G$ directed in different ways cannot be used (as two such "duplicate" edges form a cycle). Since in a hyperforest the vertices have max in-degree one, the same vertex cannot be chosen as the head of multiple different edges. In other words, the choice of edges in $G$ and heads of those edges that comprises a choice of spannning hyperforest is equivalent to the choice of a matching in the bipartite graph model of $G$ (subject to certain constraints). But by construction, the bipartite graph model of $G$ is exactly the bipartite graph $B$, so choosing a spanning hyperforest in $D_G$ is equivalent to choosing a matching in $B$ subject to certain constraints.

What are those constraints? Well a hyperforest cannot have any cycles, and must have vertex in-degrees of at most 1. The vertex in-degree constraint is already met by any matching, so the only constraint is to have no cycles. But a cycle in the hyperforest corresponds to a cycle in the bipartite graph model of $G$ such that every second edge is in the corresponding "matching". Thus, the cycle-free condition of the hyperforest is equivalent to the condition that there exists no cycle in the graph whose edges alternate between being in the matching and not being in the matching.

Thus, hyperforests in $G$ correspond to uniquely restricted matchings in $B$. All that's left is to show that the parameters also match: that having a hyperforest with root set size at least $k$ corresponds to having a matching of size at least $n$. Every vertex in a spanning hyperforest has in-degree either 0 or 1, so the number of in-degree-1 vertices is equal to the total in-degree in the spanning hyperforest. But the total in-degree is also equal to the number of edges since each edge has exactly one head. Thus, the number of in-degree-1 vertices in the spanning hyperforest is equal to the number of edges. We also know that the size of the matching equals the number of edges in the hyperforest. Thus the size of the matching equals the number of in-degree-1 vertices in the hyperforest. Furthermore, the number of roots is by definition the number of in-degree-0 vertices. Thus, the size of the root set plus the size of the matching is equal to the number of vertices $|V| = |V_1|$. Therefore, the hyperforest has root set size at most $k = |V_1| - n$ if and only if the matching has size at least $n$.