Schaefer's theorem and CSPs of unbounded width

I claim that for a “natural Boolean CSP,” if the k-restricted version is in P for every k, then the unrestricted version is also in P.  I will define a “natural Boolean CSP” below.

Schaefer’s theorem states that the Boolean CSP on a finite set S of relations is in P if at least one of the following conditions is satisfied and it is NP-complete if none of them is satisfied:

Every relation in S (except for the constant 0) is satisfied by assigning 1 to all its variables.
Every relation in S (except for the constant 0) is satisfied by assigning 0 to all its variables.
Every relation in S is equivalent to a 2-CNF formula.
Every relation in S is equivalent to a Horn-clause formula.
Every relation in S is equivalent to a dual-Horn-clause formula.  (A “dual-Horn-clause formula” means a CNF formula where each clause contains at most one positive literal.)
Every relation in S is equivalent to a conjunction of affine clauses.

Now assume that P≠NP, and consider the case where S is infinite.  If the k-restricted version is in P for every k, then by Schaefer’s theorem, every finite subset of S satisfies at least one of the six conditions above, and this means that the whole set S satisfies at least one of the six conditions.  Does this mean that this CSP without the restriction on arity is also in P?  Not yet.

When S is infinite, we have to specify how each clause in the input formula is given.  We assume that there is some surjective mapping from {0,1}* to S, which specifies the encoding of the relations in S.  A Boolean CSP is specified by giving both S and this encoding function.

Note that in each of cases 3, 4, 5, and 6 above, there is a natural way to represent relations satisfying the condition: a 2-CNF formula in case 3, a Horn-clause formula in case 4, and so on.  Even if a relation is equivalent to (say) a 2-CNF formula, there is no a priori guarantee that its encoding gives an easy access to the 2-CNF formula which is equivalent to it.

Now we say that a Boolean CSP is natural when its encoding function satisfies the following:

  Given an encoding of a relation and an assignment to all its variables, whether the relation is satisfied or not can be computed in polynomial time.  (Note: This ensures that the CSP in question is always in NP.)
  Given an encoding of a relation satisfying condition 3, 4, 5, or 6, its natural representation as specified above can be computed in polynomial time.

Then it is easy to see that if S satisfies one of the six conditions above and the encoding for S satisfies this “naturalness” condition, then we can apply the corresponding algorithm.  The claim which I stated at the beginning can be proved by considering both the case of P=NP and the case of P≠NP.


How can we bound the optimal solution of the dual bin packing when we solve the knapsack problem for each bin?

The "dual bin packing problem" is more commonly referred to as the Multiple Knapsack problem. One can show that $ALG \ge (1-1/e) OPT_b$ assuming an optimal algorithm for the Knapsack problem is used in each bin. If the bins are of different sizes then one can show that $ALG \ge OPT_b/2$ irrespective of the order in which the bins are processed. See Section 4 in the paper below for these results. http://epubs.siam.org/doi/abs/10.1137/S0097539700382820


Second Smallest $s$-$t$-Cut in a Network

The second smallest cut, and more generally the $k$ smallest cuts, can be found in time polynomial in $k$ and the network size. See:

H. W. Hamacher. An $(K\cdot n^4)$ algorithm for finding the $k$ best cuts in a network. Oper. Res. Lett. 1(5):186–189, 1982, doi:10.1016/0167-6377(82)90037-2.

H. W. Hamacher, J.-C. Picard, and M. Queyranne. On finding the $K$ best cuts in a network. Oper. Res. Lett. 2(6):303–305, 1984, doi:10.1016/0167-6377(84)90083-X.

H. W. Hamacher and M. Queyranne. $K$ best solutions to combinatorial optimization problems. Ann. Oper. Res. 4(1–4):123–143, 1985, doi:10.1007/BF02022039.


To follow up on Snowie's post:

For each term max(v1, v2) introduce a new variable $x_i$, subject to the constraints $x_i \geq v_1, x \geq v_2$

For each term min(v1,v2) introduce a variable $y_i$ subject to $y_i \leq v_1, y_i \leq v_2$.

Next, minimize the linear constraint $l = \sum x_i - \sum y_i$
subject to the inequations $x \geq v, y \geq v$, the linear equations $0 \leq v \leq 1$, AND the original linear system of equations.

This is a linear program, hence solvable in polynomial time. As the number of such constraints is polynomial, the entire system is solved in polynomial time.


This problem is NP-complete, by reduction from Minimum Hitting Set.

In minimum hitting set, we are given a universe, $U$, and a set of sets $S$ such that $\forall s \in S, s \subset U$. The objective is to find $H \subset U$ of smallest size such that $\forall s \in S, \exists h \in H$ such that $h \in s$.

The reduction is as follows:

The string is as follows: For each element $u \in U$, there will be a two characters of the string, $u'$. Between these characters will a character $s'$ for each $s \in S$ such that $u \in s$. Between the pairs of $u'$s, there will be unique characters that are not repeated in the string.
To homogenize the string, the $s'$ character must be moved $|s|-1$ times, for each $s$.  Additionally, for each $u$, the $u'$ character must be moved once, unless every $s'$ between the pair of $u'$ has been moved elsewhere.
Therefore, to minimize the number of moves necessary to homogenize the string, we wish to maximize the number of $u'$ such that every $s'$ has been moved elsewhere. The $u'$s where the $s'$s have not been moved elsewhere must together contain a $s'$ for every $s \in S$, so they must for a hitting set. Moreover, any such hitting set may serve as the ending locations of the $s'$s, by moving each $s$ to the $u$ which hits it.
Thus, the number of moves to homogenize this string is equal to $\sum |s| + |H^*|$, where $H^*$ is the minimum hitting set.

Since minimum hitting set is NP-Hard, optimally homogenizing a string is as well. Since the moves form a witness, it is NP-Complete.


Formalized configuration of Subset sum problem Worst-case ?

No, there isn't. If there was such a particular instance of subset sum problem that would be "the hardest" we could solve it by brute-force, and then hard-code it (and its answer) into our program solving subset sum problem. Then our algorithm, given an instance to solve, would first check whether the input matches that hard instance, and if so, it would simply output its answer in O(1) time - and thus, the instance wouldn't be hard anymore.

In general, hardness lies in the problems (which we can see as infinite sets of instances), and not in particular instances (or even some finite sets of instances), and searching for explicit instances of the problem that are "the hardest" doesn't make much sense. You could restate the question to ask about some "hard" family of instances - i.e., such families that our problem remains NP-hard when limited only to these instances. You could probably get one example of such families by looking at the details in the reduction showing that SUBSET-SUM in NP-hard.

Answer to the comment: Generally, this kind of questions is too elemental for this site - I would really advise you to read some good intro to complexity theory, or at least to do a DFS on wikipedia starting from this article: http://en.wikipedia.org/wiki/NP-complete
I think you will find all your answers there. Then, if you're interested specifically in the SUBSET-SUM problem, you could look into the reduction showing its NP-hardness - you will see there arbitrary instances of SAT (or some other NP-hard problem) being mapped into some particular instances of SUBSET-SUM (the set of these "hard" instances will probably be smaller than the set of all instances, but still infinite and "dense"). And yes, if you can solve the SUBSET-SUM problem restricted to this set of instances, you will prove that P=NP.


Complexity of summing up integral powers

Check out The generalization of Faulhaber's formula to sums of non-integral powers. Specifically, on the last page, it gives a formula indicating an error bound of $O(N^{\sigma - m})$, where $\sigma$ is $x$ (in this paper, it's generalized to complex numbers), and $m = \lfloor \sigma + 1 \rfloor$. $N$ in this case refers to the depth of a summation you have to calculate. So this implies that for rational numbers slightly greater than an integer, it would be a lot faster than for rational numbers slightly less than an integer. Of course, this is a result on real numbers, and there may be a better result for rationals.


What do we know about the phase transition of #P-Complete problems?

For counting independent sets, there is a recent proof for a computational phase transition, by Allan Sly:
http://arxiv.org/abs/1005.5584
(the algorithm is by Dror Weitz from 2006; Allan proved the matching hardness and co-won the best paper award in FOCS'10 for that)

Note that for random 3SAT and similar problems there is no proof that those problems are indeed hard in the appropriate interval. When you go to the harder counting problems, it becomes easier to prove the hardness.


Is just one W-type enough for formalizing mathematics?

We certainly do not need very many $W$-types.
If we also have universes, we only need one $W$-type, namely the natural numbers. For example, the UniMath library uses just the natural numbers and no other inductive types (if we discount the fact that standard types constructors, such as products and sum, are defined inductively in Coq).


Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

From the comment:

In "Deterministic Turing Machines in the Range between Real-Time and Linear-Time" I found:

... if $r \in T^{−1}(DTM)$ and $r' \in o(r)$ then $DTIME(n+r') \subset DTIME(n+r)$ ...


What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

Dimitris Achlioptas covers this in his survey article from the Handbook of Satisfiability (PDF).

There is conjectured to be a single threshold $r_k$ for each $k \ge 3$, so that when $m/n > r_k$ then a random $k$-SAT formula with $m$ clauses and $n$ variables is unsatisfiable with high probability, and so that when $m/n < r_k$ then a random $m$-clause, $n$-variable $k$-SAT formula is satisfiable with high probability.
(More precisely, the conjecture is that in the limit as $n$ tends to infinity, the probability of satisfiability is 0 or 1 in these two regimes, respectively.)

Assuming that this Satisfiability Threshold Conjecture holds, the best known bounds for $r_k$ are

k                   3      4      5     7     10      20
Best upper bound 4.51  10.23  21.33 87.88 708.94 726,817
Best lower bound 3.52   7.91  18.79 84.82 704.94 726,809

(this table appears on the page indicated as 247 in the draft).

In a more recent manuscript (arXiv:1411.0650), Jian Ding, Allan Sly and Nike Sun showed that for all sufficiently large $k$, there is in fact a single threshold $r_k = 2^k\ln 2 - (1+\ln 2)/2 + o(1)$, and the error term $o(1)$ in this expression goes to zero as $k$ tends to infinity.


Characterizing the exponential savings in active learning

See Hanneke's disagreement coefficient,
http://projecteuclid.org/euclid.aos/1291388378


My research practices, when I go into new research domain, cover combination of memory management, mnemonic, notes and other practices.

I have no one recipe, cause each is dependent on nature of given domain.

For some inspiration and sake of discussion, here is and example that came now into my mind:

Go through papers into a few iterations:

First, to get adjusted to domain and get first intuition about approaches and notations.
Next step is preparation to "clusterization" of papers.

prepare list of tags representing approaches, notations, features and other interesting me properties.
Before I start tagging I go through papers and evaluate my tags, correct appropriately.
Finally I tag papers

Then I process papers according to tags in groups: with similar notation, approach...

Thanks to working with papers sharing common properties, you can concentrate on differences.
I prepare notes in form of MindMap with FreeMind. To easily reach "what was what".

After processing papers grouped in sets with tags, try look at whole area with all groups to get boarder view.
Now is step of looking thought whole domain to see connections and differences. When I can't remember details, I check-out in my MindMap to remind, what was what.

Try to avoid overloading your memory, when it's unneeded, use: Mnemonics and Art Of Memory techniques. Use MindMapping.


It sounds like your graph is a transitively closed DAG, right? If so (and this is probably a restatement of what you say in your citation of Ntafos et al) the minimum number of paths needed to cover the DAG is just the maximum number of pairwise incomparable elements; this is Dilworth's theorem.

Your example may be simple enough that one can identify this maximum incomparable set directly, but in general it is possible to find this set in polynomial time, by an algorithm based in graph matching. The "Proof via König's theorem" section of the Wikipedia article on Dilworth's theorem explains how.


Class of languages accepted by Python RegEx?

I think the answer is "it's complicated", and they probably do not recognize a definite level in the Chomsky hierarchy

Lookaround in regular expressions does not allow them to recognize non-regular languages. This is difficult to see in the standard automata formalism, but this paper describes using Brzozowski's more intuitive "derivative" formalism, which allows defining "extended regular expressions" affording complementation $\neg r$ and intersection $r \& s$. The set of regular languages is also closed under these operations, and looaround operations can be defined in terms of them. For example, negative lookahead $r(?!s)p$ can be written as $r(p\&\neg (s.*))$

This post describes the power of "perl compatible regular expressions" (PCREs). They can recognize at least the context free languages and more. However, Python does not use full PCREs, and in particular lacks the DEFINE keyword, which the author used to prove it can recognize all context-free languages. (The proof is basically embedding BNF-style grammar productions into a PCRE.)

I'm not aware of a way of embedding BNF-style productions into python regular expressions, so it's unclear whether python regexes can recognize all CFLs. They can also clearly recognize non-regular languages like the collection of strings on the alphabet $\{a\}$ which have a composite length r'^(aa+)(\1)+$', which is not even context-free.


They don't necessarily imply a partition, here is a counterexample.
Each set in each $S_i$ will have an even size, while $U$ will have an odd number of elements, this already guarantees that a partition is impossible.
$U$ is the nine vertices of a cycle of length $9$, whose edges are colored with $3$ colors, in an alternating way.
With the union operation each color class generates a set system, these will be the $S_i$.
In more detail, the generating edges are 01, 34, 67 for $S_1$, 12, 45, 78 for $S_2$ and 23, 56, 80 for $S_3$.
It is easy to check that your separating condition holds.


Constant Depth Circuit Computing Threshold Function

General weight threshold gates can be computed by polynomial size depth 2 circuits built from majority gates. An efficient construction of this is e.g. given by Amano and Maruoka. Then you can just compute each of these by constant depth circuits built from AND and OR gates.
You can always assume weights are integers of magnitude at most $(n+1)^{(n+1)/2}/2^n$. See Muroga, Toda and Takasu


Computation of reals: floating point vs TTE vs domain theory vs etc

I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think.

The community of people who work on exact real arithmetic consists of theoreticians who are not used to developing software. So they usually relegate the task of implementation to students (a notable exception is Norbert Müller's iRRAM), or they have their own toy implementations.

People who do have the necessary programming mojo do not have the necessary theoretical background. Without solid theoretical footing it is difficult to design exact real arithmetic correctly. For instance, it is a mistake to add lots of real numbers in a for loop, as you will get unacceptable performace due to loss of precision. If you want to add lots and lots of reals, you should do it with a tree-like structure, taking into account the magnitudes of the partial sums. Another thing which is difficult to get across is that < and = as total boolean function on the reals simply do not exist (you can have = but it either returns false or it diverges, and < diverges when given two equal reals).

Lastly, it is not clear at all that we know how to implement libraries for exact real arithmetic. They're not the usual pieces of libraries which just define some datatypes and some functions on them. Often exact real arithmetic requires special modes of control. For instance, iRRAM takes over the main execution of the program (it literally hijacks main), as well as standard input and output, so that it can rerun the program when loss of precision occurs. My library for real arithmetic in Haskell happens in a Staged monad (which is essentially the Reader monad). Most people expect the real numbers to be "just another datatype", but I have my doubts about that.


How to calculate machine learning time for binary classification?

By "time" do you mean the number of examples or the computation required to construct a classifier? If the former, the key quantity is the VC-dimension of the hypothesis class (i.e., collection of all classifiers you are willing to consider). The latter is strongly dependent on the representation (i.e., how you "view" the classifier in terms of algorithms and data structures) and in many cases can be NP-hard.


Clarification: Are runtime bounds in P decidable?

In my opinion, the wording of the answer is a little confusing.  Specifically:

  Given an instance $(M,x)$ of the halting problem, construct a new machine $M′$ that works as follows: on inputs of length $n$, it simulates $M$ on $x$ for n steps.

...confused me, too.  What you have to understand is that the machine $M'$ is based on one specific instance of the halting problem; it doesn't simulate $M$ on $x$ for $|x|$ steps.

Here is how I would word that part:

  Fix an instance $(M,x_1)$ of the halting problem.  Construct a machine $M'$ that takes as input $x_2$, and that works as follows:  simulate $M$ on $x_1$ for $|x_2|$ steps.  If $M$ halts within $|x_2|$ steps, loop for $|x_2|^2$ steps and stop; otherwise loop for $|x_2|^3$ steps and stop.

Hopefully that helps.


What is the minimal class of subshifts for which conjugacy is known to be undecidable?

Consider the class of subshifts defined by a forbidden context-free language. For this class, equality and non-conjugacy are recursively inseparable, i.e.

  Theorem. There is no algorithm that given two context-free languages, says "same" if they define the same subshift, and says "non-conjugate" if they are not conjugate.

Note that no requirement, even on halting, is made when they are distinct and conjugate.

Proof. Note that CFL are closed under unions and contain all regular languages, so we can forbid finitely many regular and CFL languages. We will forbid a bunch of things to force our configurations to simulate Turing machines.

Let $M$ be a Turing machine with state set $Q$ and alphabet $A$, suppose $Q \cap A = \emptyset$ and $\#, @ \notin A \cup Q$, and $0 \in A$. Let $q_0 \in Q$ be the initial state of $Q$ and $q_f$ the unique halting state.

We will construct two subshifts $X$ and $Y$ over the alphabet $Q \cup A \cup \{\#, @\}$ such that if $M$ reaches the halting state $q_f$ from the initial configuration $q_0 0^\omega$ then $X$ and $Y$ are not conjugate, and if $M$ does not, then $X = Y$ as sets.

I won't list the precise forbidden patterns since it's a lot of programming, but I'll explain what they accomplish. I'll say what needs to be true about subwords of a certain form, which you can turn into forbidden patterns by forbidding the complement of these conditions. First, with a regular set of forbidden patterns we force that $\#$ and $@$ alternate, and the word between any consecutive appearance of $\#$ and $@$ (in either order) is an element of $A^* Q A^*$ (so there's a Turing machine configuration between $\#$ and $@$).

Next, with a context-free set of forbidden patterns we force that in every pattern $u@v$ where $u, v \in (Q \cup A)^*$, we have $u = v^R$ where $v^R$ denotes reversal. We also force that in every word $\#u@va$ with $|u| = |v|$, $u, v \in (Q \cup A)^*$ and $a \in Q \cup A \cup \{\#, @\}$, we have $a = \#$, and the three symmetric conditions that together force that $\#$ and $@$ appear in a single arithmetic progression.

Next, the main trick. It's the one used in the standard proof of undecidability of whether two given context-free languages intersect: we require that in every word $@ v \# u @$, if $v$ does not contain $q_f$, then $u$ is the configuration that follows $v^R$ in the rule of $M$. If $v$ does contain $q_f$, then we require that $u^R$ is the unique word in $q_0 0^*$ of the correct length.

Finally, require that in every word $@ v \# w \# v^R @$ where $v \in (Q \cup A)^*$, the state $q_f$ appears somewhere in $w$. These patterns define the subshift $X$.

Let us analyze what kind of configurations appear in $X$. First, no matter whether $M$ halts on input $q_0 0^\omega$, in $X$ you have all configurations of the form $x @ y$ and $x \# y$ where $x$ and $y$ are over the alphabet $Q \cup A$, and all the limits of such configurations under the shift action, namely the full shift $(Q \cup A)^{\mathbb{Z}}$. Let $Y \subset X$ be this subset. It's a sofic subshift.

Suppose then that both $\#$ and $@$ appear in a configuration of $X$ (recall that they must alternate, so this happens unless the configuration is in $Y$), then the rules force that $@$ and $\#$ appear periodically in an arithmetic progression, and the configuration is of the form
$$ \ldots v_{-1} \# u_0 @ v_0 \# u_1 @ v_1 \# u_2 @ v_2 \# u_3 @ \ldots $$
with all the $|u_i|$ and $|v_i|$ of the same length, $u_i = v_i^R$ and the $M$-successor of $u_i$ is $u_{i+1}$. Since the lengths are the same, the computation must enter a loop starting from any $u_i$, i.e. $u_m = u_k$ for some $m < k$. The last rule then forces an appearance of $q_f$ somewhere between $u_m$ and $u_k$. But this means there is an occurrence of $q_0 0^n$ between them as well. Another application of this argument shows that the computation from $q_0 0^n$ reaches the halting state $q_f$.

We see that any configuration not in $Y$ is periodic, and must periodically repeat the accepting computation of $M$ on some $q_0 0^n$, where $n$ is any integer large enough that he computation has time to halt. (And if $M$ does halt on $q_0 0^n$, then periodically repeating the computation gives a valid configuration of $X$.)

In conclusion, if $M$ never halts on $q_0 0^\omega$, $X = Y$, and if $M$ does, then $X$ contains an isolated periodic point while $Y$ does not, so $X$ and $Y$ are not conjugate. So an algorithm with the properties listed in the statement would solve the halting problem, thus cannot exist. Square.

  Corollary: Equality and conjugacy of subshifts given by forbidden context-free languages are both undecidable problems.

Proof. Let's do conjugacy. If conjugacy were decidable by algorithm $A$, then it would give an algorithm $B$ that accomplishes what we claimed cannot be done: given $X$ and $Y$, if $A$ says they are conjugate, $B$ claims they are the same, and if $A$ says they are not conjugate, $B$ claims they are not conjugate as well. Now if $X = Y$, certainly $A$ says they are conjugate, so $B$ says they are the same. If $X$ and $Y$ are not conjugate, $A$ detects this, so $B$ also says they are not conjugate, contradicting the previous theorem. Square.

You can ask many follow-ups: can you make this topologically mixing (or some stronger gluing notion), can you use something weaker than CFL, and can you have the language be CFL rather than the forbidden patterns, etc. Have at it.


Regular language that discriminates between two deterministic CFGs

Eryk Kopczyński[1] showed in 2015 that separability (that's the name of your problem) of visibly pushdown languages by regular languages is undecidable.  The class of visibly pushdown languages is a strict subset of deterministic CFL.

[1]:    Eryk Kopczyński, Invisible Pushdown Languages, LICS'16, available at https://arxiv.org/abs/1511.00289


Reduction SAT to a problem on a planar graph with as few vertices as possible

You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; such algorithms exist for many graph problems). If you could get $|V(G)| = o(m^2)$ in the reduction you mention, this would imply that the Exponential Time Hypothesis (ETH) is false. This is well-appreciated, yet it has not led to any improvements on running times for CNF-SAT (as far as I know).  For more on how ETH has been used to classify the difficulty of planar (and non-planar) graph problems, see e.g. this survey of Lokshtanov, Marx, and Saurabh.

As for reducing the constant in such reductions, achieving $|V(G)| = c m^2$ for $c$ as small as possible, I don't know how much effort has been devoted to this.


List of NP-Complete graph problems/ properties?

A general list of NP-complete problems can be found in Garey & Johnson's book "Computers and Intractability". It contains an appendix that lists roughly 300 NP-complete problems, and despite its age is often suggested when one wants a list of NP-complete problems.

I haven't read the book, but based on its reputation it would be a quite good start to any investigation.


Why is it important that the secret is at the end when signing with MD5?

See "extension attacks" in the Merkle-Damgard construction. This issue arises in the use of hash functions for message authentication.

In short, putting the secret in the beginning allows the attacker, given a message and its hash, to forge any message which has the given message as a prefix. This is a problem for naive codes but is avoided by well-known codes like HMAC.


Succinct complete problems in DTIME(EXP(EXP(...)))

See, e.g., Theorem 5 of

  Balcazar, Lozano, and Toran, The complexity of algorithmic problems on succinct instances (doi)

This theorem essentially lets you bootstrap up the tower of exponentials as desired, using the appropriate standard bounded version of the halting problem as being complete for most standard classes.


Is this dense version of Kruskal's algorithm well-known?

I'm not sure about this specific method for achieving $O(n^2)$ time, but two different methods for performing Kruskal in $O(n^2)$ time are given in my paper "Fast hierarchical clustering and other applications of dynamic closest pairs" (SODA 1998, arXiv:cs.DS/9912014, and J. Experimental Algorithms 2000):

Use Prim–Dijkstra–Jarník instead and then sort the edges to get the insertion sequence that Kruskal would give, or
Use the quadtree closest-pair data structure described in the paper, viewing Kruskal as a standard agglomerative clustering procedure where we merge the closest two clusters into a supercluster at each step, with "closest" defined as the length of the shortest edge connecting two clusters.

Solution 2 is similar in spirit to what you describe but the details of how to keep track of the distances between clusters are slightly different. You keep the row-wise minima of the cluster distance matrix, allowing you to scan this list of row-minima in linear time to find the global minimum, while my paper overlays a quadtree on the same matrix and keeps track of the minimum in each quadtree square. Your method is simpler, but less flexible for some other dynamic closest pair problems (it depends on the fact that merging two clusters causes their distances to other clusters to decrease, true for this problem but not necessarily for others).

As I wrote in 2011 in the Wikipedia article on the nearest-neighbor chain algorithm, that algorithm can also be used to perform Kruskal in $O(n^2)$ time. However (unlike some other applications of the nearest-neighbor chain algorithm) you don't get a space savings, so (like the quadtree method and your method) the space is still $O(n^2)$. In contrast Prim+sorting can use only $O(n)$
space beyond that needed to store the input.


Distinguising between the cases of low or high cover number

Proving hardness of this sort of gap problem is usually how hardness of approximation is proved. For vertex cover, Håstad's famous paper (Theorem 7.1.) showed what you are asking for with $a=3/4$ and $b=7/8$.


Is there simple reduction Dominating Set to Vertex Cover?

How about the following transformation: Given a graph $G(V,E)$ with $V=\{1,\ldots,n\}$ construct $G'(V',E')$ as follows: $V'$ initially consists of two sets of vertices: the vertices $u_i, 1\le i\le n$ and the vertices $v_{i,j}, 1\le i,j\le n$ (a total of $n^2+n$ vertices). We add the following sets of edges: first, connect all $v_{i,j}$ with $v_{i,k}$ for $k\neq j$, so the graph now consists of $n$ cliques of order $n$ and $n$ isolated vertices. Next, for all $i$, connect $u_i$ with the vertex $v_{i,i}$. Then, for all $i$ connect $u_i$ with all vertices $v_{j,i}$ for which $(i,j)\in E$. On the other hand, for all $i,j$ such that $(i,j)\not\in E$ construct a new vertex $v'_{i,j}$ and connect it to $v_{i,j}$ (this constructs two new degree-1 vertices for each non-edge of $G$). This completes the construction.

The claim is that $G'$ has a vertex cover of size $n(n-1)+k$ if and only if $G$ has a dominating set of size $k$. The intuition is that any vertex cover must take at least $n-1$ vertices from each clique (giving at least $n(n-1)$ vertices overall), allowing us to select exactly $k$ of the $u_i$ vertices to represent the dominating set. The vertex that is left out of the $i$-th clique encodes the vertex of the original graph that was used to dominate $i$. Observe that the leaves $v'_{i,j}$ ensure that vertices corresponding to non-edges are not left out of the vertex cover.

Thus, the direction dominating set of $G$ $\to$ vertex cover of $G'$ is straightforward: select the vertices from $u_i$ that represent the dominating set and from each clique select all vertices except the one that is adjacent to a selected $u_i$. For the converse direction, first note that it is never optimal to take a $v'_{i,j}$ vertex in the vertex cover since these vertices have degree 1, so their neighbors must be selected. Second, observe that in any vertex cover that selects all $n$ vertices of a clique we can exchange one of them with its neighboring $u_i$ vertex, therefore we can assume that an optimal vertex cover selects $k$ such $u_i$ vertices. These must be a dominating set of $G$.


Randomized identity-testing for high degree polynomials?

It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is no for multivariate polynomials unless NP = RP, due to the reduction below.

Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we can construct in polynomial time an arithmetic circuit $C_q$ such that $C$ is unsatisfiable iff $C_q$ computes an identically zero polynomial over $\mathbb F_q$ as follows: translate $a\land b$ with $ab$, $\neg a$ with $1-a$, and a variable $x_i$ with $x_i^{q-1}$ (which can be expressed by a circuit of size $O(\log q)$ using repeated squaring).

If $q=p$ is prime (which I don’t think actually matters) and sufficiently large, we can even make the reduction univariate: modify the definition of $C_p$ so that $x_i$ is translated with the polynomial
$$f_i(x)=((x+i)^{(p-1)/2}+1)^{p-1}.$$
On the one hand, $f_i(a)\in\{0,1\}$ for every $a\in\mathbb F_p$, hence if $C$ is unsatisfiable, then $C_p(a)=0$ for every $a$. On the other hand, assume that $C$ is satisfiable, say $C(b_1,\dots,b_n)=1$, where $b_i\in\{0,1\}$. Notice that
$$f_i(a)=\begin{cases}1&\text{if $a+i$ is a quadratic residue (including $0$),}\\
0&\text{if $a+i$ is a quadratic nonresidue.}\end{cases}$$
Thus, we have $C_p(a)=1$ if $a\in\mathbb F_p$ is such that
$$a+i\text{ is a quadratic residue }\iff b_i=1$$
for every $i=1,\dots,n$. Corollary 5 in Peralta implies that such $a$ always exists for $p\ge(1+o(1))2^{2n}n^2$.


Trade off between time and query complexity

Here's an attempt at creating an artificial function with the following property:

The problem can be solved with $O(\log n)$ queries, but requires $\exp(n)$ time.
The problem can be solved with $O(n)$ time but that requires $O(n)$ queries

Let the input size be $n + \log n$. Let the first $\log n$ bits (let's call this string x) encode the input to a problem complete for EEXP. The next $n$ bits (let's call this string y) have the property that they are all zero if and only if x is a NO instance of the EEXP-complete problem.

In words, the first $\log n$ bits encode a hard problem, and the next $n$ bits give you a clue about the solution of the problem. However, to figure out the solution by looking at the $n$ bit string you make $\Omega(n)$ queries.

So this problem can be solved by either reading only the first $\log n$ bits and spending exp(n) time or by reading $n$ bits and using only linear time.

The same function goes through for quantum query complexity.. insert square root signs where necessary.


Good reference about approximate methods for solving logic problems

The motivation you state for dealing with undecidability applies to decidable but hard problems as well. If you have a problem that is NP-hard or PSPACE-hard, we will typically have to use some form of approximation (in the broad sense of the term) to find a solution.

It is useful to distinguish between different notions of approximation.

Numeric approximation: applies when you have a metric on the solution space and you can measure distance from the solution. This is the case for problems like #SAT, where you count solutions and can design an approximation algorithm that returns a value within $\varepsilon$ of the solution.
Probabilistic approximation: when you use a randomized algorithm you can give up certainty in the solution you will obtain every time you run the algorithm. You can move between randomness in the algorithm and randomness in the solution space by considering a probability distribution over solutions. Then the approximation here is that with some probability greater than $\delta$, you will obtain a correct solution.

There are $(\varepsilon,\delta)$-algorithms for problems like ALLSAT which combine the two perspectives above. In the specific case of undecidable problems, or problems where there is no obvious metric and we do not want to use a randomized algorithm, there is a question of what notion of approximation to use. This problem arises specifically in the analysis of programs in optimizing compilers and in program verification. Determining complex properties of programs is either undecidable or computationally expensive, so some form of approximation is required.

Here is an example of a different notion of approximation.  Suppose you perform a computation like multiplying two large numbers and want to check if it the multiplication was correct. There are lots of heuristic techniques that are used in practice to check correctness without repeating the calculation again. You can check that the signs were multiplied to obtain the right sign. You can check whether the numbers have the right parity (even/odd number properties). You can use a more sophisticated check like Casting out nines. All these techniques have a common property that they can tell you if you made a mistake, but they cannot guarantee if you got the right answer. This property can be viewed as a logical approximation because you may be able to prove that the original calculation is wrong but you may not be able to prove that it is correct.

All the checks I have mentioned above are examples of a technique called abstract interpretation. Abstract interpretation makes completely rigorous a notion of logical approximation distinct from numeric and probabilistic approximations. The problem I described with analysis of a single calculation extends to the more complex case of analysis of a program. The literature on abstract interpretation has developed techniques and frameworks for approximate, logical reasoning about programs, and more recently about logics. The following references might be useful.

Abstract Interpretation in a Nutshell by Patrick Cousot, which is a simple overview.
Overview of Abstraction by Patrick Cousot, as part of his course. There is a very nice example of abstraction for determining properties of a boquet of flowers. The bouquet analogy includes fixed points and can be made completely mathematically precise.
Course on Abstract Interpretation by Patrick Cousot, if you want all the depth and details.
Abstract interpretation and application to logic programs, Patrick Cousot and Radhia Cousot, 1992. Applies to logic programs, as per your request. The initial section also formalises the casting out nines procedure as an abstract interpretation.

All of this has typically been applied to reason about computer programs. There has been fairly recent work on applying ideas from abstract interpretation to study decision procedures for logics. The focus has not been modal logic but satisfiability in propositional logic and quantifier-free first-order theories. (Since I have worked in this space, one paper below is mine)

A generalization of Staalmarck's method by Aditya Thakur and Thomas Reps, 2012. Gives a generalisation of Staalmarck's method to problems in program analysis.
The reduced product of abstract domains and the combination of decision procedures, Patrick Cousot, Radhia Cousot, and Laurent Mauborgne, 2011. This paper studies the Nelson-Oppen technique for combining decision procedures and shows that it can also be used for incomplete combinations, which is particularly interesting if you have undecidable problems.
Satisfiability Solvers are Static Analysers, my paper with Leopold Haller and Daniel Kroening, 2012. Applies the lattice-based approximation view to characterise existing solvers. You could also look at my slides on the topic, instead.

Now none of the papers above answers your specific question about attacking satisfiability problems which are undecidable. What these papers do is take an approximation-oriented view of logical problems that is not numeric or probabilistic. This view has been applied extensively to reason about programs and I believe it addresses exactly what you are asking.

To apply it to modal logic, I would suggest a starting point is to use algebraic semantics of Jonsson and Tarski or the later semantics of Lemmon and Scott. This is because abstract interpretation is formulated in terms of lattices and monotone functions, so Boolean algebras with operators are a convenient semantics to work with. If you want to start with Kripke frames, you can apply Jonsson and Tarski's duality theorem (which some may call Stone duality) and derive the algebraic representation. Thereafter, you can apply the theorems of abstract interpretation for logical approximation.


Is analogy between database and probability concepts legitimate?

I would expect that the empty relation corresponds to the always-zero probability distribution.  Disjoint union corresponds to addition of probability distributions.  However, standard union would be more complicated.  I don't really know if there is some way to encode the standard union for probability distributions.  (I have heard people say that probability distributions form a boolean algebra.  So there must be some operation that serves as the union.)


Complexity of two perfect matchings with minimum shared edges?

Consider a 3-regular graph $G = (V,E)$.

If there is an edge colouring of $G$ with 3 colours, then you have a partition of $E$ in 3 disjoint perfect matchings. In particular, you can find 2 disjoint perfect matchings.

Conversely, if you can find two disjoint perfect matchings $M_1$ and $M_2$, you can also find a third disjoint perfect matching $M_3 = E \setminus (M_1 \cup M_2)$. The partition $\{M_1, M_2, M_3\}$ of $E$ is an edge colouring of $G$ with 3 colours.

Deciding if a 3-regular graph has an edge colouring with 3 colours is NP-hard (Holyer 1981). Hence it is also NP-hard to decide if there are two disjoint perfect matchings (i.e., to decide if the minimum number of shared edges is 0).


Algebra oriented branch of theoretical computer science

There have been recent developments in dependent type theory which relate type systems to homotopy types.

This is now a relatively small field, but there is a lot of exciting work being done right now, and potentially a lot of low hanging fruit, most notably in porting results from algebraic topology and homological algebra and formalizing the notion of higher inductive types.


How to automatically generate indexes and preaggregations from queries

Hmm...

You could use undirected multigraphs or alternative graph structures stacks (epicly space inefficient).


Issue with inequalities involving probablities

This uses the fact that the L1-norm between two probability distributions is equal to twice their total variation distance.

See https://en.wikipedia.org/wiki/Total_variation_distance_of_probability_measures

To prove the equality you take the subset A in the definition to be the set of points where $$p_t > p_{t|w,w}.$$


Satisfiability for various branching programs

For Q2:

For Ordered BDDs (OBDD) both satisfiability and counting solutions is polynomial in the size of the OBDD.

For indexed BDD, IBDD p. 16 satisfiability is NP-complete and the equivalence test is coNP-complete even if there are only two layers.

In general if a variable is read more than one time it is NP-complete if I remember correctly.


I wish I had a good answer for you. I use Book:Fundamental Data Structures (a collection of relevant Wikipedia articles) for my course on this subject but it's not really a complete textbook (for one thing, it has no exercises). CLRS is, I think, at a good level of detail for this sort of class but is missing too many of the important structures.


Number of reachable vertices in DAG for every vertex

The best exact algorithm will run in time O( min{mn, n^2.38} ) by using fast binary matrix multiplication. However, there is a random algorithm, which runs in time O(m+n) and estimates the number of reachable nodes from each node with a small relative error, please refer to paper "Size-Estimation Framework with Applications to Transitive Closure and Reachability" by Edith Cohen.


Minimum non-zero variable in the optimal solution of linear programming

No, it is not always possible.  The illustration below shows an example in which the smallest non-zero value must be $1/2^{\Omega(n)}$.

The example is shown in the top of the illustration.  Round nodes are vertices; square nodes are hyperedges, each with connections to its (two or three) vertices.  Each vertex $v$ is labeled with its weight $x_v$ in the optimal LP solution, which is essentially unique.

In general, the hypergraph consists of the first three vertices (labeled $1/2$) and their three edges to their left, followed by $N$ copies of the gadget shown in the middle (vertically).  The "inputs" to the gadget are the three vertices labeled $1/x$.  The "outputs" are the three vertices labeled $1/2x$; these are also the inputs for the next copy of the gadget (if any).  Above $N=3$, but in general $N$ is arbitrarily large.  The sum of the hyperedge sizes is $n = \Theta(N)$, and the given solution has a non-zero weight of value $\Theta(1/2^N) = 1/2^{\Theta(n)}$.  This solution is obtained greedily by assigning weights maximally, from left to right.

To answer the question in the post, we will show that the given solution is the unique optimal solution.  The bottom part of the illustration above is for the proof (given below).

Lemma 1. The given LP solution is the unique optimum.

Proof sketch.
Let $x$ be the LP solution given in the figure.  By inspection $x$ is feasible.  First we'll argue that $x$ is optimal, by giving a dual solution that achieves the same LP objective.
The dual LP is "covering vertices by edges":
$$\min \sum_e y_e ~:~ y_e \ge 0;~~(\forall v)~\sum_{e \ni v} y_e \ge 1.$$

We use the dual solution illustrated in the bottom part of the figure above, in green.  We give each edge weight equal to the green label at the bottom of its column.  This solution is obtained greedily, by assigning weights minimally from right to left.  By inspection, at least for the example, the dual solution is feasible and has the same cost as the primal solution $x$. In general, by calculation, the cost achieved by the given primal solution $x$ is
$$3[1/2 + N + 1/2^{N+2}],$$
while the cost achieved by the given dual solution is the same:
$$3[(1/2 - 1/2^{N+2}) + 1/2^{N+1} + N].$$
Therefore the primal and dual solutions are optimal.

To finish we argue that the optimal primal solution is unique.  Let $x^*$ be any optimal primal solution.
By complimentary slackness and the fact that all values are non-zero in the optimal dual solution, $x^*$ must make all primal constraints tight.

Let $x^*_1, x^*_2, x^*_3$ be the variables of the first three vertices, given weight $1/2$ by $x$.  That the first three constraints are tight implies $x^*_1 + x^*_2 = 1$ and $x^*_1 + x^*_3 = 1$ and $x^*_2 + x^*_3 = 1$, which implies that $x^*_1 = x^*_2 = x^*_3 = 1/2$, the same as in $x$.

Given that, the same reasoning implies that $x^*$ gives each of the next three vertices weight $1/4$, also the same as in $x$. Given that, likewise, $x^*$ must give each of the next three vertices weight $3/4$, the same as in $x$.  Continuing this reasoning inductively, $x$ and $x^*$ must be identical.  $~~~\Box$


Convex Body with minimum expected l2 norm

If we restrict $K$ and $L$ to be both ellipsoids, then your problem can be solved to any accuracy with an SDP. I know this is not what you asked originally, but it seems we have no solution even for this restricted case, and maybe it can help in general.

So let's say $E$ is the input ellipsoid and we are looking to find an optimal enclosing ellipsoid $J$. There exists a linear map $F$ s.t. $E = FB_2$ and a map $G$ s.t. $J = GB_2$, where $B_2$ is the unit ball. Then $\mathbb{E}_{x \sim J}[\|x\|_2^2] = \frac{1}{n}\mathsf{Tr}(G^TG)$. Also $E  \subseteq J \Leftrightarrow J^\circ \subseteq E^\circ$, where $E^\circ$ is the polar body of $E$. Conveniently, $E^\circ = \{x: x^TF^TFx \leq 1\}$ and $J^\circ = \{x: x^TG^TGx \leq 1\}$. It follows that $J^\circ \subseteq E^\circ$ (and therefore $E  \subseteq J$) if and only if $G^TG - F^TF$ is a positive semidefinite matrix.

So the SDP is defined by: given a symmetric PSD matrix $M$, find a symmetric PSD matrix $N$ s.t. $N - M$ is PSD and $\mathsf{Tr}(N)$ is minimized. $N$ can be found by solving the SDP and then an SVD will give the axes and axes lengths of $J$.


A simple(?) funny combinatorial problem!

The conjecture in the post does not hold, but the weaker conjecture (with respect to the floor) mentioned in the comments does hold.  In fact, something stronger holds.

Lemma 1. The conjecture in the post does not hold.  That is, there is an instance satisfying the given assumptions where
$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E \, t \big\}\big| < \binom{ E \, n}{ t }.$$

Proof.
Consider the instance with $n=3$, $c=(1, 1, 0.7)$, $E=2.7/3=0.9$, and $t=2$.  Then $E\, t = 1.8$.
For the left-hand side, we have
$$\big|\textstyle\{ S \subseteq [3] : \sum_{i \in S}~ c_i \geq 1.8 \}\big| = 2$$
because any subset $S$ that does not contain both 1's sums to at most 1.7, and there are only two subsets ($\{1,1\}$ and $\{1,1,0.7\}$) containing both 1's. And the right-hand side is $\binom{ 2.7}{ 2 } = 2.7\cdot 1.7\,/\, 2 = 2.295>2. ~~~\Box$

The weaker conjecture suggested in the comments, namely the bound w.r.t. the floor, $\lfloor E\, n \rfloor$, does hold.  In fact something slightly stronger holds:

Lemma 2. Fix $0<E<1$, integers $n,t>0$,
and vector $c \in [0,1]^n$ with $\sum_{i\in [n]} c_i \geq E\, n$.
Then
$$\big|\textstyle\big\{ S \subseteq [n] : \sum_{i \in S}~ c_i \geq E\, t \big\}\big| \,>\, \binom{ \lfloor E\, n\rfloor}{ t } + \binom{ \lfloor E\, n\rfloor}{ t+1 } + \cdots + \binom{ \lfloor E\, n\rfloor}{ \lfloor E\, n\rfloor }.$$

Proof. Let $a=\lfloor E\, n\rfloor$. Assume WLOG that $a=E\,n$.  (Otherwise scale $E$ and each $c_i$ down by a uniform factor to make it so.  This maintains $\sum_i c_i \ge E\,n$ and changes neither which subsets sum to at least $E\,t$ nor the desired lower bound on the number of such subsets.)  Assume WLOG that $t\le a$ (otherwise the claim holds trivially).

Consider any subset $S\subseteq [n]$ of size at least $n-d$, where $d=a-\lceil a\,t/n\rceil \ge 0$. Since $\sum_{i\in[n]} c_i \ge a$ and $S$ contains all but at most $d$ elements (each of which is at most 1), we have $\sum_{i\in S} c_i \ge a-d = \lceil a\,t/n\rceil = \lceil E\,t\rceil \ge E\,t$, as desired.

The number of such subsets $S$ is

${n\choose n-d} + {n \choose n-d+1} + \cdots + {n \choose n-1} + {n \choose n}$

$ = {n\choose d} + {n \choose d-1} + \cdots + {n \choose 1} + {n \choose 0}$

$ > {a\choose d} + {a \choose d-1} + \cdots + {a \choose 1} + {a \choose 0}~~~$ (using $n>a$)

$ = {a\choose a-d} + {a \choose a-d+1} + \cdots + {a \choose a-1} + {a \choose a}.$

But $a-d = \lceil a\,t/n\rceil \le t$ (using $a/n = E < 1$), so the last sum is at least the desired lower bound on the number of good subsets. $~~\Box$


Here's a quick sketch to show that there is no Turing machine to decide whether an arbitrary class of problems is decidable.

I should clarify what I mean by class of problems: a class of problems $T$ is a Turing machine which enumerates the elements (natural numbers, say) of a recursively enumerable set one after the other, such that each element in the set is eventually printed. The problem intuitively captured by $T(n)$ is: "is the number $n$ in this set?". This captures the usual problems in the field of computability, such as "is i the index of a Turing machine that halts on empty input?".

Suppose there was machine $M$ which, given as input a class of problems $T$ answered $\mathit{true}$ if that class is decidable and $\mathit{false}$ otherwise.

Now take an arbitrary Turing machine $T$. We build the following class of problems $T'$ in the following manner:

Simulate $T$.
If $T$ halts, enumerate the indices of the Turing machines that halt on empty input.

Now it is clear that if $T$ halts, then $M(T')$ returns $\mathit{false}$, as the set of indices halting Turing machines is not a decidable (recursive) set.

If $T$ does not halt, then $T'$ does not enumerate any numbers, which makes it exactly the class of problems containing no indices! Therefore $M(T')$ answers $\mathit{true}$, since that class is decidable (by the machine that always rejects).

Therefore, $M(T')$ returns $\mathit{true}$ iff $T$ does not halt, and $\mathit{false}$ otherwise. Thus the existence of $M$ allows us to solve the halting problem for an arbitrary machine $T$, which is a contradiction.


Does bisimulation or the approximation lemma work for monadic streams?

Here's a well written piece explaining what the proper definition of a stream monad should be: Proper Definition of the Stream Monad

The resumption and reactive resumption monads are similar to the stream monad:Resumption Monad Transformers


Axioms of Minimum Size Resolution Refutations

With the caveat that I am posting this quickly in a sleep-deprived state, I think the answer is "no" to all three questions.

Take the pigeonhole principle formulas PHP^m_n for m pigeons and n holes. The miniminal length of a resolution refutation for m = n+1 is exp(Omega(n)) by Haken. However, Buss and Pitassi proved that for m = exp(\sqrt(n log n)) pigeons (or something in that range) there are refutations of length exp(\sqrt(n log n)) (or something in that range). Clearly, then, the shortest resolution refutation in this case is using lots of redundant clauses (from the point of view of minimal unsatisfiability).


Some nuances on Group and Subgroup Isomorphism?

(1) In terms of structural complexity classes (as opposed to just upper bounds on deterministic time), for general Group Isomorphism, the known upper bounds are essentially the same as for Graph Isomorphism, namely $\mathsf{coAM} \cap \mathsf{SZK}$. However, Arvind and Toran showed that Solvable Group Isomorphism is in $\mathsf{NP} \cap \mathsf{coNP}$ under a relatively benign derandomization assumption (in particular, weaker than that currently needed to show Graph Isomorphism is in $\mathsf{coNP}$). Although this isn't general Group Isomorphism, as solvable groups are widely believed to contain the hardest cases of Group Isomorphism, this is "pretty close." As it is conjecture that $\mathsf{coAM} = \mathsf{coNP}$, it is also conjectured that Group Isomorphism is in $\mathsf{coNP}$. In the Cayley table model, many people believe that Group Isomorphism is even in $\mathsf{P}$.

(2) Subgroup Isomorphism in the Cayley table model is unlikely to be $\mathsf{NP}$-complete, as it has a quasi-polynomial time algorithm. Namely, $H$ has at most $\log_2|H|$ generators; try all possible mappings of these generators into $G$ to see if any gives an injection. This takes time $|G|^{\log_2|H| + O(1)}$.

(3) Every finite group has a generating set of size at most $\log_2|G|$ (simple exercise). For the rest of this part of the question, it really depends on how the group is presented. However, note that how the group is given as input - e.g. Cayley table, generating permutations, generating matrices, generators-and-relations, black-box - also has a significant effect on the complexity of the corresponding algorithms. It is known that there are $n^{\Theta(\log^2 n)}$ groups of order $\leq n$, so by counting, groups of order $\leq n$ in general need $\Theta(\log^3 n)$ bits to describe. It is an open question whether there is always a presentation with generators-and-relations of poly-logarithmic size.


Finite Automata with succinct representation of chains of states

This is a very partial answer, but I have some ideas:

Clearly the union of NSAs can be taken without any blowup - just use the nondeterministic union of the initial states.
As for determinization, you'll have a double-exponential blowup. Consider the language $L_k=(a+b)^*a(a+b)^k$. That is, the $k$-th before last letter is $a$. You can easily construct an NSA of size $O(\log k)$ for it, but any DSA would need to "remember" the last $k-1$ letters (the same argument that works for DFAs would work here). So a DSA would need $2^{k-1}$ states, which is a double exponential blowup.
As for union of DSAs, this is more of a conjecture: consider the language $L_p=(a^p)^*$ for a prime number $p$. This can be recognized by a DSA with 2 states and $p-1$ written on one of the transitions. Now, consider the union $L_p\cup L_q$ for $p\neq q$. It seems to me that you'll need a lot of states (i.e. $p\cdot q$) in order to recognize this with a DSA. But I haven't thought this through completely.


Is there any known Poly-APX-complete minimimization problem?

I've just discovered there exists at least one confirmed minimization Poly-APX-complete problem: Min ones if setting all variables true satisfies all clauses (together with other conditions). It is shown in "The Approximability of Constraint Satisfaction
Problems" by Sanjeev Khannay, Madhu Sudanz, Luca Trevisanx and David P. Williamson (http://people.csail.mit.edu/madhu/papers/2001/kstw.pdf), Theorem 2.14, item (5).


Your problem is equivalent to maximum matching. In an optimal coloring, each color class is connected. Choosing one edge from each color class, we get a matching. This shows that the maximum matching is at least the antichromatic number. In the other direction, take any maximal matching, and color each of the pairs using a different color. Every other vertex is adjacent to some colored vertex (otherwise the matching isn't maximal), so you can extend this to an antichromatic coloring, showing that the antichromatic number is at least the size of a maximum matching.


Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The following are just a sample:

Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known approximation ratio is $1/e+0.004$ (BFNS14). When "at most" is replaced by "exactly", the best known approximation ratio is 0.356 (also BFNS14).
Given a non-negative monotone submodular function and $k$ matroids, find a set $A$ belonging to all different matroids and maximizing $f(A)$. When $k=1$ the best approximation ratio is $1-1/e$, and this is optimal. For larger $k$, LSV give a $1/k$ approximation, but this is probably not tight.
There are two algorithms for maximizing a non-negative monotone submodular function over a matroid that give the optimal approximation ratio $1-1/e$: the continuous greedy algorithm and the non-oblivious local search algorithm. Both are randomized. The best known deterministic algorithm is the greedy algorithm, giving a $1/2$ approximation. Can we separate deterministic and randomized algorithms in this oracle setting? A similar question arises in the non-monotone unconstrained case, in which BFNS12 give an optimal randomized $1/2$ approximation algorithm, but the best known deterministic algorithms (one in BFNS12 and an earlier local search algorithm due to FMV) give only a $1/3$ approximation.
Both the continuous greedy algorithm and the non-oblivious local search algorithm are rather slow. Is there a fast, $\tilde{O}(n)$ algorithm for maximizing a monotone submodular function over a matroid? (see BV for the case of a uniform matroid)
Algorithms for minimizing submodular functions are also a bit slow, the fastest running in time $O(n^5)$ (see Iwata's survey).


Can a totality checker be used to guarantee a proof on the calculus of constructions + inductive types is correct?

I'm going to assume that by $\mathrm{Fix}$ you mean a new type constructor

$$\frac{\Gamma\vdash F:*\rightarrow *}{\Gamma\vdash \mathrm{Fix}\ F:*} $$

Along with the conversion rule $\mathrm{Fix}\ F\simeq F\ (\mathrm{Fix}\ F)$. This is often referred to as equi-recursive types as opposed to iso-recursive types, where the conversion rule does not exist, and you need additional $\mathrm{fold}$ and $\mathrm{unfold}$ constructs to use $\mathrm{Fix}$.

I'll ignore the fact that the rule for $\mathrm{Fix}$ is non-terminating on it's own, since this isn't that harmful. You question about terms

$$\Gamma\vdash t:A$$
with
$$\Gamma\vdash A:*$$

when are they sound proofs of the statement $A$?

You suggest using a "totality checker", to sidestep the need for messy rules such as positivity and various other restrictions when dealing with iso-recursive types.

The first remark is that simply checking termination of a term $t$ won't do: we can easily build a proof of $\forall n:\mathbb{N}. n = 0$ which has a normal form, but loops when applied to some natural number! So we really do need to check totality, which involves proving that $t$ will not lead to non-termination when placed in an arbitrary well-typed context.

Sadly, we don't really know how to do this, other than building back in all those nasty restrictions you want to avoid! For positivity for example, taking $\Lambda=\lambda X:*.X\rightarrow X$, then you can type
$$\vdash \lambda x:\mathrm{Fix}\ \Lambda.x\ x:\mathrm{Fix}\ \Lambda $$

which smells like trouble: your totality checker had better reject that as a theorem.

The other restrictions will crop up pretty quickly.

As a side note, if you can prove something using some "reasonable" totality checker (provably correct in HOL) then you can actually "reverse engineer" a proof in CoC + $\forall n. S\ n\neq 0$, by internalizing the totality check. This technique is similar to realizability, where there is a correspondance between provably total functions and $\Pi^0_2$ theorems.

As a side note that came up in the comments, it seems to me that when restricting $\mathrm{Fix}$ to positive type constructors, i.e. type constructors $F$ for which (for each variable $f$) there exists a term $t_f$ such that

$${A:*,B:*,f:A\rightarrow B\vdash t_f:F\ A\rightarrow F\ B} $$

then there is no encoding of $\mathbb{N}$ such that induction over $\mathbb{N}$ holds.

The rough argument for this is to encode $\mathrm{Fix}\ F$ by
$$\forall X, (F\ X\rightarrow X) \rightarrow X$$
which is the usual encoding for positive inductive types in system F, and show that every well typed term in the system with $\mathrm{Fix}$ can be well typed in the CoC without it. Then we can conclude by the fact that CoC doesn't have any inductive definitions of $\mathbb{N}$ itself.

The encoding is a little messy, though, I think. I'd be happy to have a reference for this.


What is the hardest instance for the group isomorphism problem?

$p$-groups of class 2 and exponent $p$ are widely believed to be the hardest case of Group Isomorphism ($p > 2$). (For $p=2$, we need to consider exponent 4, since all groups of exponent 2 are abelian - easy exercise for the reader.) Although there is as yet no reduction from general GpIso to this class of groups (though see point 0.5 below), there are several reasons for this belief. Let me outline some of them here.

0) Practical experience (see papers by Newman, Eick, O'Brien, Holt, Cannon, Wilson, ... which give the algorithms that are implemented in GAP and MAGMA).

0.5) [EDIT: added 8/7/19] Reductions. When such $p$-groups are given by generating sets of matrices over $\mathbb{F}_p$, the problem is $\mathsf{TI}$-complete [G.-Qiao '19]. Also (cf. point (4) below), isomorphism of $p$-groups of exponent $p$ and class $c < p$ reduces in poly time to isomorphism of $p$-groups of exponent $p$ and class 2 (ibid.).

1) Structure (reduce to solvable, then to $p$-group). Every finite group contains a unique maximal solvable normal subgroup, called the solvable radical, denoted $Rad(G)$. $G/Rad(G)$ contains no abelian normal subgroups, and isomorphism of such groups can be handled efficiently in practice (Cannon-Holt J. Symb. Comput. 2003) and in theory (Babai-Codenotti-Qiao ICALP 2012). Even for groups where $Rad(G)$ is abelian, some of these can be handled in $n^{O(\log \log n)}$ time (G-Qiao CCC '14, SICOMP '17) - so, not quite polynomial, but much closer than $n^{\log n}$. The main obstacle thus appears to be solvable (normal sub)groups. Now, within solvable groups, there is a lot of structure - starting with the fact that every solvable group is a knit product of its Sylow $p$-subgroups - and it seems the hardest cases are $p$-groups.

2) Counting. The number of groups of order $n$ is $\leq n^{(\frac{2}{27} + o(1))\mu(n)^2}$, where $\mu(n)$ is the largest exponent of any prime dividing $n$ (Pyber 1993). The number of $p$-groups of order $n=p^m$ is at least $p^{(\frac{2}{27} + o(1))m^2}$ (Higman 1960). So you see that the coefficient of the leading terms in the exponents match. In this sense "most" groups are $p$-groups (even of class 2 and exponent $p$). There is a long-standing conjecture which says that "most" in the preceding weak sense can be strengthened to say that proportion of groups of order $\leq n$ which are $p$-groups tends to 1 as $n \to \infty$.

3) Universality (/wildness). Giving a classification of $p$-groups would imply a classification of all modular representations of any finite group (or even Artinian algebra) in characteristic $p$ (Sergeichuk 1977).

4) Flexibility. Why $p$-groups of class 2 and not higher class? (Note that $p$-groups of nearly-maximal class, so-called "small coclass", have essentially been classified, Eick & Leedham-Green 2006, see also some of the answers here.) To any $p$-group one can associate a graded Lie ring, where bracket in the Lie ring corresponds to commutator in the group. Associativity in the group implies the Jacobi identity for the bracket, thus giving rise to a genuine Lie ring. However, note that when the group is class 2, the Jacobi identity is trivially satisfied (all its terms are automatically 0), so this puts no additional constraints on the structure. It basically just corresponds to an arbitrary skew-symmetric bilinear map. For $p$-groups of exponent $p$, there is even a reduction from class $c < p$ to class 2.


Looking for approximation class between NPO and Exp-APX

As pointed out by Markus Bläser in the comments section, objective values must be positive integers, so they cannot be 0. Hence my problem A is not formally an NPO problem. Personally I think it makes sense to consider feasible solutions with 0 objective value in that particular problem, but using standard approximation hardness notions requires redefining the problem so that 0-objective solutions are just "not feasible". In fact, under that new definition, problem A turns out to be NPO-complete.


Complexity of $r$-sum as a function of integer sizes

There is a straightforward dynamic programming algorithm with complexity $n \times 2^{O(r \cdot n^{1/k})}$.  This is pretty slow.

For $r=2$, you can use algorithms for the birthday paradox to find a solution in time $O(n)$, if a solution exists.  A solution will exist with high probability.  In fact, for $r=2$, with high probability a solution will exist within the first $n^{1/2k}$ numbers, and we can find a solution in expected running time $O(n^{1/(2k)})$.

There is an algorithm with complexity $O(r \cdot n^{1/(k(1+\lg r))})$.  You start by finding pairs (2-sums) whose sum has many of their high bits equal to zero (by combining pairs of elements, using algorithms for the birthday paradox); then look for 4-sums whose sum has a (slightly smaller) number of high bits equal to zero (by combining pairs of 2-sums); then look for 8-sums (by combining pairs of 4-sums); and so on.  The running time comes from optimizing the exact number of high bits that you ask to be zero at each stage.

For instance, for the case $r=4$, there is an algorithm with complexity $O(n^{1/(3k)})$ for finding at least one such solution.

As far as I know, it is an open problem whether one can do better than this.

See also the following research papers:

A. Blum, A. Kalai, H. Wasserman. "Noise-tolerant learning, the parity problem, and the statistical query model".  JACM, 50(4):506-519, 2003.
P. Camion, J. Patarin.  "The Knapsack hash function proposed at Crypto'89 can be broken".  EUROCRYPT '91, pp.39-53.
R. Schroeppel, A. Shamir.  "A T = O(2^n/2), S = O(2^n/4) algorithm for certain NP-Complete problems".  SIAM J. Computing,  10(3):456--464.
P. Chose, A. Joux, M. Mitton.  "Fast Correlation Attacks: an algorithmic point of view".  EUROCRYPT 2002.


The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this.

Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata with SAT Solvers. Revised Selected Papers from the 8th International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, Springer, pages 81-92, 2010.


Definition of Rabin acceptance condition for omega automatons

As Emil explained in a comment:
The sides are interchangable when defining the Rabin condition - my professor defined the left side as the one that is required to be visited infinitely often while Wikipedia and the paper I've mentioned define the right side as the one that is required to be visited infinitely often.
Whichever the side that has to be visited infinitely often is, it can be required to be non-empty, since if it is empty, the pair is meaningless - it cannot be visited infinitely often.
It is okay not to require it to be non-empty, because if it is empty, the pair simply accepts the empty language without causing any contradiction or changing any of the desired results of the definition.


Is the topsort from "Structuring Depth-First Search Algorithms" guaranteed to be (reverse) stable?

Stripping the Haskell encryption from your question (and ignoring why you are using dff instead of dfs to get a search that respects a given order), you appear to be asking about the stability of the topological sorting algorithm that performs a depth first search and reverses a postorder traversal of the depth-first spanning forest. However, there is a more general answer to your question: it is not generally possible, given a sequence of vertices in a DAG, to find a topological ordering that respects the input sequence for all incomparable pairs of vertices in the DAG. That is, stable topological ordering is not possible.

To see this, consider a DAG with three vertices $a$, $b$, and $c$, and one edge $a\rightarrow b$, with the vertex ordering $bca$. The DAG has three topological orderings $abc$, $acb$, $cab$, but none of these are stable: $abc$ and $acb$ both reverse the pair $ca$, and $acb$ and $cab$ both reverse the pair $bc$.

For the same reason, reverse-stable topological ordering is also not possible. In particular the reverse-postorder-dfs algorithm is not reverse-stable.


Is there an efficient algorithm to find the i-th dearrangement?

Actually this is might be good question but it is badly formulated in its current form. The well-known algorithms for generating random derangements have linear expected time, but maybe it's an open problem to find a worst case polynomial time algorithm.

See for example:
http://www.siam.org/proceedings/analco/2008/anl08_022martinezc.pdf (and slides: http://www.lsi.upc.edu/~conrado/research/talks/analco08.pdf)


machine learning for code and compiler optimization?

Genetic Programming (GP) has been used to modify source code for performance improvement.

e.g. Evolutionary Improvement of Programs

(This is close to my PhD topic, would be very interested to hear your approach)


Bounds on size of self-concatenation of Finite Languages

You can show $ |L|^i $ is a tight upper bound by using the following language:

  $ L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}. $

Any concatenation gives a new string. For a lower bound, I can suggest the following unary language:

  $ U = \{a,aa,aaa,\ldots,a^k \mid k \geq 1 \} $.

Then, $ U^i = \{ a^i,a^{i+1},\ldots,a^{ki} \} $ and so $ |U^i| = i|U|-i+1 $.

Emil's (Jerabek) comment appeared during writing my answer and so before posting my answer.


Is there a name for this Assignment definition

Seems to me that the submodular welfare problem falls under your description. Have a look at http://theory.stanford.edu/~jvondrak/data/KAM_thesis.pdf chapter 4; here we assume that the utility function of subsets is submodular.
In general, your problem is just the combinatorial auction problem which is hard to approximate without any assumptions on the valuation function.


Is Gap-3SAT NP-complete even for 3CNF formulas where no pair of variables appears in significantly more clauses than the average?

Not a full answer, but hopefully close. This is very close to Luca's comments above. I believe the answer is that at least there do exist constants B∈ℕ, a>0, and 0<s<1 such that Gap-3SATs is NP-complete even for a 3CNF formula which is pairwise B-bounded and consists of at least $an^{2-\epsilon}$ clauses, for any constant $\epsilon$.

The proof is as follows. Consider a GAP-3SAT$_s$ instance $\phi$ on $N$ variables in which each variable appears at most 5 times. This is NP-complete, as you say in the question.

Now we create a new instance $\Phi$ as follows:

For every variable $x_i$ in $\phi$, $\Phi$ has $n$ variables $y_{ij}$.
For every set of indices $i$, $a$ and $b$ with $a\neq b$, $\Phi$ has a pair of clauses $y_{ia}∨￢y_{ib}∨￢y_{ib}$, and $y_{ib}∨￢y_{ia}∨￢y_{ia}$. I'll refer to these as comparison clauses since they ensure that $y_{ia} = y_{ib}$ if they are satisfied.
For every clause in $\phi$ acting on variables $x_i$, $x_j$ and $x_k$, for every $a$ and $b$, $\Phi$ contains an equivalent clause, where $x_i$ is replaced by $y_{ia}$, $x_j$ is replaced by $y_{jb}$ and $x_k$ is replaced by $y_{k(a+b)}$  (here addition is done modulo $n$). I'll refer to these as inherited clauses.

The total number of variables is then $m = nN$. Note $\Phi$ has $2Nn^2$ comparison clauses and $\frac{5}{3}Nn^2$ inherited clauses, for a total of $\frac{11}{3}Nn^2$ clauses. Taking $n = N^k$ we have $m = N^{k+1}$ and the total number of clauses $C = \frac{11}{3}N^{2k+1} = \frac{11}{3}m^{2-\frac{1}{k+1}}$. We take $k = \epsilon^{-1} - 1$, so $C \propto m^{2-\epsilon}$.

Next, $\Phi$ is pairwise 8-bounded (max of 2 from the comparison clauses and 6 from the inherited clauses).

Finally, if $\phi$ is unsatisfiable, then at least $(1-s)N$ clauses are unsatisfied. Now, if $y_{ia} \neq y_{ib}$ for any $a,b$ then at least $n-1$ clauses are unsatisfied. Note that in order to satisfy the $(1-s)N$ unsatisfied clauses in a set of inherited clauses for fixed $a,b$ then the assignment of variables $y_{:a}$, $y_{:b}$ and $y_{:(a+b)}$ must differ at at least $\frac{1-s}{5}N$ positions, leaving at least $\frac{1-s}{5}N(n-1)$ comparison unsatisfiable clauses. This must hold for every choice of $a$ and $b$, so at least $\approx \frac{1-s}{5}Nn^2 = \frac{3(1-s)}{11}C$ comparison clauses must remain unsatisfied in total for enough inherited clauses to be satisfied.  If however you look at the other extreme where all comparison clauses are satisfied, then $(1-s)Nn^2 = (1-s)m^{\frac{2k+1}{k+1}} = (1-s)C$ clauses are unsatisfiable. Hence a gap remains (although reduced) with $s' = \frac{4+s}{5}$.

The constants probably need to be double checked.


If your function is $f:\mathbb{R}\to\mathbb{R}$, you can "learn" $f'$ as a standard regression problem (linear, polynomial, etc.) and then recover $f$ up to an additive constant by integrating $f'$. Obviously, you will only able to recover $f$ up to an additive constant from the derivative.

Update: As for error estimates, here's a simple one. Suppose you've managed to recover $f'$ up to $\epsilon$-accuracy in $L_\infty$. Suppose further that you know that $f(0)=0$ and you only care about $f$ on $[0,T]$. Then your estimate of $f$ (obtained by integrating $f'$) is accurate up to $T\epsilon$ in $L_\infty$.


Is this an equivalent condition for algebraic posets?

An example where $A(x)$ is empty is the set of real numbers $\mathbb{R}$ with the usual ordering. It has no compact elements at all.

If we assume the second condition then $A(x)$ cannot be empty: if $A(x) = \emptyset$ then by the second condition $x$ is the empty join, therefore the least element of $L$, which is compact, therefore $x \in A(x) = \emptyset$, a contradiction.

Your proposal to replace the first condition with non-emptyness does not work. Consider the poset $L$ which consists of two copies of $\mathbb{N}$ and $\infty$, where we write $\iota_1(n)$ and $\iota_2(n)$ for the two copies of $n$, ordered by:

$\iota_1(m) \leq \iota_1(n) \iff m \leq n$
$\iota_2(m) \leq \iota_2(n) \iff m \leq n$
$x \leq \infty$ for all $x$.

In words, we have two incomparable chains with a common supremum. All elements are compact except $\infty$. Now:

${\downarrow}x \cap K(L) \neq \emptyset$, obviously.
$x = \bigvee ({\downarrow}x \cap K(L))$, obviously.
The set ${\downarrow}\infty \cap K(L) = \mathbb{N} + \mathbb{N}$ is not directed.


Common insights into hypothetical complexity of graph problems

Here are two references for the second part of your question.

The paper [1] addresses certain types of colorability of sparse graphs with given girth $g$. For every fixed $g$, they show that the associated decision problem is either trivial (every graph in the class has a coloring) or NP-complete. But determining which is the threshold value of $g$ remains a difficult open problem!
Edit: One of the considered problems is related to Jaeger's conjecture, that every planar graph of girth $4k$ admits a homomorphism to $C_{2k+1}$. It is shown in [1] that any counterexample directly provides a hardness proof. (A similar conjecture by Klostermeyer and Zhang exists for the odd-girth.) For the other problems considered in [1], there is no official conjecture, but for any guess about the correct threshold value $g$ that one can make, if proved false by a counterexample, the latter directly implies a corresponding hardness proof.

In the introduction of the above cited paper is also mentioned the following interesting result about SAT [2]. It is proved there that for every $k$, there exists a function $f(k)$ such that $(k,f(k))$-SAT (i.e. $k$-SAT where each variable occurs $f(k)$ times) is trivial, but $(k,f(k)+1)$-SAT is NP-complete. (The precise value of $f(k)$ seems unknown, although some estimate is given.)

[1] L. Esperet, M. Montassier, P. Ochem and A. Pinlou. A complexity dichotomy for the coloring of sparse graphs. Journal of Graph Theory 73:85-102, 2012. link + PDF on an author's website

[2] J. Kratochvil, P. Savicky and Zs. Tuza. One more occurrence of variables makes satisfiability jump from trivial to NP-complete. SIAM Journal on Computing 22:203-210, 1993. link


Yes, you can use Levin universal search to construct a "universal one-way function" (e.g., these lecture notes). From this one-way function you can then construct symmetric-key encryption primitives (pseudorandom generators, block ciphers, CPA/CCA-secure encryption) using standard theoretical constructions.

One-way function $\to$ pseudorandom generator:

  Håstad, J., Impagliazzo, R., Levin, L.A. and Luby, M., 1999. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4), pp.1364-1396.

Pseudorandom generator $\to$ pseudorandom function:

  Goldreich, O., Goldwasser, S. and Micali, S., 1986. How to construct random functions. Journal of the ACM (JACM), 33(4), pp.792-807.

Pseudorandom generator $\to$ block cipher / pseudorandom permutation:

  Luby, M. and Rackoff, C., 1988. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2), pp.373-386.

Block cipher $\to$ CCA-secure encryption:

  CBC mode + CBC-MAC


A variation on discrepancy involving random graphs

You could approach this with a "second moment method" calculation, similar to the one I used in A sharp threshold for a random constraint satisfaction problem, Discrete Mathematics 285/1-3 (2004), 301-305.

When the average degree grows like a sufficiently large constant times $\log n$, this approach has often been sufficient to find precisely the threshold of satisfiability.  It could possibly also show the fraction of clauses that can be satisfied in an unsatisfiable instance, although I have not investigated that.

To make your problem look more like my general one, you can view it as a "MAX-AT-LEAST-HALF-SAT" with a special graphical structure underlying the clauses in the CNF formula. I don't think that this special structure will help in a worst-case analysis, however, and since your clause size is non-uniform and your "bad" assignment set is growinyou'll have to go through the calculation and see if it still works.


Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs?

I assume, as stated in the comments, that the problem is to find a 2-factor with two cycles of length $|V|/2$ each in a cubic graph.
This problem is NP-complete:

1) HC in cubic graphs is NP-complete.

2) The following problem HC' is also NP-complete: Given a cubic graph $G$ and an edge $e$
in $G$, is there a Hamiltonian cycle through $e$. We can reduce HC to it: Given a graph $G$, replace one arbitrary vertex (left hand side) by a triangle with another vertex in it (right hand side):

Call this new graph $G'$.
$G'$ is Hamiltonian iff $G$ is. Furthermore, if $G'$ is Hamiltonian, then for any red edge, there is a Hamiltonian cycle that contains this red edge. (Without the vertex in the middle, every Hamiltonian cycle contains two green edges and any green edge can then be replaced by two red ones.) The reduction from HC to HC' maps a cubic graph $G$ to $G'$ together with any red ege.

3) Finally, we reduce HC' to the problem of the question. Given an instance
$(G,e)$, we create two copies of $G$, subdivide $e$ in each copy and connected the two vertices that subdivide the two copies by a new edge $f$. This edge $f$ is a bridge in the new graph. If $G$ has a Hamiltonian cycle through $e$, then the new graph has a 2-factor consisting of two cycles of the same size.
Conversely, if the new graph has such a 2-factor, then it cannot use $f$. Therefore, it splits into two Hamiltonian cycles of the two copies. Since in these copies, the vertex subdividing $e$ has degree two, we get a Hamiltonian cycle of $G$ that contains $e$.


Exact arithmetic complexity of Ryser's formula for computing permanent

Ryser: $n(n-2)2^{n-1} + n$ additions and $(n-1)(2^{n}-1)$ multiplications.

Ryser+Gray code: $n(2^{n}-2)$ additions and $(n-1)(2^{n}-1)$ multiplications.

Number of multiplications: For each nonempty subset of $[n]$, $n-1$ multiplications are used to multiply $n$ sums together.

Number of additions for Ryser: for each nonempty $S \subseteq [n]$, and for each $i \in [n]$ you compute $\sum_{j \in S} a_{ij}$ which uses $|S|-1$ additions. $\sum_{\emptyset \neq S \subseteq [n]}(|S|-1) = \sum_{k=1}^{n} (k-1) \binom{n}{k} = \sum_{k=1}^{n} k \binom{n}{k} - \sum_{k=1}^{n} \binom{n}{k} = n2^{n-1} - (2^{n}-1)$.

Additions for Ryser+Gray: The Gray code version does not give you a smaller formula, but only a smaller circuit (which is still good, I just thought it was worth pointing out). Its savings require the re-use of previously computed quantities. For each $i \in [n]$, it does a Gray code over the nonempty sets $S \subseteq [n]$. Since there are $2^{n}-1$ such sets, and each transition of the Gray code involves a single addition/substraction, that gives the $2^{n}-2$.


Just an alternative proof using a mix of well known results.

Suppose that:

variables are expressed with the regular expression $d = (+|-)1(0|1)^*$
and that the (regular) language (over $\Sigma = \{0,1,+,-,\land,\lor\})$ used to represent CNF formulas is: $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$; just note that $S$ grabs all valid CNF formulas up to variable renaming.

For example $\varphi = (x_1 \lor x_2) \land -x_3$ is written as: $s_{\varphi} = +1 \lor +10 \land -11 \in S$ (the $\lor$ operator has the precedence over $\land$).

Suppose that $L = \{ s_{\varphi} \in S \, \mid $ s.t. the corresponding formula $\varphi$ is satisfiable $\}$ is CF .

If we intersect it with the regular language: $R = \{ +1^a \land  -1^b \land -1^c \mid a,b,c > 0 \}$ we still get a CF language. We can also apply the homomorphism: $h(+) = \epsilon$, $h(-) = \epsilon$ and the language remains CF.

But the language we obtain is: $L' = \{ 1^a \land 1^b \land 1^c \mid a \neq b, a \neq c\}$, because if $a=b$ then "source" formula is $+x_a \land -x_a \land -x_b$ which is unsatisfiable (similarly if $a=c$). But $L'$ is a well known non CF language $\Rightarrow$ contradiction.


Graph partition optimization with weights on edges and vertices

(not quite an answer, but too long for a comment)

Given your new cost function, I'm wondering if there's a simpler formulatio. Let $W = \sum_{(i,j) \in E} w_{ij}$. Now your goal is to maximize

\[ W - \sum_{|\{i,j\} \cap S| = 1} w_{ij} + \sum_{|\{i,j\} \cap S| = 1} w_{ij}u_j\]

Collecting terms, your goal is then to minimize

\[ \sum_{|\{i,j\} \cap S| = 1} w_{ij} (u_j - 1)\]

Setting $w'_{ij} = w_{ij}(u_j - 1)$, your problem now becomes a min cut problem with the twist that it's not a typical min cut (you're not counting edges going from one side to the other, but both sides)


Intersection of two deterministic parity automata

The following paper:
http://www.faculty.idc.ac.il/udiboker/files/AutomataTypes.pdf
shows that the intersection (and union) of deterministic parity automata may involve an exponential blowup.

Thus, you cannot do much better than converting to nondeterministic Buchi automata, and taking the intersection there (and determinizing back to parity).


Your problem is equivalent to MAX SMTI (Stable Marriage with Ties and Incomplete lists).  You can find the current best approximation algorithm for MAX SMTI in the following paper:
Z. Kiraly, Linear Time Local Approximation Algorithm for Maximum
Stable Marriage, Algorithms 2013, 6, 471-484.

There are many papers on MAX SMTI, but unfortunately I am not aware of any paper that handles the weighted version of MAX SMTI.


Judging from their archive, it seems that since 1994 the Journal of the ACM is issued 6 times a year, so roughly every other month. Until 2006 it was published on odd months. From 2007 on, the schedule seems to be somewhat random, but there are still 6 issues a year (though sometimes one of them is published on the wrong year, as in 2009 and 2010).


The exponential function over algebraic numbers

As written, the problem requires time $2^{\Omega(m)}$, where $m$ is the length of input (you unfortunately used $n$ for something else). Indeed, if e.g. $\alpha$ is a positive integer (given by its minimal polynomial $x-\alpha$) and $n=0$, the size of the output is exponential in the size of the input. This bound is of course optimal, as there are a number of ways how to compute the result in time $2^{O(m)}$.

Let me try to reformulate the question so that it makes a bit more sense. The main issue is how to choose the representation of the input and output, as well as the notion of approximation, so that exponentiation stands a fighting chance of being computable in polynomial time.

One way was mentioned by Kaveh in the comments: restrict the domain to a fixed finite interval. While this works, it is unnecessarily restrictive; in particular, there is no good way how to transform an algebraic number into one that is bounded so that their exponentials have anything to do with each other.

A more flexible approach is to represent the input as a fixed point number, and the output as a floating point number. To be specific, a fixed point representation is a string
$$\pm a_ra_{r-1}\dots a_0.a_{-1}\dots a_{-s}$$
denoting $\pm\sum_ja_j2^j$, where $a_j\in\{0,1\}$, and a floating point representation is
$$\pm2^e\times a_0.a_{-1}\dots a_{-s}$$
with a similar interpretation, where $e$ is a binary integer, and $a_0=1$. (As an exception, we also allow $0$ to represent itself.) An approximation of a real $x$ to $m$ bits of absolute accuracy is a real $x'$ such that $|x-x'|<2^{-m}$, and an approximation to $m$ bits of relative accuracy is $x'$ such that $|1-x'/x|<2^{-m}$. We will use absolute accuracy for fixed point approximations, and relative accuracy for floating point approximations. It follows that in both cases, we may as well assume $s\le m$ (up to loss of one bit of accuracy).

Fixed point and floating point representations of dyadic Gaussian rationals, and approximations of complex numbers, are defined similarly, using a pair of reals. Everywhere below, $n$ denotes the total size of the input.

Now, let (real or complex) exponentiation be the following problem: the input is a fixed point representation of a number $x$ and a unary natural number $m$, and the output is a floating point approximation of $e^x$ to $m$ bits of relative accuracy. Dually, logarithm takes as input a floating point number $x$ and unary $m$, and the output is a fixed point approximation of $\log x$ (say, the principal branch in the complex case) to $m$ bits of absolute accuracy.

As long as we stick to run-time bounds satisfying some mild regularity conditions, and ignore constant multiplicative factors, we have:

The complexity of exponentiation, logarithm, or any similar analytic function, is at least the complexity of integer multiplication: e.g., we can read off $a^2$ from $\exp(a2^{-t})=a2^{-t}+a^22^{-2t-1}+O(a^32^{-3t})$ for sufficiently large $t$, linear in the length of $a$.
Exponentiation and logarithm have the same complexity. The reason is that we can compute the inverse of a nice function by Newton iteration (or more sophisticated methods such as in Brent) using evaluation of the function itself. The iteration typically involse multiplications or divisions, but we can afford these by the previous point.

As for algebraic numbers $\alpha$, they can be represented by their minimal polynomial $f$ (written as a sequence of integer coefficients in binary) together with some means to distinguish between the roots of the same polynomial. A natural way to do that is to require an isolation interval or disk: a pair of fixed point numbers $c,\rho$ such that $|c-\alpha|<\rho$. We need to at least require that $\alpha$ is a unique root of $f$ with this property, but something stronger may be more suitable. More on that later.

Let algebraic number approximation be the following problem: given an algebraic number $\alpha$ in the representation above, and $m$ in unary, compute a (complex) fixed point approximation of $\alpha$ to $m$ bits of absolute accuracy.

$\DeclareMathOperator\re{Re}$The original question asked for $\re e^\alpha$, but let me ignore that for now, and define algebraic number exponentiation as the following problem: given $\alpha$ and $m$ as above, compute a (complex) floating point approximation of $e^\alpha$ to $m$ bits of relative accuracy.

  Fact: Up to linear factors, the complexity of algebraic number exponentiation is the same as the complexity of algebraic number approximation plus the complexity of complex exponentiation.

Proof sketch: On the one hand, we can first compute the fixed point approximation of $\alpha$ and then exponentiate it. Note that $m+O(1)$ bits of absolute accuracy for $\alpha$ determine $e^\alpha$ to $m$ bits of relative accuracy, and vice versa.

On the other hand, if we can do algebraic number exponentiation, we can also do plain exponentiation, as we can readily convert a fixed point number (considered exact) to its representation as an algebraic number. By the comments above, this means we can also compute logarithms in the same time bound. Thus, we can approximate an algebraic number by first approximating $e^\alpha$, and then taking a logarithm. QED

This splits the question to two quite unrelated problems. The best known upper bound on exponentiation is

  Theorem (Brent): If we can multiply $n$-bit integers in time $M(n)$, we can compute complex exponentiation (and logarithm) in time $O(M(n)\log n)$.

The best known lower bound is the $\Omega(M(n))$ mentioned above. The best known upper bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$ by Fürer’s algorithm.

Figuring out the state of art for algebraic number approximation (that is, root finding) is rather harder, as it is still an area of active research, and the formulations of bounds in the literature are often not as clear as one would want them. Let $\tilde O(f(n))$ denote $O(f(n)\mathrm{polylog}(f(n)))$.

For real root approximation, Pan and Tsigaridas give:

  Theorem: Real algebraic number approximation can be done in time $\tilde O(d^2\tau+dm)$, where $d=\deg(f)$, and $\tau$ is maximum of bit-lengths of the coefficients of $f$.

In the same paper, they mention $\tilde O(d^3+d^2m)$ as the best known bound for complex root approximation. In a slightly more recent paper (http://arxiv.org/abs/1404.4775), they seem to claim the same bounds for the complex case as for the real case, under the assumption that the given isolation disk has isolation ratio (the distance of the disk’s center to the nearest other root of $f$ divided by the radius of the disk) at least $1+1/\log d$ or so, but it’s written in a rather messy way and I may misinterpret it.

Now, the final complication. I defined the problem as approximation of $e^\alpha$, whereas the question asks for $\re e^\alpha$. This actually makes the problem harder: if $\re e^\alpha\ll\operatorname{Im}e^\alpha$, then an approximation $x+iy$ of $e^\alpha$ to $m$ bits of relative accuracy has error $y2^{-m}$, which may well be larger than $x$ itself, and in any case is not guaranteed to be bounded by $x2^{-m}$.

For exponentiation of exact rationals, we can circumvent the problem:

  Proposition: Given $\alpha=x+iy$ and unary $m$, where $x,y$ are binary rationals (or exact fixed point numbers), we can compute a floating point approximation of $\re e^\alpha$ to $m$ bits of relative accuracy within the same time bound as complex exponentiation as defined above, up to linear factor. (I.e., $O(M(n)\log n)$ using Brent’s algorithm.)

Proof sketch: We have $\re e^\alpha=e^x\cos y$. We can approximate $e^x$, and floating point numbers are easily multiplied, the problem is to approximate $\cos y$ with relative error $2^{-m}$. We can compute the integer $k$ nearest to $2y/\pi$, whence $\cos y$ is $\pm\cos y'$ or $\pm\sin y'$, where $y'=y-k\frac\pi2$ satisfies $|y'|\le\pi/4$. The issue arises when we need to compute $\sin y'$ and $y'$ is very small, since in order to have $\sin y'$ to $m$ bits of relative accuracy, we need $m+\log|{y'}^{-1}|$ bits of absolute accuracy. Assume that $y=u/v$, where $u,v$ are integers given as input. If $y'$ is small, we have a good rational approximation of $\pi$:
$$\left|\pi-\frac{2u}{kv}\right|\le\frac{2|y'|}k.$$
Now, $\pi$ is known to have a finite irrationality measure $\nu$ (the current bound is $7{.}6063$ by Salikhov). This implies
$$|y'|\ge\frac1{2k^{\nu-1}v^\nu},$$
which gives a linear upper bound on $\log|{y'}^{-1}|$ in terms of the length of the input. We can thus compute $y'$ to the desired accuracy; evaluating $\sin y'$ is then not a problem (if $y'$ is sufficiently small, we can just take $\sin y'\approx y'$). QED

I do not know whether the same holds for algebraic $\alpha$. In the argument above, one can get a bound on $\log|y'|$ from Baker’s theorem, however, none of its versions that I’ve seen is good enough to make the required accuracy linear in the size of the input: in particular, the bounds involve a (rather nasty) polynomial in $\deg(f)$. This makes the resulting algorithm polynomial in the size of the input, but with a ridiculous exponent.


Is uniform convergence faster for low-entropy distributions?

First, let's use McDiarmid's inequality to conclude that
$$\mathbb{P}\left[|| \bar X - \mu ||_\infty \ge
\mathbb{E}|| \bar X - \mu ||_\infty
+
\varepsilon \right] \le  e^{-2n\varepsilon^2},$$
so it remains to bound $\mathbb{E}|| \bar X - \mu ||_\infty$.
Using Jensen's inequality,
$$ (\mathbb{E}|| \bar X - \mu ||_\infty)^2\le \mathbb{E}|| \bar X - \mu ||_\infty^2
\le \sum_{j=1}^d\mathbb{E}(\bar X(j)-\mu(j))^2=
\sum_{j=1}^d\mathrm{Var}[\bar X(j)]=\frac1{n^2}\sum_{j=1}^d\mathrm{Var}[X(j)],
$$
whence
$$ \mathbb{E}|| \bar X - \mu ||_\infty\le
\frac1{n}\sqrt{\sum_{j=1}^d\mathrm{Var}[X(j)]}.
$$
For sufficiently small variances, this is an improvement over your bound.

Update. A different approach would be to introduce the Rademacher random variables $\sigma_i$ and to use the standard symmetrization argument to obtain
$$ \mathbb{E}|| \bar X - \mu ||_\infty
\le2\mathbb{E}\max_{j\in[d]}\frac1n\sum_{i=1}^n\sigma_i X_i(j),
$$
where $X_i(j)$ indicates the $j$th bit of $X_i$. Now there must be a way to bound the latter Rademacher complexity using the entropy of $\mathcal{D}$, but I don't have anything off the top of my head. Massart's finite class lemma will give you a distribution-free bound of $O(\sqrt{\log(d)/n})$.


An analog of DP for the second level of the polynomial hierarchy

The definition of the class that you are referring to is interesting.

Originally, the definition of the class $D^P$, as the class of the languages that are the intersection of an $NP$ language and a co-$NP$ language, appeared in [1].
Then, the idea behind $D^P$ was generalized to the Boolean Hierarchy ($BH$) [2], which is a hierarchy between $NP$ and $\Delta^P_2$, and $D^P$ is at the second level of $BH$, i.e, $D^P = BH(2)$.
The definition of $BH$ was subsequently extended to the "Boolean Hierarchy over $\Sigma^P_2$" ($BH_3$) [3], which is a hierarchy similar to $BH$ but located between $\Sigma^P_2$ and $\Delta^P_3$.
In $BH_3$, at the second level, there is the class that you are mentioning.
Hence, in the literature, this class is sometimes denoted by $BH_3(2)$.
However, for the similarity between the definitions of $BH_3(2)$ and $BH(2) = D^P$, pretty soon, in the literature, the notation $D^P_k$ was used to denote the generalization of $D^P$ to upper levels in the polynomial hierarchy, even before a formal definition of it was given.
Therefore, the class you are referring to is usally denoted by $D^P_2$.

Regarding the $D^P_k$-hardness of languages, similarly to other definitions, a language $L$ is $D^P_k$-hard if, for every language $L'\in D^P_k$, there is a polynomial reduction from $L'$ to $L$.
Unfortunately, showing that a language $L$ is $\Sigma^P_k$-hard and $\Pi^P_k$-hard is not enough to show that $L$ is $D^P_k$-hard.
However, if there is a reduction from a $D^P_k$-hard language $L'$ to $L$, then $L$ is $D^P_k$-hard as well.
In this respect, it is helpful what it is said in a comment to the initial question.
In fact, a problem $L$ can be shown to be hard for $D^P_k$ if there is a polynomial reduction to $L$ from the task of recognizing pairs of "yes"-instances of two languages, one $\Sigma^P_k$-hard and the other $\Pi^P_k$-hard.
More formally, given two languages $L_1$ and $L_2$, which are $\Sigma^P_k$-hard and $\Pi^P_k$-hard, respectively, if there is a polynomial reduction $h$ such that $\langle s_1,s_2\rangle\in L_1\times L_2 \Leftrightarrow h(\langle s_1,s_2\rangle)\in L$, then $L$ is $D^P_k$-hard [4, by a generalization of the argument in the proof of Theorem 17.1].

[1] C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244–259, 1984. DOI: 10.1016/0022-0000(84)90068-0

[2] J.-Y. Cai, T. Gundermann, J. Hartmanis, L. A. Hemachandra, V. Sewelson, K. W. Wagner, and G. Wechsung. The boolean hierarchy I: Structural properties. SIAM Journal on Computing, 17(6):1232–1252, 1988. DOI: 10.1137/0217078.

[3] R. Chang and J. Kadin. The boolean hierarchy and the polynomial hierarchy: A closer connection. SIAM Journal on Computing, 25(2):340–354, 1996. DOI: S0097539790178069.

[4] C. H. Papadimitriou. Computational Complexity. Addison Wesley, Reading, MA, USA, 1994.