Is this partition problem strongly NP-complete?

Your problem can be reduced to the Partition problem (which is weakly NP-complete) without an exponential blowup of the numeric values; so your problem is weakly NP-complete, too.

This is the idea: you can view the $2N$ integers as nodes of a graph $G$, the pairs in $P$ indentify the edges between the nodes.

Clearly $G$ cannot contain cycles of odd length (checkable in polynomial time); otherwise there would be a conflict and at least one element should be excluded from the partition $A$ vs $S \setminus A$.

Each connected part $H_i$ of $G$ is bipartite $H_i = H_i' \cup H_i''$, and you can treat it like a single integer $h_i = | \sum  H_i' - \sum H_i''|$

Let $w_i$ be the difference between the number of elements in the greatest side and the number of elements in the smallest side of the bipartite component $H_i$ plus $N$:

$w_i = N + |H_i'| - |H_i''|$ if $\sum  H_i' > \sum H_i''$;

$w_i = N + |H_i''| - |H_i'|$ otherwise.

Let $a_1,a_2,...,a_m$ be the "isolated" integers.

Let $k$ be the minimum value such that $2^k > \sum h_i + \sum a_j$.

We finally build a Partition problem with the elements:

$B = \{ a_j + 2^k (N + 1) \} \cup \{ h_i + 2^k w_i \}$

It is not hard to show that $B$ has a partition $B = B_1 \cup B_2$, $\sum \{B_1\} = \sum \{B_2\}$ if and only if the original $S$ can be split into two equal size halves having the same sum and such that no pair in $P$ have both elements in the same side.

Very informally: if $h_i$ is placed on one side, it also carries the $w_i$ (positive) "weight" that keeps track of the (absolute) difference between the number of elements of $H_i'$ and $H_i''$; so on the opposite side both the sum and the weight must be "balanced" and this ensures that a solution leads to a valid equal size partition also on the original problem. In the original problem we can derive $A$ from $B_1$: if $h_i$ (or $a_j$) is placed on $B_1$ then the integer nodes of the bipartite component $H_i$ must be arranged in such  a way that $A$ recieves the elements from $H_i'$ or $H_i''$ according to which have the greater sum.

A simple example: given the integers: $1,1,2,3,4,7$ and the pairs $(7,2), (7,3)$, we build the following graph $G$:

We then reduce the connected component to a single number $(2,-1)$ (for better clarity we use the notation $(x,y)$ instead of $x + 2^k (N + y ))$; and solve the corresponding partition problem.

You can also apply the Partition problem pseudo-polynomial time dynamic programming algorithm  to the set $B$ to find the solution.


Is the lower bound proof in this paper correct?

I get the same answer as you, $\frac{1+\sqrt{2}}{\sqrt{\pi}}$.

If I place two unit disks inside a larger square, their centers are one unit away from the left and right sides, and $\sqrt{2}$ units apart from each other in $x$-coordinates, so the side of the larger square is $2+\sqrt 2$. The unit disks have area $\pi$, and we want area $\frac{1}{2}$, so dividing the side length and the disk radius by $\sqrt{2\pi}$ gives the result.


Can someone suggest a recent survey on product form Markov chains?

There is this unpublished book by Aldous and Fill, two experts in the field. You'll find walks on product of chains there.


Extensional type theory and function extensionality

Yes, equality reflection and $\eta$-rule for functions together imply function extensionality.

Recall that equality reflection is the rule
$$\frac{\vdash p : \mathsf{Id}_A(a,b)}{\vdash a \equiv b : A}$$
Suppose $A$ is a type, $x : A \vdash B(x)$ is a type over $A$, and $f, g : \prod_{x : A} B(x)$. We claim that function extensionality
$$\textstyle (\prod_{x:A} \mathsf{Id}(f x, g x)) \to \mathsf{Id}(f, g)$$
is inhabited by $\lambda r \,.\, \mathsf{refl} f$. Indeed, suppose $r : \prod_{x:A} \mathsf{Id}(f x, g x)$. We have $$y : A \vdash r y : \mathsf{Id}(f y, g y),$$ therefore by equality reflection $$y : A \vdash f y \equiv g y : B(y).$$ Now it follows that $$(\lambda y : A . f y) \equiv (\lambda y . g y) : \textstyle\prod_{x : A} B(x)$$
By $\eta$-rule for functions (it does not matter whether this is propostional or judgemental $\eta$, thanks to equality reflection) we get
$$f \equiv (\lambda y . f y) \equiv (\lambda y . g y) \equiv g : \textstyle\prod_{x : A} B(x)$$
Because $f$ and $g$ are judgmentally equal, $\mathsf{refl}\,f$ indeed has the type $\mathsf{Id}(f,g)$.


How to make the Lambda Calculus strong normalizing without a type system?

I can think of a few possible answers coming from linear logic.

The simplest one is the affine lambda-calculus: consider only lambda-terms in which every variable appears at most once.  This condition is preserved by reduction and it is immediate to see that the size of affine terms strictly decreases with each reduction step.  Therefore, the untyped affine lambda-calculus is strongly normalizing.

More interesting examples (in terms of expressiveness) are given by the so-called "light" lambda-calculi, arising from the subsystems of linear logic introduced by Girard in "Light Linear Logic" (Information and Computation 143, 1998), as well as Lafont's "Soft Linear Logic" (Theoretical Computer Science 318, 2004).  There are several such calculi in the literature, perhaps a good reference is Terui's "Light affine lambda calculus and polynomial time strong normalization" (Archive for Mathematical Logic 46, 2007).  In that paper, Terui defines a lambda-calculus derived from light affine logic and proves a strong normalization result for it.  Even though types are mentioned in the paper, they are not used in the normalization proof.  They are useful for a neat formulation of the main property of the light affine lambda-calculus, namely that the terms of a certain type represent exactly the Polytime functions.  Similar results are known for elementary computation, using other "light" lambda-calculi (Terui's paper contains further references).

As a side note, it is interesting to observe that, in proof-theoretic terms, the affine lambda-calculus corresponds to intuitionistic logic without the contraction rule.  Grishin observed (before linear logic was introduced) that, in the absence of contraction, naive set theory (i.e., with unrestricted comprehension) is consistent (i.e., Russel's paradox does not give a contradiction).  The reason is that cut-elimination for naive set-theory without contraction may be proved by a straightforward size-decreasing argument (as the one I gave above) which does not rely on the complexity of formulas.  Via the Curry-Howard correspondence, this is exactly the normalization of the untyped affine lambda-calculus.  It is by translating Russel's paradox in linear logic and by "tweaking" the exponential modalities so that no contradiction could be derived that Girard came up with light linear logic.  As I mentioned above, in computational terms light linear logic gives a characterization of the polynomial-time computable functions.  In proof-theoretic terms, a consistent naive set theory may be defined in light linear logic such that the provably total functions are exactly the polynomial-time computable functions (there is another paper by Terui on this, "Light affine set theory: A naive set theory of polynomial time",
Studia Logica 77, 2004).


Minimal set of Hyperrectangles covering an n-dimensional binary matrix with row permutations

If "n-partitioned hypergraphs" are defined as "hypergraphs together with a partition of their vertices into n subsets such that each hyperedge has only one vertex from each of those subsets" then your problem can be reformulated as  n-clique hyperdge-cover for n-uniform

n-partitioned hypergraphs, and that reformulation preserves approximations and the parameter

(when your problem is parametrized by number of hyperrectangles).

In particular, your problem is NP-hard to approximate, even for n=2.

Those problems are equivalent to:

Find [the assignment of one positive integer to each '1' in the matrix] such that with

C being the largest of those positive integers, [for all elements H of {1,2,3,...,C-1,C}

and all '0's in the matrix, there is a coordinate such that no '1' [with the

same value for that coordinate as the '0'] was assigned H], which minimizes C.

Thus, your problem can be solved in

((minimum_number_of_hyperrectangles)^(number_of_'1's)) * poly(input_size)

time with an embarassingly parallel workload.

Aside from the reformulation and the equivalent problem I mentioned,

I don't know of any problems that your problem is reducible to for any reason

other than your problem being in NPO and the other problem being NPO-hard.


What is known about solutions to sparse integer linear programming problems?

The answer to this (at least to the concrete question about linearly bounding the solution) is no.  This is part of the following paper: http://arxiv.org/abs/1011.3493.  Theorem 5.1 was the motivation for this question.

The counterexample is this:

base case:

a_1'  + b_1'  - t ≥ 0
a_1'' + b_1'' - t ≥ 0
a_1   + b_1'  - t ≤ -1
a_1 ' + b_1'' - t ≤ -1

recursive case:

a_n'  + b_n'  + a_{n-1}   - t ≥ 0
a_n'' + b_n'' + a_{n-1}   - t ≥ 0
a_n   + b_n'  + a_{n-1}'' - t ≤ -1
a_n'  + b_n'  + a_{n-1}'' - t ≤ -1

along with requiring them all to be nonnegative.

You can prove by induction that any real solution must satisfy a_n'' >= a_n + 2^n.  We change the "< 0"-inequalities into "≤ -1" because any integer solution satisfies "≤ -1" if and only if it satisfies "< 0".

So, the moral is that n inequalities of this form can have the property that all integer solutions have at least one integer at least exponential in n, certainly not linearly bounded as we originally suspected.


Crown Rule Reduction In Parameterized Complexity - Vertex Cover - Notion Question

I agree with the OP: $\mathcal{G} - \mathcal{C} = \mathcal{G}'$.

I assume the author of the paper wanted to define $\mathcal{G}'$ as $\mathcal{G} - S_{\mathcal{C}}$. With this modification, the next sentence in the paper makes sense:

  One can easily see that $\#vc(\mathcal{G}',k-|S_{\mathcal{C}}|)$ equals the number of size $k$ vertex covers $S$ in $\mathcal{G}$ with $S \supseteq S_{\mathcal{C}}$.

Here, $\#vc(\mathcal{G},k)$ denotes the number of size $k$ vertex covers in $\mathcal{G}$.


How can a problem be in NP, be NP-hard and not NP-complete?

It seems the issue is the kind of reductions used for each of them, and they are using different ones: they probably mean "$\mathsf{NP}$-hard w.r.t. Cook reductions" and "$\mathsf{NP}$-complete w.r.t. Karp reductions".

Sometimes people use the Cook reduction version of $\mathsf{NP}$-hardness because it is applicable to more general computational problems (not just decision problems). Although the original definition of both $\mathsf{NP}$-hardness and $\mathsf{NP}$-completeness used Cook reductions (polynomial-time Turing reductions) it has become uncommon to use Cook reductions for $\mathsf{NP}$-completeness (unless it is stated explicitly). I don't recall any recent paper that has used $\mathsf{NP}$-complete to mean $\mathsf{NP}$-complete w.r.t. Cook reductions. (As a side note the first problem that to be proven to $\mathsf{NP}$-hard was TAUT not SAT and the completeness for SAT is implicit in that proof.)

Now if you look at section 7 of the paper, bottom of page 195, you will see that they mean $\mathsf{NP}$-hardness w.r.t. Turing reductions.

So what they mean here is that the problem is in $\mathsf{NP}$, is hard for $\mathsf{NP}$ w.r.t. Cook reductions, but it is unknown to be hard for $\mathsf{NP}$ w.r.t. Karp reductions (polynomial-time many-one reductions).


Quasi-polynomial time algorithm for permutation group isomorphism

The answer is basically yes, if we take into account the hidden assumption that the degree of the group is at most $n$. More precisely, let $G_1, G_2$ with $|G_1|=| G_2|=n$ be finite permutation groups acting on a set $\Omega$. Then existence of a permutational isomorphism between $G_1$ and $G_2$ can be checked in time $n^{\log_2 n} \cdot {\max(|\Omega|,n)}^{O(1)}$.

As suggested in the question, a permutation group has a base and corresponding strong generating set (SGS) of size at most $\log_2 n$, and both can be computed in time polynomial in $n$. But this isn't even needed, any generating set of size at most $\log_2 n$ is enough.

After computing such a generating set for $G_1$, the algorithm simply maps successively each element of the generating set to an element of $G_2$, and checks for each such mapping whether it leads to an isomorphism of $G_1$ and $G_2$. For those who do, the algorithm then checks whether there is a permutation of $\Omega$ inducing that isomorphism (for example by a canonical labeling technique, which is closely related to a similar technique for deterministic finite automata, but more group theoretic methods also work). Those checks can be done in time ${\max(|\Omega|,n)}^{O(1)}$, and because there are at most $n^{\log_2 n}$ such mappings, and every isomorphism between $G_1$ and $G_2$ is determined by such a mapping, the above time bound follows.


One line of work has shown how to improve the analysis of the classic INW PRG for the special cases of fooling regular and permutation branching programs. The seed length is only $\widetilde{O}(\log n)$ or $O(\log n)$ in some cases. [LRTV09] [BV10] [De11] [KNP11] [Ste12] [BRRY14] [HPV21]
Another line of work has developed a PRG framework based on iterated pseudorandom restrictions. This framework has been used to fool various classes of functions that can be computed by "arbitrary-order" read-once branching programs. Again, in some cases the seed length is $\widetilde{O}(\log n)$ or even $O(\log n)$. [GMRTV12] [GLS12] [RSV13] [CSV15] [SVW17] [CHRT18] [HLV18] [FK18] [MRT19] [DHH19] [Lee19] [LV20] [DHH20] [DMRTV21]
The paper referenced in the original question is part of a line of work that uses spectral techniques to design graph algorithms for space-bounded derandomization. That line of work, which most famously includes Reingold's algorithm for undirected connectivity, has continued. Recently the focus has been on simulating random walks of length much less than the mixing time of the graph. [CRV11] [MRSV17] [MRSV19] [AKMPSV20]
Finally, there is a line of work designing improved low-error generalized PRGs for polynomial-width read-once branching programs. By "generalized PRGs," I am referring to (a) hitting set generators and (b) weighted pseudorandom generators, aka pseudorandom pseudodistribution generators. [BCG20] [HZ20] [CL20] [CDRSTS21] [PV21] [Hoz21]

Please forgive me for inevitably omitting many excellent papers from this summary, including lots of work that doesn't fit neatly into the four themes above.
See also: Reingold's two-part presentation "Recent Developments Related to RL vs. L" at the DIMACS Day of Complexity Tutorials prior to CCC 2019, and the STOC 2020 workshop "Derandomizing Space-Bounded Computation" organized by Meka, Tal, and Zuckerman.


Extending Hindley-Milner to type mutable references

To get behaviour similar to Ocaml, simply avoid generalizing the type of mutable variables.

With ordinary let-bindings, you generalize if you bind a value, and don't generalize otherwise. With mutable variable bindings, you never generalize.

The standard ML-like behaviour is then:

let xs = []          // xs : forall a. list a

let as = 1 :: xs     // as : list int   -- instantiate a to int
let bs = true :: xs  // bs : list bool  -- instantiate a to bool

The mutable variable typing will go:

let mut xs = []     // xs : list ?a  -- a is an unification variable

let as = 1 :: xs    // as : list int  AND ALSO
                    // xs : list int, since ?a gets resolved to int
let bs = true :: xs // TYPE ERROR, since xs : list int


Term for a correspondence of two point sets regarding their ordering in each dimension

Associate with $S$ and $S'$ the posets $P = (\leq, S)$ and $P' = (\leq, S')$, where $\leq$ is the dominance order in $\mathbb{R}^d$. The function you describe is an isomorphism between $P$ and $P'$.


Generating "infinite" randomness from a constant number of sources

This is a great question, Suresh!

Our randomness expansion result does not imply any complexity theoretic result. Here's one way to understand the result: we believe that quantum mechanics governs the world, and under this assumption, there are quantum devices that generate genuine, true, information-theoretic randomness.

However, imagine that you're mistrustful of these boxes that claim to do this wonky quantum stuff and generate randomness (for some, this may not take too much imagining). You don't want to deal with qubits. All you understand are classical bit strings.

Randomness expansion is a protocol where you, as a classical verifier, can interact with a bunch of black boxes (think of them as non-communicating provers), and after running a protocol with these black boxes, you've certified that their outputs contain very high entropy -- if the provers pass. Furthermore, the amount of randomness you started with is much less than the output entropy you certified.

In other words, it's an interactive proof for randomness generation.

So, the only "derandomization" aspect of it is to argue that the protocol itself requires small startup randomness. But the outcome is very un-derandomized: the output produced by the boxes is true randomness, not pseudorandomness (i.e. no computational assumptions).


The wikipedia page for ISWIM says that it is a higher-order language, and that ISWIM is syntactic sugar for the $\lambda$-calculus.

Although it seems to have no explicit $\lambda$ construct, thereby making it impossible to have anonymous functions, one achieves the same expressive power by combining lexical scoping and first-class functions: Define a new name  for a function locally; pass function as value to higher-order function.


Is ALogTime != PH hard to prove (and unknown)?

Not sure why Fortnow says there's "no meaningful model where $L$ and $NP$ collapse"... it seems to me that QBF should make them collapse, under the usual Ruzzo-Simon-Tompa oracle model (and the link you included agrees). Note this oracle model also has its quirks: we have $L = NL$ if and only if $L^A = NL^A$ for every oracle $A$, so any oracle witnessing a separation would imply the unrelativized separation.

ALogTime = LOGTIME-Uniform $NC1$. So yes, $ALogTime = NP$ is open. There is a relativized notion of uniform $NC1$, and you can collapse $NP$ and $NC1$ under that notion. See Theorem 6 in http://link.springer.com/article/10.1007/BF01692056.
(A caveat: technically speaking, that paper considers LOGSPACE-uniform NC1, but I believe some reasonable version of that oracle construction should work in the LOGTIME-uniform setting.)

Beyond that, I know of no particular reason to believe it is "hard to prove" other than the observation that many people have tried and none have succeeded yet.


Is it easy to "fit a wrapped chain in a graph"?

Allow me to try to redeem my previous incorrect answer with an attempt at showing that this problem is NP-complete via a reduction from GRAPH 3-COLORABILITY. The key idea is to identify SEQ as a list of edges of some graph and observe that a "relaxed node assignment" corresponds to a graph homomorphism.

Let $H = (U, E)$ be a connected, undirected graph with $U = \{u_1, u_2, \ldots, u_n\}$. Let $P = (u_{a_1}, u_{a_2}, \ldots, u_{a_p})$ be a (non-simple) path in $H$ that traverses every edge at least once (i.e.: if there is an edge between $u_i$ and $u_j$, then they appear consecutively in $P$ in either order). First, we need to show that $P$ is not too long. We can construct $P$ as follows:

Start at $u_1$.
Visit each neighbor of $u_1$, returning to $u_1$ after each visit. I.e., if the neighbors of $u_1$ are $u_{n_1}, u_{n_2}, \ldots, u_{n_d}$, we have the following sequence: $u_1, u_{n_1}, u_1, u_{n_2}, u_1, \dots, u_1, u_{n_d}, u_1$.
Travel to $u_2$.
Visit each neighbor of $u_2$.
etc...

By visiting each vertex's neighbors, each edge in $H$ is traversed. Each neighbor visitation step adds $O(n)$ steps to the path. Each travel to a successive vertex adds another $O(n)$ steps. So, in total length of $P = (u_{a_1}, u_{a_2}, \ldots, u_{a_p})$ is $O(n^2)$.

Let $SEQ = (x_0, x_{a_1}, x_{a_2}, x_{a_3},\ldots,x_{a_p}, x_{n+1})$ be the sequence of variables.

Let $G = (V, A)$ be the complete, directed graph on three vertices adjoined with a universal source and a universal sink. Explicitly, let $V = \{v_1, v_2, v_3, v_{source}, v_{sink}\}$. There is an arc from $v_{source}$ to $v_i$ and from $v_i$ to $v_{sink}$ for $i=1,2,3$. And, for all $i,j = 1,2,3, i \neq j$ there is an arc from $v_i$ to $v_j$.

Finally, we claim that a valid relaxed node assignment from $SEQ$ to $G$ exists iff $H$ is 3-colorable. Let $c:U \rightarrow \{1,2,3\}$ be a 3-coloring of $H$. Let $f:X \rightarrow V$ be defined by:

$f(x_0) = v_{source}$
$f(x_{n+1}) = v_{sink}$
$f(x_i) = v_{c(u_i)}$

It should be clear that $f$ is a valid relaxed node assignment. It should be equally clear that we can reverse this construction to use any valid relaxed node assignment to define a 3-coloring of $H$.


Improving Cook's generic reduction for Clique to SAT?

You can express $k$-clique as a SAT instance with $O(nk)$ variables and $O(nk^2)$ clauses.  For fixed $k$, this is linear in $n$.

Let $x_{iv}=1$ if $v$ is the $i$th vertex in the clique (by lexicographically sorted order).  In other words, $x_i$ is a "one-hot" encoding of the $i$th vertex in the clique (it is the characteristic vector for a set with one element).  This introduces $nk$ variables.

Now for each $(i,j)$ you can enforce that the corresponding two vertices are connected by an edge, using $n$ clauses.  e.g., one clause is $(\neg x_{iu} \lor x_{jv_1} \lor \dots \lor x_{jv_m})$ where $v_1,\dots,v_m$ are the vertices that are adjacent to vertex $u$.  You get one clause per vertex $u$.  This introduces a total of $O(nk^2)$ clauses.

For each $i$, you can enforce that $x_i$ is a vector of Hamming weight 1 and that $x_i < x_{i+1}$, using $O(n)$ clauses.  This adds a total of $O(nk)$ more clauses.

It might be possible to do better by using $k \lg n$ variables to represent the vertices in the clique ($\lg n$ bits suffice to represent the $i$th vertex in the clique) and then building a circuit to check whether a set of $k$ vertices correspond to a clique.  One approach to build such a circuit might be by constructing the list of all $k(k-1)/2$ pairs of these vertices, in sorted order, then comparing that to the list of edges using the Merge procedure from Mergesort, or something like that.  It might be possible to get something like a $O((n+m+k^2) \text{poly}(\lg n))$-size circuit, which then translates to a SAT instance of the same size (where $m = $ the number of edges in the graph).  I haven't tried to work out the details to see whether it's actually possible, though.


What graph properties only consider neighbours of a node in their calculations?

There are several measures like clustering coefficients that sort of satisfy this, such as edge embeddedness. But this looks at the number of neighbours in common to two adjacent nodes.

The property of v being simplicial is an important structural property used in algorithmic graph theory, and is fully characterized by only the neighbourhood of v.

Notice that the two examples you gave are: (1) the number of nodes in v's neighbourhood, and (2) the number of edges in v's neighbourhood. Perhaps You might also be interested in the number of triangles in v's neighbourhood (i.e. the number of K4s that v is in) or perhaps the number of $P_3$s in v's neighbourhood, etc.

Perhaps you could loosen your requirement of locality, or else you will only be asking about properties such as "the number of _ in v's neighbourhood," which might be too limiting.

How about the number of connected components in v's neighbourhood? Something similar to this was used in a recent Kleinberg paper on predicting spouses by looking at Facebook egonets.


The complexity of Area-lawed Hamiltonians

One could consider the following slightly silly example of a 2d system which obeys an area law which is QMA-complete.  Take a 2d system, one row of which is equal to one of the known QMA-complete 1d Hamiltonians (see Aharonov, Gottesman, Irani, Kempe), and all the other rows are in a product state.  Then, this obeys an area law (consider drawing a rectangle which includes the given row, with k rows and l columns; the entanglement is bounded by a constant times l and the area is also at least equal to l).

However, this, in my opinion, certainly doesn't mean that proving an area law in 2d would be pointless from the point of view of complexity.  Rather, I think it means that we need to consider not just the area law for entanglement entropy, but other entanglement properties also.  One such property would be having a PEPS of polynomial bond dimension.  Actually, proving that there is an area law in 2d does not imply having a PEPS of polynomial bond dimension.  The implication in 1d relies on the fact that we can cut the system across various bonds, truncate to a polynomial Schmidt rank across each bond, and bound the error.  This procedure doesn't work in 2d.  So, proving the existence of a PEPS for a gapped system in 2d would be a next step.  My feeling is that proving an area law in 2d would be a good first step to doing that.

In fact, it is well-studied in condensed matter physics that there exist gapless 2d Hamiltonians which obey an area law.  While in 1d, the systems which are described by conformal field theory have a logarithmic behavior of the entanglement entropy, in 2d many critical systems show an area law and then the logs show up in subleading behavior, so the entropy is equal to L + const*log(L)+...  That is, the interesting, universal terms in the entropy are not the leading terms, but the subleading, in such 2d theories.


The function $f$ maps $x$ to the conditional distribution of $Y$ given that $X = x$. This is a "deterministic" function. The expression $f(X)$ is a random variable depending on $X$. When $X = x$, the value of this random variable is $f(X) = f(x)$. In words, the random variable $f(X)$ gives the distribution of $Y$ conditional on the value of $X$.

Given $f(X)$, the variables $X,Y$ become independent. Suppose that $f(X) = \phi$. For each $x$ such that $f(x) = \phi$, the conditional distribution of $Y$ given that $X = x$ is $\phi$, that is, $\Pr[Y = y | X = x] = \phi(y)$. This doesn't depend on the value of $x$ as long as $f(x) = \phi$. In particular, the value of $X$ tells us nothing on $Y$, so the conditional mutual information is zero.


Here was my first attempt at an argument. It was wrong, but I fixed it after the "EDIT:"

If you could efficiently approximately solve the max-cut problem with negative edge weights, couldn't you use that to solve the max-cut problem with positive edge weights?  Start with a max-cut problem you want to solve whose optimal solution is $b$. Now, put a large negative weight edge (with weight $-a$) between $u$ and $v$. The optimum solution of the new problem is $b-a$, so our hypothetical approximation algorithm will get you a solution with maximum cut whose value is at most $(b-a)/2$ worse than optimal. On the original graph, the maximum cut is still at most $(b-a)/2$ worse than optimal. If you choose $a$ close to $b$, this violates the inapproximability result that if P$\neq$NP, you cannot approximate max-cut to better than a $16/17$ factor.

EDIT:

The above algorithm doesn't work because you can't guarantee that $u$ and $v$ are on opposite sides of the cut in the new graph, even if they were originally. I can fix this as follows, though.

Let's assume that we have an approximation algorithm which will give us a cut within a factor of 2 of OPT as long as the sum of all the edge weights are positive.

As above, start with a graph $G$ with all non-negative weights on edges. We'll find a modified graph $G^* $ with some negative weights such that if we can approximate the max cut of $G^* $ within a factor of 2, we can approximate the max cut of $G$ very well.

Choose two vertices $u$ and $v$, and hope that they're on opposite sides of the max cut. (You can repeat this for all possible $v$ to ensure that one try works.) Now, put a large negative weight $-d$ on all edges $(u,x)$ and $(v,x)$ for $x \neq u,v$, and a large positive weight $a$ on edge $(u,v)$. Assume that the optimal cut has weight $OPT$.

A cut with value $c$ in $G$, where vertices $u$ and $v$ are on the same side of the cut, now has value at $c - 2dm$ where $m$ is the number of vertices on the other side of the cut. A cut with $(u,v)$ on opposite sides with original value $c$ now has value $c + a - (n-2)d$. Thus, if we choose $d$ large enough, we can force all cuts with $u$ and $v$ on the same side to have negative value, so if there is any cut with positive value, then the optimal cut in $G^* $ will have $u$ and $v$ on opposite sides. Note that we are adding a fixed weight $(a - (n-2)d)$ to any cut with $u$ and $v$ on opposite sides.

Let $f=(a - (n-2)d)$. Choose $a$ so that $f \approx - 0.98 OPT$ (we'll justify this later). A cut with weight $c$ in $G$ having $u$ and $v$ on opposite sides now becomes a cut with weight $c - 0.98 OPT$. This means the optimal cut in $G^* $ has weight $0.02 OPT$. Our new algorithm finds a cut in $G^* $ with weight at least $0.01 OPT$. This translates into a cut in the original graph $G$ with weight at least $0.99OPT$ (since all cuts in $G^* $ with positive weight separate $u$ and $v$), which is better than the inapproximability result.

There is no problem with choosing $d$ large enough to make any cut with $u$ and $v$ on the same side negative, since we can choose $d$ as large as we want. But how did we choose $a$ so that $f \approx -.99OPT$ when we didn't know $OPT$? We can approximate $OPT$ really well ... if we let $T$ be the sum of the edge weights in $G$, we know $\frac{1}{2}T \leq OPT \leq T$. So we have a fairly narrow range of values for $f$, and we can iterate over $f$ taking all values between $-.49T$ and $-.99T$ at intervals of $0.005T$. For one of these intervals, we are guaranteed that $f \approx -0.98 OPT$, and so one of these iterations is guaranteed to return a good cut.

Finally, we need to check that the new graph has edge weights whose sum is positive. We started with a graph whose edge weights had sum $T$, and added $f$ to the sum of the edge weights. Since $-.99T \leq f \leq -.49T$, we're O.K.


Best book on Simplex Method implementation?

I strongly recommend the paper by Bixby, the "father" of CPLEX, that surveys not only on implementing aspects of the (revised) simplex algorithm: Robert E. Bixby, Solving Real-World Linear Programs: A Decade and More of Progress, Operations Research (50) 2002, 3-15.


If TCS is something you enjoy, and you want to pursue a PhD, I wouldn't let the fear of failure stop you.  You can also mitigate some of the risk by enrolling in a program that awards you a Master's after a year or two -- that way, if you realize research isn't for you, you won't come out "empty-handed".  And if you don't succeed in landing a research job afterwards, as long as you enjoy grad school, it's not a big sunk cost.

To answer your question about "having what it takes" more directly -- I think you need to both have talent and put in the hard work to succeed.  My feeling is that most people who fail to get a PhD, however, fail not because they were not talented enough, but because they weren't disciplined enough.


Mathematical analysis and computational complexity?

Flajolet and Sedgewick published the book "Analytic Combinatorics" http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html.  I don't know much about that topic, but people in the field use tools from complex analysis.  So far, their applications seem more on analysis of algorithms, not on computational complexity, as far as I see.


Relationship between Turing Machine and Lambda calculus?

The lambda calculus is older than Turing's machine model, apparently dating from the period 1928-1929 (Seldin 2006), and was invented to encapsulate the notion of a schematic function that Church needed for a foundational logic he devised.  It was not invented to capture the general notion of computable function, and indeed a weaker typed version would have served his purposes better.

It seems to be incidental to the purpose of that the calculus Church invented turned out to be Turing complete, although later Church used the lambda calculus as his foundation for what he called the effectively computable functions (1936), which Turing appealed to in his paper.

Church's simple theory of types (1940) provides a more moderate, typed theory of functions that suffices to express the syntax of higher-order logic but does not express all recursive functions.  This theory can be seen as being more in tune with Church's original motivation.

References

Church (1936).  An unsolvable problem in elementary number theory.  American Journal of Mathematics 58:345—363.
Church (1940).  A formulation of the simple theory of types.  Journal of Symbolic Logic 5(2):56—68.
Seldin (2006). The logic of Curry and Church.  In Handbook of the History of Logic, vol.5: Logic from Russell to Church, p. 819—874.  North-Holland: Amsterdam.

Note This answer is substantially revised due to objections by Kaveh and Sasho.  I recommend the Wikipedia timeline that Kaveh suggested, History of the Church–Turing thesis, which has some choice quotes from seminal articles.


Why is differential privacy defined over the exponential function?

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties:

Composition: If $A(\cdot)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ A$, defined by $A'\circ A(D) = A'(D, A(D))$, is $(\varepsilon + \varepsilon')$-DP.
Group Privacy: If $A$ is $\varepsilon$-DP, then it satisfies $k\varepsilon$-DP on pairs of data sets that differ in at most $k$ data points.

It may be more natural to define $\varepsilon$-DP with $(1+\varepsilon)$ in place of $e^\varepsilon$, but then the formulas above would be far less nice. There is no real connection with Chernoff bounds here.

Another reason is that this definition makes it more clear how the differential privacy definition is related to divergences between distributions. To see what I mean, let me define the privacy loss of an output $a$ of an algorithm $A$ (with respect to datasets $D$ and $D'$) as
$$
\ell_{D, D'}(a) = \log\left( \frac{\Pr[A(D) = a]}{\Pr[A(D') = a]}\right).
$$
Then, the expectation $\mathbb{E}[\ell_{D, D'}(A(D))]$ is simply the KL-divergence between $A(D)$ and $A(D')$. The differential privacy condition asks that this KL-divergence is bounded by $\varepsilon$, but in fact it asks much more: that the random variable $\ell_{D, D'}(A(D))$ is bounded by $\varepsilon$ everywhere in its support. There are also intermediate definitions which put bounds on moments of $\ell_{D, D'}(A(D))$, and correspond to bounding Renyi divergences between $A(D)$ and $A(D')$.


Finding min-max vertex-disjoint paths with a common source on planar graphs

This is not exactly what you asked, but the problem is NP-complete if k is not a constant but part of the input.

This follows from the proof of Theorem 1 in van der Holst and de Pina [HP02], which says: given a planar graph G, distinct vertices s and t in G, and positive integers k and b, it is NP-complete to decide whether there are k pairwise internally vertex-disjoint paths between s and t each of length at most b.

Note that the problem in the statement of Theorem 1 is different from yours in two respects.  One difference is, as I mentioned, that k is given as part of the input.  The other is that the problem in [HP02] is about paths with common endpoints instead of paths with a common source and different sinks.  I do not know how to fix the first difference; the difference is so large that it is likely that we will need a completely different proof to fix k.  But I know at least how to fix the second difference.

The proof of Theorem 1 in [HP02] gives a reduction from 3SAT.  This reduction has the following property: in the instance (G, s, t, k, b) constructed by the reduction, the degree of vertex t is always equal to k.  Let t1, …, tk be the k neighbors of t.  Then instead of asking whether there are k pairwise internally vertex-disjoint paths between s and t each of length at most b, we can equally ask whether there are pairwise vertex-disjoint-except-source paths P1, …, Pk such that each Pi is a path between s and ti of length at most b−1.

[HP02] H. van der Holst and J. C. de Pina.  Length-bounded disjoint paths in planar graphs.  Discrete Applied Mathematics, 120(1–3):251–261, Aug. 2002.  http://dx.doi.org/10.1016/S0166-218X%2801%2900294-3


Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$

I don't know a reference, but I think both of these should be doable.

For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A_1}$ and $NP^{A_1}$ from $PP^{A_1}$.  Then you want a second oracle (call it $A_2$) that encodes the solutions to all $PH^{A_1}$ problems, in a "staggered" fashion such that accessing the $k^{th}$ level of the hierarchy requires queries of size (say) $n^k$ (and hence you can only get a constant number of alternations in polynomial time).  This second oracle should cause $P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$.  (Note that $A_2$ is just an "outer" layer, meaning that any queries to $A_2$ can be simulated by $PH^{A_1}$ queries.)  Finally, you'll want to appeal to Yao's and Hastad's $AC^0$ lower bounds (i.e., the switching lemma) to show that a $PH^{A_1}$ machine still can't solve the $MAJORITY$ instances in $A_1$, and therefore $PP^{A_1}$ (and certainly $PP^{A_1,A_2} = PP^{PH^{A_1}}$) remains larger.

For your second oracle, you'll want to construct $B$ in such a way that you need to solve an $NP$ search problem in order to "unlock" a part of the oracle string that then boosts your power up to $PSPACE$.  (Here we exploit the fact that $NP^{PSPACE}$ and $PP^{PSPACE}$ are both $PSPACE$.)  A subtlety is that the secret part of the oracle can't just decide an unrelativized $PSPACE$-complete language: it also needs to provide the answers to $PSPACE$ computations that query $B$ itself.  Fortunately, it's known how to achieve that in stages, avoiding the circularity: basically, you encode the outputs of the $PSPACE^B$ machines that only query $B$ on inputs of size $p(n)$ or less, in a part of $B$ that requires queries of size $>p(n)$ to access, and that's therefore "out of reach" for those machines (but not for other $PSPACE^B$ machines).  Meanwhile, the $P^B$ machines are left "completely in the dark" by all this.


Max cut problem between two connected subgraphs

Here is a straightforward reduction from the max-cut problem:

Take any graph and add two new vertices $u,v$ and connect them to every other vertex with weight 0 and connect them to each other by a very very big weight edge. In an optimal solution to the above problem $u$ is in one partition and $v$ in the other (this also ensures that each part is a connected component), hence an algorithm that solves this problem in the new graph, could solve the max-cut problem in the original graph and vice versa.

P.S: I supposed we can have edge weights as otherwise a similar argument works however instead of adding vertices we add two long paths (each of length $n^2$), for $i\le n$ we connect the $i$'th vertex of the path $P_j$ (for $j\in \{0,1\}$) to the $i$'th vertex of the graph and we connect all vertices of $P_1$ to the all vertices of $P_2$. Then again in an optimal solution path $P_1$ is on one side and path $P_2$ on the other side.


Is there a simple argument that shows that  the unique games conjecture implies the PCP theorem

It depends a bit how you define the PCP Theorem, is it with perfect completeness or not. As we state in our book, an equivalent form of the PCP Theorem is that there is some constraint satisfaction problem for which it's NP-hard to distinguish between the perfect satisfiable case and the case that one can satisfy at most some fraction $s<1$ of the cosntraints. But, we could have state a variant with imperfect completeness, replacing the perfect satisfiable case with being able to satisfy some fraction $c>s$.

The unique games conjecture is an assumption of this latter form (where, making the condition stronger $c$ is close to $1$ and $s$ is close to $0$) and, most importantly, the constraints are of a very special form (permutation constraints on two variables). In that sense it's (essentially) stronger form of the PCP Theorem.

You can ask if there's an easy transformation to convert a PCP with imperfect completeness to one with perfect completeness. I think it probably can be done easier than proving the PCP Theorem, but I'm not aware at the moment of a very simple argument.


techniques or examples of analyzing a series of graphs

I think your question falls in the context of "graph operators". A graph operator $S$ is just a map from the class of graphs to the class of graphs, and you then have a sequence $G$, $S(G)$, $S^2(G)$, etc.

I do not think that there could possibly be a general way to determine $S^n(G)$ as a function of $n$ and $G$ that could work for all $S$, even for a fixed $S$. For example, if $S(G)$ is the intersection graph of the maximal cliques of $G$ (considered in Harary's book and denoted by $K$), then what you ask is known for only a handful of families, including the complements of $nK_2$, the locally $C_6$ graphs and the so called "clockwork graphs".

Many other graph operators are studied in the book "Graph Dynamics" by Erich Prisner.


How do I get started in theoretical CS ?

Let me provide an answer from the other side. I've had a few undergraduate student researchers work with me. The experience has been mixed: with some, I have published papers and have work in progress, and with others, we never really got off to any kind of start.

It's great that you know what you want to do. As an undergraduate, here's what you should be focusing on:

Building the mathematical "muscles" that will help you when you start working on problems in earnest
Exploring different aspects of theoretical CS to get a sense of the area and figure out what kinds of problems/areas you find interesting
(depending on the area) working out some puzzles, maybe solving some exercises, and working your way up to a research question.

Find a professor to guide you, and PUT IN THE TIME ! The hardest thing you'll face is creating the open time to think about problems in the midst of classwork, assignments and exams. But you need to reserve blocks of time for your independent study and research otherwise it will be very hard to make any kind of progress. How you do this is upto you: maybe you can find a professor to meet with you once a week and set intermediate goals for you, or maybe you can set a long term goal (working through X exercises from a text) and work steadily on that.


Collaborative tools for dummies/professors

First off: If your are interested in real-time collaborative editing, try something like gobby. It lets you literally edit a document at the same time.

As for revision systems, I am only familiar with SVN. This is what you do, after installing subversion, of course:

Get someone to set you up a repository and give you URL, username and password
Go to where you want to have your lokal copy
In a shell (command line?), type: svn co url://to.your/repository (check-out). Now a new folder with the repository's contents appears.

That's all. Now the most basic commands:

Whenever you add a new file foo, enter: svn add foo
Whenever you want to remove a file, enter: svn rm foo
Whenever you have made changes, enter: svn ci (check-in)
Whenever you want to get the newest stuff, enter: svn up (update)

There are also commands for moving, copying, branching, resolving conflicts,  ... but as long as you do not try funny stuff, you are fine with the above. If anything breaks or seems to, backup your edits, delete the whole folder and checkout the whole thing anew. That's for svn like rebooting for Windows.

Addendum: I see you seem to be concerned about "smart merges". I assume that you refer to have to different versions of a file merged, with the assumption that two people added things in disjoint parts of the paper. As far as I know, svn would treat that as a conflict, and probably rightly so. I don't think that there is a general procedure that ensures you get what you want after two people manipulated the same source. There are graphical svn clients that visualise such conflicts and help you resolving them; they are pretty much diff-viewers were you can choose which version to keep for every conflicting line). It will require work, though.


Dealing with duplicates in Genetic Algorithm

What you've hit upon is the basic mechanism that drives GAs -- convergence to some fixed point that you hope is near optimal. In your case, clearly it isn't. So the name of the game is to try and balance this tendency to drive convergence with the competing interest of exploring the space looking for other solutions. There's no silver bullet for this problem -- you always end up tuning things to suit your particular problem.

In general, there are two ways to do this. One is to delay convergence for longer, thus giving the algorithm more time to find better solutions. You can switch to a weaker selection operator (binary tournament selection for example), you can increase your mutation rate, etc. The other option is to allow the algorithm to converge, but figure out a sensible way to restart the search (as you mentioned, putting random points in tends not to work because their fitness is too low to allow them to survive and contribute to the search).

I'll give an example of the latter approach. There is a relatively-little known algorithm called CHC (Eshelman 1991) that tends to work really well for a lot of problems. Unfortunately, one reason it's little-known is that the only way to access the original paper is to buy the printed proceedings of the first FOGA conference, but you can probably find a little bit of information online, hopefully enough to get you started. I can give you something of a quick overview though. In rough pseudocode, CHC looks like

delta = k/4               # k = chromosome length
while not done
    create new child population
    for i = 1 to n/2     # n = population size
        select p1, p2 from population without replacement
        if hamming_distance(p1, p2) > delta
            c1, c2 = HUX crossover(p1, p2)
            insert c1, c2 into child pop
        end if
    end for
    if child pop is empty
        delta = delta - 1
    else
        take best n individuals from union of parent and child populations as next population
    end if
    if delta < 0
        keep one copy of best individual in population
        generate n-1 new population members by flipping 35% of the bits of the best individual
        delta = k/4
    end if

The HUX crossover operator is like uniform crossover, but instead of choosing randomly between the parents independently for each bit, it exchanges precisely half the differing bits from the parents.

You then just keep running this loop until you decide to quit, either because you've found a good enough solution, you've exhausted the amount of time you have to spend on the problem, or whatever other criteria you desire.


Stochastic version of a strongly NP-Complete problem

A first observation is that the stochastic version of an optimization problem will always be at least as hard as the deterministic version, since fixed constant values in an optimization instance are degenerate special cases of random-variable values.

Now to understand the computational complexity of stochastic optimization problems in more detail, it's important first to explicitly define the "order of quantification" for the problem, and also the measure of "success."

Suppose $x = (x_1, x_2, \ldots, , x_n)$ are the variables to be set by the optimizing party, and $r = (r_1, \ldots, r_m)$ are the "stochastic" variables.  For simplicity of discussion, let's assume these variables are all Boolean.  Let $F(x, r): \{0, 1\}^{n + m} \rightarrow [0, 1]$ be the objective function we want to maximize.

The $r_i$'s are going to be set uniformly at random by Nature, let's assume.  But, are these variables set before the optimizer's decision, or after?  Or, are the optimizer's decisions "interlaced" with the random settings?

(I'm assuming that in whatever model we use, the optimizer can at least "see" the random settings that have already been made by Nature.)

The different possibilities described above can be denoted concisely as

(O1)  $[x_1, \ldots, x_n, r_1, \ldots, r_m]$ (optimizer moves first);

(O2)  $[r_1, \ldots, r_m, x_1, \ldots, x_n]$ (nature moves first);

(O3)  $[x_1, r_1, x_2, r_2, \ldots, x_n, r_n, r_{n + 1}, \ldots, r_{m}]$  (alternation; assuming here that $m \geq n$).

So that's the "quantification order" question.  Next, we also have to decide how to measure the "success" of an optimizer's strategy.  There are two simple possibilities:

(S1)  Measure success as the expected output value of $F(x, r)$;

(S2)  Measure success as the probability that $F(x, r)$ meets or exceeds a desired threshold value $\alpha \in [0, 1]$.

To make my life easier, I'm only going to discuss (S1), but most of what I say also applies to (S2).

Finally, we have the issue of what kind of function $F$ is.  There are two fairly general options to consider:

(C1)  $F$ is a general poly-time computable function into $[0, 1]$;

(C2)  $F$ is defined by a collection of local Boolean constraints $\psi_1, \ldots, \psi_\ell$, each acting on $O(1)$ variables in $(x, r)$, and $F(x, r)$ equals the fraction of satisfied constraints.

OK, now having multiplied the number of questions to consider, I can at least answer some of them.  First, if one is asking for extremely accurate information about the achievable success, then the problem becomes ridiculously hard, even if there are no optimization variables!  (i.e., even if x is empty.)  For instance, if $F(r)$ is a SAT instance outputting 0 or 1 according to whether it is satisfied, then (S1) asks us to compute the fraction of accepting inputs, which is $\# P$-complete.  So I think it is more reasonable to settle for a .001-approximation (accurate to within $\pm .001$), or maybe more ambitiously for a $1/n^c$-approximation to the success measure, for each $c > 0$.  Now with these goals in mind:

-For (O1), in which the optimizer sets all the $x$-variables first, the problem is $MA$-complete to .001-approximate, if $F$ is a general Ptime-computable function.  (One has to define completeness for an approximation problem appropriately, and for the promise class $MA$, but morally this is the right complexity classification.)  The proof just follows the definitions.  If $F$ is as in (C2), then the problem is in $NP$, since we can use linearity of expectations to compute the expected value of $F(x, r)$ for any fixed $x$.

-For (O2), in which Nature sets the $r$-variables first, the problem is $AM$-complete to .001-approximate, whether $F$ is as in (C1) or (C2).  For (C1) this follows from an easy black-box application of the Cook's theorem plus the PCP theorem.  For (C2), I showed the $AM$-completeness result in the following paper:

http://eccc.hpi-web.de/report/2010/019/

-For (O3), interlaced variable-settings, the problem is $PSPACE$-complete to .001-approximate, even in the (C2) case; this was shown by Condon, Feigenbaum, Lund, and Shor in this paper:

http://cs-www.cs.yale.edu/homes/jf/CFLS.pdf

Hope this is helpful...


Graph planar drawing, with each edge's length is known

There is considerable work on the problem of finding planar embeddings with specified edge lengths. Survey and some results can be found in $[1]$.

Cabello, S. and Demaine, E.D. and Rote, G., "Planar embeddings of graphs with specified edge lengths," Graph Drawing, 283--294, 2004.


Using decision version of TSP to solve optimization version

I'm not sure if we should be answering such questions, since it is at the level of a homework question, and not a research level question. So instead I'll just give a hint to the OP so the OP can figure out the answer with some effort. (Other posters may choose to give out the explicit solution if they wish, of course.)

The concept you refer to, i.e., reducing the search problem (or optimization problem) to the decision problem, is called self-reducibility. It is known that all NP-complete problems, and some others like Graph Isomorphism have this property. See this powerpoint presentation on self-reducibility. It explains in detail how SAT, GI and NP-complete problems in general can be shown to be self-reducible.

If you read those notes and understand those examples, you should be able to do the same for TSP using similar ideas.  Hope that helps.


$\mathcal{G}_B$ is the bipartite double cover of $\mathcal{G}_A$. So it has twice as many vertices and edges, and if  $\mathcal{G}_A$ has an embedding with $x$ even faces and $y$ odd faces then $\mathcal{G}_B$ has an embedding (possibly on a nonplanar surface) with $2x+y$ faces, formed by making two copies of each even face and replacing each odd face by its double. Therefore, by Euler's formula, when the embedding of $\mathcal{G}_A$ is planar, the genus of $\mathcal{G}_B$ is at most $(y-2)/2$. In particular, if $\mathcal{G}_A$ is already bipartite, $\mathcal{G}_B$ consists of two disjoint copies of $\mathcal{G}_A$, and if $\mathcal{G}_A$ has only two odd faces then $\mathcal{G}_B$ will still be planar.

This is not a complete characterization: It might also be possible for $\mathcal{G}_B$ to be planar in some other cases, by using a different embedding from the one derived from $\mathcal{G}_A$. For instance, if $\mathcal{G}_A=K_4$, then $\mathcal{G}_B$ is a cube, and is planar, but the embedding derived from the planar embedding of $\mathcal{G}_A$ is a toroidal embedding of the cube with four hexagonal faces (the four equators of a standard cube) instead of the usual planar embedding with six square faces.

Some planar graphs $\mathcal{G}_A$ will definitely give nonplanar graphs $\mathcal{G}_B$. For instance, if $\mathcal{G}_A$ is the graph of the regular dodecahedron, its bipartite double cover is the cubic symmetric graph on 40 vertices, which is nonplanar. In the other direction, it is also possible for $\mathcal{G}_B$ to be planar even when $\mathcal{G}_A$ is nonplanar; for instance, if $\mathcal{G}_A$ is the nonplanar graph formed from $K_{3,3}$ by subdividing the edges of a 6-cycle, then $\mathcal{G}_B$ is the planar graph of the hexagonal prism (with both of its 6-cycles subdivided in the same way).


Are there analogous works to PPSZ algorithm for #P?

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets
$2^{n(1-1/O(k))}$ time (like PPSZ):
https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf
There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link:
http://tmc.web.engr.illinois.edu/detapsp_soda.pdf
A caveat: this second algorithm uses exponential space. I believe it is open to find a deterministic algorithm with a similar running time and polynomial space. Be sure look on Google scholar for related references too.


Second eigenvalue and the last eigenvalue

Regarding the last eigenvalue:

The last eigenvalue $\lambda_n$ measures (roughly) how close is the graph to be bipartite. For example, $\lambda_n = -d$ if and only if the graph is bipartite (this is a fairly easy exercise). You can read more about it in Luca Trevisan's blog:

http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/

http://lucatrevisan.wordpress.com/2008/09/23/max-cut-gain-and-the-smallest-eigenvalue/


Explaining computer science algorithms/concepts/ideas using metaphors

B-Trees, N-ary Trees, Autocracy and Democracy

http://rkvsraman.blogspot.in/2008/08/b-trees-n-ary-trees-autocracy-and.html


Interval partitioning with restrictions: NP-complete or efficiently solvable?

Here's a reduction from 3SAT. For each of your 3SAT variables $x_0$, imagine there is one event $x_0$ and two rooms called "Room $x_0$ is true" and "Room $x_0$ is false". The event $x_0$ has to be in one of those two rooms. Whichever statement is true, that's the room we don't use. And it is going to take all day. So the only rooms generally available for other events are the rooms named with a true statement.

Now let's say you want to add a condition - $x_0$ OR $x_1$ OR NOT $x_2$. Make that into an event that's just one nanosecond long, at a random time so it doesn't conflict with the other condition-events. And it has to be held in one of "Room $x_0$ is true", "Room $x_1$ is true", or "Room $x_2$ is false".

Now solving your event assignment problem lets you solve an arbitrary 3SAT problem.


What does "hold uniformly" mean in the context of asymptotic analysis?

We say a bound on a family of objects holds uniformity if there is a single bound that applies to all objects in the family, as opposed to a bound that is dependent upon the parameter that determines which element of the family is under discussion.

For example, $f_n(x)= \sin(nx)$ is uniformly bounded by $1$, while $g_n(x)=n\cos(nx)$ is not. In fact, $g_n$ isn’t uniformly bounded by anything, as any bound on it needs to depend on $n$.


Something like this is used in the definition of creative sets by Joseph and Young (1985). See the Wikipedia article on polynomial creativity. But their use is to concoct NP-hard sets with unusual properties (potential counterexamples to the Berman–Hartmanis conjecture rather than to say anything nontrivial about the complexity of any natural algorithmic problem.


Combining multiple time-based datasources with different periods

(not enough rep for comment)
Can you tell us more about the data streams? I am a roboticist, and I often deal with sensors which are outputting data streams at different rates. Specifically, can you please elaborate on the following:

do the data streams have the same modality? (eg, are they all telling you the velocity of something, or is one telling you velocity and the other position, leaving you to infer velocity?)
is either stream noisy and/or can you otherwise get conflicting data from the streams? If so, do you have an error model?

Once I know more about your streams, I will try to suggest some relevant literature.


The relationship between QCMA and QMA in the Turing and Communication model

Consider two complexity classes, say P and NP. To show that a proof that P=NP would need non-relativizing techniques, one has to describe an oracle relative to which the classes are not equal. For this the usual approach is to take an exponential separation between deterministic and non-deterministic query complexity and then use a standard argument to turn this into the oracle separation.

For algebrization one needs the stronger statement that even if the weaker class (here P) is given access to the polynomial extension of the oracle the classes remain different. Aaronson and Wigderson give some direct constructions for that, but the easiest argument is that a separation in communication complexity (e.g. an exponential separation between deterministic and non-deterministic communication complexity) can take the place of the query complexity separation. Compare Theorem 4.11 in the algebrization paper.

Of course many such separations are known (e.g. non-disjointness is easy for non-deterministic protocols but hard for deterministic protocols).
The separation that is left open in our paper is QCMA- vs. QMA-communication complexity (in the two-way model). Giving an exponential separation would immediately imply that any proof that QMA=QCMA (for Turing machines) would need non-algebrizing techniques (of course this inclusion might not be true).

Again, the reasoning here is that an algebrizing proof of QCMA=QMA would (by definiton) also work for the algebraic oracle model (for any oracle) and algorithms in this one could be simulated in the communication complexity model, contradicting a separation result there.


References for the computational complexity of training neural networks

See the papers by Roi Livni and coauthors:

*Roi Livni, Daniel Carmon, Amir Globerson:
Learning Infinite Layer Networks Without the Kernel Trick. ICML 2017: 2198-2207

*Roi Livni, Shai Shalev-Shwartz, Ohad Shamir:
On the Computational Efficiency of Training Neural Networks. NIPS 2014: 855-863


Finding divisors of an interval of integers

Your problem is more or less equivalent to the problem of factoring $N,N+1,\ldots,N+n$. To get from these factorizations to the solution to your problem, simply enumerate the factors. To get from the solution to your problem to the factorization, simply test each factor for primality. In the future you may wish to state this problem in this other form, as it sounds more natural and fundamental that way.

One way to factor these numbers is to simply use a standard factorization algorithm on each one. Note that most numbers have lots of small divisors and therefore are a lot easier to factor than the products of two large primes that need to be factored to break RSA public key cryptography. According to Wikipedia the Lenstra elliptic curve factorization method works well on numbers with small factors and the Quadratic Sieve works well for numbers under 100 digits. I would give those two factorization algorithms a try.

In light of the above I suggest something along the lines of the following algorithm:

Iterate over all numbers X between $N$ and $N+n$. For each such X:

Compute its prime factors as follows:

i. Use trial division by 2,3,5 and 7 to dispose of tiny factors

ii. Run the Lenstra or Quadratic Sieve factorization method to factor what's left.
Use the prime factorization to generate all factors (prime or composite) of X. Insert all of these factors that are between $n$ and $\sqrt{N}$ to your output list.


Connections between Graph Isomorphism and Polynomial Equivalence

The paper you linked in the comments - and references therein - already seems to answer your first question.

For your second question: I have little reason to think that there is a theorem of the form "If GI is in P, then [something about derandomizing PIT]." For example, it is possible that GI is in P, but Polynomial Equivalence is not. (Note that PolyEq and RingIso are relatively close to one another, and RingIso is as hard as integer factoring...)

Note that equivalence problems in general tend to be nontrivially harder than their specific instances or testing for triviality. For example, Formula Isomorphism is believed to be intermediate between the first two levels of $\mathsf{PH}$, although testing isomorphism to the trivial formula is $\mathsf{coNP}$-complete. (This is the Boolean analogue of your suggestion of trying to use PolyEq to solve PIT. Of course, one could argue that our intuition for the intermediate status of Formula Iso is largely based on Graph Iso...) As another example, testing for Knottedness is in $\mathsf{NP} \cap \mathsf{coNP}$ (assuming GRH; albeit only recently), but the current best upper bound on testing Knot Equivalence is that it can be done in time that is a tower of 2's of height $c^n$, where $n$ is the number of crossings and $c = 10^{10^6}$ (see here). Although it is possible that both Knottedness and Knot Equivalence are in $\mathsf{P}$, the latter seems significantly harder than the former.


Under what models do we know linear time sorting?

One obvious answer is "spaghetti sort", or in other words - sorting in a spaghetti model.

Intuitively, the spaghetti model says that your integers are given as lengths of (uncooked) spaghetti, and you sort them by placing them on a table, and then lowering your hand until you hit the tallest spaghetto (for spaghetto is the singular of spaghetti). You take that one out, and repeat.

A bit more formally, this model gives you the operation $\arg\max\{a_1,\ldots, a_n\}$ in $O(1)$.

Determining how "far" this is from a general model is a vague question. There is a trivial lower bound of $\Omega(n)$ on computing the maximum of $n$ elements in a RAM model (and an even worse bound of $\Omega(n\log n)$ in a single-tape Turing Machine), so this is not a realistic model.
You could say that it's equivalent to a RAM model with oracle access to $\max$. I'm not sure how interesting that is.

Another cute aspect of this model is to consider it's physical properties, in the intuitive spaghetti description: recall that in this description, you lower your hand onto the spaghetti. Now, if you actually want to do this to an arbitrary number of spaghetti, then you would need an increasingly large hand.
So this model induces a notion of "hand size" complexity.


Is there a simple game with asymmetric complexity?

Perhaps a fairly natural game is the following:

Player 1 is placed in the middle of a maze and must reach the exit in order to win.

Player 2 is in the same maze and must collect a set of "components" to build  a radio controller that lets him close the exit (and win).

Deciding the next move from a winning position is easy for Player 1: just follow the shortest path from his current position and the exit; but can be very hard for Player 2.
Indeed if the (remaining) components of the radio controller are on the vertices of a grid graph of $n$ nodes (suppose that Player 2 is himself on an adjacent vertex) and the distance between Player 1 and the exit is exactly $n$, then he must find an Hamiltonian path in order to move.

To make the game more "interactive", we can also add some extra actions to Player 2 that can only cause a polynomial slowdown in the calculation of the next move for Player 1; for example allowing him to block a fixed numbers of corridors of the maze.


Efficient flow problem for a complex integer program

Isn't this problem NP-complete?

Start with a graph $G$. Make $x_i = 1 \ \ \forall i$, where $i$ is a vertex of $G$. Now, for each edge $(i,j)$ of $G$, make $x_{i,j} = -3$. Otherwise, make $x_{i,j}=0$. Give weight 0 to all three- and four-level marbles. To maximize your objective function, you want to pick as many marbles as you can so long as you don't take two marbles connected by an edge. This is the maximum independent set problem, which is NP-complete.


Maintaining order in a list in $AC^0$ in $O(1)$ time

Yes!

Use a two-level structure as discussed at the end of Section 2 of the Dietz and Sleator paper. For the top structure, use a scapegoat tree. By using a balance factor that can be implemented in $AC^0$ (like $2$), we get the result.

See also exercise 8.12 from open data structures and Roura's "A new method for balancing binary search trees".


Can modern SAT-Solvers utilise the symmetry of First Order Logic?

There exist first order (FO) logic systems that allow you to actually write FO constraints, and to reason with them in very intricate ways. E.g., see the IDP system.
For instance, I took a small variation of your example and coded it up in the online IDP editor:
vocabulary V{
    type D
    P(D)
}

theory T: V{
    ?x: P(x).
}

structure S:V{
    D = {a;b}
}

procedure main(){
    //stdoptions.symmetrybreaking="static"
    printmodels(allmodels(T,S))
}

If you press the run button, it will print all the models (==solutions) of the FO specification, which in this case amounts to three models. The system uses a SAT solver under the hood.
Now, if you uncomment the //stdoptions.symmetrybreaking="static" line, its automatic symmetry detection and breaking kicks in. Run again, and only two models will be printed, as the third is removed by symmetry breaking. Here is a reference to how this is done under the hood.
Now, can modern SAT solvers exploit this symmetry, without knowing the high level FO specification?
Not completely. The problem is that it seems hard to extract the interchangeability of first-order domain elements in the propositional logic formula. While the SAT solver typically can find permutations of variables that represent symmetries, it can not detect the particular structure of the symmetry group imposed by interchangeable FO domains. However, a succesful preprocessor for SAT solvers that partially detects FO interchangeability symmetry is described here and is available for download.


Interesting results in TCS which are easily explainable to programmers without technical background

In addition to the halting problem, I suggest discussing:

Rice's Theorem.  Some of the explanation on Wikipedia is a bit jargon-heavy, but it's generally not a hard theorem or proof to understand other than that; it has a lot of relevance to real-world concepts like anti-virus software.  The proof is about as involved as the proof of the halting problem (and actually depends on the undecidability of the halting problem).  Basically, just understand that a "computable function" is a Turing machine or computer program.


Problems of similar complexity for different measures

The answer to the first question is that we don't know, because we don't know whether $\mathbf P=\mathbf L$, so it could be that all $\mathbf P$ problems use only logarithmic space.

For the second one, most reasonable problems need at least linear time to read the input, even for non-deterministic machines, so it does not make a lot of sense to say "polynomial non-deterministic lower bound", or you need to make your question more precise.

Finally, the last question is like the first one: it could be that $\mathbf{NL}=\mathbf{NP}$, in which case such a problem wouldn't exist, we don't know...


Lower bound of checking graph connectivity on stream

Here's a reduction from Disjointness that might work:

Given input $n$ bit vectors $x$ and $y$, Alice and Bob want to come up with edge sets $E_1$ and $E_2$ for a graph $G$ such that $G$ is connected iff there is no index such that $x_i = y_i = 1$.

The graph $G$ will have vertex set ${0,1,\ldots,n} \times {0,1}$. For $i < n$, Alice adds the edge $((i-1,0),(i,0))$ to $E_1$ iff $x_i = 0$; similarly, Bob adds the edge $((i-1,1),(i,1))$ to $E_2$ iff $y_i = 0$. Additionally, Alice adds all the edges of the form $((i,0),(i,1))$ for $i\in {0,\ldots,n}$.

I think this graph has one connected component iff $(0,0)$ is connected to $(n,0)$, which happens iff for each $i\in{1,2,\ldots,n}$, either $x_i$ or $y_i$ is 0; that is, the two inputs are disjoint.


Maintaining the product of a queue of semigroup elements

A queue can be represented as two stacks and be maintained in amortized constant time. It's then easy to maintain product of all elements of a stack.

See Purely Functional Data Structures by Chris Okasaki. (More specifically, figure 3.2 on pp. 18. )

About how to maintain on stacks:

Suppose the stack is $s_1, s_2,\ldots, s_n$ from bottom to top. For one stack, we need to maintain $s_1 s_2 \ldots s_n$; for the other, we need to maintain $s_n\ldots s_2 s_1$. We only consider the first case.

Let $p_k=s_1\ldots s_k$, then $p_n$ is the answer we need.

When pop, simply delete $p_n$ and $s_n$.

When push, $p_{n+1}=p_n s_{n+1}$.


Digital steganography re-encoding resistance

I'm not sure what policy here is on reviving dead questions. I'll answer in case anyone else needs this question answered. I'm sorry, but I know of no papers on the subject (likely due to ignorance rather than non-existence, however).

As with most lossy methods of compression, JPEG aims to remove the image features that are not important or differentiable to the human eye. Unfortunately, those parts of the image are precisely where Steganography would occur (for example, in the least significant bits) - so if you had embedded data in an image, JPEG encoding would almost certainly destroy the stego data. Re-encoding image files is actually considered a good way of protecting against steganography. Since steganography is concerned with making the data as un-noticeable as possible (and in the process making it as indistinguishable to the human eye as possible) it is an entirely natural conclusion that steganography would be at odds with format changes (at least, lossy format changes. Lossless changes would not destroy any embedded steganography, unless they relied on some part of the format rather than the pixels themselves).


In 1998, Michel X. Goemans gave an ICM talk, in which, he addressed this issue:"Semidefinite programs can be solved(or more precisely, approximated) in polynomial-time within any specific accuracy either by the ellipsoid algorithm or more efficiently through interior-point algorithms...The above algorithms produce a strictly feasible solution(or slightly infeasible for some versions of the ellipsoid algorithm) and, in fact, the problem of deciding whether a semidefinite program is feasible(exactly) is still open. A special case of semidefinite programming feasibility is the square-root-sum problem. The complexity of this problem is still open."
http://garden.irmacs.sfu.ca/op/complexity_of_square_root_sum

In 1976, Ron Graham, Michael Garey, and David Johnson could not show some geometric optimization problems such as whether Euclidean Traveling Salesman Problem is NP-complete(they can only show the problem is NP-hard), the reason is that they could not show whether the square-root-sum problem is polynomial time solvable or not.
https://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/

The square-root-sum problem is a long open problem which puzzles scholars from computational geometry, optimization, computational complexity, game theory and some other areas a lot as they all at some point, figure out the main obstacle for their problems is to handle the square-root-sum problem.

The most remarkable progress towards this problem is by Eric Allender and his co-authors, in 2003, they showed this problem lies in the 4th level of the Counting Hierarchy.
http://ftp.cs.rutgers.edu/pub/allender/slp.pdf

So based on above facts, one can't solve convex optimization problem in (true) polynomial time with the Ellipsoid method and Interior Point method.

The big O notation is to measure the running time of the algorithm in worst case. However, in practice, the worst case may be a very rare event, that's why you can not use it to measure the practical performance.


Paths and Probabilities for a Random Walk on a Graph

You can make a state machine from this as follows.

Let the set of points generated be $V$.

Add extra dummy start node $s$. Add edges $(s, v)$ for all $v \in V$. And add edge
from $(u, v)$ where $u, v \in V$ are nearest neighbors.

Assuming points to visit are chosen uniformly assign probability $1/|V|$ to edges $(s,v)$
and probability of $1/\text{number of nearest neighbors}$ to edges that connect nearest neighbors.

This now forms a state diagram like http://en.wikipedia.org/wiki/Markov_chain#Example

The graph can be represented as matrix $G$ where $G_{ij} =1$ if there is edge between $i$ and $j$.
And probabilities can be put in a matrix $P$ of size $N + 1 \times N + 1$.

$G^k_{ij}$ gives number of paths of length $k$ from $i$  to $j$.

$(P^k x)_j$ gives probability of reaching $j$ from $i$ in $k$ steps where $x$ is a vector where only $i^{th}$ entry is 1 and others are 0.


Algorithm/Complexity for the following SAT Version

The search problem in the question—let me call it MAX-WEIGHT-3-SAT for now—is $\def\fnwl{\mathrm{FP^{NP[wit,log]}}}\fnwl$-complete.

Recall that $\fnwl$ is defined as the class of search problems solvable by a polynomial-time Turing machine using $O(\log n)$ queries to a witnessing NP oracle: that is, the oracle is required to provide witnesses to all its YES answers.

However, for the present purpose, the following equivalent description is more convenient: a search problem is in $\fnwl$ if it is solvable by a polynomial-time machine using (polynomially many) parallel queries to an (ordinary) NP oracle, followed by a single query to a witnessing NP oracle that always has a positive answer.

To see that MAX-WEIGHT-3-SAT is in $\fnwl$, let $\phi(x_1,\dots,x_n)$ be the input formula. First, using $n+1$ parallel NP queries, check for each $0\le w\le n$ whether $\phi$ is satisfiable by an assignment with $w$ 1s. Let $w_m$ be the maximal $w$ where the answer is positive; make a final witnessing query to get a satisfying assignment with $w_m$ 1s.

In order to show $\fnwl$-completeness, let $S$ be a search problem from $\fnwl$, and fix a poly-time $S$-solver $M$ using $n^c$ parallel NP queries followed by a witnessing query. The predicate $A(x,y,z_1,\dots,z_{n^c})$ defined as “$M$ has a run with input $x$ and output $y$ if $z_i\in\{0,1\}$ is supplied as the answer to the $i$th parallel query, and moreover, whenever $z_i=1$, this answer is indeed correct” is in NP, hence by the proof of the Cook–Levin theorem, there is a poly-time computable sequence of 3-CNF formulas

$$\phi_x(y_1,\dots,y_{n^d},z_1,\dots,z_{n^c},u_1,\dots,u_{n^d})$$

such that if we identify $y$ with its binary representation,

$$A(x,y,z_1,\dots,z_{n^c})\iff\exists u_1,\dots,u_{n^d}\,\phi_x(y,\vec z,\vec u)=1.$$

Now, if we take a satisfying assignment to $\phi_x$ with the maximal number of 1s among the $z_i$’s, then all answers supplied by $\vec z$ for the computation of $M$ are correct, and we can read of the output ($y$) from the assignment. Thus, $S$ is reducible to the following generalization of MAX-WEIGHT-3-SAT:

input: a (satisfiable) 3-CNF formula $\phi(x_1,\dots,x_n,y_1,\dots,y_m)$

output: a satisfying assignment to $\phi$ with the maximal possible number of 1s among the $x_i$’s

But in fact, this problem is reducible to the original MAX-WEIGHT-3-SAT: given $\phi$ as above, consider the formula
$$\phi(\vec x,\vec y)\land\bigwedge_{i=1}^n\bigwedge_{j=1}^m(x_i\leftrightarrow z_{i,j})$$
which behaves just like $\phi$, except that each $x_i$ variable split in $m+1$ variables with the same truth value (under satisfying assignments), overwhelming the count  of the $y_i$ variables.

A related $\fnwl$-complete problem is also given in the answer to Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard? .


Parametrized Complexity of Counting Bicliques

This should be #W[1]-hard by a standard interpolation argument. Here is a rough sketch.

First, consider the multicolored version of the biclique problem: given a graph whose set of vertices is partitioned into classes $X_1,\dots, X_{2k}$, find a biclique containing exactly one vertex from each set. Unlike Biclique, whose FPT status is open, this multicolored version is known to be W[1]-hard: there is an easy reduction from clique. I believe it should also be #W[1]-hard.

Given a graph $G$ and partition as above, let us obtain a new graph $G'$ by replacing every vertex of $X_i$ with an independent set of size $x_i$ (and replacing each edge between $X_i$ and $X_j$ by an $x_i\times x_j$ biclique). Now the number of $k\times k$ bicliques in $G'$ is a function of the $2k$ variables $x_1,\dots,x_{2k}$. In fact, one can see that this function is a polynomial of degree at most $2k$ and the coefficient of the term $x_1\cdot\dots\cdot x_{2k}$ is exactly the number of multicolored bicliques in $G$. Thus by substituting sufficiently many combination of values into the variables $x_i$ and counting the number of bicliques in $G'$, we can evaluate this polynomial at sufficiently many places to recover its coefficients by interpolation.


How to use a -coin so a TM can decide an undecidable language in polynomial time?

I'll take as given the existence of Chaitin's constant $\Omega\in[0,1]$, and that knowing its first $k$ bits is equivalent to be able to decide the halting problem for all Turning machines of size up to $k$:
https://en.wikipedia.org/wiki/Chaitin%27s_constant

Given access to an $\Omega$-biased coin, one can use Chernoff bounds to compute $\hat\Omega_k$, which agrees with $\Omega$ up to $k$ bits (i.e., $|\Omega-\hat\Omega_k|<1/2^{k+1}$), by sampling the coin $O(2^{2k})$ times. Now this is exponential in $k$ and is actually tight, so how does this square with the problem statement:
"Describe a real number $\rho$ such that given a random coin that comes up “Heads” with probability $\rho$, a Turing machine can decide an undecidable language in polynomial time" ?

The trick is to use a very inefficient encoding for the undecidable language.
Fix a universal encoding (the same one used to define $\Omega$) and consider the language $L$, which consists of all Turing machine descriptions $<M>$, such that $M$ halts on all inputs. Clearly, $L$ is undecidable. Now order $L$ in lexicographic order where $<M_i>$ is the $i$th word, and define $L'$ to consist of the words $<M_i'>$, where $M_i'$ is a TM equivalent to $M_i$ (the two halt on and accept the same set of inputs), but $M_i'$ contains an additional $2^i$ dummy states.

Thus, to determine whether a word $x$ belongs to the undecidable language $L'$, one only needs to know $O(\log|x|)$ bits of $\Omega$, which is feasible in expected poly$(|x|)$ time via the argument above.


Are there Conservation Laws in Complexity Theory?

This is a question that has run across my mind many times.

I think one place to look is information theory.  Here is a speculation of mine.  Given a problem maybe we can give some sort of entropy value to information given as input and the information received from the algorithm.  If we could do that, then there would be some minimum amount of information gain required by an algorithm to solve that problem.

There's one related thing I've wanted to figure out.  In some NP-complete problems you can find a constrained version in P; with the Hamiltonian path if you specify that the graph is a DAG then there is a p-time algorithm to solve it.  With other problems like TSP, there's often p-time algorithms that will approximate the optimal.  It seems to me, for constrained p-time algorithms, there should be some proportional relationship between the addition information assumed and run-time complexity reduction.  In the case of the TSP we aren't assuming additional information, we're relaxing the precision, which I expect to have a similar effect on any sort of algorithmic information gain.

Note on Conservation Laws

In the earlier 1900's there was little known German-American mathematician named Emily Noether.  Among other things she was described by Einstein and Hilbert to be the most import women in the history of mathematics.  In 1915 she published what is now known as Noether's First Theorem.  The theorem was about physical laws of conservation, and said that all conservation laws have a corresponding differential symmetry in the physical system.  Conservation of Angular Momentum comes from a rotational symmetry in space, Conservation of Linear Momentum is translation in space, Conservation of Energy is translation in time.  Given that, for there to be some law of conservation of complexity in a formal sense, there would need to be some corresponding differential symmetry in a Langragian function.


Asymptotic complexity of CDCL SAT solver that only selects negative literals

Not a direct answer to the question but, as DPLL can be seen as a special case of CDCL, hopefully of interest.

The problem of finding optimal branching literals for DPLL is (in a way) harder than SAT itself: the paper "On the complexity of choosing
the branching literal in DPLL" by Liberatore shows that
choosing optimal branching literals in DPLL  is both NP-hard and coNP-hard.


If every term in system T terminates, then $t\overline{n}\leadsto\overline{m}$ for every numeral $n$, and it is easy to show that a normal form $\overline{m}$ in the empty context is a numeral as well (and cannot be more complex!). In addition, it is easy to show, if the term $t\overline{n}$ is normalizing, that computing the normal form $\overline{m}$ can be done by a Turing machine, which is to say that the function $|t|$ is recursive (the terminology is slightly confusing here). This is what is meant by the first paragraph you have quoted.

Furthermore, every fact stated above can be easily proven in $\mathrm{PA}$, except the normalization of an arbitrary term of system T. They go on to show that each individual term $t$ can be shown to be normalizing in $\mathrm{PA}$ wich they suggest implies that every term $t$ defines a function in $\mathrm{PA}$: for every term $t:\mathrm{Int}\rightarrow\mathrm{Int}$, there is a proposition $\phi_t(x,y)$ such that
$$\mathrm{PA}\vdash \forall x\exists! y\phi_t(x,y)$$

and

$$\mathrm{PA}\vdash\phi_t(\overline{n},\overline{m})$$
iff
$$|t|(n)=m$$

As the following pages explain, the other direction is provable as well, that is to every $\phi$ with the first property, there is some term $t$ in system T that corresponds to it.


A comparison of extractors in terms of tradeoffs between time, randomness and space ?

The default reference is Ronen Shaltiel's survey.  This predates the important results of [Barak-Impagliazzo-Wigderson '04], [Barak-Kindler-Shaltiel-Sudakov-Wigderson '05], [Barak-Rao-Shaltiel-Wigderson '06] etc.  I believe Anup Rao's Ph.D. thesis is a good recent reference that describes these developments.


Select circle with given radius that contains most points

Your algorithm is correct.  If the best circle contains one point, your post-processing step will find it.  If the best circle contains two or more points, then there is a way to shift it around so it contains the same set of points and also two of them are on the perimeter; thus, in this case your algorithm will also find it.

There may be other algorithms that are even faster, but your algorithm shows that the problem can be solved in $O(n^2)$ time.


I'm not exactly sure if this is the type of problem you were looking for, but the phase transition of NP-Complete problems is a (by now) well known phenomenon.  See Brian Hayes's articles "Can't Get No Satisfaction" about the 3-SAT phase transition and "The Easiest Hard Problem" about the Number Partition Phase transition, for some popular articles on the subject.

Selman and Kirkpatrick were first to show numerically that the phase transition for 3-SAT was when the ratio of clauses to variables was at around 4.3.

Gent and Walsh were first to show numerically that the phase transition for the Number Partition Problem happened when the ratio of bits to list length was about 1.  Later this was proved analytically by Borgs, Chayes and Pittel.

Travelling Salesman, Graph Coloring, Hamiltonian Cycle, amongst others, also appear to have phase transitions for a suitable parameterization of problem instance creation.  I think it's safe to say that it is a commonly held belief that all NP-Complete problems exhibit a phase transition for a suitable parameterization.


What are the relations between Alternative, MonadPlus(LeftCatch) and MonadPlus(LeftDistributive)?

MonadPlusDist $\rightarrow$ Alternative is true.

Corollary: Alternative $\rightarrow$ MonadPlusCatch is false

(because as Petr Pudlák pointed out, [] is a counterexample - it doesn't satisfy MonadPlusCatch but does satisfy MonadPlusDist, hence Applicative)

Assumed: MonadPlusDist Laws

-- (mplus,mzero) is a monoid
mzero >>= k = mzero`                             -- left identity >>=
(a `mplus` b) >>= k  =  (a >>=k) `mplus` (b>>=k) -- left dist mplus

To prove: Alternative Laws

-- ((<|>),empty) is a monoid
(f <|> g) <*> a = (f <*> a) <|> (g <*> a) -- right dist <*>
empty <*> a = empty                       -- left identity <*>
f <$> (a <|> b) = (f <$> a) <|> (f <$> b) -- left dist <$>
f <$> empty = empty                       -- empty fmap

<*> expansion lemma
Assume we use the standard derivation of an applicative from a monad, namely (<*>) = ap and pure = return. Then

mf <*> mx = mf >>= \f -> mx >>= \x -> return (f x)

because

mf <*> mx = ap mf mx                                  -- premise
          = liftM2 id mf mx                           -- def(ap)
          = do { f <- mf; x <- mx; return (id f x) }  -- def(liftM2)
          = mf >>= \f -> mx >>= \x -> return (id f x) -- desugaring
          = mf >>= \f -> mx >>= \x -> return (f x)    -- def(id)

<$> expansion lemma
Assume we use the standard derivation of a functor from a monad, namely (<$>) = liftM. Then

f <$> mx = mx >>= return . f

because

f <$> mx = liftM f mx                    -- premise
         = do { x <- mx; return (f x) }  -- def(liftM)
         = mx >>= \x -> return (f x)     -- desugaring
         = mx >>= \x -> (return.f) x     -- def((.))
         = mx >>= return.f               -- eta-reduction

Proof

Assume (<+>,m0) satisfy the MonadPlus laws. Trivially then it's a monoid.

Right Dist <*>

I'll prove

(mf <+> mg) <*> ma = (mf <*> ma) <+> (mg <*> ma) -- right dist <*>

because it's easier on the notation.

(mf <+> mg) <*> ma = (mf <+> mg) >>= \forg -> mx >>= \x -> return (forg x) -- <*> expansion
                   =     (mf >>= \f_g -> mx >>= \x -> return (f_g x))
                     <+> (mg >>= \f_g -> mx >>= \x -> return (f_g x))      -- left dist mplus
                   = (mf <*> mx) <+> (mg <*> mx)                           -- <*> expansion

Left Identity <*>

mzero <*> mx = mzero >>= \f -> mx >>= \x -> return (f x) -- <*> expansion
             = mzero                                     -- left identity >>=

as required.

Left Dist <$>

f <$> (a <|> b) = (f <$> a) <|> (f <$> b) -- left dist <$>

f <$> (a <+> b) = (a <+> b) >>= return . f              -- <$> expansion
                = (a >>= return.f) <+> (b >>= return.f) -- left dist mplus
                = (f <$> a) <+> (f <$> b)               -- <$> expansion

empty fmap

f <$> mzero = mzero >>= return.f   -- <$> expansion
            = mzero                -- left identity >>=

as required


Converting Kuroda normal form rules to the Penttonen normal form

You can find the proof in Penttonen's original research article:

Martti Penttonen, One-Sided and Two-Sided Context in Formal Grammars. Information and Control 25, pp. 371-392 (1974). https://doi.org/10.1016/S0019-9958(74)91049-3


Complexity of Acyclic Hypergraph Isomorphism

To complete the answer by Holf, it is claimed here DAM 145(3) that isomorphism is GI-complete in $\beta$-acyclic hypergraphs.


Algorithm for computing unordered tree edit distance

A student of ours recently looked into a dynamic programming A* algorithm for computing the unordered tree edit distance (although we adapted it for the ordered tree edit distance). I was not directly involved into this project, but as far as I know, this algorithm explores a search tree that represents all possible edit distances and stops exploring unpromising paths. This way it returns the tree edit distance in the end.

The student also implemented this A* algorithm, so it is not just a theoretical one.

Here's the link: http://ieeexplore.ieee.org/document/6630333/

Hope this helps!


Variants of Cluster-Vertex-Deletion problem

It seems to me that the case where G\X is a disjoint union of exactly two cliques has an FPT algorithm with runtime $O^*(3^k)$.

Here's what the algorithm would do.

If $k \leq 0$ then output YES if and only if G is a disjoint union of two cliques.
If the input graph contains an induced path on three vertices ($P_3$), then at least one of these three vertices need to be deleted to turn the graph into a cluster graph. Thus we branch in three ways depending on a choice of vertex, decreasing the parameter by 1 in each branch. Output the OR of the recursive calls.
If the graph is induced $P_3$-free, it is a cluster graph. If there is only 1 clique in this cluster graph: output NO. If there are two cliques in this cluster graph: output YES. If there are more than 2 cliques: sum the number of vertices in all but the two largest cliques. If this number is more than k, then output NO (all those vertices need to be deleted to reduce the number of cliques to 2, but we can't afford this). If the sum is at most k, output YES.

The approach generalizes to obtaining a cluster graph with exactly $\ell$ cliques for any value of $\ell$.


Thanks to Andreas Björklund, I realized that $c_k$ is the number of all tuples with repetitions. I reread the article carefully and reformulated the problem in the following way:

Let $B = 2^{\mathcal{F}}$, $A_i = \{S \in 2^\mathcal{F} \mid S \cap \{i\} = \emptyset \}$ (i.e. set of all subsets of $\mathcal{F}$ that avoid singleton set $\{i\}$), and $C(\mathcal{F})$ is the number of distinct covers of $\mathcal{F}$. Then from the inclusion-exclusion principle we have:
$$C(\mathcal{F}) = \sum_{X \subseteq N} (-1)^{|X|} 2^{a(X)}$$
As before, $a(X)$ stands for the number of sets in $\mathcal{F}$ that avoid all of $X$.

I've tested this formula on a couple of examples, and it works like a charm. For the simple example from the question above we have:
$$2^3 - 2^1 - 2^1 + 2^0 = 5$$


How to use induction without Fixpoint definition in Coq?

You have an equational specification of the power function. You can prove that it's equivalent to some recursively defined function, in that it has the same values whenever the two functions are passed equal arguments. This is called extensional equality of the two functions.

There is a Zpower function in the standard library, defined recursively:

Fixpoint iter_pos (n:positive) (A:Type) (f:A -> A) (x:A) {struct n} : A :=
  match n with
    | xH => f x
    | xO n' => iter_pos n' A f (iter_pos n' A f x)
    | xI n' => f (iter_pos n' A f (iter_pos n' A f x))
  end.
Definition Zpower_pos (z:Z) (n:positive) := iter_pos n Z (fun x:Z => z * x) 1.
Definition Zpower (x y:Z) :=
    match y with
      | Zpos p => Zpower_pos x p
      | Z0 => 1
      | Zneg p => 0
    end.

Here's a quick-and-dirty proof that your function is equal to Zpower for nonnegative exponents.

Lemma neq_int_bool : forall x y, eq_int_bool x y = false <-> x <> y.
Proof.
  intros.
  pose (A := eq_int_bool_axiom x y); clearbody A.
  split; intros.
  intro E; apply <- A in E. assert (false = true); solve [eauto with bool].
  case_eq (eq_int_bool x y); intro E.
  apply -> A in E. elimtype False. solve [auto with bool].
  reflexivity.
Qed.

Lemma pow_x_0 : forall b, pow b 0 = 1.
Proof.
  intros; rewrite _jc_axiom_sum.
  replace (eq_int_bool 0 0) with true. reflexivity.
  symmetry. apply <- eq_int_bool_axiom. reflexivity.
Qed.

Lemma pow_nat_is_power :
  forall b n, pow b (Z_of_nat n) = Zpower b (Z_of_nat n).
Proof.
  induction n; simpl.
  apply pow_x_0.
  rewrite _jc_axiom_sum.
  replace (eq_int_bool (Zpos (P_of_succ_nat n)) 0) with false.
  replace (Zpos (P_of_succ_nat n) - 1) with (Z_of_nat n).
  rewrite IHn; clear IHn.
  rewrite Zpower_pos_nat. rewrite nat_of_P_o_P_of_succ_nat_eq_succ.
  replace (S n) with (1 + n)%nat. 2: solve [auto with arith].
  rewrite Zpower_nat_is_exp.
  unfold Zpower_nat at 1; simpl.
  replace (b * 1) with b. 2: solve [auto with zarith]. f_equal.
  destruct n; simpl.
  reflexivity.
  rewrite Zpower_pos_nat. rewrite nat_of_P_o_P_of_succ_nat_eq_succ. reflexivity.
  rewrite Zpos_P_of_succ_nat. solve [auto with zarith].
  symmetry. apply <- neq_int_bool. intro; discriminate.
Qed.

What about negative exponents? Your function is underspecified; you may want to try to coerce a more precise specification out of Jessie. One possibility is that pow b e = 0 whenever e < 0, which would make pow extensionally equal to Zpower. But it's also possible that pow 1 e = 1 whenever e < 0.

You can also prove properties of the function independently of the function's definition. For example, you can use induction on the arguments to prove interesting properties like

Lemma pow_plus :
  forall b n1 n2,
    pow b (Z_of_nat n1 + Z_of_nat n2) =
    pow b (Z_of_nat n1) * pow b (Z_of_nat n2).
Proof.
  induction n2.
  (*same techniques as above*)
Qed.


Algorithm to find $n$ player nash equilibrium

The problem of computing Nash equilibria in general games is PPAD complete (which is believed to be hard), even for 2-player games. This was proven for 3-player games by Daskalakis et al. for 3-player games in this paper and extended to 2-player games by Chen et al. in this paper. See the Wikipedia article on the PPAD class for more details.
There are nonetheless many approaches to finding equilibria if you have further game structure, from convexity of the payoff functions to potential and zero-sum games.
Having said that, even finding local min-max equilibria in two-player zero-sum games with nonconvex-nonconcave objectives was recently proven to be PPAD complete (as hard as finding Nash equilibria in general games) by Daskalakis et al., see this video link.