Are there non-closed complexity classes for which there are complete problems?

I assume that you are asking about the relation between a complexity class having a complete problem under a certain notion of reducibility and the same complexity class being closed under the same notion of reducibility.  It is a common misunderstanding that these two notions are related.  They are not!

For example, SAT is an NP-complete problem under polynomial-time Turing reducibility.  But NP is not closed under polynomial-time Turing reducibility unless, say, NP=coNP.  On the other hand, PH is closed under polynomial-time Turing reducibility, but PH does not have a complete problem unless the polynomial hierarchy collapses to a finite level.

This is not to say that complete problems and the closure property are unrelated.  For example, consider the equivalence that P=NP if and only if SAT∈P.  One explanation for this equivalence is that it holds because SAT is NP-complete under polynomial-time Turing reducibility and P (not NP!) is closed under the same notion of reducibility.  Of course, this is a little contrived explanation for this equivalence because we do not have to use Turing reducibility and we can use many-one reducibility instead, under which both P and NP are closed.  But when we consider classes of relation problems such as FP and FNP and consider polynomial-time function reducibility, then we have to be careful about which class is closed and which class is not, because FNP is not necessarily closed under polynomial-time function reducibility.  Still, the notion of FNP-complete problems is useful because FP is closed under polynomial-time function reducibility.


Complexity of counting m-cycles in a graph with n nodes

Perhaps this paper which deals with cycle lengths in planar graphs might be of value:

Li, Ming-Chu; Corneil, Derek G.; Mendelsohn, Eric (2000), "Pancyclicity and NP-completeness in planar graphs", Discrete Applied Mathematics 98 (3): 219–225.


Treewidth of two complete binary trees joined at their leaves

Indeed, this graph has treewidth 2. It's a well-known result in phylogenetics where the leaves are labelled. See Bryant, David, and Jens Lagergren. "Compatibility of unrooted phylogenetic trees is FPT." Theoretical Computer Science 351.3 (2006): 296-302. The graph structure they use unifies leaves with the same label (rather than putting an edge between them), but their graph can be obtained from yours by suppressing degree-2 vertices, and this does not impact upon the treewidth.


Complexity of Finding Largest Set of Intersecting Convex Polytopes

Suppose that the dimension $d$ of the Euclidean space is fixed, and that the input consists of $n$ convex polytopes in $\mathbb{R}^d$ that altogether have $p$ facets.

Let $h_1,\ldots,h_p$ denote the supporting hyperplanes for the $p$ facets of the input polytopes. The arrangement of $h_1,\ldots,h_p$ is the decomposition of $\mathbb{R}^d$ into connected open cells of dimensions $0,1,\ldots,d$.
It is well-known that the arrangement has combinatorial complexity $O(p^d)$ and that it can be computed in time $O(p^d)$; see for instance

  Chapter 28 "Arrangements" by D. Halperin and M. Sharir,
  in Handbook of Discrete and Computational Geometry (edited by J.E. Goodman, J. O'Rourke, and C.D. Tóth)
  https://www.csun.edu/~ctoth/Handbook/chap28.pdf

So you may compute the arrangement in polynomial time $O(p^d)$, and then compute for every cell $C$ in the arrangement the number $x(C)$ of input polytopes that contain $C$.
The maximum of all these numbers $x(C)$ yields the answer to your question.


Why can machine learning not recognize prime numbers?

The question is, in my opinion, quite vague and involves some misunderstanding, so this answer attempts only to provide the right vocabulary and point you in the right direction.

There are two fields of computer science that directly study such problems. Inductive inference and computational learning theory. The two fields are very closely related and the distinction is a social and aesthetic one, rather than a formal one.

Fix a finite alphabet $A$ and the set of all languages $\mathcal{P}(A^*)$ consisting of finite-length words over $A$. This is everything you can express in terms of $A$. Now consider a family of languages $\mathcal{F} \subseteq \mathcal{P}(A^*)$. You can think of this as the concepts you are interested in. You often have to fix the family of concepts you care about because, as others have pointed out, the representation of the concept and presentation of data are extremely important.

Imagine a teacher who is going to teach you a concept. The teacher will choose one of the languages without your knowledge. The teacher will then present information to you about the language. There are many presentations. The simplest is to give you examples. A presentation of positive data is a function $f: \mathbb{N} \to A^*$ satisfying that

$$\bigcup_{i \in \mathbb{N}} f(i) = T, \text{ for some } T \text{ in } \mathcal{F}.$$

So, a presentation of positive data is an enumeration of the target concept, often with some additional fairness conditions thrown in. You can similarly ask for a presentation that labels words depending on whether they are in the language or not. Again, you can add additional conditions to ensure fairness and coverage of all words.

Suppose we have a family $Rep$ of representations of languages. That means every element $M$ of $Rep$ defines a language $L(M)$. Examples of representations are Boolean formulae, finite automata, regular expressions, systems of linear equations, domain specific programming languages, etc. Anything you want, really, except various condition are usually imposed to ensure the representation has basic tractability properties.

A passive learner is a function $p: \mathbb{N} \to Rep$ that makes a conjecture after seeing each word provided by the teacher. We may often require that the learner is consistent. Meaning, the language $L(p(i))$ should contain all the words $f(j)$ for $j \le i$. The learner stabilizes if the learner's guess for the target language does not change. Specifically, there should exist some index $k$ such that for all $j \ge k$, $L(p(j)) = L(p(j+1))$. The learner succeeds if the final language equals the target language.

Let me emphasise that this is only one specific formalisation of one specific learning model. But this is step zero before you can start asking and studying questions that you are interested in. The learning model can be enriched by allowing interaction between the learner and the teacher. Rather than arbitrary families of languages, we can consider very specific languages, or even specific representations (such as monotone Boolean functions). There is a difference between what you can learn in each model and the complexity of learning. Here is one example of a fundamental impossibility result.

  Gold [1967] No family of languages that contains all finite languages and at least one super-finite language is passively learnable from positive data alone.

One should be very very careful in interpreting this result. For example, Dana Angluin showed in the 80s that

  Angluin [1982] The class of $k$-reversible languages is passively learnable in the limit from positive data.

The class of $k$-reversible languages is infinite, contains super-finite languages, but interestingly, does not contain all finite languages. Now once you change the learning model, the fundamental results change.

  Angluin [1987] Regular languages are learnable from a teacher that answers equivalence queries and provides counterexamples. The algorithm is polynomial in the set of states of the minimal DFA and length of the maximal counterexample.

This is quite a strong and positive result and recently has found several applications. However, as always the details are important, as the title of the paper below already suggests.

  The minimum consistent DFA problem cannot be approximated within and polynomial
  , Pitt and Warmuth, 1989.

Now you may be wondering, how is any of this relevant to your question? To which my answer is that the design space for a mathematical definition of your problem is very large and the specific point you choose in this space is going to affect the kind of answers you will get. The above is not meant to be a comprehensive survey of how to formalise the learning problem. It's just meant to demonstrate the direction you may want to investigate. All the references and results I quote are extremely dated, and the field has done a lot since then. There are basic textbooks you could consult to obtain the sufficient background to formulate your question in a precise manner and determine if the answer you seek already exists.


A public key cryptographic technique usable without aid of computer

Secure cryptographic protocols that can be executed by humans are considered in this paper: http://link.springer.com/chapter/10.1007%2F3-540-45682-1_4 (Hopper and Blum, "Secure Human Identification Protocols"). Reading the abstract, it sounds like they don't fully solve the problem. I suspect a satisfying solution is not known, but if you want to look into it I would start by looking at papers citing this one.


Algorithmic game theory - nonstandard equilibrium concepts?

You may be looking for something like Sink Equilibria (start from e.g. http://arxiv.org/abs/0902.0382 ) -- but the cycle length is not considered.


By simplification I understand either minimization or determinization. I'll try to sum up what I know about both problems, in the quite general setting of weighted automata over arbitrary semiring. The original works were done by Marcel-Paul Schützenberger (who introduced them), and you'll find a nice account of what is known about them in the book Elements of Automata Theory by Jacques Sakarovitch (also available in French):
For shorter explanations, check out the lecture notes by Jacques Sakarovitch again:

For both minimization and determinization (called "sequentialization") there are nice theoretical answers. For instance, every weighted automaton over a field can be minimized in polynomial time (see for instance this lecture note).


Mergeable Exact Order Statistics Data Structure

Most balanced trees that have logarithmic-time insert and delete also have logarithmic time $merge$. This includes AVL trees, red-black trees, and B trees.

You can see this question on Stack Overflow for several references results. They include a paper on CGAL (red-black), a reference to the OCaml standard library (AVL), as well as the red-black tree chapter of CLRS's Introduction to Algorithms.

When I was learning about this topic, I was happy to find that $merge$ is actually usually a simpler operation than $insert$ and $delete$.


Difference between Strict Consistency and Sequential Consistency

You are not missing anything :)

Dekker's algorithm will not be sequentially consistent on distributed shared memory hierarchy based multiprocessor but it is very much possible as the memory updates propagate not in step with local memory (cache) update but asynchronously through Cache Coherence protocols like MESI (Weaker memory model).

On a uni-processor on which Dekker's algorithm this is not the case and it will be strictly consistent.


The problem is strongly NP-complete.

Reduction from 3-partition, a strongly NP-complete problem. The multiset $S$, $|S| = 3m$, $\sum_{x \in S} x = n$ can be partitioned into tuples of size three of equal sum if and only if $A \leq B$ where $A = S$ and $B$ is $m$ duplicates of $\frac{n}{m}$. If $A \leq B$, we can have $C = A$. If $A \not\leq B$, we must have $|C| > |A|$, hence a 3-partition exists if and only if a set $C$ of size $|A|$ exists.

As for approximations, a trivial 2-approximation exists, since $\max(|A|, |B|) \leq |C| \leq |A| + |B|$. Construction: Build $C$ by always taking smallest integer in either of $A$ or $B$, then remove it from that set, and subtract it from an arbitrary integer in the other set. The value $|C| + |A| + |B|$ can only decrease over the course of the algorithm. This also shows that the problem is in NP.


How do I use canonical ordering to reduce symmetry in the SAT encoding of the pigeonhole problem?

Let $m$ be the number of pigeons and $n$ be the number of holes.  Let the propositional variables $B_{i,0}$ ... $B_{i,log(n)}$ encode the binary representation of $j-1$ if the $i$th pigeon is put into the $j$th hole. (Example, if pigeon 1 were placed in hole 10, $j - 1 = 9$, which is binary 1001.  So $B_{1,3}$ = true, $B_{1,2}$ = false, $B_{1,1}$ = false and $B_{1,0}$ = true.)

Enforce a particular ordering of the pigeons in the holes by requiring that the hole encoded by the $B_{i}$ variables is less than that of $B_{i+1}$.  The encodings are compared as you would expect:

$B_{i,log(n)}$ < $B_{i+1,log(n)}$
OR
$B_{i,log(n)}$ = $B_{i+1,log(n)}$ AND $B_{i,log(n)-1}$ < $B_{i+1,log(n)-1}$
OR
$B_{i,log(n)}$ = $B_{i+1,log(n)}$ AND $B_{i,log(n)-1}$ = $B_{i+1,log(n)-1}$ AND $B_{i,log(n)-2}$ < $B_{i+1,log(n)-2}$
OR
...

... following the pattern of allowing the most significant bits to be equivalent as long as the next bit to the right is less than that of the next pigeon.  There will be $O(log(n))$ conjunctions per comparator and $O(m)$ comparators, giving the expected $O(m * log(n))$ additional clauses.

The $B$ variable values must be implied by the $X_{i,j}$ values.  Each $B_{i,*}$ bit is implied by any one of a particular set of the $X_{i,j}$ variables being set.  Example: assuming $n = 16$, you would have:

$ExactlyOne(X_{1,9}, X_{1,10}, X_{1,11}, X_{1,12}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,3}})$

which forces $B_{1,3}$ true if pigeon 1 is placed in any of holes 9-16.  Otherwise $B_{1,3}$ is set false to satisfy the clause.  These clauses set the remaining $B_{i}$ bits.

$ExactlyOne(X_{1,5}, X_{1,6}, X_{1,7}, X_{1,8}, X_{1,13}, X_{1,14}, X_{1,15}, X_{1,16}, \overline{B_{1,2}})$
$ExactlyOne(X_{1,3}, X_{1,4}, X_{1,7}, X_{1,8}, X_{1,11}, X_{1,12}, X_{1,15}, X_{1,16}, \overline{B_{1,1}})$
$ExactlyOne(X_{1,2}, X_{1,4}, X_{1,6}, X_{1,8}, X_{1,10}, X_{1,12}, X_{1,14}, X_{1,16}, \overline{B_{1,0}})$

There will be $log(n)$ of these clauses for each pigeon.  Since there are $m$ pigeons, $m * log(n)$ clauses are added.


This is a basic question, yet I tend to answer simple ones too :)

In the book you mentioned, take a look at section 1.2.1 (page 18). It describes how various objects are encoded. Among other things, it includes a section "Strings," in which "relation encoding" is described:

At times, we associate $\{0, 1\}^∗ \times \{0, 1\}^∗$ with $\{0, 1\}^∗$; the reader should merely consider an adequate encoding (e.g., the pair
$(x_1 \dots x_m, y_1 \dots y_n) \in \{0, 1\}^∗ \times \{0, 1\}^∗$
may be encoded by the string $x_1x_1 \dots x_mx_m01y_1 \dots y_n \in \{0, 1\}^∗$).

Functions are a special type of relation, so they can be similarly encoded. In particular, a (finite and discrete) function can be seen as a list of input-output relations: $f=\{(x_1,y_1),\dots,(x_n,y_n)\}$. This can be easily encoded by incorporating a special symbol, say $\circ$. That is, $enc(f)=x_1 \circ y_1 \circ \dots \circ x_n \circ y_n$. (The encoding can be done without any special symbol, but it adds unnecessary intricacy.)

This way, the size of $f$ is the size of its encoding: $|enc(f)| \approx \sum_{i=1}^{n}{(|x_i|+|y_i|)}$.

Needless to say, infinite functions have infinite size, unless you can compress the list somehow. (This brings up the "Kolmogorov Complexity Theory", which is a story for another day!)


Transitive feedback arc set (TFAS): NP-complete?

To add a little context, here's a construction for a graph that doesn't have a transitive feedback arc set. For this construction, I'll use the following gadget graph:

This tournament has the following properties (which I checked using a program, I didn't prove it formally):

if (2,7) is not in a given TFAS, then (1,3) is
if (5,1) is in a given TFAS, then so is (3,6)
if (7,3) is in a given TFAS, then (5,1) is not

or slightly abusing predicate logic notation:

$\neg (2,7) \rightarrow (1,3)$
$(5,1) \rightarrow (3,6)$
$(7,3) \rightarrow \neg (5,1)$

You'll notice that for each implication, the two edges are pairwise disjoint, so the following construction works:

I hope you can make out the idea of the graph: using the implication properties of the tournament above, we can construct a graph in which each transitive feedback arc set both includes and doesn't include the edge $A$, i.e. a contradiction, which means the graph doesn't have a transitive feedback arc set. Any completion of that graph cannot have one either since the same contradiction will remain in any completion. I left out a large number of vertices, all of which can be derived from substituting the tournament above for the implications.


What is the minimum over all distributions of unit vectors of the variance of the dot product of the vectors?

I will present an equivalent but simpler-looking formulation of the problem, and show a lower bound of (n/k − 1) / (n−1).  I also show a connection to an open problem in quantum information.  [Edit in revision 3: In earlier revisions, I claimed that an exact characterization of the cases in which the lower bound shown below is attained is likely to be difficult because an analogous question in the complex case includes an open problem about SIC-POVMs in quantum information.  However, this connection to SIC-POVMs was incorrect.  For details, see the section “Incorrect connection to SIC-POVMs in quantum information” below.]

Equivalent formulation

First, as was already pointed out in daniello’s answer, note that Var(xiTxj) = E[(xiTxj)2] − E[xiTxj]2 = E[(xiTxj)2].  So in the rest of the answer, we forget about variance and instead minimize maxi≠jE[(xiTxj)2].

Next, once we decide our goal is to minimize maxi≠jE[(xiTxj)2], we can ignore the constraint that E[xiTxj] = 0.  This is because if we have random unit vectors x1, …, xn, then we can negate each of them independently with probability 1/2 to satisfy E[xiTxj] = 0 without changing the value of the objective function maxi≠jE[(xiTxj)2].

Moreover, changing the objective function from maxi≠jE[(xiTxj)2] to (1/(n(n−1)))∑i≠jE[(xiTxj)2] does not change the optimum value.  The latter is at most the former because the average is at most the maximum.  However, we can always make the values of E[(xiTxj)2] for different choices of (i, j) (i≠j) equal by permuting the n vectors x1, …, xn randomly.

So for any n and k, the optimum value of the problem in question is equal to the minimum of (1/(n(n−1)))∑i≠jE[(xiTxj)2] where x1, …, xn are random variables which take unit vectors in ℝk as values.

However, by linearity of expectation, this objective function is equal to the expected value E[(1/(n(n−1)))∑i≠j(xiTxj)2].  Because the minimum is at most the average, there is no need to consider probability distributions anymore.  That is, the optimum value of the problem above is equal to the optimum value of the following:

  Choose unit vectors x1, …, xn ∈ ℝk to minimize (1/(n(n−1)))∑i≠j(xiTxj)2.

Lower bound

Using this equivalent formulation, we will prove that the optimal value is at least (n/k − 1) / (n−1).

For 1≤i≤n, let Xi=xixiT be the rank-1 projector corresponding to the unit vector xi.  Then, it holds that (xiTxj)2 = Tr(XiXj).

Let Y = ∑iXi.  Then, it holds that ∑i≠jTr(XiXj) = ∑i,jTr(XiXj) − n = Tr(Y2) − n.

The Cauchy–Schwarz inequality implies that Tr(Y2) ≥ (Tr Y)2/k = n2/k, and therefore ∑i≠jTr(XiXj) = Tr(Y2) − n ≥ n2/k − n.  By dividing by n(n−1), we obtain that the objective value is at least (n/k − 1) / (n−1).

In particular, when n=k+1, daniello’s answer is within a factor of 2 from the optimal value.

When is this lower bound attainable?

Attaining this lower bound (n/k − 1) / (n−1) is equivalent to making Y=(n/k)I.  I do not know the exact characterization when it is attainable, but following sufficient conditions exist:

When n=k+1, it is attainable by considering k+1 unit vectors which form a regular k-simplex centered at the origin, improving from 2/(k(k+1)) in daniello’s answer to the optimal 1/k2.
When n is a multiple of k, it is clearly attainable by fixing an orthonormal basis of ℝk and assigning each of the basis vectors to n/k of v1, …, vn.
More generally than the last bullet point, if it is attainable with some choice of k and both n=n1 and n=n2, then it is also attainable for the same k and n=n1+n2.  In particular, it is attainable if n=ak+b where a and b are integers satisfying a≥b≥0.

Although I have not checked details, it seems that any spherical 2-design gives a solution attaining this lower bound.

Incorrect connection to SIC-POVMs in quantum information

In earlier revisions, I stated:

  I suspect that answering this completely is a difficult question.  The reason is that if we instead consider the complex vector space ℂk, this question is related to an open problem in quantum information.

But this relation was incorrect.  I will explain why.

  More precisely, consider the following problem:

    Choose unit vectors x1, …, xn ∈ ℂk to minimize (1/(n(n−1)))∑i≠j|xi*xj|2.

  The lower bound above equally holds in this complex version.   Consider the case where n=k2 in the complex version.  Then the lower bound is equal to 1/(k+1).

So far, it was correct.

  A set of k2 unit vectors x1, …, xk2 ∈ ℂk attaining the lower bound is called a SIC-POVM in dimension k,

This part was incorrect.  A SIC-POVM is a set of k2 unit vectors x1, …, xn ∈ ℂk for which |xi*xj|2 = 1/(k+1) for all i≠j.  Note that here the requirement must hold for all pairs i≠j, not just the average over all pairs i≠j.  In the “Equivalent formulation” section, we showed the equivalence between minimizing the maximum and minimizing the average, but this was possible because x1, …, xn were random variables taking unit vectors there.  Here x1, …, xn are just unit vectors, so we cannot use the same trick.


This is sort of an unserious answer in that it's not what I consciously do most of the time, but:

Think about what the next paper after yours might be — not the next paper that takes some small follow-on problem from your paper and solves that too, but the next paper that takes it to another level, finds tight upper and lower bounds, shows that it's an instance of a more general phenomenon, and generally makes your paper obsolete. Then write about the results in that paper instead of the ones you already have.


What is the computational complexity of this SAT Variant

The class ${\bf C_=P}$ is defined to be the set of languagges $L$ such that there exist functions $f \in {\bf \# P}$,$t\in {\bf FP} $ and for all $x, x\in L$ if and only if $f(x)=t(x)$.  Exact-SAT is the standard complete language for ${\bf C_=P}$. Exact-SAT = $\{F, k\} | F$ is a Boolean formula with exactly $k$ satisfying truth assignments.  It is known that ${\bf CoNP} \subseteq {\bf US} \subseteq {\bf C_=P}$  See the paper "On the Power of Deterministic Reductions to ${\bf C_=P}$ " by Frederic Green.


Euclidean Capacitated Facility Location Problem

If I rmemeber correctly, you have to approximate the number of clients connected to each gate. Otherwise, you would immediately get something like $O(n^{O(g)})$, where $g$ is the number of gates in a subproblem. By approximating this number up to a facotr of $(1+\varepsilon/\log n)$ throughout the dynamic programming one can get a $(1+\varepsilon)$ error in the end. That would yield running times similar to what you stated above.


Known property? Maximum radius of connected induced subgraph

The property $\Pi_r$, defined as containing exactly the graphs $G$ such that every induced subgraph $H$ of $G$ has diameter at most $r$, is the same as the class of graphs that do not contain a $P_{r+2}$ as induced subgraph, where the $P_{r+2}$ is the path on $r+2$ vertices.

The equivalence can be seen as follows. The two degree-one vertices in the $P_{r+2}$ have a distance of $r+1$. Hence, if $G$ contains a subgraph isomorphic to the $P_{r+2}$, then $G$ does not fulfill $\Pi_r$. Conversely, if $G$ does not fulfill $\Pi_r$, then $G$ has an induced subgraph $H$ containing two vertices $u$ and $v$ such that the distance between $u$ and $v$ in $H$ is at least $r+1$. Take the vertex set $P$ of a shortest path between $u$ and $v$ in $H$. Since $P$ is a shortest path, $G[P]$ is an induced path, that is, it is isomorphic to some $P_\ell$. Since $u$ and $v$ have distance at least $r+1$ in $G[P]$, we have $\ell\ge r+2$. Hence $G$ contains $P_{r+2}$ as an induced subgraph.


Span programs, witness size, and certificate complexity

The minimum witness size over all witnesses of a span program for a given function equals the generalized adversary bound, as shown e.g. in Theorem 1.7 here. Further, the generalized adversary bound is just a semi-definite relaxation of certificate complexity, see e.g. slide 40 in Reichardt's tutorial. The relation to deterministic and randomized query complexity is discussed in these tutorial slides as well.


Indeed, it can be solved in polynomial time.  This is a result by Frank (1985).


This should be a comment, as it is a mostly boring answer, but I don´t have enough reputation.

The sum of square roots problem is in $P^{PP^{PP^{PP}}}$ from [ABKM98], so any problem hard for this class has the required property. This is done by reducing the sum-of-square-roots problem to a problem called $PosSLP$, defined as deciding whether a straight-line problem represents a positive integer, so that problem is sum-of-square-roots hard.

[ABKM98]: On the Complexity of Numerical analysis, by Allender, Burgisser, Kjeldgaard-Pedersen and Miltersen.


Automatic theorem prover for first-order logic versus model checker

To add to the answer in the comments, it might help to first ask what the difference is between a model checker and an automated theorem prover for propositional logic.

Given the statement $$p \wedge q$$ we can ask whether it is true in the model $\{p=\top,q=\bot\}$ (model checking) or we can ask whether it is true in all models (theorem proving). We can also ask whether it is true in some models (satisfiability checking).

The same concepts follow over to first-order logic. For model checking we need a model; for theorem proving we don't.


Is bounded-error probabilistic computation sensitive to transition types?

If you have a coin which has an uncomputable probability of landing heads, then you can estimate with bounded error the first $k$ bits of this probability using $O(4^{k})$ coin flips.

This lets you construct a machine with bounded error that computes an uncomputable function. The uncomputable function is the $k$th bit of the probability. The computation is estimating the probability of landing heads by flipping the coin $4^k$ times. Considerations of running time don't matter when you're worrying about whether a function is computable or uncomputable, so it doesn't matter that it takes time exponential in $k$ to estimate the $k$th bit of the function; it's still an uncomputable function.


Hard-looking algorithmic problems made easy by theorems

If I understand your question correctly, a canonical example would be deciding if a graph $G$ has an Eulerian circuit: equivalent to checking that $G$ is connected and every vertex has even degree.


Complexity of finding the most likely edge

If you are happy with an approximation, then you can use approximate Laplacian solving, which takes time $\widetilde{O}(m)$. This is done explicitly in this paper by Spielman and Srivastava, Theorem 2.
My guess is that this is optimal, even if you just want to determine the edge with maximal effective resistance.


Fastest known deterministic algorithm for the undirected Graph Isomorphism problem

Babai invented the fastest known algorithm which runs in quasipolynomial time $2^{(\log n)^{O(1)}}$.


Petrank's proof for the APX-hardness of MAX k-VERTEX COVER on subcubic graphs

Here is the proof of Petrank's reduction. This was suggested to me by Édouard Bonnet. I still do not know whether this can be turned into an L-reduction.

  Suppose there is a PTAS algorithm $\mathscr{A}$ for MAX k VERTEX COVER, thus giving a $(1-\varepsilon)$-factor-approximate solution on a cubic graph $G=(V,E)$ with $|V|=n, |E|=m=3n/2$.
  We can use $\mathscr{A}$ to solve MIN VERTEX COVER on $G$ by invoking it for $k=1,2,\dots, n$, and keep the best of all the produced solutions. Assume that it is obtained for $k=k_0$.
  We claim that $\mathscr{A}$ for $k=k_0$ produces a solution where $k_0$ vertices cover at least $(1-\varepsilon)m$ edges. Indeed, when $k=opt_{VC}(G)$ (where $opt_{VC}(G)$ denotes the minimum solution size for MIN VERTEX COVER on $G$), at least $(1-\varepsilon)m$ edges must be covered by the result of $\mathscr{A}$. Since the result of $\mathscr{A}$ for $k=k_0$ is at least as good as this, the claim follows.

  Thus, at most $\varepsilon \cdot m$ edges are not covered. We construct a set $C$ with the $k_0$ vertices selected by $\mathscr{A}$, to which we add one arbitrary vertex of each of the remaining $\varepsilon \cdot m$ uncovered edges.
  This set $C$ is a vertex cover for $G$, and its size is $k_0 + \varepsilon \cdot m$.
  However, in a cubic graph, $m \leq 3k_0$ (in any optimal solution for MIN VERTEX COVER, each vertex can cover at most 3 edges).
  Therefore, $|C| \leq k_0 + \varepsilon \cdot 3k_0 = k_0(1+\varepsilon')$, by setting $\varepsilon' = 3\varepsilon$. This contradicts the APX-hardness of MIN VERTEX COVER on cubic graphs.


How to Create Mission Critical Software?

The question is rather broad.  To answer it in a reasonable space I will make many oversimplifications.

Let us agree on terminology.  A program is correct when it implies its specification.  This vague statement is made precise in many ways, by pinning down what exactly is a program and what exactly is a specification.  For example, in model checking the program is a Kripke structure and the specification is often an LTL formula.  Or, the program could be a list of PowerPC instructions and the specification could be a set of Hoare-Floyd assertions written in, say, first-order logic.  There are very many possible variations.  It is tempting to conclude that in one case (Kripke structure) we do not verify an actual program, while in the second case (list of PowerPC instructions) we do.  However, it is important to realize we really are looking at mathematical models in both cases, and this is perfectly fine.  (The situation is quite similar to physics where, for example, classical mechanics is a mathematical model of reality.)

Most formalizations distinguish between the syntax and the semantics of a program; that is, how it is represented and what does it mean.  The semantics of a program is what counts from the point of view of program verification.  But, it is of course important to have a clear way of assigning meanings to (syntactical representations of) programs.  Two popular ways are the following:

(small step) operational semantics: This is very much like defining a programming language by writing an interpreter for it. For this you need to say what is the state, and it is affected by each statement in the language.  (You may wonder in which language you write the interpreter, but I'll pretend you aren't.)
axiomatic semantics: Here each statement type comes with an axiom schema. So, roughly, whenever a particular statement of that type is used, it translates in being able to use certain axioms.  For example, the assignment ${\bf x}:={\bf e}$ comes with the schema $\{P[{\bf x}/{\bf e}]\}\,{\bf x}:={\bf e}\,\{P\}$; the particular assignment $x:=x+1$ comes with the axiom $\{x+1=1\}\,x:=x+1\,\{x=1\}$ if we instantiate the schema with $P=(x=1)$.

(There are others.  I feel particularly bad for omitting denotational semantics, but this answer is already long.)  Machine code plus operational semantics is pretty close to what most people would call a ‘real program’.  Here is a seminal paper, which happens to use operational semantics for a subset of the DEC Alpha machine code:

Necula, Lee, Proof-Carrying Code, 1996

Why would you ever use some higher-level semantics, like the axiomatic ones?  When you do not want your proof of correctness to depend on the hardware on which you run.  The approach then is to prove correctness of an algorithm with respect to some convenient high-level semantics, and then prove that semantics sound with respect to lower-level semantics that are closer to actual machines.

In summary, I could think of three reasons that led to your question:

You saw only high-level semantics that don't look like what you are used to call a program, and you wonder if there are low-level ones.  The answer is yes.
You wonder how you prove that a model corresponds to reality.  Like in physics, you don't.  You simply come up with better models and check them against reality.
You have not seen the distinction between syntax and semantics, and various ways to assign meanings to programs.  Two previous questions list some books.

This answer is merely trying to identify three different ways in which I understood the question.  Going deep in any of these points would require a lot of space.


Testing whether a Petri net $\mathcal{N} = (P, T, F)$ does not terminate from a marking $M_0$ can be decided by testing whether there exist a firing sequence $\sigma$ and markings $M, M'$ such that $M_0 \rightarrow^* M \rightarrow^\sigma M'$, $|\sigma| > 0$ and $M' \geq M$. By [Rac78], if such a firing sequence exists, then there is one of length doubly exponential. Thus, it can be guessed non deterministically, which shows that the problem is in EXPSPACE. By [Lip76], the problem is EXPSPACE-hard and hence EXPSPACE-complete. See, e.g., Section 3.2.4 of these lecture notes for a presentation of Lipton's reduction.

[Rac78] Charles Rackoff. The covering and boundedness problems for vector addition systems. Theoretical Computer Science, 6:223–231, 1978.

[Lip76] Richard J. Lipton. The reachability problem requires exponential space. Technical report 63, Department of Computer Science, Yale University, 1976.


Complexity classes not closed under intersection and union

The class $AWPP$ is not known to be closed under union, though it is easy to show it is closed under intersection
For the class $A_0PP$ it's the other way around: it is closed under intersection, but not known to be closed under union.

These classes have nice machine model definitions, namely they are something akin to an abstract version of the quantum complexity classes $BQP$ and $QMA$, respectively. These classes, in turn, are the quantum analogues of $P$ and $NP$, respectively. Let me give the definition (The Zoo) of $AWPP$:

Definition$^{(\ast)}$ (AWPP) A language $L\subseteq \{0,1\}^\ast$ is in $AWPP$ when there is a Gap function $g\colon \{0,1\}^\ast\to \mathbb{Z}$ satisfying the following Soundness and Completeness properties for a polynomial $p(x)$ and a polynomial-time computable function $f(x)$:

Soundness If $x\not\in L$ then $0\leq g(x)\leq 2^{-p(x)}f(x)$
Completeness If $x\in L$ then $(1-2^{-p(x)})f(x)\leq g(x)\leq f(x)$

These soundness and completeness conditions are precisely what you get if you were to (1) trace through the definition of $BQP$ using only the Hadamard gate and classical gates and then (2) interpret the acceptance probabilities as "paths", and then (3) impose that there is a large gap in acceptance probabilities depending on whether $x\in L$ or not.

It is interesting that this is not known, because both $BQP$ and $QMA$ are known to be closed under intersection and union. As far as I know, there have been no publications exploring the closure properties of these classes; perhaps they are a bit niche, or perhaps I am simply ignorant.

Of course it is also unknown whether $AWPP$ and $A_0PP$ are closed under complement, because this would imply the other closures as well; the converse does not hold; they may be closed under union and intersection but not complement, like $NP$ probably is.

$^{(\ast)}$In this definition, the polynomial $p(x)$ can be replaced by a polynomial $p^\prime(n)$ which depends only on $n=|x|$ the length of the string; similarly the function $f(x)$ can also be replaced by such a polynomial $f^\prime(n)$. This may make certain things easier to prove.


Elementary bounds on parameter in fixed-parameter tractability?

In his dissertation thesis "Modiﬁzierte parametrische Komplexitatstheorie", Mark Weyer considered, among other things, hierarchies within FPT w.r.t. the function f and reductions between them.   He also did indeed relate these sub-hierarchies to fragments of FO and MSO: Chapter 6 is essentially about the relation between FO/MSO (the number of quantifier alternations of the formulas) and the function f(w) in Courcelle's theorem (w being the treewidth).  He considered both upper and lower bounds and, using the aforementioned reduction framework between certain hierarchies within FPT, he was able to give quite tight bounds.  The examiners of the thesis were Flum and Grohe.

Unfortunately the thesis is in German, and I'm not aware whether material of his thesis has been published in an English journal.  I'm therefore aware that they might be of limited use for you, but nevertheless the references therein might be a good starting point.


Calculating a fast matrix vector product between vector of reals and a 0-1 matrix

Well, if you dont mind some approximation than regular dimension reduction techniques would give you some speedup as they preserve (approximately) dot product.

Otherwise, you can think about each vector as being a CNF clause. If you just have to decide if the dot product is not zero for all vectors, then what you are asking for is the shortest equivalent DNF to the given CNF (or to be more precise some kind of minimal computation that compute the given CNF). This however is easier than the problem of deciding if the given CNF is never satisfiable, which is co-NP complete. In short, this problem should be computationally hard.

I think there was quite a bit of work on stuff like that in the learning community, especially in the dinosaurs age ;) (80s and earlier?).


How not to compute the smallest circle enclosing a finite set of circles

This step of removing $X$ from $L$ before continuing recursion actually improves the algorithm, because it removes the already-added $X$ from the pool of basis candidates. It will always, provably work, because it's equivalent to the existing algorithm, and it will also work for higher dimensions.

Trace through the algorithm. When you use $MSW(L,B^{\prime\prime})$, there is $X \in L$ and $X \in B^{\prime\prime}$. Suppose we chose it again in step 2. Regardless of the result of step 3, $B^\prime$ will always have $X$, because the recursive function has the invariant $B \subseteq MSW(L,B)$.

In other words, your improvement to the algorithm shortcuts to step 3 in the part where $X$ is chosen.


Placing color boxes on a colored image such that color consistency is maximized

Just an extended note to show that the decision version of your problem ("Is there a placement of the bounding boxes such that $n_{good} - n_{bad} \geq k$?" ) is NP-complete even for two colors $C = \{c_1, c_2\}$ and two bounding boxes $B_1 \equiv \langle col=c_1, w=3, h=1 \rangle$, $B_2 \equiv \langle col=c_2, w=1, h=1 \rangle$.

The reduction is straightforward from: Danièle Beauquier, Maurice Nivat, Eric Rémila, Mike Robson: Tiling Figures of the Plane with Two Bars. Comput. Geom. 5: 1-25 (1995)

They prove that tiling a figure on the plane grid with two horizontal/vertical bars with length at least 3 is NP-complete.

The reduction to your problem is simple: just color the "pixels" of the figure with color $c_1$ and fill the remaining background pixels of the $N+1\times N+1$ square region around it with color $c_2$. You can place the bounding boxes $B_1, B_2$ with $n_{good} - n_{bad} = (N+1)^2$ if and only if the original figure is tileable with $3 \times 1$ horizontal/vertical bars.


How to auto-derivate sequential iterative programs from a mathematical specification?

Short answer: no.

Long answer: No, because the synthesis problem is in general undecidable once you allow for a modest amount of expressive power in the assertions (pre- and post-conditions).

The specification for your synthesizer $S$ would look something like this. Its type would be $S:\mathit{Assn}^2\rightarrow\mathit{Prog}$, that is, given two assertions (a pre- and a post condition) it would return a program. Its functionality would be given by $\{\phi\}S(\phi,\psi)\{\psi\}$, for all $\phi,\psi\in\mathit{Assn}$. I understand your question as "is $S$ computable?"

Before we need to get technical, note that we've been a bit sloppy. $S$ can hardly be a total function for we could feed it an infeasible spec such at $[\mathit{true},\mathit{false}]$. Consequently, the best we could hope for is a partial function that works for all implementable specifications.

To answer the refined question we need to answer another first.

What expressive power would we need in the assertion language?

Firstly, assuming that we're living in a simple world where we only deal with integers, we require the usual operations from integer arithmetic.

Secondly, we need a mechanism to refer in the post-condition to the value of a program variable in the pre-condition. Without such a mechanism, we cannot even specify an increment-by-one function. Various such mechanisms exist. Let us here use one borrowed from the Z specification language: in the post-condition primed occurrences $x'$ of a variable $x$ refer to its value after the program has terminated whereas unprimed occurrences denote its value in the pre-condition. With this convention the increment-$x$-by-one function is specified by $[true,x'=x+1]$.

Thirdly, we'd also want quantifiers so we can at least specify simple examples such as

a primality checker

$[x > 0, x=x'\land(p\Leftrightarrow x>1\land\forall k(k>1\land \exists j(kj=x)\Rightarrow k=x))]$, and

a sorter that takes arrays of arbitrary size as inputs

$[\mathit{true},\mathit{length}(a)=\mathit{length}(a')\land\mathit{elements}(a)=\mathit{elements}(a')\land\forall i(1\leq i <\mathit{length}(a')\Rightarrow a'[i]\leq a'[i+1])]$.

With those ingredients, we have quite some power at our disposal, too much as it turns out. Even the domain of $S$ is undecidable because we would need to say whether a spec $[\mathit{true},\phi]$ is implementable or not, for arbitrary formulas $\phi$ of Peano arithmetic, before worrying about how to synthesize implementations. But that is already undecidable.


Temporal Logic and Access Control Models

There were a lot of publication on extending and or formalizing RBAC/SOD with LTL or other flavors of temporal logics, not sure of other AC models. Google Scholar (or simple google) search with yield a bunch of articles. Most of them might be not sufficiently formal for somebody like yourself, yet might be of some interest. Not sure is LTL the best way. Yet for a hammers everything is a nail, so if temporal logic is your specialty you might be more successful with it than without.. Consider also traditional programming language semantics approaches such as Z and alike, Game Theoretical/Modular/HyperProperties, dedicated logics. Totally depends on your AC.

Check example articles and see what you feel is the way
https://www.sciencedirect.com/science/article/pii/S1571066109003107


Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?

It depends on the precise definition of RAM being used, but (for most reasonable definitions of RAMs) this would also imply that SAT is not solvable in $O(n^{2-e})$ time by multitape TMs, a longstanding open problem.
The reason is that there is a very efficient reduction from linear time on RAMs to SAT (in general, nondeterministic quasi linear time on RAMs is the same as nondeterministic quasi linear time on multitape TMs.)
I have never seen the above reference before, and I would be skeptical if it never appeared in a journal or conference, but it could be worth checking to see if it implies a SAT lower bound as well. Interesting find!

UPDATE: I looked at the paper at your link above briefly this morning. The claimed hard function is a complicated partial match query problem. Essentially there is a notion of a "string pattern" and one is given a bunch of binary strings and asked to determine which strings fit the pattern (and which don't). Let me write out the definition of the function, as I understand it. I will use different symbols and terminology to try to make the definition easier to understand.
The set of "string templates" (the author's $U$, Definition 5.1) is a set of strings over $\{0,1,end,branch\}$, defined recursively:

$end \in U$
$\alpha \in U$ implies $0\alpha, 1\alpha \in U$
$\alpha, \beta \in U$ implies $branch~ \alpha \beta \in U$.
Note that every string ends in an $end$ symbol. The $branch$ is used to denote a possible choice in the match: either $\alpha$ can be matched as a partial string, or $\beta$, and $end$ is used at the end of $\alpha$ to signal where $\alpha$ ends and $\beta$ begins.

We say that a binary string $x$ "matches" a string template $\alpha \in U$ (the author's Definition 5.2) if $x$ is in the set $\phi(\alpha)$, recursively defined as:

$\phi(end) = \epsilon$ ($end$ symbols are removed)
$\phi(b\alpha) = b \phi(\alpha)$ for $b \in \{0,1\}$ (normal string matching)
$\phi(branch~ \alpha \beta) = 0\phi(\alpha) \cup 1 \phi(\beta)$, for $\alpha,\beta \in U$.
The third condition is the main one here: the author intends for us to find the $end$ symbol that "matches up" with the first $branch$ symbol, and partition $\alpha$ and $\beta$ according to that. Then, depending on whether the next symbol of $x$ is $0$ or $1$, the next piece of $x$ should either partial-match to $\alpha$ or partial-match to $\beta$.

It should be analogous to think of an $\alpha$ as an encoding of a (rooted) binary tree (each node has at most two children), where we label each edge of the tree by $0$ or $1$, and we say that a string $x$ matches the tree if there's some root-to-leaf path whose concatenated symbols are exactly $x$.
Anyway, the final presumed hard function $g$ (Definition 5.2) is:
Given a string template $\alpha \in U$ and given binary strings $x_1,\ldots,x_k$ (where each string is separated by a new symbol) output $k$ bits indicating which $x_i$'s match the template $\alpha$.
If this was a "normal" partial match query problem (e.g. with strings over $\{0,1,\star\}$, then it would be easily computed in $O(n)$ time on a multitape Turing machine, even one that just reads its input in one direction. I don't see  why computing multiple queries on a binary search tree should take super-linear time for a multitape Turing machine. (I don't see why following $K$ paths down a binary tree of description size $N$ should take more than $(N+K) \cdot poly(\log(KN))$ time.) And the fact that it didn't appear in a major conference or a major journal makes me very suspicious. (It does appear in a journal: https://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&vol=13&iss=2&rank=5) But I didn't spend more than an hour looking at this!

FINAL UPDATE: Brynmor Chapman looked at this paper more closely, and observed the proof only gives a lower bound for the "on line" version of the function, where the query for each binary string $x_i$ (as described above) must be answered (the TM must output a bit) before the TM is allowed to read the next binary string $x_{i+1}$. This a data structure lower bound for TMs, which is much easier to prove given the 1-dimensional nature of TM tapes. That is, the lower bound proved is much weaker than what is claimed: that there is a function $g$ computable in linear time on RAMs which requires nearly quadratic time on a multi-tape Turing machine. As far as I know, that claim remains open.


Collatz Conjecture & Grammars / Automata

I guess these papers by Jeffrey C. Lagarias could help:

The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author).
The 3x+1 Problem: An Annotated Bibliography, II (2000-2009).

Another good source is the recent book "The Ultimate Challenge". In it  chapter "Generalized $3x+1$ functions and the theory of computation",section $\#$ 8, can also be of interest.


Some heuristic evidence: to the best of our knowledge  $\pi(n)$ looks like a simple function corrected by random fluctuations.  Thus I’d expect a poly-time machine with a $\pi(n)$ oracle to be no stronger than such a machine with a random oracle, and w.r.t. a random oracle $X$ adding a separate random oracle $Y$ to $\mathsf{P}$ gives $\#\mathsf{P}^X \not\subset \mathsf{P}^{XY}$ with probability 1 (here $Y$ corresponds to $\pi(n)$ and $X$ is an independent random oracle).


What is known about multi-prover interactive proofs with short messages?

Completely classical case (MIP)

If the verifier is classical and there is no prior entanglement among provers, your class contains BPP∪NP and is contained in MA.

It is trivial that BPP is a lower bound.  To show that the class contains NP, consider the standard two-prover one-round interactive proof system for 3-colorability with perfect completeness and soundness error 1−1/poly.  If you want to reduce the soundness error to a constant, combine this with the PCP theorem.

As for the upper bound, the following stronger statement holds: MIP with the restriction that the total message length from the verifier to each prover is O(log n) is equal to MA.  This is because a strategy of each prover can be described by a string of polynomial length.

Interestingly, another upper bound exists when the system has perfect completeness.  Namely, multi-prover interactive proof systems with perfect completeness with O(log n)-bit total communication recognize at most PNP[log], and this holds even if we allow unbounded soundness error.  To prove this in the case of two provers, let xs be the concatenation of all answers given by the first prover when the concatenation of all questions to the first prover is s, and define yt analogously for the second prover.  To be accepted by the verifier with certainty, these variables xs and yt must satisfy certain constraints, and note that this is a 2CSP.  There are at most poly(n) choices for tuples (s, t, xs, yt), and for each choice, we can use the NP oracle to test whether the verifier rejects that tuple.  Therefore, with the NP oracle, we can list up all the constraints on the variables xs and yt in polynomial time.  Finally, we use the NP oracle once more to test whether there is an assignment to these variables which satisfies all the constraints.  Although this algorithm uses the NP oracle polynomially many times, all the queries except for the last one can be made in parallel, and therefore this can be converted to a PNP[log] algorithm.  The case of more than two provers is analogous.

This upper bound implies that although every MA system can be turned to one with perfect completeness, we cannot hope for a multi-prover interactive proof system with perfect completeness with O(log n)-bit communication unless MA⊆PNP[log].  I do not know how unlikely the inclusion MA⊆PNP[log] is, but I just note that Complexity Zoology states that there is an oracle relative to which BPP⊈PNP (and therefore clearly MA⊈PNP[log]).

(In the case of single prover, Theorem 2 of Goldreich and Håstad [GH98] implies that IP with the total message length O(log n) bits is equal to BPP.)

Added.  A necessary and sufficient characterization is as follows.

To explain this characterization, we need a variant of the notion of Karp reducibility (polynomial-time many-one reducibility).  For two decision problems A and B, let’s say that A is FPBPP-reducible to B (I know, this is an awful name) when there is a deterministic polynomial-time Turing machine M with access to the BPP oracle which maps yes-instances to yes-instances and no-instances to no-instances, where we allow “non-smart” oracle access (meaning that M can make a query to the BPP oracle about an instance which does not satisfy the promise of the BPP problem, in which case then oracle returns yes or no arbitrarily).  Then it can be proved that the following conditions on a problem A are equivalent.

(i) A has a multi-prover interactive proof system with O(log n)-bit communication and two-sided bounded error.
(ii) A has a two-prover one-round interactive proof system with O(log n)-bit communication, exponentially small completeness error, and constant soundness error.
(iii) A is FPBPP-reducible to a problem in NP.

(Proof idea: Implication (ii)⇒(i) is trivial.  Implication (i)⇒(iii) can be obtained in a similar way to the above proof in the case of one-sided error.  Implication (iii)⇒(ii) follows from the PCP theorem because the class of problems satisfying condition (ii) is closed under FPBPP-reducibility.)

Classical verifier with entangled provers (MIP*)

Next consider the case with a classical verifier and entangled provers.  In this case, the class with bounded error again contains BPP∪NP.

Kempe, Kobayashi, Matsumoto, Toner, and Vidick [KKMTV11] shows that every problem in NP has a three-prover one-round interactive proof system with perfect completeness and soundness error 1−1/poly where the total length of messages is O(log n) bits, and the soundness holds against entangled provers.  Therefore, MIP* with total message length O(log n) bits and bounded error contains NP.  A later result by Ito, Kobayashi, and Matsumoto [IKM09] (shameless plug) reduces the number of provers from three to two.  The case of constant soundness is open at the top of my knowledge.

It is not known whether MIP* with total message length O(log n) bits is contained in the class R of decidable problems or not, and this question is equivalent to whether MIP*⊆R (another open problem) by the padding argument.

References

[GH98] Oded Goldreich and Johan Håstad.  On the complexity of interactive proofs with bounded communication.  Information Processing Letters, 67(4):205–214, Aug. 1998.  http://dx.doi.org/10.1016/S0020-0190%2898%2900116-1

[IKM09] Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto.  Oracularization and two-prover one-round interactive proofs against nonlocal strategies.  Proceedings: Twenty-Fourth Annual IEEE Conference on Computational Complexity (CCC 2009), 217–228, July 2009.  http://dx.doi.org/10.1109/CCC.2009.22

[KKMTV11] Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, and Thomas Vidick.  Entangled games are hard to approximate.  SIAM Journal on Computing, 40(3):848–877, 2011.  http://dx.doi.org/10.1137/090751293


Having discussed with other users, I believe the following answers the question.

To begin with let us recap the greedy algorithm for the set cover problem, in which we wish to cover all of $E$ as cheaply as possible. At each step, the algorithm adds the set $S_i$ for which $\frac{w_i}{|\hat{S}_i|}$ is lowest, where $\hat{S}_i$ is the subset of $S_i$ which has yet to be covered. It can be shown that this minimum is upper bounded by $\frac{OPT}{Z}$ where $OPT$ is the optimal weight for the (full) set cover problem and $Z$ is the number of elements not yet covered. From this, one can show a a total weight bounded by $H_{|E|} \approx \log |E|$.

However, if one were to stop the algorithm as soon as $p|E|$ elements were covered, then we would get the bound  $\approx \log \frac{1}{1-p}$, as per @SashoNikolov's comment.

We can get a $H_{p|E|}$ approximation for the partial set problem by modifying the greedy algorithm as follows: At each iteration, choose the $S_i$ which minimizes $\frac{w_i}{\min(|\hat{S}_i|, Z)}$ where $Z$ is the number of elements we still need to get to complete $p|E|$ elements. Now we can guaranteed that there is an $S_i$ for which the above is bounded by $OPT/Z$ (where now $OPT$ is the optimal for the partial set cover). To see this, suppose an optimal solution is the collection of sets $S_1=\{xx|...\}$ $S_2=\{xxx|...\}$, $S_3=\{xxx|......\}$. In this notation, the $x$ represents an already covered element, and after the $|$ are elements which are not covered. Let $a_1, a_2, a_3$ denote the number of such uncovered elements and suppose $a_1, a_2, a_3\leq Z$. Then
$$min \{\frac{w_1}{a_1}, \frac{w_2}{a_2}, \frac{w_3}{a_3}\}\leq \frac{w_1+w_2+w_3}{a_1+a_2+a_3}  = \frac{OPT}{a_1+a_2+a_3} \leq \frac{OPT}{Z}.$$

Of course, if any of the $a_i$'s is larger than $Z$ then it is replaced by $Z$ in the above inequalities and they hold.

The starting $Z$ is $Z_0=p|E|$, and a similar analysis as for the full set cover leads to a total weight bounded by $OPT \cdot H_{Z_0}$.


Continuity vs Uniformity when designing Hash functions

While continuity in a strong sense is probably too much to ask for, locality sensitive hashing (LSH) achieves a very similar goal: given a set of items $x_1, \ldots, x_n$ which belong to some metric space with metric $d$, an LSH family of hash functions (parametrized by $D, c, p, q$) maps $x_i$ and $x_j$ into the same bucket with probability $\geq p$ if $d(x_i, x_j) \leq D$ and maps $x_i$ and $x_j$ into different buckets with probablity $\geq q$ if $d(x_i, x_j) > cD$. Of course there is tension in the requirements, so one looks for tradeoffs. Look at the wiki page and Alex Andoni's webpage, especially the CACM survey.

For context, LSH is a tool to solve the approximate nearest neighbor problem in high dimensional metric spaces. There exist solutions for various metrics, like hamming distance and $\ell_p$ norms, see the CACM survey. The approximate nearest neighbor problem is an important problem in computational geometry, and the high-dimensional version comes up in a variety of applications, for example in computer vision and information retrieval.

The way LSH is used to solve approximate near neighbor search is a fairly natural two-level hashing scheme. As you note, there is tension between the "continuity" property and bounding the number of collisions. For that reason, usually the gap between $p$ and $q$ (as I defined them above) is pretty small. To overcome this we construct a new hash function by choosing several functions from an LSH family and taking their concatenation. The resulting universe is too big, so it is reduced using traditional hashing. Then we build several hash tables using these hash functions. A query is answered by hashing the query point and inspecting the other points in the same bucket(s) to determine if they are close enough (this is the linear search part). Parameters can be chosen so that a query is answered in sublinear time.


My answer addresses the general theory of disease (and similar) modelling and only briefly touches on the implementations. For simulations (as opposed to analytic work, which usually uses evolutionary game theory or SIR models) the popular paradigm is agent-based modeling (ABM). A good recent book on agent-based modelling from a CS perspective is:

  Yoav Shoham and Kevin Leyton-Brown
  [2009], "Multiagent systems:
  algorithmic, game-theoretic, and
  logical foundations", Cambridge
  University press.

A big general conference of agent-based modeling is AAMAS (links to 2011 and 2012). They don't specialize in disease modeling in particular, but a lot of the techniques they use can be applied there.

In terms of software for doing rapid prototyping of ABMs, a popular one is NetLogo. This seems to be particularly popular in the social sciences, where they do slight variations of standard epidemic models to describe certain social processes.

Currently, it seems like the focus of theoretical work in this field (and this is obviously biased by my own interests) is to consider environments where agents are limited in their interactions. If you just have agents meet randomly, then ABMs are usually overkill and things can be done analytically. However, if there is some interesting network structure (fixed or dynamic) to the interactions (as there often is in real life) then ABMs become an essential tool. A fun recent book that discusses some of these ideas (once again from a CS perspective) is:

  David Easley and Jon Kleinberg [2010],
  "Networks, crowds, and markets:
  Reasoning about a highly connected
  world," Cambridge University press. (a
  draft is available
  online)


Is combinatory strong reduction equivalent to lambda beta-eta reduction?

The answer to the second question is yes, beta-reduction is harder to imitate than beta-eta-reduction.  There is an article by J P Seldin in "Theoretical Computer Science" (2011) I think that discusses the problems to which beta-reduction gives rise.

As to the question, "could we use strong reduction to evaluation lambda terms?", the correspondence is not as neat as you might wish.  There is a mapping called the H-transformation that takes lambda terms to combinatory terms and which preserves the relation "reduces to", but it is not one-to-one and therefore not invertible.  So if you start with a lambda term M and find its image H(M) under the H-transformation and you can reduce H(M) to a normal form, you will know that M also has a normal form, but it may not be entirely easy to find it.  In the other direction, there is a mapping called the lambda-transformation that takes combinatory terms to lambda terms but it is not onto and is not the inverse of the H-transformation.  It also does not preserve the reduction relation, unlike the H-transformation.

All the above information is found in sections 6E and 6F of "Combinatory Logic Volume I" by Curry and Feys and in chapter 9 of "Lambda Calculus and Combinators" by Hindley and Seldin.  Hindley also wrote an article published in MLQ in 1977 that discusses these things in more detail.


Undecidable problems not Turing-complete?

Yes, there are intermediate degrees.  One way to see this is that there are computably enumerable sets that are Turing incomparable.  See https://secure.wikimedia.org/wikipedia/en/wiki/Turing_degree for some basic information.


Algorithms Design and Complexity - How to think in that 'way'?

I think courses on algorithm design and computational complexity are always challenging for students who not familiar with these subjects because they do require some degree of mathematical maturity and problem solving skill. In my first graduate course on "computational complexity", a friend of mine who had his degree in pure mathematics told me how surprised he was by the fact that although that course didn't require much maths background (at least that's what was told in the course outline), it actually required nearly all the skills he got through all of his pure maths undergrad degree!

I found that I got to know about "the way" most (when I first start my graduate study) by reading and doing exercises from Sipser's book. Be sure that you do the exercises because problem solving skill and mathematical maturity is what you want to learn and not just a bunch of facts or definitions.

However, Sipser's book is only good for complexity and NP-completeness stuffs, it won't suffice to substitute the CLRS book. The only problem with CLRS book is that its advantage of comprehensive coverage might become its weakness since the book might look quite scary or overwhelming for students. So my advice is that you should really go to the library and search for books on algorithms, scan through one by one and choose the ones that fit your thinking pattern most. And again don't forget to do exercises!

For algorithms, I personally suggest the following books (besides the ones suggested by Sadeq and JeffE):

The very readable and beautiful book Algorithms by by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.
The killer notes (or book draft) by Jeff Erickson. (Since JeffE is too modest to suggest his own notes, I have to do it myself.)

In general, whenever you study a certain algorithm or data structure, if somehow the exposition in your textbook is not clear enough for you, then the best way is to search on google for lecture notes of that particular topic. In may cases, different explanations of the same thing eventually give you the complete picture. At least, that's how it works for me.


Are the $\lambda_I$-Calculus and the $\lambda_K$-Calculus equivalent?

You've basically answered the question yourself.
$\lambda K$ is just another name for the standard, untyped lambda calculus.
$\lambda I$ is a strict subset of $\lambda K$.
$\lambda I$ doesn't allow terms where one abstracts over a variable but doesn't use it. So
$$K = \lambda xy.x \in \lambda K$$
but
$$ K \not\in \lambda I$$
Thanks to this restriction, $\lambda I$ has some interesting properties, in particular if $M$ has a normal form then so do all its sub-terms.
Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics contains some notes about $\lambda I$, namely:

... the $\lambda I$ calculus is sufficient to define all recursive functions  (since $K_1 := \lambda xy . yIIx$ satisfies $K_1xc_n = x$ for each of Church's numerals $c_n := \lambda fz . f^n z$ - it is also the case that for each finite set $n$ of nf's, we can find a "local $K$ for $n$" $K_n$ such that $K_nMN = M$ for each $N$ in $n$).
... The $\lambda I$ calculus corresponds to the combinatory logic with primitive combinators $I$, $B$, $C$, and $S$. ...


The definition of an object $X$ is impredicative, if the definition uses a collection $C$ in the construction of $X$, such that $X$ is a member of $C$.  So impredicativity is a form of circularity.

We are wary of circular definitions because they are often paradoxical. Fortunately it turns out that not all forms of
circularity are (or appear to be) problematic.  The most famous example of an impredicative definition that is circular, but (as far as we know) not contradictory is the definition of natural numbers in set theory:

$$
\mathbb{N}\ \stackrel{\text{def}}{=}\ \bigcap \{X\ |\ X\ \text{is an inductive set}\}
$$

where a set is inductive if it contains $\emptyset$ and
  is closed under the set-theoretic successor operation.  Clearly, $\mathbb{N}$ is itself inductive, hence what you define on the left already occurs in some sense on the right.

By the "impredicative version of Martin-Löf's type theory" I guess you mean the type theory in his 1971 manuscript "An intuitionistic theory of types". This system has an  impredicative axiom  that stipulates a type of all types.  For this reason the system is often simply called "type:type". This axiom is too strong as J.-Y. Girard showed, as it makes the type-theory inconsistent.

In contrast, the impredicativity in the CoC is not (known to be) inconsistent.

In some sense there are two forms of impredicativity: those that are known to be paradoxical, and those that are not.


I think you can build $G$ in iterations:

$M$ contains all $(v, \{e\})$ where $v \in \Gamma(v_0)$ ($\Gamma$ being neighborhood); so you can identify all edges to nodes that are distance 1 from $v_0$, as well as the nodes themselves; you can also identify the edges between nodes in $\Gamma(v_0)$ by looking for pairs $(v, \{e_1, e_2\})$, where $v \in \Gamma(v_0)$ and $e_1$ is an edge between $v_0$ and some $u \in \Gamma(v_0)$.
then, iteratively, you can identify all edges and nodes in the subgraph of $G$ induced on the vertices which are distance at most $i$ to $v_0$ (call it $G_{i}$), using $G_{i-1}$. The idea is the same as above: you look for pairs $(v, S)$, where all but one edges in $S$ are in $G_{i-1}$; this gives $V(G_i \setminus G_{i-1})$. Then you can identify edges between vertices $u, v \in V(G_i \setminus G_{i-1})$ by looking for pairs $(v, S)$, where $S = S' \cup \{e_1\} \cup \{e_2\}$, such that $S' \subseteq E(G_{i-1})$, and $e_1$ has one point in $G_{i-1}$ and the other point is $u$; $e_2$ is the edge $(u, v)$.

Are you aware of the reconstruction and edge reconstruction conjectures? They have the same spirit as your probelm and, as far as I know, are open. Check out this beautiful half page proof by Lovasz that the edge reconstruction conjecture is true for any graph that has more edges than its compliment.


Is there any relation between $\mathsf{PPP}\subseteq\mathsf{TFNP}$ and $\mathsf{UP}$?

I doubt any of these inclusions hold, though probably proving that is hard.

$\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{PPP}}$: this seems unlikely because PPP only captures one style of reasoning, whereas problems in UP can have unique witnesses for many different kinds of reasons. (It would be interesting to know if there are natural candidates witnessing this separation, even if the absence of natural candidates doesn't prove the containment.)

$\mathsf{PPP} \subseteq \mathsf{FP}^{\mathsf{UP}}$: This seems unlikely because there is no reason that either kind of output (a preimage of $0^n$ nor a collision) should be unique. Even though the proof that one of these two things must occur has one branch of the conditional being that $C$ is a bijection, that is not the only way for $0^n$ to be in the image.

For the other two, note that $\mathsf{TFNP}$ is sometimes said to correspond to $\mathsf{NP} \cap \mathsf{coNP}$, though I think more accurately it is like $\mathsf{NPMV}_t$. So it's sort of somewhere between $\mathsf{NP} \cap \mathsf{coNP}$ and $\mathsf{NP}$, but either way, it being contained in $\mathsf{FP}^{\mathsf{UP}}$ would be surprising. (Though with randomized reductions it might be interesting to think about Valiant-Vazirani in this context.)

If you think of $\mathsf{TFNP}$ as like $\mathsf{NP} \cap \mathsf{coNP}$, then $\mathsf{UP} \subseteq \mathsf{P}^{\mathsf{TFNP}}$ would be morally like $\mathsf{UP} \subseteq \mathsf{coNP}$.


Concurrent transactions satisfying "serializability" but not "snapshot isolation"

Answer my own question:

I am not sure with the ideas below. Both comments and answers from experts are highly appreciated. Any references are also welcome.

I think the confusion arises from the fact that the two definitions of serializability ($\textrm{SR}$, for short) adopted in [Lin et al@TODS'2009] and [Berenson et al@MSR-TR'1995] are different.

The SR in [Lin et al@TODS'2009]:

In [Lin et al@TODS'2009] (at least in the test of $H_{example}$), the serializability is the classic One-Copy Serializability (or, $\textrm{1-SR}$) introduced in [Bernstein et al@TODS'1983].

To tell if an multiversion (or MV) history is $\textrm{1-SR}$, we should first decide on a version order $\ll$ (which is a total order) for each data item. Given a history $H$ and a version order $\ll$, an multiversion serialization graph $MVSR(H, \ll)$ can be constructed. As a consequence, we have

  1-SR Theorem: An MV history $H$ is $\textrm{1-SR}$ iff there exists a version order $\ll$ such that $MVSG(H, \ll)$ is acyclic.

Back to the history $H_{example}$, the version order for $x$ can be chosen as $x_1 \ll x_2$. It is easy to show, according to the above theorem, that $H_{example}$ is $\textrm{1-SR}$ because it is equivalent to the serial history of $T_1 \; T_3 \; T_2$.

The SR in [Berenson et al@MSR-TR'1995]:

The $\textrm{SR}$ adopted in [Berenson et al@MSR-TR'1995] is defined by avoiding phenomena ($P$) and anomalies ($A$). In this sense, Snapshot Isolation (or $\textrm{SI}$) avoids $P_0, P_1, A_3, A5A, P4$. The $\textrm{SR}$ here is thus strictly stronger than $\textrm{SI}$ because it further avoids $A5B$.

Back to the history $H_{example}$, it even does not avoid $P_1$ which indicates a "dirty read". Notice that $P_1$ (instead of $A_1$) prohibits an execution sequence if something anomalous might in the future. Although $r_2(x_1)$ reads-x-from $w_1(x_1)$ that is committed later on, it is still a "dirty read". In this way, it does not satisfy $\textrm{SR}$.

The perspective of computational complexity:

[Bernstein et al@TODS'1983] also shows that

  It is $\textrm{NP}$-complete to decide whether an MV history is 1-$\textrm{SR}$.

However, if we know that $H$ is $\textrm{SI}$ in advance, we can decide efficiently whether it is 1-$\textrm{SR}$. The key here is that the version order $\ll$ has been determined by $\textrm{SI}$. See [Cahill et al@SIGMOD'2008].

Furthermore, I guess that, for an $\textrm{SI}$ history, the above two different definitions of serializability coincide. More precisely,

  A guess: With $\textrm{SI}$, a history $H$ is 1-$\textrm{SR}$ in [Bernstein et al@TODS'1983] iff it is $\textrm{SR}$ in [Berenson et al@MSR-TR'1995].

References:

([Bernstein et al@TODS'1983]) Multiversion Concurrency Control — Theory and Algorithms

([Cahill et al@SIGMOD'08]) Serializable Isolation for Snapshot Databases


Relationship between two graph optimization problems

One example: choosing the property "G contains a node that has an edge to all nodes in G" makes P1 trivial in $O(n + m)$ (pick node with largest degree), but makes P2 the problem of finding the minimum size dominating set, which is NP-hard.


Merging Graph Edges to form a 2 color-able Graph (with weight constraints)?

Your problem is exactly equivalent to the 2-colorable perfect matching problem:
On input a graph, color the vertices of the graph with two colors such that each vertex has exactly one neighbor of the same color.

The 2-colorable perfect matching problem was introduced in "The complexity of satisfiability problems" by T. J. Schaefer and is NP-complete.


How hard is recognizing a permutation that is a square for the shift product?

It's really quite easy. Let $$\rho_k = \left( \begin{matrix}1&2&\ldots&n\\ (k+1)\bmod n&(k+2)\bmod n&\ldots&(k+n)\bmod n\end{matrix}  \right)$$ be the shift permutation. Then the shift of $\tau$ is just $\sigma = \tau \circ \rho_k$, and the shift product of $\tau$ is $\tau \circ \rho_k \circ \tau$. But $$\pi = \tau \circ \rho_k \circ \tau \iff \rho_k \circ \pi = (\rho_k \circ \tau)^2$$

Given $\pi$ you can find $\rho_k \circ \pi$ in linear time, and then you just need to see whether it has a square root, which can also be done in linear time.


D. Knuth definition of a computational method

1/ Then he goes on defining Q as being states of the computation. What exactly are states of computations?

Q consists of the input $I$, output $\Omega$, and all the intermediate "states" or values during the computation. (it will be clear in the Euclid example.)

  2/ The Euclid algorithm on page 22 is formalized in the defined computational method, but if Q is made up of (m,n), (n), (m,n,r,1), (m,n,r,2) and (m,n,p,3) are those the states of computation and how do you come up with them? and how does one recognize them from an algorithm. more precisely, how do you translate a given algorithm into the given computational method?

Yes, those are the states of computation. Note that the input $I$ consists of all pairs of $(m,n)$, which can be seen as the initial state, and $\Omega$ consists of all singleton $(n)$, which is the output and final computation state. The quadruples ends with 1,2,3 define various states of the computation and how $f$ maps each of those states corresponds to the various steps of the Euclid's algorithm as he described earlier in the book.

Now let's run through the steps.

  $f((m,n)) = (m,n,0,1);$

this just says that given an initial input of (m,n), the algorithm will transform into "state #1" of the computation. How $f$ handles state #1 is defined below. Note that the value 0 here is simply a placeholder, because the 3rd value in the quadruple is ignored in "state #1".

  $f((n)) = (n);$

given a singleton (only obtained as the final result), it is mapped to itself, which indicates the termination of the computation.

  $f((m,n,r,1)) = (m, n, m\bmod n, 2);$

this is the first step of the Euclid's algorithm. Given $(m, n)$ (note, value $r$ is ignored here.), compute the remainder of $m$ divided by $n$ and this new state will be mapped as follows:

  $f((m,n,r,2)) = (n)$ if $r = 0$, $(m,n,r,3)$ otherwise;

note the $r$ is the remainder computed in the 1st step. If $r=0$, then this state is mapped to the singleton $(n)$, which indicates the termination of the algorithm because $(n) \in \Omega$, which means $f((n)) = (n)$. Else, it's mapped to another state and how $f$ handles this state is defined below:

  $f((m,n,p,3)) = (n,p,p,1)$

Here $p$ gets the value of $r$ from the previous step. $p$ is introduced because $p >0$ as opposed to $r>=0$. This is the final step in Euclid where $m\gets n, n\gets r$, and a new state is produced with those values and f will handle this state according to "state rule #1" as defined earlier (basically computation returns to step 1).

  3/ How are the values of f deduced from the algorithm?

I guess you mean the final output, which is $(n)$.

hopefully this helps!


Is a software implementation of a PCP encoder available?

There has been some recent effort to make PCPs practical for use in verifying outsourced computation. Check the work by this UT Austin group for example: http://www.cs.utexas.edu/pepper/.


Start with the notes form Ras Bodik's course, Program Synthesis for everyone: http://www.cs.berkeley.edu/~bodik/cs294fa12

The slides from the recent summer school are also useful: https://excape.cis.upenn.edu/summer-school.html


Is any computational problem a search problem?

The linked PDF, "Handout 2
 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems":

Decision problems
Search problems
Optimization problems
Counting problems

As the document notes at the beginning, it focuses on the first two: decision and search problems.

  In this course we will deal with four types of computational problems: decision problems, search problems, optimization problems, and counting problems. For the moment, we will discuss decision and search problem.

However, the document seems to talk about decision problems and search problems as though they were conceptually distinct from each other.  It also fails to mention the mapping between them, which is simple and commonly known (PlanetMath):

  A relation $R$ can be viewed as a search problem, and a Turing machine which calculates $R$ is also said to solve it. Every search problem has a corresponding decision problem, namely $L(R)=\{x\mid\exists yR(x,y)\}$.

In short, you're correct to realize that decision and search problems are two sides of the same coin.  You're also correct that it's weird that the document doesn't appear to mention this obvious fact.

Personally, I'd tend to see these terms differing in connotation.  This is, while they can often be mapped to each other, referring to a particular problem as one type rather than another suggests a perspective on how to see that problem, rather than asserts that that problem can't be cast to another type.


Postselection in geometric complexity theory

I like to think this way too, and I link it with the $P=NP\cap co-NP$ conjecture. It is mentionned there or there (I am having a hard time finding pages about this conjecture as I can only refer to it with math symbols that Google does not like).

A problem is in NP when you can give a certificate for a "True" answer (example : a hamiltonian cycle for the TSP problem or a valid assignment for the SAT problem). It is in co-NP when you can give a certificate for a "False" answer (example : a "proof" that the SAT formula is not satisfiable, a bad cut in a graph that prevents the existence of a hamiltonian cycle, etc...)

Actually, those may be the "obstructions" you may refer too. And this conjecture is about saying : a problem which is in NP is polynomial when I know what the obstructions are.

Now, the "obstructions" can take many different forms. For the matching problem (which is polynomial) it can be a partition of the graph (see Tutte's characterization of graphs admitting a perfect matching), or it can be the certificate given by Farkas's Lemma for linear programming (and graph problems that can be reduced to it). It can actually be a great many things, and so I usually "use" this conjecture in one direction :
When I can find no obstructions, I do not deduce that my problem is NP-Hard. Some obstructions are really hard to find... But when I have a complicated polynomial algorithm for a problem, I am sometimes convinced that "there must be an understandable set of obstructions, which would be easier to understand that the complicated algorithm".

Well... My two cents :-)

Nathann


Algorithm for converting very large NFA to DFA

Have you tried Brzozowski's algorithm?  It's worst-case running time is exponential, but I see some references suggesting that it often performs very well, especially when starting with a NFA that you want to convert to a DFA and minimize.

The following paper seems relevant:

On the performance of automata minimization algorithms, Marco Almeida, Nelma Moreira, Rogerio Reis.

It evaluates a number of different algorithms for DFA minimization, including their application to your situation where we start with a NFA and want to convert it to a DFA and minimize it.

What does the strongly connected components (SCC) decomposition of your NFA (considering it as a directed graph) look like?  Does it have many components, where none of the components is too large?  If so, I wonder if it might be possible to devise a divide-and-conquer algorithm, where you take a single component, convert it from NFA to DFA and then minimize it, and then replace the original with the new determinized version.  This should be possible for single-entry components (where all edges into that component lead to a single vertex, the entry vertex).  I don't immediately see whether it would be possible to do something like this for arbitrary NFAs, but if you check what the structure of the SCC looks like, then you might be able to determine whether this sort of direction is worth exploring or not.


Amal Ahmed's very readable thesis dissertation could be a nice start.


Fewest number of gates for Multiplication

Below is a detailed 2008 survey that covers top theoretical algorithms for multiplication, including the ones discussed in the comments to your question (including the Schönhage–Strassen algorithm and the $O(n\log n \, 2^{\log^* n})$ Fuerer algorithm, see page 335 of survey). However, implementation is a different matter and some of these algorithms may not be considered practical; the survey does not cover practical implementations. Although the survey includes algorithms for polynomials, power series, real numbers, and 2-adic numbers, integers are a special case of these (see Figure 1 on page 336).

Fast Multiplication And Its Applications, Bernstein (Algorithmic Number Theory / MSRI Publications / Volume 44, 2008)


Writing pseudocode is like writing code:  It's not particularly important which standard you follow, as long as you (and the people you write with) actually follow some standard.

But for the record, here's the idiosyncratic standard I use in my lecture notes, research papers, and upcoming book.

Use standard imperative syntax for control flow and memory access — if, while, for, return, array[index], function(arguments).  Spell out "else if".

But use $field(record)$ instead of record.field or record->field

Use standard mathematical notation for math — Write $xy$ instead of x*y, $a\bmod b$ instead of a%b, $s\le t$ instead of s <= t, $\lnot p$ instead of !p, $\sqrt{x}$ instead of sqrt(x), $\pi$ instead of PI, $\infty$ instead of MAX_INT, etc.

But use $x\gets y$ for assignment, to avoid the == problem.
But avoid notation (and pseudocode!) entirely if English is clearer.

Symmetrically, avoid English if notation is clearer!

Minimize syntactic sugar — Indicate block structure by consistent indentation (à la Python).  Omit sugary keywords like "begin/end" or "do/od" or "fi".  Omit line numbers.  Do not emphasize keywords like "for" or "while" or "if" by setting them in a different typeface or style.  Ever.  Just don't.

But typeset algorithm names and constants in \textsc{Small Caps}, variable names in italic, and literal strings in sans serif.
But add a small amount of vertical "breathing" space (\\[0.5ex]) between meaningful code chunks.

Don't specify unimportant details.  If it doesn't matter what order you visit the vertices, just say "for all vertices".

For example, here is a recursive formulation of Borůvka's minimum spanning tree algorithm.  I've previously defined $G / L$ as the graph obtained from $G$ by contracting all edges in the set $L$, and Flatten as a subroutine that removes loops and parallel edges.

I use my own lightweight algorithm LaTeX environment to typeset pseudocode.  (It's just a tabbing environment inside an \fbox.)  Here's my source code for Borůvka's algorithm:

\begin{algorithm}
 \textul{$\textsc{Borůvka}(G)$:}\+
\\ if $G$ has no edges\+
\\  return $\varnothing$\-
\\[0.5ex]
 $L \gets \varnothing$
\\ for each vertex $v$ of $G$\+
\\  add the lightest edge incident to $v$ to $L$\-
\\[0.5ex]
 return $L \cup \textsc{Borůvka}(\textsc{Flatten}(G / L))$
\end{algorithm}


Finding invariant elements of binary matrix from row and column sums

The answer is yes. The basic idea is to determine whether there is a matrix $A$ with $A_{i, j} = 0$ and one with $A_{i, j} = 1$. If both answers are yes, then $A_{i, j}$ cannot be determined. otherwise you will know what it is.

Consider such a problem: Given $r$ (row sum) and $c$ (column sum), how to determine whether there is a solution or not?

This problem can be solved by network flow algorithm. Imagine a bipartite graph $G$ whose two disjoint vertex sets are $S$ and $T$. Each vertex in $S$ corresponds to a row in $A$ (so $|S| = n$), and each vertex in $T$ corresponds to a column in $A$ (so $|T| = m$). The network $N$ can be constructed as follows:

Add edge between source and each $s_i$ in $S$ with capacity $r_i$.
Add edge $E_{i, j}$ between each node $s_i$ in $S$ and $t_j$ in $T$ with capacity $1$.
Add edge between each $t_j$ in $T$ and sink with capacity $c_j$.

Find the maxflow in $N$. All edges form source are full iff there is a binary matrix A whose row sum is $r$ and column sum is $c$. And flow in $E_{i, j}$ equals to the value of $A_{i, j}$. It can be found in poly time.

Consider how to find the answer when some $A_{i, j}$ is determined.

We can also construct a network $N$ as above and change the upper and lower bound of corresponding $E_{i, j}$. If you want to find whether there is solution with $A_{i, j} = v$, you can change the upper and lower bound to $v$. You should run this algorithm $2nm$ times to find whether each $A_{i, j}$ can be $0$ or $1$.

PS: The first problem can also be solved by a theorem called "Gale-Ryser Theorem". But I've no idea how to modify it to solve the second one.


Standard format for representing large graphs

I do not think there's a single standard format. igraph library (http://igraph.sourceforge.net/) could be of use, however, as it supports reading/writing of number of different graph formats.


Is this homework problem on T-joins wrong?

The statement of the problem is incorrect.
But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is:
Assume $G$ is connected.
Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the length of the shortest path between vertices $a$ and $b$ in $G$. Now, find a minimum weight perfect matching in $G'$. This gives the minimum $T$-join in $G$.


Is Hamiltonian cycle fixed parameter tractable with parameter clique cover?

Yes, this problem is FPT. We showed this in the paper "Parameterized Edge Hamiltonicity" (Lampis, Makino, Mitsou, and Uno, DAM 2018).

In particular, in this paper we state the result for Hamiltonian Path, but things doesn't change much if you want to consider Hamiltonian Cycle. In the conference version (and the slightly outdated version on the arxiv) we state the result as parameterizing by the chromatic number of the complement of the input graph (which is equal to clique cover).


Maintaining multiple field dynamic values

One possibility (that depends on the relative size of the attribute set and the record set) is to use an inverted index, which is a wildly successful structure for use in text searching. Rather than storing the documents and doing a search, you store a list of which documents contain which value of which attribute for each attribute value pair (again, this only works if the number of attribute-value pairs is not large). Then processing a query requires an intersection of the resulting lists.


[Reposting comment as an answer, based on the OP's response to the comment.]

For a combinatorial definition, it seems like what you're looking for is a circular ordering around the vertices together with a map $f$ from the set of components to the set of faces such that $f(C_i)$ is the face of the graph that contains the component $C_i$.

If you prefer a topological definition, I believe what you're looking for is that the map between the graphs can be extended to a map from the plane to itself that is isotopic to the identity. (Isotopy is, for example, the topological relation typically used to define two knots as being equivalent.)


This answer expands my comment above.

You can do it with $O(\log e + \log \log b)$ space as follows:

1) First compute $b^e$ in Chinese remainder representation modulo sufficiently many primes.

2) Then use the Chiu-Davida-Litow algorithm to convert the Chinese remainder representation into binary representation. (Informatique Theoretique et Applications, Vol 35(3), pages 259-275, 2001)

3) Finally, just count the number of $1$'s.

This is a composition of a finite number of log-space computable functions, which is itself log-space computable.


NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

No NP-complete problem is known to admit a polynomial-time algorithm under uniqueness promise. Valiant and Vazirani theorem applies to any known natural NP-complete problem.
For all known NP-complete problems, there is a parsimonious reduction from 3SAT. Oded Goldreich states the fact that "all known reductions among natural $NP$-complete problems are either parsimonious or can be easily modified to be so". ( Computational Complexity: A Conceptual Perspective By Oded Goldreich).
Edit: This edit is solely to allow change of votes.


Memory requirement for fast matrix multiplication

The space usage is at most $O(n^2)$ for all Strassen-like algorithms (i.e. those based on upper bounding the rank of matrix multiplication algebraically). See Space complexity of Coppersmith–Winograd algorithm

However, I realized in my previous answer that I did not explain why the space usage is $O(n^2)$... so here goes something hand-wavy. Consider what a Strassen-like algorithm does. It starts from a fixed algorithm for $K \times K$ matrix multiplication that uses $K^c$ multiplications for some constant $c < 3$. In particular, this algorithm (whatever it is) can WLOG be written so that:

It computes $K^c$ different matrices $L_1,\ldots,L_{K^c}$ which multiply entries of the first matrix $A$ by various scalars and $K^c$ matrices $R_1,\ldots,R_{K^c}$ from the second matrix $B$ of a similar form,
It multiplies those linear combinations $L_i \cdot R_i$, then
It multiplies entries of $L_i \cdot R_i$ by various scalars, then adds all these matrices up entrywise to obtain $A \cdot B$.

(This is a so-called "bilinear" algorithm, but it turns out that every "algebraic" matrix multiplication algorithm can be written in this way.) For each $i=1,\ldots,K^c$, this algorithm only has to store the current product $L_i \cdot R_i$ and the current value of $A \cdot B$ (initially set to all-zeroes) in memory at any given point, so the space usage is $O(K^2)$.

Given this finite algorithm, it is then extended to arbitrary $K^{\ell} \times K^{\ell}$ matrices, by breaking the large matrices into $K \times K$ blocks of dimensions $K^{\ell-1}\times K^{\ell-1}$, applying the finite $K \times K$ algorithm to the block matrices, and recursively calling the algorithm whenever it needs to multiply two blocks. At each level of recursion, we need to keep only $O(K^{2\ell})$ field elements in memory (storing $O(1)$ different $K^{\ell} \times K^{\ell}$ matrices). Assuming the space usage for $K^{\ell-1}\times K^{\ell-1}$ matrix multiplication is $S(\ell-1)$, the space usage of this recursive algorithm is $S(\ell) \leq S(\ell-1) + O(K^{2\ell})$, which for $S(1) = 2K^2$ solves to $S(\ell) \leq O(K^{2\ell})$.


Pursuing Theoretical Computer Science after CS major

In order to get some feeling of what TCS might look like, I recommend watching the lectures given by Prof. Ryan O'Donnell:
https://www.youtube.com/c/RyanODonnellTeaching/playlists
And lectures given by Prof. Tim Roughgarden:
https://www.youtube.com/channel/UCcH4Ga14Y4ELFKrEYM1vXCg/playlists
And by Prof. Jeff Erickson:
https://www.youtube.com/channel/UClzjdrM8L81bVX_a6u6Hobg/playlists
You may also want to browse some of the podcasts by Simons Institute:
https://www.youtube.com/c/SimonsInstitute/playlists
Good Luck!


Channel coding results using Kolmogorov complexity

For channel capacity, it seems difficult to replace Shannon entropy by Kolmogorov complexity. The definition of channel capacity does not contain any mention of entropy.
Using the Shannon entropy gives the right formula for channel capacity (this is Shannon's theorem). If you replaced the formula with Shannon entropy by a formula with Kolmogorov complexity, it would presumably be a different formula, and so it would be the wrong answer.

If you want to send a string with Kolmogorov complexity $K$ through a channel with capacity $C$ using only slightly more than $K/C$ channel uses, this is very easy. Find the description of the Turing machine that produces the string. Then encode it with an error-correcting code so this description can be sent through the noisy channel with only a small probability of error.

The hard part of the source-channel separation theorem is showing that you can't do better than the obvious method (described in the previous paragraph) of first compressing and then encoding. I don't know whether anybody has proved this for Kolmogorov complexity and channel capacity, but it's a reasonable question to investigate.


I knew him as a mentor back in the day.  In person he went by "Stewart Bainbridge".  Which also answers the question asked by @a3nm about what the "S" stands for.  I never heard about the "Edwin" so presumably it was a given name he wasn't fond of.


A simple way of obtaining a lower bound $c\ge\sqrt{2}$ is to consider pairs of vectors $u,v\in\mathbb{R}$. First of all, it makes sense to focus on pairs of unit vectors for which all $\{-1,1\}$-linear combinations are as long as possible (note that this is just an interesting special case, I'm not saying that it is opotimal in any way). This is achieved when $u,v$ are orthogonal, and by checking the possible rotations we find that $u=\frac{1}{\sqrt{2}}(1,1), v=\frac{1}{\sqrt{2}}(1,-1)$ show that $c$ must be at least $\sqrt{2}$.

This example can be generalized to the sets of vectors $V_k=\{2^{-\frac{k}{2}}v_{i,k}\ |\ 0\le i\le k\}\subseteq\mathbb{R}^{2^k}$, where the $j$-th coefficient $(v_{i,k})_j$ of $v_{i,k}$ is $1$ if the $i-th$ binary digit in $j$ is $0$, and $-1$ otherwise.

The $\infty$-norm of any $\{-1,1\}$-linear combination of the vectors in $V_k$ is $(k+1)2^{-\frac{k}{2}}$, which reaches its maximum $\frac{3}{2}$ at $k=2$, with the set of vectors

$V_2=\{\frac{1}{2}(1,1,1,1),\frac{1}{2}(1,1,-1,-1),\frac{1}{2}(1,-1,1,-1)\}$.

There may be better lower bounds, but this is a start.


What are the current best upper bounds of #P?

One such algorithm for $\#3\operatorname{SAT}$ is due to Kutzkov.


How do you argue a query is impossible in a query language like SPARQL or SQL?

From page 52 of Leonid Libkin's Elements of Finite Model Theory textbook:

  Since we know that graph connectivity is not Hanf-local and transitive closure is not Gaifman-local, we immediately obtain, without using games, that these queries are not FO-definable.

SQL and (original) SPARQL are based on fragments of first-order logic, without fixed-point or transitive-closure operations.  The basic idea is that first-order formulas can only express things that are "local" in some sense, with the reach of locality increasing with the length and complexity of the formula.  (The definitions of Gaifman and Hanf locality make this precise.)  Transitive closure and graph connectivity require either a more powerful way of talking about arbitrarily long paths (like property paths in (new) SPARQL, or a fixed point operator), or arbitrarily long formulas.  So one can't capture path expressions of arbitrary length without explicitly adding support for them to a first-order-based query language.

If you want to know more, have a look at the above textbook, or at the paper:

Leonid Libkin, Logics capturing local properties, ACM Transactions on Computational Logic 2, 135–153, 2001.  doi:10.1145/371282.371388

which has a brief overview of the history with further references.


What kind of optimization problem is that?

As pointed out in the comments already, this is an instance of weighted geometric set cover. Here are some recent relevant references:
http://www.divms.uiowa.edu/~kvaradar/paps/weightedcover.pdf
See also the follow up work:
http://www.cs.uwaterloo.ca/~tmchan/cover_soda.pdf


Given a graph $G$ and a number $k$, such that you want to know whether $G$ contains a $k$-clique, let n be the number of vertices in $G$. We construct another graph $H$, such that $H$ is $n$-colorable if and only if $G$ has a $k$-clique, as follows:

(1) For each vertex $v$ in $G$, make an $n$-clique of vertices $(v,i)$ in $H$, where $i$ ranges from $1$ to $n$.

(2) Add one additional vertex $x$ to $H$.

(3) For each triple $\{x,y,z\}$ of vertices in $H$, where $y=(v,i)$ and $z=(u,j)$, test whether one of the following conditions holds: either $u\ne v$ and $i=j$, or $u$ and $v$ are nonadjacent vertices in $G$ with $\max(i,j)\le k$. If either of these two things is true, add another $n$-clique to $H$. Within this clique, select three vertices $x'$, $y'$, and $z'$. Connect $x$ to every vertex in the clique except for $y'$ and $z'$; connect $y$ to every vertex in the clique except for $x'$ and $z'$; and connect $z$ to every vertex in the clique except for $x'$ and $y'$.

The gadgets added in step (3) prevent the triple of vertices $x$, $y$, and $z$ from all being given the same color as each other in a valid coloring of $H$. The clique in $G$ can be recovered from a coloring of $H$ as the set of vertices $(v,i)$ that are in the same color class as $x$ and that have $i\le k$.