In this context the duality refers to taking the least fixed point in one case and the greatest fixed point in the other. We should try to understand in what sense $L = \forall X . (F(X) \to X) \to X$ and $G = \exists X . (X \to F(X)) \times X$ are the "least" and "greatest" solutions of recursive equation $F(X) \cong X$.

First of all, $L$ and $G$ are indeed fixed points (under certain technical assumptions which restrict the nature of $F$) because the comparison maps $v : F(L) \to L$ and $w : G \to F(G)$ given by
$$v \, x \, X \, g = g \, (F (\lambda h : L \,.\, h \,X\, g)\, x)$$
and
$$w (X, (f, x)) = F (\lambda y : X \,.\, (X, (f, y))) \, (f x)$$
are isomorphisms. Notice that we used the fact that $F$ is a functor, i.e., it is monotone, when we applied it to functions.

Suppose $Y$ is any solution to $F(Y) \cong Y$ with a mediating isomorphism $u : F(Y) \to Y$. Then we have canonical maps $$\alpha : L \to Y \text{  and } \beta : Y\to G$$ defined by
$$\alpha \, f = f\, Y\, u$$
and
$$\beta \, y = (Y, (u^{-1}, y)).$$
Therefore, $L$ is least because we can map from it to any other solution, and $G$ is greatest because we can map from any other solution to it. We could make all this more precise by talking about initial algebras and final coalgebras, but I want my answer to be short and sweet, and cody explained the algebras anyhow.

In practice the least solutions are eager datatypes and the greatest solutions are lazy datatypes. For example, if $F(X) = 1 + A \times X$ then in the first case we get finite lists of $A$'s and in the second finite and infinite lists of $A$'s.


Finding output with unique witness in matrix multiplication

You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one more row to the first matrix B, both of which are all-ones. If the BMM of A and B had a 0 in an entry, your new product over the integers will have 1, and if the BMM had a 1 in an entry, your new product over the integers will have at least a 2. Thus determining these "exactly one" entries is at least as hard as BMM.
Whether or not BMM can be solved faster than matrix multiplication over a ring or field is a major open problem.


NP-intermediate approximation regimes for natural problems within the MAX-k-CSP family

The sidebar algorithm has done its work, and linked to this similar question. The accepted answer there explains that under the Unique Games Conjecture, no such regimes exist.


Unary parametricity vs. binary parametricity

Typically, you use binary parametricity to prove program equivalences. It's unnatural to do this with a unary model, since it only talks about one program at a time.

Normally, you use a unary model if all you are interested in is a unary property. For example, see our recent draft, Superficially Substructural Types, in which we prove a type soundness result using a unary model. Since soundness talks about the behavior of one program (if $e : A$  then it either diverges or reduces to a value $v : A$), a unary model is sufficient. If we wanted to prove program equivalences in addition, we would need a binary model.

EDIT: I just realized that if you look at our paper, it just looks like a plain old logical relations/realizability model. I should say a little bit more about what makes it (and other models) parametric. Basically, a model is parametric when you can prove the identity extension lemma for it: that is, for any type expression, if all of the free type variables are bound to identity relations, then the type expression is the identity relation. We don't explicitly prove it as a lemma (I don't know why, but you rarely need to when doing operational models), but this property is essential for our language's soundness.

The definition of "relation" and "identity relation" in parametricity is actually a bit up for grabs, and this freedom is actually essential if you want to support fancy types like higher kinds or dependent types, or wish to work with fancier semantic structures. The most accessible account of this I know is in Bob Atkey's draft paper Relational Parametricity for Higher Kinds.

If you have a good appetite for category theory, this was first formulated in an abstract way by Rosolini in his paper Reflexive Graphs and Parametric Polymorphism. It has since been developed further by Dunphy and Reddy in their paper Parametric Limits, and also by Birkedal, Møgelberg, and Petersen in Domain-theoretical Models of Parametric Polymorphism.


The originator of the fixed point theorem for DCPOs

The non-constructive version of Pataraia's theorem is called the Bourbaki-Witt fixed point theorem. I learned it from Davey and Priestley's Introduction to Lattices and Order, and Wikipedia gives the following references:

Nicolas Bourbaki (1949). "Sur le théorème de Zorn". Archiv der Mathematik. 2: 434–437. doi:10.1007/bf02036949.
Ernst Witt (1951). "Beweisstudien zum Satz von M. Zorn". Mathematische Nachrichten. 4: 434–438. doi:10.1002/mana.3210040138.

However, as usual, some classically equivalent formulations of this theorem become distinguishable constructively. Andrej Bauer and Peter Lumsdaine have a very nice paper about this, On the Bourbaki-Witt Principle in Toposes, where they examine these issues in detail.


Does $\delta^+(G)+\delta^-(G) \geq n$ imply strong connectivity?

The variation that I suggested was actually slightly different variation of Woodal theorem. Perhaps I saw it in the Bang-Jensen and Gutin's book. At the time that I wrote a comment I didn't check the book for correctness. So to be sure I wrote the graph should be strongly connected. BTW, that statement holds because can be interpreted as a special case of Woodal theorem. In addition does not need strongly connectivity requirement.

This is the theorem 6.4.6 from Bang-Jensen and Gutin's book:

  Let $D$ be a digraph of order $n\ge 2$. If $\delta^+(x)+\delta^-(y) \ge n$ for all pairs of vertices $x$ and $y$ such that there is no arc
  from $x$ to $y$, then $D$ is hamiltonian.

That means the answer to the second part of your question is also Yes.

There was a doubt about that whether $n$ is a tight bound or not. Here I try to answer it. We cannot reduce the requirement of at least $n$ to $k<n$, consider the following graph. $a,b,c$ are making bidirected triangle, and $e,d$ are making a bidirected $k_2$. If hamiltonian cycle starts at $e$, it cannot go to $d$ in the next move because the only way for $d$ is using $b$ but, $b$ is the only way to back to $e$. On the other hand the Hamiltonian cycle after $e$ cannot go to $c$, because then the only back way to $e,d$ is going directly to $d$ to use $b$ in next moves, but again we are in the previous position. Also from the picture it's clear that every vertex has in and out degree at least $2$. So sum of every two arbitrary in-out is at least $4=5-1 = n-1$. We can extend these sort of graphs to arbitrary $n$.

P.S1: Sure the aforementioned theorem holds for simple digraphs. i.e digraphs without loop or parallel edges.

P.S2: I don't have a good Tex tool right now. So image is not good.


Randomized algorithm that "looks" deterministic?

Shafi Goldwasser communicated to me that she and coauthors have been investigating exactly such algorithms for number-theoretic problems!  The following is known:

Lenstra has shown that there is such an algorithm for finding a quadratic non-residue mod a given prime.
Gat and Goldwasser have shown that there is such an algorithm for finding a generator of $\mathbb{Z}_p^*$, where $p$ is a given prime of the form $2q + 1$ for a prime $q$.

(I don't know of citable references.) There is also ongoing research on the question I asked about finding a prime between $n$ and $2n$.

EDIT: The paper by Gat and Goldwasser is now published: http://eccc.hpi-web.de/report/2011/136/. This paper though doesn't resolve the question of finding a prime between $n$ and $2n$.


Trees that structure partially ordered data

Interval trees store partially ordered data (intervals) and can answer complex queries (e.g. find all the intervals overlapping given one/containing given one/etc). Looks like criteria (2) and (3) are met, but I'm not sure if I understand (1) correctly.


Approximation schemes for P-complete problems?

This one seems related, although it focuses more on parallel time (NC) rather than the closely related space (L): http://www.springerlink.com/content/8hn2q8lvf3ukbbx0/


Downward self-reducibility of factorization

The state of the art here is: We can decide primality in polynomial time, but the fastest, general-purpose algorithm to $\underline{\rm find}$ the factors of an n-bit composite integer takes time $\approx 2^{n^{1/3}\log^{2/3}n}$.

More to your question, a primality test is the same thing as a compositeness test. Therefore, we can easily implement the 'primality decision oracle' required by any (supposed) Cook reduction from factoring to itself.

The reason, then, that factoring is commonly presented as an example of a problem that is "unlikely to be downward self-reducible" is because of the possibility that such a reduction identifies prime factors of the original integer. This can be phrased in many ways, but as Joshua points out in comments above, a good example is a reduction that takes $(n, k)$ (is there a factor of $n$ that is at most $k$?) to $(m, k')$ where $m|n$.

A reduction of this particular type would have the consequence of breaking the plethora of cryptosystems based on the hardness of factoring (without the need for a quantum computer), e.g. RSA.


Linear time algorithm for finding shifted max

We can compute $m$ in linear time.

For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$.
We want to compute $m = \max_i B[i]+i$.

Let $max = \max_i A[i]$.
Obviously $max \leq m$.

Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have
$$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$$

Therefore we can ignore $A[j]$ when $A[j] \leq max - n$.
We only need to consider the numbers in the range $[max-n, max]$.

We can use counting sort to sort the numbers in $A$
which are in the range $[max-n, max]$ in linear time and
use the sorted list to compute $m$.


Please check the following proof, and see the final remark with a link to code for an $O(n)$-time algorithm.
Theorem 1. There is an $O(n\log n)$-time algorithm for the problem.
Proof.
Fix an instance $(n, A, W)$ of the problem. Define index set $I = \{(i, j) : 1\le i\le j \le n\}$. The goal is to compute $\max_{(i,j)\in I} M_{ij}$, where
$$\textstyle M_{ij} = \Big(\sum_{h=i}^j A[h]\Big) - (j-i+1) W[j].$$
Observe that $M_{ij}$ has the (upper-triangular) inverse Monge property (see e.g. this survey on Monge matrices):
Lemma 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i<k$ and $j < \ell$, $$M_{i\ell} - M_{ij} \le M_{k\ell} - M_{kj}.$$
Proof of Lemma 1.  By calculation,
$$M_{i\ell} - M_{ij} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-i+1) W[j] - (\ell-i+1) W[\ell],$$
while
$$M_{k\ell} - M_{kj} = \Big(\sum_{h={j+1}}^\ell A[h]\Big) + (j-k+1) W[j] - (\ell-k+1) W[\ell],$$
so
$$(M_{i\ell} - M_{ij}) - (M_{k\ell} - M_{kj}) =
(k-i) W[j] - (k - i) W[\ell] = (k-i)(W[j] - W[\ell]),$$
which is non-positive as $k > i$, and $j<\ell$ so $W[j] \le W[\ell]$.  This proves Lemma 1. $~~~\Box$
It is well-known (e.g. Section 3.7 of this survey) that the Monge property is sufficient to obtain a simple $O(n\log n)$-time algorithm, and it is easy to adapt that algorithm to the upper-triangular case.  For completeness I'll sketch the algorithm here.
Lemma 1 implies that $M$ is (upper-triangular) totally (inverse) monotone:
Corollary 1. For any $(i, j)$ and $(k, \ell)$ in $I$ such that $i<k$ and $j < \ell$, if $M_{ij} \le M_{i\ell}$ then $M_{kj} \le M_{kl}$.
For $1\le i \le n$, define $J(i) = \arg\max_{j} M_{ij}$ to be the column index of the maximum entry in row $i$.  Corollary 1 implies the following additional corollary:
Corollary 2. $J(1) \le J(2) \le \cdots \le J(n)$
The algorithm computes $J(i)$ for the middle row $i=\lfloor n/2 \rfloor$ in $O(n)$ time (having precomputed all partial sums of $A$ in $O(n)$ time, so that the value of any given $M_{ij}$ can be computed in constant time), then subdivides $M$ into four quadrants around the point $(i, J(i))$, recurses on the upper-left and lower-right quadrants, and takes either $(i, J(i))$ or one of the two points returned recursively, whatever is best.
(Note that the algorithm does not explicitly construct all of $M$.  In fact, it examines $O(n\log n)$ entries of $M$.)
By Corollary 2, the maximum cannot be in the upper-right or lower-left quadrant, so the algorithm is correct.
Letting $T(n, m)$ denote the worst-case runtime on an $n\times m$ index set, we have $$T(n, m) \le m + \max_{1\le j\le m} ~T(\lfloor n/2 \rfloor -1, j) + T(n - \lfloor n/2\rfloor, m-j+1)$$
and $T(1, m) \le m$.  For any execution of the algorithm, the recursion tree has $O(\log n)$ levels. Within a given level, letting $(n_j, m_j)$ denote the dimensions of the $j$th subproblem on that level, we have $\sum_j m_j = O(m)$, from which it follows that the total work for all subproblems on that level (outside of their recursive calls) is $O(m)$, so that $T(n, m) = O(m\log n)$. (This can also be easily verified by induction.) So the run-time of the top-level call is $T(n, n) = O(n\log n)$. $~~~\Box$
Remarks. The total monotonicity of $M$ (Corollary 1 above) probably also implies an $O(n)$-time algorithm via the SMAWK algorithm. (It would if $M$ was totally (inverse) monotone, instead of just "upper-triangular" totally inverse monotone.)  I don't know whether SMAWK applies in this case, but I'd guess so. EDIT: See comment below.
Note that the above proof requires neither the assumption $A[i] \ge W[i]$, nor the non-negativity of the $A[i]$'s and $W[i]$'s.
EDIT: It seems to me that we can extend $M$ to make it totally inverse Monge simply by taking $M_{ij}$ to be, say, $-n W[n]$, for $1\le j < i \le n$.  Then we no longer require the "upper triangular" assumption: the property in Corollary 2 holds for all pairs $(i, j)$ and $(k, \ell)$ with $(1,1) \le (i, j) < (k, \ell) \le (n, n)$.  That is, $M$ extended in this way is totally (inverse) monotone. So the SMAWK algorithm can be applied to this $M$ to solve the problem in $O(n)$ time.
A quick google search gives this Python implementation of the SMAWK algorithm by David Eppstein.  I adapted his code to solve your problem; here is my adaptation.


When do coherence spaces have pullbacks and pushouts?

I now see how to define equalizers for coherence spaces, which means pullbacks always exist (since products do). I don't know how to do this, actually....

Recall that composition is the usual relational composition, so if $f : A \to B$ and $g : B \to C$, then:

$f ; g = \{(a,c) \in A \times C \;|\; \exists b \in B.\; (a,b) \in f \land (b,c) \in g\}$

(In this definition, the existential actually implies unique existence. Suppose that we have $b' \in B$ such that $(a,b') \in f$ and $(b', c) \in g$. Since we know that $a \Bumpeq_A a$, this means that $b \Bumpeq_B b'$. Then this means that we have $b \Bumpeq_B b'$ and $(b,c) \in g$ and $(b',c) \in g$, so consequently $b = b'$.)

We now construct equalizers. Suppose we have coherence spaces $A$ and $B$, and morphisms $f, g : A \to B$. Now define the equalizer $(E, e : E \to A)$ as follows.

For the web, take
$$E = \left\{
\begin{array}{l|c}
& \forall b.\; (a,b) \in f \implies \exists a' \Bumpeq_A a.\; (a',b) \in g \\
a \in A & \land \\
& \forall b.\; (a,b) \in g \implies \exists a' \Bumpeq_A a.\; (a',b) \in f \\
\end{array}
\right\}
$$
This picks out the subset of tokens of $A$ on which either $f$ and $g$ agree (up to coherence -- I had this wrong in my first version), or are both undefined.
Define the coherence relation on $\Bumpeq_E = \{ (a,a') \in \Bumpeq_A \;|\; a \in E \land a' \in E\}$. This is just the restriction of the coherence relation on $A$ to the subset $E$. This will be reflexive and symmetric since $\Bumpeq_A$ is.
The equalizer map $e$ is just the diagonal $e : E \to A = \{(a, a)\;|\;a \in E\}$.

Since I messed up my first version of the proof, I'll give the universality property explicitly. Suppose we have any other object $X$ and morphism $m : X \to A$ such that $m;f = m;g$.

Now define $h : X \to E$ as $\{(x,a) \;|\; a \in E\}$. Obviously $h;i \subseteq m$, but to show the equality we need to show the converse $m \subseteq h;i$.

So assume $(x,a) \in m$. We now need to show that $\forall b.\; (a,b) \in f \implies \exists a' \Bumpeq_A a.\; (a',b) \in g$ and $\forall b.\; (a,b) \in g \implies \exists a' \Bumpeq_A a.\; (a',b) \in f$.

First, assume $b \in B$ and $(a,b) \in f$. So we know that $(x,a) \in m$ and $(a,b) \in f$, so $(x,b) \in m;f$. Therefore $(x,b) \in m;g$, and so there is an $a' \in A$ such that $(x,a') \in m$ and $(a',b) \in g$. Since $x \Bumpeq x$, we know $a \Bumpeq a'$, and so there is an $a' \Bumpeq a$ such that $(a',b) \in g$.

Symmetrically, assume $b \in B$ and $(a,b) \in g$. So we know that $(x,a) \in m$ and $(a,b) \in g$, so $(x,b) \in m;g$. Therefore $(x,b) \in m;f$, and so there is an $a' \in A$ such that $(x,a') \in m$ and $(a',b) \in f$. Since $x \Bumpeq x$, we know $a \Bumpeq a'$, and so there is an $a' \Bumpeq a$ such that $(a',b) \in f$.


Using a linear sieve like this:

https://e-maxx-eng.appspot.com/algebra/prime-sieve-linear.html

you can factor every number in range $j=2,3,..,k-1$ in linear time.

From there, you get an array with some prime divisor (the least for example) of each number in the range. Using that you can solve your problem by filling $A$ in order, and for each new number $j$ you just use the prime divisor of it, find it's greater exponent in $a$, and $j$, and use the previously calculated results in $A$ to get your answer. I'm not totally sure this last part it runs in linear time, but it should be possible.


Are there Similar Distance Binary Error Correcting Codes?

Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.

To see it, write the elements of the set as the rows of a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the relative distance between codewords is always between $0.5 - \epsilon$ and $0.5 + \epsilon$.

One particular construction of such sets will give you a code whose dimension is linear in its block length. It is mentioned here:
http://www.wisdom.weizmann.ac.il/~benaroya/SmallBiasNew.pdf

Basically, the idea is to take AG codes of constant rate and relative distance close to $1$, and concatenating them with the Hadamard code.


Functions that typed lambda calculus cannot compute

A nice example is given by Godelization: in lambda calculus, the only thing you can do with a function is to apply it. As a result, there is no way to write a closed function of type $(\mathbb{N} \to \mathbb{N}) \to \mathbb{N}$, which takes a function argument and returns a Godel code for it.

Adding this as an axiom to Heyting arithmetic is usually called "the constructive Church thesis", and is a strongly anti-classical axiom. Namely, it is consistent to add it to HA, but not to Peano arithmetic! (Basically, it is a classical fact that every Turing machine halts or not, and there is no computable function that can witness this fact.)


From the paper: what is actually proven is, in Theorem 1.4,
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad s(f) \geq \sqrt{\deg f} \tag{1}
$$
which cannot be improved (it is tight for some functions). Then it is combined with the previously known result of Nisan and Szegedy [1],
$$
\forall f\colon\{0,1\}^n \to \{0,1\}, \qquad \deg f \geq \sqrt{\frac{1}{2}\operatorname{bs} f}
\tag{2}
$$
(a separation, incidentally, you asked about a few years back). From this survey [2] (see Table 1), referencing [3], (2) cannot be improved beyond
$$
\operatorname{bs} f \gtrsim (\deg f)^{\log_3 6}
$$
where $\log_3 6 \approx 1.63$. So this avenue of using the degree as a proxy cannot give a quadratic sensitivity upper bound on the the block sensitivity.

On the other hand, it's possible that using similar techniques (i.e., interlacing eigenvalues of signed matrices) but on different objects (first and foremost, without using the degree as a proxy) may lead to sharper bounds. This is explicitly stated as open question in Huang's paper [4]:

  Perhaps one could close this [quadratic vs. quartic] gap by directly applying the spectral method to boolean functions instead of to the hypercubes.

[1] Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomials. Comput. Complexity, 4:462–467, 1992. doi:10.1007/BF01263419

[2] Pooya Hatami, Raghav Kulkarni, and Denis Pankratov, Variations on the Sensitivity Conjecture. Theory of Computing Graduate Survey, 2011. https://theoryofcomputing.org/articles/gs004/

[3] Noam Nisan and Avi Wigderson. On rank vs. communication complexity. Combinatorica, 15:557–565, 1995. doi:10.1007/BF01192527

[4] Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. arXiv:1907.00847, 2019.  https://arxiv.org/abs/1907.00847


Quantum Hardness of Approximating Lattice Problems

The answer to your question is the same as with many other such assumptions in cryptography: despite a lot of effort no one has found any substantially faster quantum algorithms for lattice problems. Why do we assume that RSA is secure? We don't have any particular justification for its classical hardness other than the fact that no one has found any fast algorithms for it, and we know that it is vulnerable to quantum attacks. Despite this we trust it to protect billions of dollars of e-commerce.

On the other hand, the situation is not really the same. There is much better justification for LWE-based systems being secure. What makes LWE appealing is that it's based on the worst-case (quantum) hardness of lattice problems. As you probably know, a holy grail of crypto is to derive average-case-hard primitives like one-way functions from worst-case hardness assumptions like $P \neq NP$. Regev's reduction is a big step in this research program, and as far as I know there are no non-lattice based schemes whose security is based on worst-case hardness assumptions.

Finally, it's worth noting that LWE may still be secure against classical attacks even if there are efficient quantum algorithms for lattice problems. A major open problem in lattice-based cryptography is to prove classical hardness of LWE with parameters that match the quantum reduction. A paper by Peikert in 2009 and a follow-up paper by Brakerski et al. in 2013 made progress towards this goal by showing classical hardness of LWE under some weaker parameter settings.


Which properties of planar graphs generalize to higher dimension / hypergraphs?

Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper:

http://www.cs.uiuc.edu/~jeffe/pubs/crum.html

This already implies that you can encode pretty nasty graphs as intersection graphs of triangles in 3d. See section 4 of this paper:

http://sarielhp.org/p/09/set_cover_hard/

BTW, I am interested in a similar version of your problem by trying to understand how geometric intersection graph behaves...


What you describe is a non-stochastic version of the "functional multi-arm bandit problem": you know you have an unknown function from some class C (does not have to be randomly selected), and you have query access to this function. The goal is to find the element which maximizes the function. As you say, depending on the class C, this may or may not require learning the function.

This paper by Amin, Kearns, and Syed exactly characterizes the query complexity of the problem: http://www.cis.upenn.edu/~mkearns/papers/haystack.pdf


Is it possible to find if a sequence exists in polynomial time in the following problem?

... I searched some patterns to build a reduction from a NPC problem, but didn't find a way to represent a "flow" with a "fork" ...

So (after some work) this is a polynomial algorithm ...

ALGORITHM

The starting list can be viewed as an array of $N*2$ consecutive "holes". For each initial pair $(a_j,b_j)$, put the "element" $b_j$ at hole number $a_j$. Each pair can be viewed as a directed edge from position $a_j$ to position $b_j$. A move consists in picking an element $b_j$ at position $a_j$ and moving it to its destination position $b_j$ (the destination hole becomes an unmovable peg). We delete the edge, and proceed to choose the next move which will start from one of the two nearest reachable elements $b_k$ from position $b_j$ (only holes between $b_j$ and $b_k$ are allowed). We must find a sequence of $N$ consecutive moves.

For each $(a_j,b_j)$ consider $b_j$ (at array position $a_j$) as the starting element $start$.

For each $(a_k,b_k), a_k \neq a_j $ consider $a_k$ as the final element $end$ (the edge from position $a_k$ to position $b_k$ will be the final edge).

generate a sequence of moves from $start$ using the following criteria until you reach element $end$ (and a solution has been found), or a stop condition

When you make a move you fix a peg at position $b_j$ and the array is splitted in two partitions $L$ (left) and $R$ (right) and the only way to go from $L$ to $R$ (or from $R$ to $L$) is using an edge that jump across the peg. Set

$edgesLR$ = number of edges from  left to right (do not count the final edge)
$edgesRL$ = number of edges from right to left (do not count the final edge)
$flow$ = $edgesLR - edgesRL$

Cases:

A) if $| flow | > 1$ then one of the two partitions will become unreachable, stop

Now suppose that $end > b_j$, i.e. $end \in R$

B) if $flow = 1$ then there is an extra edge from left to right, you must go left (pick the nearest element of $L$), otherwise you will never reach $end$

C) if $flow = -1$ then there is an extra edge from right to left and whatever node you pick you will never reach $end$, stop

D) if $flow = 0$ you must go right (pick the nearest element of $R$), otherwise you will neve reach $end$

If $end < b_j$ ($end \in L$), B,C,D are inverted.

NOTE: when moving left or right, you must consider $end$ as a peg. For example, if you must go right, but the nearest element on $R$ is $end$ then the move is impossible (and you must proceed with another pair $(start,end)$)

Apply the same resoning at every move.

COMPLEXITY

The flows over each hole can be precalculated in O(N) and reused at every scan.

The loops are:

for start = 1 to N
  for end = 1 to N
    for move = 1 to N
      make a move (fix a peg and update flows)
      check if another move can be done using flow

No choices are made during the computation, so the complexity of the algorithm is $O(N^3)$

CODE

This is a working Java implementation of the algorithm:

public class StrangeSort {
    static int PEG = 0xffffff, HOLE = 0x0;
    static int M = 0, N = 0, choices = 0, aux = 0, end;
    static int problem[][], moves[], edgeflow[], field[];
    boolean is_hole(int x) { return x == HOLE; }
    boolean is_peg(int x) { return x == PEG; }
    boolean is_ele(int x) { return ! is_peg(x) && ! is_hole(x); };
    int []cp(int src[]) { // copy an array
        int res[] = new int[src.length];
        System.arraycopy(src, 0, res, 0, res.length);
        return res;
    }
    /* find the first element on the left (dir=-1) right (dir=1) */
    int find(int pos, int dir, int nm) {
        pos += dir;
        while (pos >= 1 && pos <= M ) {
            int x = field[pos];
            if ( is_peg(x) || (pos == end && nm < N-1) ) return 0;
            if ( is_ele(x) ) return pos;
            pos += dir;
        }
        return 0;
    }
    void build_edges() {
        edgeflow = new int[M+1];
        for (int i = 1; i<=M; i++) {
            int start = i;
            int b = field[start];
            if (! is_ele(b)) continue;
            if (i == end) continue;
            int dir = (b > start)? 1 : -1;
            start += dir;
            while (start != b) { edgeflow[start] += dir; start += dir; }
        }
    }
    boolean rec_solve(int start, int nm) {
        boolean f;
        int j;
        int b = field[start];
        moves[nm++] = b;
        if (nm == N) return true;
        //System.out.println("Processing: " + start + "->" + field[start]);
        field[start] = HOLE;
        field[b] = PEG;
        int dir = (b > start)? 1 : -1;
        int i = start + dir;
        while (i != b) { edgeflow[i] -= dir; i += dir; } // clear edge
        int flow = edgeflow[b];
        if (Math.abs(flow) > 2) return false;
        if (end > b) {
            switch (flow) {
            case 1 :
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case -1 :
                return false;
            case 0 :
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }
        } else {
            switch (flow) {
            case -1 :
                j = find(b,1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            case 1 :
                return false;
            case 0 :
                j = find(b,-1,nm);
                if (j <= 0) return false;
                return rec_solve(j,nm);
            }
        }
        return false;
    }
    boolean solve(int demo[][]) {
        N = demo.length;
        for (int i = 0; i < N; i++)
            M = Math.max(M, Math.max(demo[i][0], demo[i][1]));
        moves = new int[N];
        edgeflow = new int[M+1];
        field = new int[M+1];
        problem = demo;
        for (int i = 0; i < problem.length; i++) {
            int a = problem[i][0];
            int b = problem[i][1];
            if ( a < 1 || b < 1 || a > M || b > M || ! is_hole(field[a]) || ! is_hole(field[b])) {
                System.out.println("Bad input pair (" + a + "," + b + ")");
                return false;
            }
            field[a] = b;
        }
        for (int i = 1; i <= M; i++) {
            end = i;
            build_edges();
            if (!is_ele(field[i])) continue;
            for (int j = 1; j <= M; j++) {
                if (!is_ele(field[j])) continue;
                if (i==j) continue;
                int tmp_edgeflow[] = cp(edgeflow);
                int tmp_field[] = cp(field);
                choices = 0;
                //System.out.println("START: " + j + " " + " END: " + i);
                if (rec_solve(j, 0)) {
                    return true;
                }
                edgeflow = tmp_edgeflow;
                field = tmp_field;
            }
        }
        return false;
    }
    void init(int demo[][]) {

    }
    public static void main(String args[]) {
        /**** THE INPUT ********/

        int demo[][] =  {{4,2},{5,7},{6,3},{10,12},{11,1},{13,8},{14,9}};

        /***********************/
        String r = "";
        StrangeSort sorter = new StrangeSort();
        if (sorter.solve(demo)) {
            for (int i = 0; i < N; i++) { // print it in clear text
                int b =  moves[i];
                for (int j = 0; j < demo.length; j++)
                    if (demo[j][1] == b)
                        r += ((i>0)? " -> " : "") + "(" + demo[j][0] + "," + demo[j][1] + ")";
            }
            r = "SOLUTION: "+r;
        }
        else
            r = "NO SOLUTIONS";
        System.out.println(r);
    }
}


There are deterministic and randomized algorithm running in time $\mathrm{poly}(n,d,k)$, where $n$ is the number of variables, $d$ is the degree and $k$ is the sparsity. AFAIK, the results are stated for characteristic zero fields but work over any field large enough (again, polynomially large in the parameters).

This paper of Kaltofen and Yagati discusses both the randomized algorithm of Zippel and the deterministic algorithm of Ben-Or and Tiwari, and then goes on to present some improvements.


For sampling-based algorithms, nearly tight upper and lower bounds are known for the query complexity of estimating the number of distinct elements in a sequence.

Charikar, Chowdhuri, Motwani and Narsayya showed that multiplicative approximation of the number of distinct elements to within a factor $\alpha$ can be achieved with $q= O(n/\alpha^2)$ queries into the sequence.

Here's the algorithm. Sample $q$ items uniformly at random from the sequence. Let $d$ be the number of distinct items in the sample, and let $f_1$ be the number of items that appear exactly once in the sample. Then, output $d + \sqrt{n/q} \cdot f_1$.

The analysis is also very clean. Assume without loss of generality that each element in the sequence is an integer in $[k]$, where $k$ is the number of distinct elements. Let $p_i$ be the probability of selecting $i$ when sampling uniformly from the sequence. Then, the expected output of the estimator is:

$$\mathbb{E}[d + \sqrt{n/q}\cdot f_1] =  \sum_{i=1}^k (1 - (1-p_i)^q) + \sqrt{n/q} \cdot p_i q (1-p_i)^{q-1}$$

Now, the point is that for any valid $p_i$, the value inside the summation is between $\Omega(\sqrt{q/n})$ and $O(\sqrt{n/q})$. (This uses the fact that $1/n \leq p_i < 1$.) So, the expected output of the algorithm is within $O(\sqrt{n/q})$ of $k$.

Charikar et al.'s estimator can also be used to get an additive approximation of the number of distinct elements. One can estimate the number of distinct elements upto $\pm \beta n$ by making $O((1-2\beta) n)$ samples. This was the state-of-the-art for a long while until STOC '11 when Greg and Paul Valiant showed that it's possible to reduce the sample complexity and time complexity to $O(\frac{n}{\beta^2 \log n})$. Their algorithm is based on a very general result that, given a probability distribution $D$, constructs a distribution $D'$ using $O(n/\log n)$ samples such that $D$ and $D'$ are close to each other in relative earthmover distance. So, one can make sure that the support size of $D'$ and the support size of $D$ are only an additive $\beta n$ away from each other.

As for lower bounds, Charikar et al. showed that for $\alpha$-multiplicative approximation, $\Omega(n/\alpha^2)$ queries are needed. The proof stems from the observation that $\Omega(n/\alpha^2)$ queries are needed to distinguish $n$ identical items from the same sequence with $\alpha^2$ unique elements inserted in random locations. For additive approximation, however, this bound is sort of trivial; for constant $\beta$, this would only give a constant lower bound on the query complexity. Raskhodnikova, Ron, Shpilka, and Smith showed a nearly linear bound even for additive approximation. Specifically, they prove that estimating to within additive error $n/23$ requires $n/2^{\sqrt{\log n} \log \log n}$ queries. The Valiants in their above-cited paper showed a lower bound of $\Omega(n/\log n)$ for estimating to any additive error less than $n/4$, implying that their upper-bound is tight upto constant factors.


Can you decide equivalence for monotone Boolean expressions that do not contain negation in PTIME?

Corollary 3.5 of [BHR84] shows that the problem is coNP-complete.

[BHR84] P. A. Bloniarz, H. B. Hunt, III, and D. J. Rosenkrantz.  Algebraic structures with hard equivalence and minimization problems.  Journal of the ACM, 31(4):879–904, Oct. 1984.  http://dx.doi.org/10.1145/1634.1639


Why does Dinur's proof of the PCP theorem fail to work for unique games?

The powering step fails. After the powering, each vertex is labeled with a neighborhood of the original graph. each edge checks that its endpoints agree on the intersection of their neighborhoods, and that this labeling satisfies the edges in this intersection. However, the edge cannot check anything about part of the labeling that lies outside the intersection of the neighborhoods, and therefore cannot enforce the uniqueness property.


If $\mathcal{G}$ is a class of graphs with bounded treewidth, then the homomorphism problem from graphs in $\mathcal{G}$ is polynomial-time solvable. This can be generalized to the more general property of "graphs whose core has bounded treewidth."

Grohe proves a converse: if the cores of the graphs in $\mathcal{G}$ have unbounded treewidth, then the homomorphism problem from $\mathcal{G}$ is not polynomial-time solvable (assuming $FPT\neq W[1]$). Therefore, if you restrict the left-hand side graph to Cayley graphs etc., then what matters is whether the cores have bounded treewidth.

http://dl.acm.org/authorize?951212

Note that this does not completely answer your question: in the result of Grohe, it is  assumed that the right-hand side graph is arbitrary. You seem to be interested in results where the right-hand side graph is also restricted to some specific class of graphs.


How can you prove that a problem is not solvable in a certain time complexity?

One area where unconditional and nontrivial time lower bounds are known is in data structures, where the time is for individual data structure operations (or sequences of operations). The standard model for this sort of thing is called the "cell probe model"; it assumes only that main memory is divided into words of a certain size and that the CPU has a very limited amount of local storage (e.g. in registers or cache), and bounds the number of word read/write operations that must be performed.

For instance, in the cell probe model one can prove that the problem of maintaining prefix sums of word-length values (that is, maintain an array of values subject to operations that change one value in an array or that query the sum of a prefix of the values) requires $\Omega(n\log n)$ time to perform a sequence of $n$ operations on an array of length $n$. The difficulty here comes in part from the fact that the operations have to be performed online (not knowing in advance the sequence of future operations).

Fredman and Saks' STOC'89 paper "The cell probe complexity of dynamic data structures" and Patrascu and Demaine's SICOMP'05 "Logarithmic lower bounds in the cell-probe model" are probably good starting points; look up cell probe lower bounds in Google scholar for much more.


Two rectangles whose sum of areas is given

Assume all integers involved are even. This can be ensured by multiplying $P$ by 4. Here is an idea that should speed up the search. Let $p = \left\lceil\sqrt{P}\right\rceil$. If $p*p = P$ we are done. Otherwise, let $k$ be the minimum such that $\alpha =p*p-k*k \leq P$. If $\alpha=P$, we are done as $(p-k)\times(p+k)$ is the desired solution with perimeter $$4p$$. Otherwise, clearly $1 \leq k^2 \leq 4p$ (otherwise, $p$ would be smaller). But this implies that $k \leq c*P^{1/4}$, where $c$ is some small constant. This implies that $P - \alpha \leq c'*P^{1/4}$.  Thus, the solution with rectangles $$(p-k)\times(p+k) \text{ and } 1\times(P-\alpha)$$ has perimeter $4p + O(P^{1/4})$. Since $4(p-1)$ is a lower bound on the solution by the argument below (intuitively, the isoperemeteric inequality), this implies that search range is only of size $O(P^{1/4})$ (as far as the overall perimeter is concerned).

It definitely feels like this argument can be pushed even further...

And Jeff is right - this is not necessarily too interesting as far as pure theory. But it is fun...

Lower bound. Observe that if the two rectangles are $x_1\times y_1$ and $x_2\times y_2$, then the rectangle $(x_1+x_2)\times(y_1+y_2)$ must have area larger than $P$. But then, the minimum perimeter rectangle of a given area is a square. This implies that $2(x_1+x_2+y_1+y_2) \geq 4\sqrt{P}$.


Examples in which the size of the alphabet ($\geq 2$) used for an encoding matters

Dinur's proof of the PCP theorem relies heavily on the manipulation of the alphabet size.

Specifically, the overall structure of the proof is an iterative application of a graph powering technique a logarithm in the graph size number of times. On each iteration, the graph is pre-processed into a regular expanding graph, amplified by a power (which blows up the alphabet size), and then a PCP composition is applied (turning each constraint over a large alphabet into a system of constraints over a small alphabet).

The implicit goal of the process is to find a way to re-use the amplification step until the UNSAT value becomes a constant fraction (proving the PCP theorem). The key point is that unless the alphabet size is pulled back each time, the resulting graph is not what is needed for the final reduction.


Here are some results of a simple Google search:

Certification of a Type Inference Tool for ML: Damas–Milner within Coq by Catherine Dubois and Valérie Ménissier-Morain
Formalization of a Polymorphic Subtyping Algorithm by Jinxu Zhao, Bruno C. d. S. Oliveira, and Tom Schrijvers
type-inference formalization in Coq, based on A Rewriting Semantics for Type Inference


When does a set of infixes determine a set of ($\omega$-) words

There are several interesting subquestions in your question:

Which $\omega$-languages are determined by a set of finite infixes of a specific length?
When does a set of infixes determine a $\omega$-word uniquely?
What could be said about the relations about infix-sets and $\omega$-languages?
Are there any results or articles on this topic?

Let $A$ be a finite alphabet, let $n$ be a positive integer and let $F$ be a subset of $A^n$.
Given an $\omega$-word $u$, let $F_n(u)$ be the set of its factors (= infixes) of length $n$.

Question 1. It can be restated as follows: What is the $\omega$-language
$$
  L(F) = \{ u \in A^\omega \mid  F_n(u) = F \}?
$$
The answer is
$$
  L(F) = \bigcap_{x \in F}A^*xA^\omega \setminus \bigcup_{x \in A^n \setminus F}A^*xA^\omega
$$
which shows that $L(F)$ is $\omega$-regular (it actually belongs to a much smaller class of $\omega$-languages than the regular ones, see below).

Question 2. I only have a weak answer to this question. Given $F$, one can effectively compute $L(F)$ (say, by a finite Büchi automaton) and then one can effectively decide whether $L(F)$ contains a single $\omega$-word (which has to be ultimately periodic). I also tried the other way around: given an ultimately periodic word $uv^\omega$, is the language $\{uv^\omega\}$ of the form $L(F)$ for some $F$? This question is again decidable, but they might be some simple combinatorial characterization on the pair $(u, v)$. Unfortunately, I only got some partial results in this direction.

Question 3. I know of several topics in which infix-sets and $\omega$-languages are related.

Locally testable $\omega$-languages (the notion of locally testable languages was originally introduced for finite words and later extended to infinite words [2]). The language $L(F)$ is an example.
Factors of biinfinite words [1].
First order logic of one successor [3].
Sophic shifts and subshifts of finite type in symbolic dynamics [4].

Question 4. A few references:

[1] D. Beauquier and M. Nivat, About rational sets of factors of a bi-infinite word, LNCS 194, (1985) 33-42.
[2] J.P. Pécuchet Étude syntaxique des parties reconnaissables de mots infinis, Theoret. Comput. Sci. 56 (1988) 231-248.
[3] The expressive power of existential first order sentences of Büchi's sequential calculus.
[4] M.P. Béal and D. Perrin, Symbolic Dynamics and Finite Automata.


Maximum fractional packing of spanning trees.

The problem gets very easy if you look at the feasible space, which is simply the spanning tree polytope, intersected with a linear number of half-spaces, one for each packing constraint.

The spanning tree polytope has a separation oracle (check this for example), therefore since you only have an additional linear number of constraints, it carries over to yield a separation oracle for your problem. Using this oracle, you can optimize any linear functional of the polytope in polynomial time.

If I remember well, using the ellipsoid algorithm, you can get a running time of $\tilde{O}(m^2 \cdot T)$, where $T$ is the running time of the separation oracle (which in this case you can get from a min-cut algorithm). Probably not as good as other existing algorithms, but it gives you an idea of how you can quickly check that the problem is polynomial time solvable.


Matrix vector multiplication algorithm using minimal number of additions

This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history).

A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can one do better. It is known that for a random matrix one cannot do significantly better.

Some matrices - such as the Fourier transform matrix, a matrix of low rank, or a sparse matrix - can be done significantly better.

A sufficiently rigid matrix cannot be computed by linear circuits that are simultaneously linear size and log depth (Valiant), but to this day no explicit matrices are known for which there is a super-linear lower bound on the size of linear circuits.

I don't recall seeing results saying that it's hard to compute the size of the smallest linear circuit for a given matrix, but I wouldn't be surprised if it were NP-hard.


"Parity testing set" for disjoint pairs of sets

Recall that a distribution $Y$ over $\{0, 1\}^n$ is called $\epsilon$-biased if for every nonempty set $P \subseteq [n]$, we have
$$
\left|\mathbb{E}[\oplus_{i \in P} Y_i] - \frac{1}{2}\right| \leq \frac{\epsilon}{2}.
$$
In other words, an $\epsilon$-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error $\epsilon/2$. I claim that an $\epsilon$-biased distribution automatically also fools functions of the form $\mathsf{AND} \circ \mathsf{PARITY}$. That is:
Claim: Let $f \colon \{0, 1\}^n \to \{0, 1\}$ be of the form $f(x) = \wedge_{i = 1}^m \bigoplus_{j \in P_i} x_j$, where $P_1, \dots, P_m \subseteq [n]$. Let $Y$ be $\epsilon$-biased and let $U$ be uniform random over $\{0, 1\}^n$. Then
$$
\left|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]\right| \leq \epsilon.
$$
Proof: We can use the Fourier expansion of the AND function:
$$
f(x) = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot \prod_{i \in T} (-1)^{\oplus_{j \in P_i} x_j} = \sum_{T \subseteq [m]} \frac{(-1)^{|T|}}{2^m} \cdot (-1)^{\bigoplus_{i \in T, j \in P_i} x_j}
$$
For a fixed $T \subseteq [m]$, we have
$$
|\mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} Y_j}] - \mathbb{E}[(-1)^{\oplus_{i \in T, j \in P_i} U_j}]| \leq 2 \cdot |\mathbb{E}[\oplus_{i \in T, j \in P_i} Y_j] - \mathbb{E}[\oplus_{i \in T, j \in P_i} U_j]| \leq \epsilon.
$$
Therefore, by the triangle inequality,
$$
|\mathbb{E}[f(Y)] - \mathbb{E}[f(U)]| \leq \sum_{T \subseteq [m]} \frac{\epsilon}{2^m} = \epsilon. \qquad \square
$$
Your condition, that $|S \cap P|$ and $|S \cap Q|$ are both odd, can be rephrased as a function $f$ as in the claim by considering the indicator vectors of all the sets under consideration. Under the uniform distribution, the condition is satisfied with probability $1/4$. Therefore, it suffices to take $X$ to be the support of an $\epsilon$-biased distribution with $\epsilon < 1/4$. Plugging in known constructions of small-biased distributions gives an explicit construction with $|X| = O(n)$.


How did TCS become conference-oriented rather than journal-oriented?

While I don't know the answer to this question, it seems crucial that the phenomenon isn't limited at all to theoretical computer science.  I believe SIGGRAPH plays the same sort of role for graphics, NIPS for machine learning, ISCA for architecture, etc. that STOC and FOCS play for theory.  Yet it's true that the emphasis on publication in conference proceedings is a striking feature of computer science as a whole, one that isn't shared by any other academic field that I know about.  (But maybe there are other such fields?)


Which definition of asymptotic growth-rate should we teach?

I prefer teaching the original definition with quantifiers.

IMO, humans generally have trouble in understanding formulas and definitions with more than two alternation of quantifiers directly. Introducing new quantifiers can clarify what the definition means. Here, the last two quantifiers just mean "for all sufficiently large n", introducing this kind of quantification can help.

The pictures I draw for explaining these concepts match better with the quantifier versions.

I think the limit simplification is useful for engineering student who are only interested in computing the growth rate, but won't be as useful for computer science students. In fact, using this simplification can cause more harm than good.

This idea is similar to suggestion that we use the rules for computing derivatives (of polynomials, exponentiation, ..., chain rule, ...) in place of the epsilon-delta definition of it, which IMHO is not a good idea.


Existence of solution for a system of multi-variate polynomial equations and in-equations

The question seems to be based on false premises, so let me try to deconfuse it.

Solvability of systems of polynomial equations with integer coefficients is NP-hard over any fixed field (or integral domain). For instance, it is straightforward to reduce the satisfiability of a 3-CNF $\phi(x_1,\dots,x_k)$ to the solvability of a polynomial system including $\{x_i^2-x_i:i=1,\dots,k\}$ and a bunch of polynomials translating each 3-clause.
Solvability of general polynomial systems with integer (or rational) coefficients is polynomially reducible to solvability of systems of multilinear degree-$2$ polynomials with coefficients in $\{-1,0,1\}$ and at most $3$ nonzero monomials each. To see this, express each polynomial by an arithmetical circuit (aka straightline program) using operations $+$, $\cdot$, variables, and constants $0,1,-1$. Introduce a new variable for each node in the circuit, and take the set of polynomials describing the value of each node in terms of its inputs.
The multivariate polynomial ring $K[x_1,\dots,x_k]$ (for a field $K$) is indeed a GCD domain, but for $k\ge2$ it is not a Bézout domain, hence the gcd’s do not behave the way you think they do. For example, the polynomials $x_1$ and $x_2$ have a common root $(0,0)$, even though $\gcd(x_1,x_2)=1$.

Thus, your problem is NP-hard, and as such it has no known polynomial-time algorithm (deterministic or randomized). Under plausible assumptions, it even has no subexponential-time randomized algorithm.

Furthermore:

Over a field, inequations can be replaced by equations: instead of $q(x_1,\dots,x_k)\ne0$, use $q(x_1,\dots,x_k)y=1$, where $y$ is a fresh variable.
Solvability of systems of polynomial equations (hence also inequations, by above) in $\mathbb C$ can be ckecked in PSPACE, due to Canny [1]. This is the best known unconditional result, but:
Assuming the Riemann hypothesis for Dedekind $\zeta$ functions, solvability of polynomial systems in $\mathbb C$ can be checked in the class AM, due to Koiran [2]. Moreover, we can derandomize AM to NP under plausible Nisan–Widgerson-style complexity assumptions, thus assuming both, the problem becomes NP-complete.

[1] John Canny, Some algebraic and geometric computations in PSPACE, Proc. 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 460–467.

[2] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.


When polynomial GI implies polynomial (edge) colored GI?

Q2: a nice example is the graph labeling gadget used to prove that:

Theorem: Planar 3-connected colored GI $\leq_T^L$ planar 3-connected GI

See Thomas Thierauf, Fabian Wagner: The Isomorphism Problem for Planar 3-Connected Graphs Is in Unambiguous Logspace. Theory Comput. Syst. 47(3): 655-673 (2010)

The "labeling gadget" used preserves the 3-connectedness and planarity constraints.


Perfect Matching with ``set-over-like" constraints?

The problem can be solved in $O(n^k \, \text{poly}(n))$ time, so it's not "NP-hard in $n$" unless P=NP.

Here's one simple algorithm.  Enumerate all subsets $E'$ of $E$ such that $|E'|\le k$.  Check whether the union of labels of $E'$ is equal to $\{1,2,\dots,k\}$; if not, move on to the next candidate for $E'$.  Then, check whether there's a perfect matching of $G$ that includes all edges of $E'$.  This can be done as follows: check that no pair of edges in $E'$ meets in a common vertex; let $V^*$ be the set of vertices that don't touch any edge of $E'$, and $E^*$ the set of edges both of whose endpoints are in $V^*$; then check whether $G^*=(V^*,E^*)$ has a perfect matching.  If such a perfect matching exists, you have found a valid solution to your original problem.  There are $O(n^k)$ possible subsets $E'$, so the entire procedure runs in $O(n^k \, \text{poly}(n))$ time.  Correctness follows because if there is a set of edges whose labels have union equal to $\{1,2,\dots,k\}$, then there is a set of size $\le k$ with this property.


The short answer is yes, MLTT can reasonably be equated with CIC without impredicative Prop.

The main technical issue is that there are dozens of variants when one talks about Martin-Löf Type Theory and, perhaps more surprisingly, when one talks about CIC. For example, taking the version of CIC defined in Benjamin Werner's thesis, it doesn't even make sense to remove Prop, as one doesn't have either Set or universes of Type.

The main variations one can consider in either of these theories are:

Universes: how many, and how are they defined (Palmgren, On Universes in Type Theory, discusses many inequivalent variations), and whether or not universe polymorphism is admitted.
Which inductive types/families: Agda admits Inductive-Recursive types, but there are many more mundane variations depending on how "large" the types in the constructors and eliminators are allowed, handling parameters vs indices, etc.
Injectivity of type constructors. This leads to a system inconsistent with EM in Agda. Of course Epigram has a more extreme "Observational Type Theory", but this can be considered something different altogether.
Axiom K: this comes for free with certain versions of dependent pattern matching.
Intentional vs Extensional: this is a huge difference, where essentially a new conversion rule is added in the extensional systems
$$ \frac{\Gamma\vdash t:\mathrm{Id}_{\mathrm{Type}}\ A\ B }{\Gamma\vdash A\ =\ B} $$
Which makes type-checking undecidable (but much more powerful!). Martin-Löf himself seems to have considered both types of systems.
The presence of coinductive types and associated elimination principles.

All of the above variations (except OTT) have been considered in the literature and associated with the name "Martin-Löf Type Theory" or "Calculus of Inductive Constructions", mostly because of their association with the Agda and Coq systems, respectively.

So the long answer is that there is no consensus about what the exact definition of either of these systems is.


Impagliazzo and Wigderson's famous P=BPP paper

Check Chapter 7 of Salil Vadhan's monograph. Corollary 7.64 is Impagliazzo and Wigderson's result.


An improper planar coloring with monochromatic component size $\leq 2$

2-colorable perfect matching in cubic planar graphs is very similar to your problem which was stated to be NP-complete by Schaefer in his famous dichotomy theorem paper although he did not give the proof for cubic planar graphs. The problem asks for the existence of two coloring of cubic planar graphs such that every vertex has exactly one neighbor of the same color as itself.

EDIT:
Defective coloring is the decision version of your problem. A graph is (k, d)-colorable if one can color the vertices with k colors such that no vertex is adjacent to more than d vertices of its same color. The decision problem (2,1)-coloring with defects, which is equivalent to your optimization problem, was shown to be NP-complete even for planar graphs.


Does using Normal Order Evaluation instead of Normal Order Reduction lose the Normalization theorem?

NOE reduction strategy (as you define it) won't find the $\beta$-normal form of a term. For example, the normal form of $\lambda x.((\lambda y.y)x)$ is $\lambda x.x$
but NOE won't find it, because it won't reduce the inner redex $(\lambda y.y)x$ which is under the outer $\lambda$-abstraction. So it's not a normalizing reduction strategy.

However, in a typed functional language with data types like Int, if you know that some expression is of such a type, you know that it cannot be a function, so it's enough to restrict reductions to so-called Weak Head Normal Form (which is close to NOE), and it simplifies many things. See also:

http://www.haskell.org/haskellwiki/Weak_head_normal_form
https://en.wikibooks.org/wiki/Haskell/Graph_reduction#Weak_Head_Normal_Form
https://stackoverflow.com/questions/6872898/haskell-what-is-weak-head-normal-form


Are the problems PRIMES, FACTORING known to be P-hard?

PRIMES is known to be hard for $\mathsf{TC^0}$.  See my paper with Saks and Shparlinski, "A Lower Bound for Primality" in JCSS 62 (2001).  No improvement on that front since then.


DFA intersection algorithm for special cases

Yes, there are some cases of the DFA non emptiness insersection problem that are inside P. My master's thesis is devoted to this question, but unfortunately it is in French. However, most of the results have appeared here in $[2]$.

When the alphabet is unary, then the problem is L-complete when each DFA has at most two final states, and NP-complete otherwise. Most of the other cases are restriction on the transition monoids of the automata. For example, for abelian group transition monoids, the problem is in $\text{NC}^3$ when each DFA has at most one final state, and NP-complete otherwise; for elementary 2-group transition monoids, the problem is $\oplus$L-complete when each DFA has at most two final states, and NP-complete otherwise.

Let me now address your more precise question, which can only be found in $[1]$. Suppose you are given DFAs working over $\{0,1\}$ and shaped as trees, i.e there exists a state $u$ (initial state) such that for each state $v$ there exists a unique path from $u$ to $v$. Then, deciding the intersection non emptiness is:

L-complete for one final state in each DFA,
NL-complete for two final states in each DFA, and
NP-complete for three or more final states in each DFA.

The hardness results still hold even if you "fork" respectively 0, 1 or 2 times (this is your $K$). Now if your DFAs are directed acyclic graphs instead of trees, then the problem is NP-complete even with one final state in each DFA and $K=2$; the reduction is quite straightforward and is from Monotone 1-in-3 3-SAT.

Therefore, no, I don't think there is an efficient algorithm for your problem.

Now, if the number of automata is fixed, you might want to discuss with Michael Wehar who has recently published $[3]$.

EDIT: Since OP edited his question, let me clarify my answer with his new requirements. Consider the NP-complete problem Monotone 1-in-3 3-SAT where you are given a formula in 3-CNF without negation, and where you have to determine whether there is an assignment that makes exactly one variable true in each clause. You can reduce this problem to the non emptiness intersection problem as follows. For example, for the clause $x_2 \lor x_3 \lor x_5$, you build the following automaton:

$\hskip2in$

Note that the automata are trees (and hence DAGs), are levelled, and have three final states. Actually, the three final states coud be merged into a single one, if one is satisfied with DAGs. Moreover, only two states have two (distinct) outgoing transitions.

Michael Blondin. Complexité raffinée du problème d'intersection d'automates, M.Sc. thesis, Université de Montréal, 2012.
Michael Blondin, Andreas Krebs et Pierre McKenzie. The Complexity of Intersecting Finite Automata Having Few Final States, Computational Complexity (CC), 2014.
Michael Wehar. Hardness Results for Intersection Non-Emptiness. ICALP, 2014.


Like Emil says, the answer is yes, because the length (in binary) of the input string is actually computable by a deterministic logtime Turing machine, so is a fortiori in $\mathsf{FO}$.

You may find this stated as Lemma 13 of Buss's The Boolean formula value problem is in ALOGTIME.  The idea, attributed to Dowd, is to use the query tape to do binary search (under the convention that the machine gets an "out of range" response if the query tape contains a binary number exceeding the length of the input).  I cut-and-paste the proof for quick reference (the number $n$ referenced in the proof is the length of the input, i.e., the desired output; the "index tape" is what Emil and I called query tape):

  The [...] Turing machine proceeds as follows. First determine the least value of $i$ such that $n < 2^i$: this is easily done in $O(\log n)$ time since we assume that the index tape and its tape head are unaffected when the input tape is accessed. Once the value $2^i$ is obtained, written on the [index] tape, it is now easy to do a binary search to determine the value of $n$. Finally the index tape is copied to the output tape.

(NB: the paper actually says "Once the value $2^i$ is obtained, written on the input tape", etc., but it must be a typo, the computation described is obviously done by writing on the index/query tape. Besides, the input tape is usually read-only in this setting).


Examples for derandomization via small sample spaces

Here is an example from low degree testing literature: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BSVW03/BSVW03.pdf.

High-level summary: Consider BLR linearity testing algorithm that given oracle access to a function $f:\mathbb{F}^m \rightarrow \mathbb{F}$, first, samples $x,y$ uniformly randomly from $\mathbb{F}^m$ and then tests if $f(x)+f(y)=f(x+y)$ by querying the function at required points. This paper reduces the amount of randomness usage by sampling $y$ from an epsilon-biased set instead of sampling from the entire space.


Church's Theorem and Gödel's Incompleteness Theorems

First, I suggest you read Kleene's "Metamathematics" as a good book on these topics. First two chapters of volume I of Odifreddi's "Classical Recursion Theory" can also be helpful in understanding the relation between these concepts.

We know that Church's theorem (or rather, the independent proofs of Hilbert's Entscheidungsproblem  by Alonzo Church and Alan Turing) proved that in general we cannot calculate whether a given mathematical statement in a formal system is true or false.

I think you are referring to Church's theorem that the set of theorems of first order logic is not decidable. It is important to note that the language is first order.

As I understand, the Church-Turing thesis provides a pretty clear description of the equivalence (isomorphism) between Church's lambda calculus and Turing machines, hence we effectively have a unified model for computability.

No. The equivalence if lambda-computability and Turing-computability is a theorem of Kleene. It is not a thesis. It is considered as evidence supporting Church's thesis.

Note: As far as I know, Turing's proof makes use of the fact that the halting problem is undecidable. Correct me if I'm wrong.
Now, Gödel's first incompleteness theorem states that not all statements in a consistent formal system may be proven within this system. In many ways, this appears to me to be saying exactly the same thing to me as Church's theorems, considering lambda calculus and Turning machines are both effectively formal systems of sorts!

No. Godel's theorem states that for every $\omega$-consistent, recursively enumerable theory which contains enough arithmetic, there is a sentence $\varphi$ s.t. $\varphi$ and $\lnot \varphi$ are not provable in it.
This does not state the same thing. It does not say anything about set of theorems of the theory being undecidable.

This is however my holistic interpretation, and I was hoping someone could shed some light on the details. Are these two theorems effectively equivalent? Are there any subtleties to be observed? If these theories are essentially looking at the same universal truth in different ways, why were they approached from such different angles? (There were more or less 6 years between Godel's proof and Church's).

Over the years there has been lots of abuse of Godel's theorems (and similar theorems). One should be very careful in making interpretations of them. As far as I have seen, the abuses are usually result of forgetting to mention some condition in the theorem or combining the theorems by some other beliefs. A careful look shows that theses theorems, although related, are not equivalent.

Finally, can we essential say that the concept of provability in a formal system (proof calculus) is identical to the concept of computability in recursion theory (Turing machines/lambda calculus)?

I don't understand what you mean by "identical". Certainly there are many relations between computability and provability. I may be able to make a more helpful comment if you clarify what you mean by these being identical.
update
Lets consider the set of well-formed sentences in the language of arithmetic as $L$. Let $T$ be (the axioms of) a theory satisfying the conditions of first incompleteness theorem. Let $Thm(T)$ be the set of theorems of the theory $T$ and $\lnot Thm(T)$ be the set of sentences whose negation is a theorem of $T$. Let $True$ be the set of sentences that are true in the standard model, and $False$ the set of false sentences. A sentence is in $True$ iff its negation is in $False$. Also every sentence is either true or false, i.e. $L = True \cup False$.
The Godel's incompleteness theorem states that $Thm(T) \cup \lnot Thm(T)$ is a proper subset of $L$. Therefore truth in the standard model and provability in $T$ are different.
Note that $Thm(T)$ is r.e., Church's theorem states that $Thm(T)$ is not decidable.
On the relation between provability in formal system and computability. One is the following: If the system is effective, then the set of derivable expression in it is r.e., and the system is a special case of a grammar. Grammars is another way for defining the concept of computable which is equivalent to Turing machine computability.


How large a treewidth can a tree plus half the edges have?

Your model is not really any less general than asking about arbitrary 3-regular graphs, and 3-regular expander graphs have linear treewidth. So I don't know about constant factors, but Θ(n) is best possible, yes.


Efficient all pair bottleneck computation for a tree

You can even get $O(|V|)$ time if the edge weights are sorted. See the following paper:

Erik D. Demaine, Gad Landau, and Oren Weimann, “On Cartesian Trees and Range Minimum Queries”, in Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), Lecture Notes in Computer Science, volume 5555, Rhodes, Greece, July 5–12, 2009, pages 341–353.


An excellent beginner overview is given by the following article from 2009.

Boolean Satisfiability: From Theoretical Hardness to Practical Success, Sharad Malik, Lintao Zhang,  Communications of the ACM, 2009

There are several ways to get into the technical aspects. You can even start with the original Davis-Putnam paper. It is extremely clear and has detailed examples. When discussing SAT optimizations in a course, we discovered that a few one  may imagine are already there. The Davis-Logeman-Loveland paper is (I feel) less instructive, but it is so short you may as well read it.

A Computing Procedure for Quantification Theory, Martin Davis, Hilary Putnam, Journal of the ACM, 1960.
A machine program for theorem-proving, Martin Davis, George Logemann, Donald Loveland, Communications of the ACM, 1962.

There are may ways to catch up on the developments of the next 50 years. I would recommend lecture slides. Just searching for 'DPLL' will throw up many many tutorials. If you browse through them, I'm sure the mist will clear -- to some extent. There are also many useful surveys. The Zhang-Malik paper is a good place to start. There are several articles in the Handbook of Satisfiability you may find useful.

The Quest for Efficient Boolean Satisfiability Solvers, Lintao Zhang, Sharad Malik, Joint invited paper for CAV and CADE 2002.
Handbook of Satisfiability, Edited by Armin Biere, Marijn Heule, Hans van Maaren, and Toby Walsh, 2009
Anatomy and Empirical Evaluation of Modern SAT Solvers, Karem  Sakallah, Joao Marques-Silva, Bulletin of the EATCS, 2011.

I second the suggestion of Mikolaos. The MiniSAT code is clean and of manageable size. You can play with it. There are several other solvers you can try. CryptoMiniSat is also quite clean. You should also consult the work of Armin Biere, who writes SAT solvers and writes about writing SAT solvers.


Is there any special property the resulting graph G' has?

The formal statement of the graph you are describing is the sum of $n$ complete $k_i$-partite graphs (where $k_i$ is the number of groups in $G_i$).

Here is an interesting property: $G'$ is $\prod k_i$-colorable.

A $k$-partite graph (assuming non-empty parts) is $k$-colorable (color all of the vertices in one part with the same color). A complete $k$-partite graph has chromatic number $k$ (clearly two vertices in two different parts require different colors). In fact, it has a maximal set of edges such that the graph has chromatic number $k$ (adding an edge within a part will force another color). If the graphs $G_1$ and $G_2$ are $k_1$ and $k_2$ colorable respectively, the sum $G = G_1 + G_2$ is $k_1k_2$ colorable by the product coloring. It follows that each $G_i$ is $k_i$ colorable, and that the sum, $G'$ is $\prod k_i$-colorable.

This property is tight if we know nothing more about the graphs. For arbitrary $n$ let $p_1p_2\cdots p_k$ be the prime factorization of $n$ (where repeated primes are listed repeatedly). If $G'$ is the sum of $k$ correctly-chosen complete $p_i$ partite graphs, $G' = K_n$. To choose $G_1$, let the parts be the residues modulo $p_1$. For $G_2$, let $i$ be in a part according to the residue of $\lfloor \frac{i}{p_1}\rfloor$ modulo $p_2$. Continuing this for each $k$ makes the right subgraphs. The best way to imagine this is to express $i$ has a number where the 1s place goes up to $p_1$, the $p_1$s place (the next digit over) goes up to $p_2$, etc. Then $G'$ is complete because if $i \neq j$ then The representations of $i$ and $j$ are different.


Is iszero of the untyped lambda calculus sound and complete?

No, iszero does not have to test whether two functions are equal. It only has to detect a difference between them, i.e., extract enough information to tell whether the given function represents a 0 or not.

You could ask the same question about equality testing. It is possible to implement an equality test eq for numbers (exercise, but implement predecessor first). Isn't it the case that eq is comparing functions for equality? No. First of all, eq does not compare arbitrary functions but only those that happen to encode numbers. Second, even when comparing two function n and m that encode numbers, it does not answer the question "are n and m equal function?" but rather "do n and m encode the same number?" These are two different questions.


Why is Feige-Fiat-Shamir not Zero Knowledge without sign bits?

The Feige-Fiat-Shamir (FFS) identification protocol is a proof of knowledge (PoK), in which the prover (Peggy) proves her knowledge the square roots of the given input to the verifier (Victor).

FFS want to discriminate PoK from proofs of language membership, in which Peggy proves that the input has some property (more formally, the input belongs to a certain language).

If we don't use the negative signs, it's possible that the inputs do not possess any square root. For instance, the number 20 does not have any square roots mod 21. Since distinguishing squares and non-squares is a famous hard problem, FFS avoid it by allowing the input to be the plus or minus of some number squared. In their own words (changed a bit):

  By allowing $v_i$ to  be either plus or minus a square modulo a Blum integer, we make sure that $v_i$ can range over all the numbers with Jacobi symbol $+1 \bmod n$ and  thus the $s_i$ exist (from V's point of view) regardless of $v_i$ character, as required in unrestricted input zero-knowledge proofs of knowledge.

By unrestricted input zero-knowledge proofs of knowledge, they mean a ZK PoK whose corresponding proof of language membership is trivial; i.e. V can by himself decide that the input is the plus or minus of some square (by just checking the Jacobi symbol).


Sequential execution is an edge case of concurrent computation.
Robin Milner said this clearly in his  Turing award lecture "Elements of interaction" (CACM, 36(1), 1993):

I reject the idea that there can be a unique conceptual model,
or one preferred formalism, for all aspects of something as large
as concurrent computation, which is in a sense the whole of our
subject – containing sequential computation as a well-behaved
special area.

You can see sequential computation as a form of well-behaved, nice concurrent computation. This niceness comes out when comparing the processes of reasoning about, an implementing sequential vs concurrent computation.

But this insight is much older and forms the essence of the Actor
model. See for example Hewitt's 1976 "Viewing Control Structures as
Patterns of Passing Messages".

There are various ways of enforcing sequential computation in process
calculus. A simple one is only to allow processes that have at most
one active output, i.e. an output that is not under an input
prefix. This can be enforced by typing see e.g. "Strong Normalisation in the $\pi$-Calculus".

Now coming to your question: does interaction on $x$ in  $x(v).P \ |\ \overline{x}y.Q \rightarrow P[y/v] \ |\ Q$ represent sequential behaviour as such? No. The reason is that other processes could be running in parallel with $x(v).P \ |\ \overline{x}y.Q$. All we are seeing here is an exchange of messages, a handshake, where the receiver has to wait until the sender's message arrives.


What is the relation of HOL Light type theory and some of the intuitionistic type theories?

HOL is a simple type theory, while Martin-Löf's is a dependent type theory. That is the fundamental difference between the two.

One can embed HOL into extensional type theory, i.e., type theory with identity types and the equality reflection principle
$$\frac{\vdash p : \mathrm{Id}_A(s,t)}{\vdash s \equiv_A t}$$
You could try a less drastic principle, such as Streicher's $K$ axiom or uniqueness of identity proofs, in which case you will be interested in conservativity of intensional type theory with $K$ over extensional type theory. But perhaps you don't want to dig into such details right now.


Minimum Parity Weight Path - what is the complexity?

The problem can be solved in $O(n(m + n \log n))$ time. The solution below is based on one by Grötschel and Pulleyblank to compute shortest paths with an even (odd) number of edges (Gröschel and Pulleyblank in turn contribute it to 'Waterloo-folklore'. Schrijver contributes their solution to J. Edmonds.) We'll solve the stronger problem of finding a minimum parity weight $s - t$ path with an odd (even) number of edges. The cheaper of the odd and even solutions is the minimum parity weight $s - t$ path.

Let $G=(V,E)$ be your input graph. Create a new graph $G'$. Graph $G'$ contains two copies of $G$ denoted $G_1$ and $G_2$. Every edge $e \in E$ retains its weight in $G_1$ but is given weight $0$ in $G_2$.
Finally, for every vertex $v \in V$, $G'$ contains an edge of weight $0$ between $v$'s copies in $G_1$ and $G_2$. Let $v_i$ be the copy of $v$ in graph $G_i$. Find a minimum weight perfect matching $M$ in $G' - s_2 - t_2$ in $O(n(m + n \log n))$  time (Gabow [1990]). Let $P = (V,E')$ contain exactly the edges of $M$ that were copied from $G$ (possibly with multiplicity). One connected component of $P$ is a minimum parity weight $s - t$ path with an odd number of edges, and its parity weight is equal to $M$'s total weight.

To prove the claim, let $P$ a minimum parity weight $s - t$ path in $G$ with an odd number of edges. Let $M$ be the perfect matching of $G' - s_2 - t_2$ containing $G_1$'s copies of the first, third, etc. edges of $P$, $G_2$'s copies of the second, forth, etc. edges of $P$ and the $0$ weight edges between $v_1$ and $v_2$ for every vertex $v$ not in $P$. Matching $M$ has the same weight as $P$'s parity weight, so some perfect matching of $G'$ contains $P$ and has the appropriate weight.

Conversely, let $M$ be a perfect matching in $G' - s_2 - t_2$, and let $P = (V,E')$ contain exactly the edges of $M$ that were copied from $G$ (possibly with multiplicity). For every vertex $v \notin \{s,t\}$, either $v$ is incident to two edges copied from $G$ in $M$, or both copies of $v$ were matched along a $0$ weight edge not present in $G$. Vertices $s$ and $t$ have one matched copy in $M$. Therefore, every vertex of $P$ has degree $2$ or $0$ except for $s$ and $t$ which have degree $1$. Therefore, $s$ and $t$ lie in the same connected component of $P$, and that component is a path. Further, when tracing the edges of that path from $s$ to $t$ you find they come from $G_1$, then $G_2$, then $G_1$, etc. ending with $G_1$. There are an odd number of edges, and the parity weight of that path is the weight of those edges in $G'$. Every other component of $P$ must have non-negative weight, so $M$ is a perfect matching in $G' - s_2 - t_2$ with weight no less than $P$.

Finding a minimum parity weight $s - t$ path with an even number of edges is solved in exactly the same way, except you find a minimum weight perfect matching in $G' - s_2 - t_1$.


Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory

A) The input here is the triple of partitions $(\lambda, \mu, \nu)$, represented as sequences of numbers in binary. The dimension of the irreducible representation $M_{\lambda}$ can actually be exponential in $r$, take for example the hook partition $n + 1, 1, 1, \dots, 1 \vdash 2n + 1$. Using the hook formula for the dimension we get $\frac {(2n)!}{(n !)^2}$.

B) The $P$ in $\# P$ means polynomial time, but the $\#$ in $\#P$ means "count computation paths of a nondeterministic machine". An example of $\#P$ problem is $\#SAT$ (count the number of satisfying assignments for a given formula), and the corresponding decision problem is $SAT$, which is probably not in $P$.


Why does Fourier analysis of Boolean functions "work"?

Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions of TCS, there is an underlying need to analyze the effects that such operators have on certain functions.

Now, the point is that the Fourier basis is the basis that diagonalizes all those operators at the same time, which makes the analysis of those operators much simpler. More generally, the Fourier basis diagonalizes the convolution operator, which also underlies many of those questions. Thus, Fourier analysis is likely to be effective whenever one needs to analyze those operators.

By the way, Fourier analysis is just a special case of the representation theory of finite groups. This theory considers the more general space of functions $f:G\to \mathbb{C}$ where $G$ is a finite group, and operators of the form $\sigma_h$ (for $h\in G$) that map $f(x)$ to $f(x\cdot h)$, The theory then allows you to find a basis that makes the analysis of such operators easier - even though for general groups you don't get to actually diagonalize the operators.


First order expression for functional dependency

Apparently, we must project away variable z from ternary relation Q, which is done via existential quantifier:

∀y1∀y2∀x:(∃z:Q(x1,y,z))∧(∃z:Q(x2,y,z))⟹x1=x2.

This is equivalent to standard textbook FD definition:

∀y1∀y2∀x∀z1∀z2:Q(x1,y,z1)∧Q(x2,y,z2)⟹x1=x2.


Notation for a Conditional Hamiltonian Evolution Operator

I remember struggling with this very same question! Ultimately I concluded that the $C$ is just a notational device (it doesn't represent any mathematical operation), just to indicate that, for a specific $\tau$, the Hamiltonian evolution operator $e^{iA\tau t_0/T}$ is performed on $\left|b\right>$, but only when conditioned on $\left|b\right>$ being tensored with $\left|\tau\right>$.

If you ignore the $C$'s, I think a calculation will show that you just apply the operator $\sum_{\tau=0}^{T-1} \left|\tau\right>\left<\tau\right|\otimes e^{iA\tau t_{o}/T}$ "as-is". I hope this helps.


Constraint satisfaction problem on a graph

1 in 3 Sat reduces to this problem.
http://en.wikipedia.org/wiki/One-in-three_3SAT

Set d=3, each k_i = 2 and each l_i=1

To implement negation add $x,\overline{x},a$ and $x,\overline{x},b$ and $a,b,c$.
The only possible assignment is a=0,b=0 and c=1, so $x$ and $\overline{x}$ must be different.


What's known about basing one-way function on the $P \neq NP$ assumption?

We cannot hope to prove a general impossibility result since if one-way functions exist (and we believe they do), then in particular it follows that the statement "If $P \ne NP$ then one-way functions exist" is true.

However, we can prove that certain proof techniques are too weak to prove that statement. In particular, the following paper of Akavia, Goldreich, Goldwasser and Moshkovitz proves that this statement cannot be proved by certain black-box reductions (conditioned on plausible assumptions):

http://www.wisdom.weizmann.ac.il/~oded/p_aggm.html


What can I do to supplement my theoretical undergraduate CS curriculum so that I can increase my value in industry & academia?

I need some suggestions on what skills or knowledge I should accumulate before I graduate and apply for graduate school, or get a job in industry (hopefully more than just programming). Basically, I'm looking for a good direction.

What are you really passionate about?

Among the things that you're really passionate about, what are you really good at?

Do that.

Talk to everyone you can who does that.  Figure out who does that well and who just spouts shiny nonsense about doing that.  Ask the good ones how they got good at doing that.  Do what they do.  Most of what they do won't work for you, but until you try and fail yourself, you won't know what works and what doesn't.  And you will fail; brush it off, get back up, and keep doing that.  Don't avoid the uncomfortable, frustrating,  boring, but necessary stuff you have to do to learn to do that well and to keep doing that.

Oh, and as long as you're in college, you might as well take some classes.


What's the complexity of this estate-division game?

Perhaps this paper will be of interest though I don't know if it addresses complexity issues:

http://or.journal.informs.org/cgi/content/abstract/19/2/270

or

http://www.jstor.org/pss/169267


Kristoffer's solution can be used to show that, assuming reals are represented so that we can compute limits of sequences of reals which are computably Cauchy. Recall that a sequence $(a_n)_n$ is computably Cauchy if there is a computable map $f$ such that, given any $k$ we have $|a_{m} - a_{n}| < 2^{-k}$ for all $m, n \geq f(k)$. The standard representations of reals are like that, for example the one where a real is represented by a machine that computes an arbitrarily good rational approximation. (We can also speak in terms of computing digits, but then we have to allow negative digits. This is a well known issue in computability theory of the reals.)

  Theorem: Suppose $S \subseteq \mathbb{R}$ is a subset such that there exists a computable sequence $(a_n)_n$ which is computably Cauchy and its limit $x = \lim_n a_n$ is outside $S$. Then question "is a real number $x$ an element of $S$" is undecidable.

Proof.
Suppose $S$ were decidable. Given any Turing machine $T$, consider the sequence $b_n$ defined as
$$b_n = \begin{cases}
a_n & \text{if $T$ has not halted in the first $n$ steps,}\\
a_m & \text{if $T$ has halted in step $m$ and $m \leq n$.}
\end{cases}$$
It is easy to check that $b_n$ is computably Cauchy, therefore we can compute its limit $y = \lim_n b_n$. Now we have $y \in S$ iff $T$ halts, so we can solve the Halting Problem. QED.

There is a dual theorem in which we assume the sequence is outside $S$ but its limit is in $S$.

Examples of sets $S$ satisfying these conditions are: an open interval, a closed interval, the negative numbers, the singleton $\lbrace 0 \rbrace$, rational numbers, irrational numbers, transcedental numbers, algebraic numbers, etc.

A set which does not satisfy the conditions of the theorem is the set $S = \lbrace q + \alpha \mid q \in \mathbb{Q}\rbrace$ of rational numbers translated by a non-computable number $\alpha$. Exercise: is $S$ decidable?


Introductory notes on parallelization, in particular patterns of problems and algorithms

If you do not want to delve into the gory details, a very good introduction to parallelization design patterns is provided by the book Patterns for Parallel Programming by Mattson, Sanders and Massingill.

You will find general, widely applicable solutions to parallelization and even a brief introduction to both  OpenMP and MPI. The book starts by introducing design patterns and concurrency. Then, the authors proceed to illustrate how to exploit the concurrency, how to structure the algorithm, and how to actually implement the algorithm taking into account synchronization and communication.

Again, this is not a textbook on parallel algorithms. It does a very good job of presenting materials strictly related to parallel software engineering, with both a practical and theoretical focus. Therefore, it should suit perfectly your needs.


Test set and benchmarks for linear programming

The standard reference is probably Hans Mittelmann's page. Note, however, that the number of simplex iterations performed will depend on the pivoting rule and how the code deals with degeneracy.


Count satisfying assignments of CNF formulas over all possible negation assignments

The quantity $\sum_k|\phi_k|$ can be computed in polynomial time, in fact, in uniform $\mathrm{TC}^0$. By double counting, we have
$$\sum_k|\phi_k|=|\{(a,k):a\models\phi_k\}|=\sum_{a\in\{0,1\}^n}|\{k:a\models\phi_k\}|.$$
Now, if $a\in\{0,1\}^n$ is any assignment, and $C$ a clause in $l$ literals, then there are exactly $2^l-1$ ways how to negate the literals in $C$ so that it is satisfied by $a$: the unique unsatisfied instance is the one where every literal is negated or not opposite to what $a$ says. Moreover, for a CNF $C_1\land\dots\land C_m$, we choose the negations of literals of each clause $C_j$ independently, and the whole formula is satisfied iff each $C_j$ is satisfied, hence irrespective of $a$ and of the structure of the formula,
$$|\{k:a\models\phi_k\}|=\prod_{j=1}^m(2^{l_j}-1),$$
hence
$$\sum_k|\phi_k|=2^n\prod_{j=1}^m(2^{l_j}-1).$$


Maximize quadratic function subject to linear constraints

It's NP-hard.

Here's a reduction from the feasibility version of Binary Integer Programming (BIP), which is NP-hard. The problem is to decide if there's a feasible solution to the constraints $Ax \leq b$ and $x_i \in \{0,1\}$. It's easy to convert this to a problem with the constraints $Ax \leq b$ and $x_i \in \{-1,1\}$.

Now consider the following optimization problem:
$\max \sum_i x_i^2$ subject to the constraints $Ax \leq b$ and $-1 \leq x_i \leq 1$ for all $i$.

This problem has objective value $n$ (the total number of variables $x_i$) if and only if the original BIP problem was feasible.


Almost universal string hashing in $Z_{2^n}$ and sublinear space

Yes. Wegman and Carter's "New hash functions and their use in authentication and set equality" (mirror) shows a scheme meeting the requirements stated (almost universal, over $\mathbb{Z}_{2^b}$, sublinear space and randomness, linear evaluation time) based on a small number of hash functions drawn from a strongly universal family.

This is sometimes called "tree hashing", and it is used in "Badger - A Fast and Provably Secure MAC" by Boesgaard et al.


What are examples of how non-uniformity can be useful?

An example I like is the argument that $\mathrm{NE\subseteq coNE}/(n+1)$ by counting strings in the language (see e.g. https://blog.computationalcomplexity.org/2004/01/little-theorem.html).


Algorithm for finding the largest subgraph without a directed triangle

The problem of finding a maximum set with no induced directed triangles is NP-complete via a reduction from maximum independent set.

Let G=(V,E) be an undirected graph and k be an integer, for which we wish to know whether there is an independent set of at least k vertices. Let |V|=n. From G construct a directed graph G'=(V',A'), where V' consists of the disjoint union of V and n additional vertices. For each undirected edge in G create two directed edges between the same vertices in G'. In addition, connect each of the n additional vertices in G' by edges in both directions to the vertices in V, but do not add edges between any two of the n additional vertices.

Then, a triangle-free set of vertices in G' consists either of a subset of V only (with at most n vertices) or it contains some vertices in the set of additional vertices together with an independent set of vertices in G. Therefore, there exists a triangle-free set of size n+k in G' iff there exists an independent set of size k in G.

However, this reduction produces many 2-cycles, so it leaves open the possibility that the problem might be easier in the case that the input graph has no 2-cycles, which you say is the case for your inputs. Unfortunately this special case is still hard: a more complicated reduction based on the same idea shows that the problem remains NP-complete even for 2-cycle-free graphs. In the more complicated reduction, add mn additional vertices rather than simply n. Replace each undirected edge in G by a directed edge, oriented arbitrarily. For each directed edge uv connecting two vertices of V, make n additional vertices in V', each of them connected to u and v to form a directed triangle. Then the resulting graph has mn+k vertices in a triangle-free set iff the original graph has k vertices in an independent set.


Complexity of the inverse modulo a composite number

Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r < b$ (and all of $a,b,q,r$ nonnegative integers) the Remainder function. This function cannot be computed at all using only ring operations in the integers: any function that can be computed using only ring operations is a polynomial of its inputs, so if the Remainder function could be computed using only ring operations, it would follow that $Remainder(a,b) = f(a,b)$ for some integer polynomial $f$. For any fixed $b > 1$, the function $g(x) = f(x,b)$ would then be a univariate polynomial. Now, $g(b+1) = 1$, so $g(x)$ is not identically zero; but $g(x) = 0$ whenever $b | x$, so $g(x)$ has infinitely many zeroes, a contradiction.

However, if you allow $<$ in addition to ring operations, then the Remainder function can be computed in polynomially many steps (in the number of bits of the input) as follows: start with $q=1$ and check if $qb > a$ (if so, then the remainder is just $a$). Otherwise, multiply $q$ by $2$ repeatedly until $qb > a$. Then do binary search on $q$ to find $q$ such that $qb \leq a$ and $(q+1)b > a$, and finally output $a - bq$. This takes $O(\log (a/b))$ ring operations and comparisons; on most standard Boolean models of computation each such operation can be done in nearly $O(\log a)$ time.


"Largest" class properly contained in PSPACE for a random oracle

Yes, because $PP^{PH}=PP$ relative to a random oracle. Follows from Toda-Ogihara


Is there a linear space lower bound for streaming set equality?

There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and check-outs in the other, but that makes little difference) in my paper

Space-efficient straggler identification in round-trip data streams via Newton's identitities and invertible Bloom filters.
D. Eppstein, and M. T. Goodrich.
arXiv:0704.3313.
IEEE Trans. Knowledge and Data Engineering 23 (2): 297–306, 2011.
(and WADS 2007).

See also:

What's the difference? Efficient set reconciliation without prior context.
D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese.
Proc. ACM SIGCOMM, Toronto, Canada, 2011.

which is more explicitly about comparing two sets.

In short: you can test whether two multisets (or sets with no repetitions) are the same using only very small space, or more generally find their symmetric difference in space roughly proportional to the size of the difference.

If you really mean sets, where repetitions are allowed, I think the problem may be much harder, though I don't know of a randomized lower bound for it.


The complexity of the dominating set problem in specific subclasses of chordal graphs

Too bad you have been waiting so long without getting any answer.
I don't know for the classes you asked for, but I know some related graph classes and new techniques you can try.

First I will mention that Steven Chaplick has done work on related graph classes, he finished his thesis earlier this year, you might find his research interesting.

I know some results in this direction follow from my own work
Graph Classes with Structured Neighbourhoods and Algorithmic Applications
This gives a general technique for solving various problems including DSP in certain graph classes.
We do this by introducing new graph decompositions (see my thesis).

For instance if we are give an intersection model of UP where the tree has max degree d and the paths have max length s we can solve dominating set in $(d-1)^{3(s-1)}poly(n)$.

Similar if we have a graph given with an intersection model consisting of $0$-bend paths in a $k \times n$ grid (for constant k).

The same technique might work for CEPT arising form a host tree of maximum degree 3, but I need some more time to understand this class.
If you have a link to some characterizations of this class that would help.


1) I think this depends on the implementation of linear GP you use. Since you're writing your own implementation, I would recommend looking at some other people's implementations. IMO, this really depends on what kind of linear GP system you wrote/are using. I haven't looked myself, but ECJ might have an implementation that you can reference.

2) There are TONS of methods to crossover/mutate your individuals. I would argue that you could perform crossover using either of the approaches you mention. The one you should use will depend on the problem you're tackling and how you represent your individuals. Sometimes it's best to design crossover and mutation methods specifically for your system. A Google Scholar search for various mutation and crossover operations in GP, GAs, and linear GP will give you A LOT to work with.

3) Time series forecasting is a particularly difficult problem. In my very limited experience, economic data can be pretty volatile. Using a standard linear GP algorithm probably won't give you especially good results. With a problem that difficult, you're going to need more advanced approaches than just different crossover/mutation operators. It might be worth your time to look into some probabilistic, generalization, or strongly-typed GP approaches. Check out the Field Guide to GP for some more on those. Again, Google Scholar is a great resource for learning more about those.

I hope this helps!


Hardness of approximation assuming the existence of one-way functions

The problem of learning in the PAC model is really just a problem of combinatorial optimization: with a large enough sample size, finding a function $f \in C$ which has low prediction error is equivalent to finding a function $f \in C$ which best classifies some finite sample from the distribution.

In this area, there are plenty of hardness of approximation results that depend on the existence of one-way functions. For example,
"Cryptographic Hardness of Distribution Specific Learning" -- Kharitonov, http://portal.acm.org/citation.cfm?id=167197

"Cryptographic limitations on learning Boolean formulae and finite automata" -- Kearns, http://portal.acm.org/citation.cfm?id=174647&dl=GUIDE,

and many more recent results.


Is $UP\not=NP$ with respect to random oracle?

Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the Complexity Zoo for questions like this...


Just to get things going, rather than trying to close out this problem: there is an obvious nondeterministic algorithm using logarithmically many bits of space (search for a single path through the dynamic programming matrix) so by Savitch's theorem there is a deterministic algorithm with space $O(\log^2 n)$. Its time must be of the form $n^{O(\log n)}$, quasi-polynomial rather than exponential.

There are some space lower bounds for edit distance in http://arxiv.org/abs/1106.4412 but I don't think they match your version of the problem.


Maximum cliques of the transitive closure of a chordal DAG

I think you can extend Vinicius dos Santos' idea to show that no polynomial bound is possible.
Consider a graph on $n$ vertices divided into $d\geq 1$ groups of size about $n/d$ as follows:

Its transitive closure has about $(\frac{n}{d})^d$ maximal (undirected) cliques.


If in fact DSPACE(n) = E, then a padding argument would translate this to PSPACE=EXP.
Similarly, if DSPACE(n) $\neq$ E then a padding argument would translate this to L $\neq$ P.


Fixed Point Logic $+$ Counting (FPC) is believed to capture most of the $P$ solvable problems. Anderson, Dawar and Holm 2015 [1]showed that optimization of linear programs is expressible in FPC. Dawar and Wang 2016 [2]showed that The FPC implementation of the ellipsoid method extends to semidefinite programs (subject to some technical conditions).