Lower bound on maximum simple cycle in connected cubic bridgeless graphs

So you are looking for the circumference of a connected cubic bridgeless graph $G$. Since a bridgeless cubic graph is immediately 2-connected, Bondy and Entringer showed in the paper

  Longest cycles in 2-connected graphs with prescribed maximum degree,  Canadian Journal of Mathematics, 1980,

that $G$ contains a cycle of length at least $4 (\log_2 n - \log_2\log_2 n - 5)$. And a graph which meets the bound is provided in the result Über längste Kreise in regulären Graphen by Lang and Walther, so this is the best possible.

For the reference, see Longest cycles in 3-connected cubic graphs by Bill Jackson. If the graph is 3-connected, then the bound can be improved to $\Omega(n^c)$ with $c\approx 0.69$, and there are efficient algorithm approximately finding a long cycle in $G$.


Clustering massive data sets in practice

At the risk of sounding immodest, I wrote a short survey on stream clustering a few years ago. It's a little out of date, but not overly so, and doing forward citations will get you to the recent work in the area.


A curious Wilf equivalence class of function compositions

More generally, you can consider the identity
$$ f(g(x)) = g^{(n)}(x), $$
which generalizes your identities, in which $n=3,1,2$ (respectively).

For a given function $g$, this identity states that $f$ needs to have given values on $\operatorname{ran} g$, and is free otherwise. The specific value of $n$ doesn't matter, in fact we can put whatever we want on the right-hand side as long as it doesn't involve $f$. Using inclusion-exclusion, you can come up with an explicit formula for the number of solutions, but I'll leave that to you.


Maximizing strictly increasing convex function

I'm sorry I don't fully understand the question, but if the point is to find the maximum, considering the local maximum is the global, then any gradient based method is going to take you directly to it. For instance artificial neural networks (gradient backpropagation).


Integer Factoring via Lattice Reduction?

I am not an expert in lattice problems, but I do know the exact-case problem, Shortest Vector Problem (SVP), is NP-hard. In this paper, Schnorr appears to reduce integer factorization to some form of the approximation version of Closest Vector Problem ($\gamma$-CVP), where CVP is a generalization of SVP. However, I do not believe there are known polynomial time algorithms for this.

Some known facts about $\gamma$-CVP:

Arora, et al (PDF), show that approximating the closest vector within any constant is NP-hard.

Also, they show that, for $\epsilon > 0$, if you can approximate the closest vector within a factor of $2^{\log^{\frac{1}{2} - \epsilon}{n}}$ in polynomial time, then any problem in NP can be solved in quasi-polynomial time.

Dinur, et al (ACM Citation), later strengthened the inapproximability result to:

For $\epsilon > 0$, approximately finding the closest vector within a factor $n^{\frac{\epsilon}{\log\log{n}}}$ is NP-hard.

Although I'm unfamiliar with Schnorr's work, what we know of lattice problems would lead me to believe that this is not intended to lead to a polynomial-time algorithm directly. Rather, Schnorr spends some deal of time talking about actual implementations (e.g. running this program on such-and-such computer takes approximately so many weeks/months/years/eons).

P.S. As Suresh points out, it appears to be an effort to get "quick enough" or "quicker" run times for integer factorization, despite the complexity.

P.P.S. And if I can make a further conjecture: Given that Schnorr's paper pre-dates the work on hardness of approximating lattice problems, it's likely that there was some original hope that it might have led to a polynomial-time algorithm for integer factorization. In light of Arora et al and Dinur et al, however, it's clear that there's not a solution (or at least, a straightforward solution) along that route, however.


How bad can the greedy coloring (list color) for the c-chromatic number of graph be?

nice question.
Consider the following construction: build k P3s numbered / ordered as 1-2-3 4-5-6 7-8-9, etc.
Now 1-2-3 all get colour R by the greedy scheme. Make 4,5,6 all adjacent to 3. Then 4,5,6 each get colour B. Now make vertices 7,8,9 adjacent to 3 and to 6, then they can't get colours R or B. They get Y.

Continue with 10-11-12, with 10,11,12 adjacent to 3,6,9. They cannot be coloured with R B Y, so they get G.

These 3k vertices will need k = n/3 colours. But note that c(G) is 2, since the set {3,6,9,12,etc} induce a clique, and the rest of the graph induces a perfect matching. So this shows that greedy colouring can still be arbitrarily bad for cograph colouring as well.

We can modify this construction to cut down the max degree as well... 4,5,6 are adjacent to 3, but make 7,8,9 still adjacent to 6 but now adjacent to 1 instead of 3. Then make 10,11,12 adjacent to 9, 4(instead of 6), and 3. And for future triplets, keep alternating which end-vertex of a prior P3 they join to. The resulting graph is probably not partitionable into 2 cographs anymore, but observe that 2,5,8,11,etc form an independent set and the rest is probably coverable with 2 more cographs, but I'm not quite sure. But I don't think this is important ... what is important here is that the max degree is low enough that the greedy colouring uses more than $\frac{1+\Delta}{2}$ colours (to answer your second question.)

Another interesting question to ask would be whether a "smarter" greedy colouring (such as LexBFS) would produce a constant-ratio approximation.


Complexity relative to the graph of the Busy-Beaver function

Really nice question(s). I don't fully follow Denis’ answer, so I'm going to try my own.
For question 1, I’m going to assume that you are familiar with Kolmogorov complexity (otherwise I could write a proof heavily using Kleene’s fixed point theorem, but such proofs tend to look like black magic, while Kolmogorov complexity is rather natural). Assume for the sake of contradiction that $H$ can be computed from oracle $\Gamma_{BB}$ in computably bounded time, and let $f$ be a computable bound.
First, I claim that for all $n$, the first $2^{n+1}$ bits of $H$ form a string $x_n$ of Kolmogorov complexity at least $n$. Indeed, if we knew $x_n$, this would allow us to know which programs of size $\leq n$ halt, so we could run all of them and return a string different from all the outputs of terminating programs of size $\leq n$, hence of Kolmogorov complexity $>n$. In other words, we can computably transform $x_n$ into a string of complexity $>n$, which by conservation of complexity implies $K(x_n)>n$ (I ommit the usual additive constant).
On the other hand, by our assumption the first $2^{n+1}$ bits of $H$ can be computably obtained from the first $f(2^{n+1})$ bits of $\Gamma_{BB}$. But $\Gamma_{BB}$ is very, very, sparse hence in particular, for infinitely many $n$, the string $y_n$ consisting of the first $f(2^{n+1})$ bits of $\Gamma_{BB}$ is all zeroes except perhaps for the the first, say, $n/2$ bits, and thus $y_n$ must have Kolmogorov complexity less than $n/2$ (it suffices to specify the first $n/2$ bits), which contradicts the fact that the first $2^{n+1}$ bits of $H$ can be computably obtained from $y_n$.
Question 2 goes right into current research in computability theory. Fortnow proposed a little while ago the concept of `low for speed’. An oracle $X$ is low for speed if it does not alter any computational complexity class. More precisely, $X$ is low for speed if any computable language $L$  that can be computed from oracle $X$ in time $f$ can be computed without $X$ in time $poly(f)$. While we do not have a full characterization of low for speed oracles, we know that:

there exist non-computable ones, which can be taken to be recursively enumerable (Robertson Bayer. Lowness For Computational Speed. PhD thesis, University of California Berkeley, 2012)
that they form a measure 0 set (Bienvenu Downey, https://arxiv.org/abs/1712.09710) but they form a meager set if and only if $P \not= NP$ (Bayer, ibid)
that lowness for speed is not a Turing degree notion, but any $X \geq_T \emptyset’$ is not low for speed (Bienvenu-Downey, ibid)

From this last point, we know that $\Gamma_{BB}$ is not low for speed, so there is some computable language which can be computed much faster with $\Gamma_{BB}$ than without it. I'd have to think about it, but I believe we could cook up a language which is in $\mathbf{P}^{\Gamma_{BB}}$ but not in $\mathbf{P}$.


Number of binary gates needed to compute AND and OR of n input bits simultaneously

This paper of Blum & Seysen may be useful:

N.Blum, M. Seysen. Characterization of all Optimal Networks for a Simultaneous Computation of AND and NOR. Acta Inf. 21: 171-181 (1984)

I have thought that for $x_1\dots x_n\vee \bar{x}_1\dots\bar{x}_n$ $2n-c$ lower bound can be obtained using methods of Blum & Seysen, but it seems this is not the case.


Complexity of weighted cycle in a hamiltonian graph

If we are asking for a simple cycle the problem is NP-complete by a reduction from the Hamiltonian cycle problem.

We want to find a Hamiltonian cycle in a graph $G$. We assign weight 1 to all edges of $G$, and add to this graph all the other edges with weight $\infty$. We have thus created a clique, which is obviously Hamiltonian, and we ask whether there exist a cycle with weight $n$ in it.


I suggest you use the framework found in the following paper:

How Far Can We Go Beyond Linear Cryptanalysis?, Thomas Baignères, Pascal Junod, Serge Vaudenay, ASIACRYPT 2004.

The crucial result says that you need $n \sim 1/D(D_0 \,||\, D_1)$, where $D(D_0 \,||\, D_1)$ is the Kullback-Leibler distance between the two distributions $D_0$ and $D_1$.  Expanding out the definition of the K-L distance, we see that in your case

$$D(D_0 \,||\, D_1) = p \log \frac{p}{p+\epsilon} + (1-p) \log \frac{1-p}{1-p-\epsilon},$$

with the convention that $0 \log \frac0p = 0$.

When $p \gg \epsilon$, we find $D(D_0 \,||\, D_1) \approx \epsilon^2/(p(1-p))$.  Thus, when $p \gg \epsilon$, we find that you need $n \sim p(1-p)/\epsilon^2$ coin flips.  When $p = 0$, we find $D(D_0 \,||\, D_1) = -\log(1-\epsilon) \approx \epsilon$, so you need $n \sim 1/\epsilon$ coin flips.  Thus, this formula is consistent with the special cases you already know about... but it generalizes to all $n,\epsilon$.

For justification, see the paper.

When $p \gg \epsilon$, the justification is easy to work through by hand.  With $n$ observations, the number of heads is either $\text{Binomial}(n,p)$ or $\text{Binomial}(n,p+\epsilon)$, so you want to find the smallest $n$ such that these two distributions can be distinguished.

You can approximate both of these by a Gaussian with the right mean and variance, and then use standard results on the difficulty of distinguishing two Gaussians, and the answer should fall out.  The approximation is fine if $p \ge 5/n$ or so.

In particular, this comes down to distinguishing $\mathcal{N}(\mu_0,\sigma_0^2)$ from $\mathcal{N}(\mu_1,\sigma_1^2)$ where $\mu_0 = pn$, $\mu_1 = p+\epsilon)n$, $\sigma_0^2 = p(1-p)n$, $\sigma_1^2 = (p+\epsilon)(1-p-\epsilon)n$.  You'll find that the probability of error in the optimal distinguisher is $\text{erfc}(z)$ where $z = (\mu_1-\mu_0)/(\sigma_0+\sigma_1) \approx \epsilon \sqrt{n / 2p(1-p)}$.  Thus, we need $z \sim 1$ to distinguish with constant success probability.  This amounts to the condition that $n \sim 2p(1-p)/\epsilon^2$ (up to a constant factor)... when $p \gg \epsilon$.

For the general case... see the paper.


Scaling procedures to address false 0's after multiplying probabilities

A simplee trick (explained here) that let you use the $\log$ approach even when you must sum probabilities.

Problem: $\log(\exp(a) + \exp(b))$ can lead to an underflow, to avoid it you can use this formula:

$\log(x + y) = \log(x) + \log(1.0 + \exp( \log(y) - \log(x) ) )$

Or use another approach:

$\log(\exp(a) + \exp(b)) = \log( \exp(a - C) + \exp(b - C)) + C$

Setting $C = \max(a,b)$

For example: $\log(e^{-120}+e^{-121}) = \log(e^{-120}(e^0 + e^{-1}))= \log(e^0+e^{-1})-120$


is "spaghetti sort" really O(n) (even as a thought experiment) ?

The folklore analysis of spaghetti sort assumes a model where one can extract the longest noodle in constant time, perhaps by lowering a horizontal plate ("hand") over the vertical noodles until it stops, and then extracting the noddle touching the plate.  (Apparently the plate is pastamagnetic.)  Within this perfectly well-defined theoretical model, the analysis is clean and obviously correct.

So is the pastamagnetic-plate model reasonable?  For up to a few hundred strands of spaghetti, sure.  Beyond that, obviously not.  So should we make the model more reasonable by taking the physical costs of moving the plate, sensing collisions, or  choosing the right noodle?  What about the (nonzero!) physical cost of keeping all the noddles vertical (or at least parallel), and keeping the sensing plate and the table horizontal (or at least parallel to each other but not the noodles)?  Should we worry about the measuring process causing micro-fractures that change the exact length of the noddles, or the implication from quantum mechanics that there is no such thing as "exact length"?  Holy crap, is the spaghetti-sorting problem even well-defined?!

No, this way lies madness.  The original theoretical analysis is predictive within the context for which the algorithm was designed — manually sorting a handful of pasta #8.  That the analysis does not generalize to significantly larger values of $n$ or other types of pasta does not make the analysis "incorrect".  It merely limits its scope.


Confusing (to me) statement from "Type Classes in Haskell"

Simple answer: When the above class definition is in scope, you simply cannot bind (<) or (<=) except as part of an instance declaration for Ord.


For arbitrary $b$, Alon, Babai and Itai showed a lower bound on the probability space size of $m(n,\lfloor k/2 \rfloor)$ where
$$ m(n,k) = \sum\limits_{i=0}^k \binom{n}{i}$$

which is $\Omega(n^{k/2})$ for constant $k$.

They also gave a construction of size $O(n^{k/2})$ in the case of $b = 1$.

For $b=1$ there is a paper by Karloff and Mansour which shows lower bounds and upper bounds for arbitrary probabilities, i.e., for $p_1,\ldots,p_n$ with $p_i = P(Y_i = 1)$. E.g., there are probabilities $p_1,\ldots,p_n$ such that the probability space size is at least $m(n,k)$. They also say that $m(n,k)$ is also a upper bound for arbitrary probabilities.

I don't known any construction with a better upper bound than $O(n^k)$ which is given by the construction (see here) mentioned by Thomas as a comment.


How hard is counting the number of vertex covers after a small perturbation?

Since counting vertex covers is #P-complete, your problem is unlikely to be in P; otherwise you could count the number of vertex covers starting from the empty graph on $|V|$ vertices, adding edges one by one.


Remove unneeded atoms in CNF minimalization (SAT preprocessing)

As Kyle Jones has mentioned, the example you provided is called (restricted) resolution.

Beside that, pure literals can also be safely removed from a SAT problem. Unit clauses can be assigned a truth value. Check this paper:

The Puzzling Role of Simplification in Propositional Satisfiability.  Inês Lynce and João Marques-Silva.

It discusses several preprocessing techniques for SAT, and its experiments showed that applying preprocessing for SAT leads to mix results. However, this paper might not be state-of-the-art.


Any SAT/SMT formulations of the VRP/VRPTW (TSP, Job-Shop-Scheduling)?

The big problem I see with a SAT formulation for VRPTW is that you have to discretize time to enforce the time window constraints (unless you encode arithmetic as boolean circuits which I've never seen done but might be worth trying). This means the number of variables becomes much larger as the time window increases affecting performance.

An SMT (Sat Modulo Theory) formulation however wouldn't have a similar issue, I think since you have a propagator for the time window constraints which would return redundant constraints to the SAT solver to incorporate when you branch.

While I don't know of any work using SAT formulations for VRPTW, I know that Peter Stuckey, in his paper on Lazy Clause generation used an approach almost exactly like SMT to solve Job Shop Scheduling and seemed to get good results for that.


Explanation of states, models and worlds in Kripke semantics?

Here is a sketch (massively simplifying for reasons of
pedagogy):

Setting the scence. You can think of logic as a tool, an API in computing parlance,
to reason about things, where reasoning means deriving true
statements from true assumptions. The things that we reason about
using logic is called a model.  What makes logic useful is that
this API, in particular its dominant strain called first-order
logic (of course there are other logics), is completely generic,
meaning we can use it to reason
about teddy bears, cars, bridges over rivers, stars, computation,
whatever you want. Because logic is so generic, we can build up a
generic reasoning infrastructure that can be reused in many
domains. Example include interactive theorem provers, SAT
solvers, textbooks, social conventions such as learned journals,
career structures in the sciences, conventions about when we deem to have
lost/won an argument etc. So logic is a great labour saving
device, because we don't have to reinvent these core tools again
and again for everything that we want to reason about.

Is logic all we need to reason? Naturally not. Because logic is generic, we have to inject domain
specific assumptions, usually called axioms, to cater for domain specific
knowledge (e.g. ZFC or Peano arithmetic to found mathematics,
deontic axioms for reasoning about ethics etc).

What has all of   this to do  with Kripke semantics?
Often we want to reason about things that change over
time (e.g. traffic at a traffic light, concurrent processes using
shared memory communication, knowledge of observers).  We can do
this by injecting suitable axioms into first-order logic for each
domain separately.  However, just as with first-order logic, it
turns out that a lot of the axioms that we need to reason about
change are similar regardless of what changes over time.  So why
not 'factor out'    this similarity and create an API for reasoning
about change, just as we did with first-order logic as an API for
general reasoning? Let this new logic/API be called modal logic.

Now we come back to the notion of model, because models are what
we reason about.

What is this API called modal logic about? Well, things that change.
Let's call them worlds. Now ,
the worlds change into each other over time.  Would a description of
this change not be a
binary relation on the set of world? The set of worlds together with the
relation is the model.

Voila, Kripke semantics.

Warning: the description above is simplistic, and terminology is
not uniform.  Moreover, for most modal logics the model must also
account for variables.
In more neutral terminology (and still simplifying), a model is a
triple $( W, R, \sigma )$ where

$W$ is a non-empty set
(elements of W are called nodes or worlds or points).
$R$ is a binary relation on $W$, and is known as the
accessibility relation which regulates how 'time' flows.
$\sigma$ is a map from variables (in the ambient logic) to the
powerset of W. The idea behind $\sigma$ is that $\sigma$
controls at what points/worlds the variables are true.

If you want to know even more, maybe check the Wikipedia entries
on Kripe semantics or modal logic or any good book on
the subject such as Modal Logic, by Blackburn, de Rijke and Venema.


Minimal elements of a monotonic predicate over the powerset $2^{|n|}$

Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries".

It seems that the existence of a polynomial time algorithm is still open. Schmulevich et al. prove that "Almost all monotone Boolean functions are polynomially learnable using membership queries". If we also require that the $t$th minterm be generated in time polynomial in $n$ and $t$, then the problem is equivalent to monotone dualization, as shown by Bioch and Ibaraki. Here is a survey addressing monotone dualization.


Constructing Orbits of the Automorphism of a Graph Group in Bliss

If Bliss is not mandatory, you can try Sage: https://www.sagemath.org/
I used it successfully a few times.

This video:  https://www.youtube.com/watch?v=X4_4Bqj6EdA&t=579s
Gives a usage example.


Degree restriction for polynomials in $\mathsf{VP}$

It's not really needed, so much as it is a matter of convention and utility. Of course, depending on your aims and your specific problem, it is completely reasonable to consider arithmetic circuits of polynomial size regardless of degree. This class is often denoted $\mathsf{VP}_{nb}$ (for "Non-degree-Bounded"), or sometimes "algebraic $\mathsf{P/poly}$ or $\mathsf{algP/poly}$.

I was curious about this same question for a long time, so a while ago I spent some time digging. I found both a posteriori motivations, based on what we now know, and more historical, a priori motivations. I'm sure this list is incomplete, but here's what I found.

A priori motivations:

Skyum and Valiant [A Complexity Theory Based on Boolean Algebra. J.
ACM 32(2):484-502, 1985] seems to make it clear that the real
motivation is that in the Boolean setting p-bounded degree is what we
have, since every function can be expressed as a multilinear (and hence degree $\leq n$) polynomial. See (2), (3), and (4) below.
Valiant’s original paper (Valiant. Completeness classes in
algebra. STOC 1979) is focused on formula size, and his original
definition of p-definable is given in terms of multilinear polynomials
whose coefficients have poly size formulae, and then taking the
closure under p-projections. The motivation for p-projections is
clear. This yields p-bounded degree as a consequence.
One motivation for considering formula size:  ”We note that in the
Boolean case, although no analogue of Hyafil’s result is known, the
logarithm of formula size is intimately related to the space required
to compute the function.” [Valiant, p. 11] (We now know that, in the
Boolean case, polynomial formula size is equivalent to nonuniform $\mathsf{NC}^1$
(log-depth, poly-size circuits), but at the time I do not know if this
class was yet considered.)
Another motivation for formula size from the Boolean case (which he
discusses in Section 9): Boolean p-definable families exactly capture
$\mathsf{NP/poly}$ – that is, the only difference between "Boolean p-definable"
and "$\mathsf{NP}$" is nonuniformity. (The use of multilinearity in his
definition of p-definable may also have been motivated by this, since
all Boolean functions can be written multilinearly.)
Strassen’s result on eliminating divisions multiplies the
complexity by a factor of $deg^2$, so maintaining polynomial
complexity while eliminating divisions uses p-bounded degree.
For quasipolynomial instead of polynomial bounds, we have
qp-computable iff qp formula size, but only for families of
qp-bounded degree. This follows from two results that were known at the time: Hyafil (1979) showed that depth is at most $O((\log d + \log s)\log d)$, where $d$ is the degree and $s$ is the circuit size, and Brent (1974) showed that depth is $\Theta(\log(\text{formula size}))$
Without the restriction on degree, permanent would not be
$\mathsf{VNP}$-complete under p-projections, as any p-projection of permanent has
p-bounded degree.

A posteriori motivations:

Valiant-Skyum-Berkowitz-Rackoff [SIAM J. Comput. 12(4):641-644,
1983] extends Hyafil’s result to yield circuits of the same depth as
Hyafil, but whose size is polynomial in the original size and the
degree.
The more recent depth-reduction results (the chasms at depth 3 and 4) also involve the degree of the polynomial. As with VSBR, they become significantly less powerful for polynomials of large degree (and trivial for polynomials of really large degree).
von zur Gathen’s “Feasible Arithmetic Computations: Valiant’s
Hypothesis” [J. Symb. Comput. (1987) 4, 137-172] provides several
useful reasons for bounding the degree. In particular, by bounding the
degree in the definition of $\mathsf{VNP}$, $\mathsf{VNP}$ is closed under many natural
operations that it would not otherwise be closed under. See esp. the
two paragraphs at the top of p. 156 mentioning results of Kaltofen
(1986) and Plaisted (1984).
von zur Gathen, ibid., p. 7: "Restricting the degree is quite reasonable over infinite fields, e.g.
over $\mathbb{Q}$, where the binary representation of the value of a polynomial
like $x^{2^n}$ has exponential length even for small inputs. In a
different setting–over varying finite fields–natural problems like
the trace, testing for quadratic residuosity, or factoring
polynomials, lead to polynomials of large degree, which can
nevertheless be computed efficiently (yon zur Gathen & Seroussi,
1986)."


Citation showing minors are topological minors for subcubic graphs

If $G$ is a graph with maximum degree 3 and is a minor of $H$, then $G$ is a topological minor of $H$.

Since $G$ is a minor of $H$, $G$ can be obtained from $H$ by deleting edges, isolated vertices and performing edge contractions. It's also easy to show that we can insist that the subgraph operations are done first, i.e., we can first perform all the edge and vertex deletions and then perform all the edge contractions. Moreover, let us restrict the definition of "edge contraction" to disallow contracting edges where one of the vertices has degree 1. Contracting such an edge is the same as deleting it, so this will not change the definition of graph minors.

Let $H'$ be the graph obtained from $H$ by performing all the edge/vertex deletions first. $H'$ still contains $G$ as a minor. If we show that $H'$ contains $G$ as a topological minor then we're done, since the definition of topological minor also allows edge/vertex deletions.

Since $G$ can be obtained from $H'$ by edge contraction only, $H'$ and all intermediate graphs must have maximum degree 3 since there is no way to decrease the maximum degree of a graph by performing an edge contraction. (This would have been possible if we had allowed the contraction of edges incident on a vertex of degree 1.)

So consider any step in the conversion of $H'$ to $G$. The only types of edges we can contract are those with both degree-2 vertices or one degree-2 vertex and one degree-3 vertex. (All other combinations don't work. For example, edges with two degree-3 vertices will give rise to a vertex of degree 4 when contracted.)

And now we're done, since if $H_1$ is obtained from $H_2$ by contracting an edge with two degree-2 vertices, then $H_2$ can be obtained from $H_1$ by performing edge subdivision on that edge. Similarly for an edge with one degree-3 vertex and one degree-2 vertex. Thus $H'$ can be obtained from $G$ by performing edge subdivisions only, which means $G$ is a topological minor of $H'$ and thus $H$.

  If $G$ is a path or a subdivision of a claw and is a minor of $H$ then $G$ is a subgraph of $H$

This is easy to show once we have the previous result. Since paths and subdivisions of claws have maximum degree 3, if $G$ is a minor of $H$ it is also a topological minor of $H$. This means there is a subgraph of $H$ that can be obtained from $G$ by only performing edge subdivisions. Now it's easy to show by induction that every edge subdivision of a path or subdivision of a claw leads to a graph which contains the original as a subgraph. For example, subdividing a path of length k leads to a path of length k+1, which contains the path of length k as a subgraph. Similarly for subdivisions of a claw.

We also needed this result for a paper once, so we included a short proof in our paper. You can find the result in Quantum query complexity of minor-closed graph properties. It's mentioned on page 13. However, this fact is hidden away in the proof of something else and isn't stated explicitly as a theorem.

What's also interesting is that there is a converse to this theorem:

  The only graphs $G$ for which containing $G$ as a minor is equivalent to containing $G$ as a subgraph are those in which each connected component is a path or a subdivision of a claw.


How to cite Babai's new graph isomorphism result?

First off, I would discourage submitting for publication an unconditional paper which depends on the quasi-polynomial result, if that's what you want the citation for. Rephrase the result as conditional upon the the existence of a quasi-polynomial GI algorithm and state in a footnote that Babai may have proven this but that the paper is not publicly available. In this case, no citation is necessary because you don't need the result for the paper.

In any other context, I don't think it's particularly necessary to cite an available paper - citing his website is fine. It depends a little on what you are writing, but I would recommend asserting something along the lines of "it is widely believed that GI is solvable in quasipolynomial time and a proof of this has been announced by Laszlo Babai [citation to the webpage where he makes the claim]."

One notable advantage of citing his online claim is that his website contains both his own words as to the current claim and a link to his preprint.


Counting the number of Hamiltonian cycles in cubic Hamiltonian graphs?

In my paper "The traveling salesman problem for cubic graphs" (J. Graph Algorithms and Applications 11(1):61-81, 2007) I proved an upper bound of $2^{3n/8}$ on the number of Hamiltonian cycles, conjectured that the bound could be improved to $2^{n/3}$, and found a family of graphs that have exactly $2^{n/3}$ showing that, if true, the conjectured bound would be tight. Heidi Gebauer ("On the Number of Hamilton Cycles in Bounded Degree Graphs", ANALCO 2008) improved the upper bound to $1.276^n$.

If one allows multigraphs then a cycle that alternates between single and double bonds has $2^{n/2}$ Hamiltonian cycles, and this is tight.


Is integer factorization an NP-complete problem?

No, its not known to be NP-complete, and it would be very surprising if it were. This is because its decision version is known to be in $\text{NP} \cap \text{co-NP}$. (Decision version: Does $n$ have a prime factor $\lt k$?)

It is in NP, because a factor $p \lt k$ such that $p \mid n$ serves as a witness of a yes instance.

It is in co-NP because a prime factorization of $n$ with no factors $\lt k$ serves as a witness of a no instance. Prime factorizations are unique, and can be verified in polynomial time because testing for primality is in P.


What is this variant of set cover problem known as?

Here I show that the problem is NP-complete.

We convert a CNF to an instance of your problem as follows.
Suppose that the variables of the CNF are $n$ $x_i$'s and the clauses are $m$ $C_j$'s, where $n<m$.
Let $U=\cup_i (A_i\cup B_i\cup Z_i)$ where all sets in the union are completely disjoint.
In fact, $A_i=\{a_{i,j}\mid x_i\in C_j\}\cup\{a_{i,0}\}$ and $B_i=\{b_{i,j}\mid x_i\in C_j\}\cup\{b_{i,0}\}$, while $Z_i$ is any set of cardinality $k=2n+1$.
Also denote $Z=\cup_i Z_i$ and fix for every $Z_i$ an increasing family of length $k$ inside it, denoted by $Z_{i,l}$ for $l=1..k$.
For every variable $x_i$, we add $2k$ sets to $\mathcal F$, every set of the form $A_i \cup Z_{i,l}$ and $B_i \cup Z_{i,l}$.
For every clause $C_j$, we add one set to $\mathcal F$, which contains $Z$, and for every $x_i\in C_j$ element $\{a_{i,j}\}$ and for every $\bar x_i\in C_j$ element $\{b_{i,j}\}$.

Suppose that the formula is satisfiable and fix a satisfying assignment.
Then pick the $k$ sets of the form $A_i \cup Z_{i,l}$ or $B_i \cup Z_{i,l}$, depending on whether $x_i$ is true or not.
These are $nk$ incremental sets.
Now add the $m$ sets corresponding to the clauses.
These also keep increasing the size, as the clauses are satisfiable.
Finally, we can even add $k$ more sets (one for each variable) to make the sequence cover $U$.

Now suppose that $n(k+1)+m$ sets are put in an incremental sequence.
Notice that at most $k+1$ sets corresponding to $x_i$ can be selected for each $x_i$.
Thus, if there are no clause sets in the incremental sequence, at most $n(k+1)$ can be selected, which is too few.
Notice that as soon as a clause set is selected, we can pick at most two sets corresponding to each $x_i$, a total of at most $2n$ sets.
Therefore, we have to pick at least $n(k-1)$ variable sets before any clause set is picked.
But as we can pick at most $k+1$ for each $x_i$, this means that for each we have picked at least $1$, as $k=2n+1$.
This determines the "value" of the variable, thus we can pick only "true" clauses.

Update: Changed value of $k$ from $n$ to $2n+1$ as pointed out by Marzio.


Are there canonical non-relativizing techniques?

There's really only one "flagship" non-relativizing technique: namely, arithmetization (the technique used in the proofs of IP=PSPACE, MIP=NEXP, PP⊄SIZE(nk), MAEXP⊄P/poly, and several other results).

However, the proof that all NP languages have computational zero-knowledge proofs (assuming one-way functions exist), due to Goldreich, Micali, and Wigderson, used a different non-relativizing technique (namely, the symmetries of the 3-COLORING problem).

Arora, Impagliazzo, and Vazirani argued that even "local checkability," the property of NP-complete problems used in the proof of the original Cook-Levin Theorem (as well as the PCP Theorem), should count as a non-relativizing technique (though Lance Fortnow wrote a paper arguing the opposite).  The sticking point is whether it makes sense to relativize the complexity class of "locally checkable problems."

The pebbling arguments used in results from the 1970s such as TIME(n)≠NTIME(n) have been put forward as another example of a non-relativizing technique.

For more, you might want to check out my algebrization paper with Wigderson, and especially the references therein.  We had to pretty much catalogue the existing non-relativizing techniques in order to figure out which ones were and weren't encompassed by the algebrization barrier.

Addendum: I just realized that I forgot to mention measurement-based quantum computing (MBQC), which was recently used to great effect by Broadbent, Fitzsimons, and Kashefi to obtain quantum complexity theorems (such as QMIP = MIP*, and BQP = MIP with entangled BQP provers and BPP verifier) that most likely fail to relativize.


Algorithms on graphs represented using BDDs

You may find this link is useful.
http://www.andrew.cmu.edu/user/vanhoeve/mdd/


Systematic studies of sum of quadratic polynomials squared

To the best of my knowledge, there is no such study; furthermore, without some nontrivial advances in the technology of sum-of-squares (SOS) problems, it is not currently clear what the immediate benefit of such a study would be.  (I'll focus on the SOS connection since that, as far as I know, is the best way to solve these general quartic problems.) This statement should be taken in a positive light: I believe there is a lot of research depth surrounding these problems.  I'll substantiate my claim in a few ways, hopefully in ways people find useful..

Firstly, for the most basic problems of the type you discuss, the SVD connection gives a much better solver than the SOS black box; in particular, the latter constructs an SDP with $\binom{n+2}{2}$ terms, where $n$ is the total number of variables in the source optimization problem (for instance, the total number of elements in all unknown matrices; to see where I got these numbers, see lecture 10 from Pablo Parrilo's 2006 course:  http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-techniques-and-semidefinite-optimization-spring-2006/lecture-notes/lecture_10.pdf ).  This is an SDP you would never want to solve (running time depends on $n$ as $n^{6}$ using an interior point solver?), especially when compared with the ridiculous speed of an SVD solver (using consistent notation, SVD will be something like $\mathcal O(n^{1.5})$; you can de-fudge my computations by tracking the number of columns, rows, and target rank, but it's a disaster no matter how you rectify my negligence).  Along this vein, if you designed a specialized algorithm to solve SOS problems where the max degree within any polynomial is two: this would be amazing, and then the sort of survey you seek would have lots of value.

Secondly, since the basic formulation of these problems is out of the window, one may wonder if certain variants of these problems are well handled by SOS solvers.  As an important example, consider the NMF (non-negative matrix factorization) problem, where the matrix unknowns you are optimizing over (in your above formulation) must now have non-negative entries.  Unfortunately, if you take the standard SDP used to solve these problems (see for instance Pablo Parrilo's notes from above), there's no way to introduce those constraints.  (And since some formulations of the resulting problems are NP-hard, you would now be building an approximation scheme; i.e., this can get nasty.)  Furthermore, there is recent work that exploited the polynomial structure of this problem to build solvers with some guarantees: see http://arxiv.org/abs/1111.0952 by Arora, Ge, Kannan, and Moitra.  They build a few algorithms, however when they solve an "exact" NMF problem (where there is an exact factorization, i.e., one giving objective value 0), they do not use a SOS solver: they use a solver checking feasibility of "semi-algebraic sets", a much more difficult optimization problem which allows the kinds of constraints which NMF raises, but now with exponential running time.

Anyway, to summarize and give some further perspective; since SOS is afaik the only solver for the quartic problems you speak of (i.e., I don't think there is a specialized quartic solver), I've discussed how these solvers have better alternatives for the kinds of quartic problems people care about.  To effectively use SOS tools here, you would either have to build some amazing solver for the quartic case (inner polynomials of degree at most 2), or you would have to find some way to add constraints to these problems.  Otherwise, the connection to SOS problems, while fascinating, does not give you much.

You also mention that you are surprised that the literature you have found does not make this connection.  I think that is mostly due to the newness of practical SOS solvers (even though abstract consideration of SOS problems goes back very far), and what I said above.  In fact, when I first found SOS solvers, it was via Parrilo's notes and papers, and I similarly wondered, "why isn't he talking about PCA-type problems"?  Then I checked the above facts and frowned a lot.  I think it's also a bad sign that Parrilo himself has not, as far as I can tell/skim, discussed these problems outside the reference you mention in his thesis (meanwhile, he has papers on various extensions, and I have a lot of respect for his work in these field: he must have thought about these specific quartic problems many times.. okay I just checked and found a related negative result by him and some colleagues, which has some connections in its introduction: http://arxiv.org/abs/1111.1498 ).


Can I bound the cardinality of a set if testing for membership in it is known to be NP-complete?

Mahaney’s Theorem states that sparse NP-complete sets exist iff P=NP. Therefore, assuming $P \neq NP $ implies a super-polynomial lower bound on the number of instances of size $n$ in $NP$-complete sets, for infinitely many $n$. That is, if $P \neq NP$, then any $NP$-complete set must have some $\epsilon \gt 0$ such that for infinitely-many integers $n\ge 0$, the set contains
at least $2^{n^{\epsilon}}$ strings of  length $n$.

H. Buhrman and J. M. Hitchcock proved the lower bound ($2^{n^{\epsilon}}$) is tight, unless the polynomial hierarchy collapses.

[1] H. Buhrman and J. M. Hitchcock, NP-Hard Sets are Exponentially Dense Unless coNP ⊆ NP/poly, In IEEE
Conference on Computational Complexity, pages 1–7, 2008

[2] Eric Allender, A Status Report on the P Versus NP Question, Advances in Computers, Volume 77, 2009, Pages 117-147


Is a monotone boolean function monotone as a multilinear polynomial?

Yes.

  Let $f : \{-1,1\}^n \to \mathbb{R}$, and let $F : [-1,1]^n \to \mathbb{R}$ be its multilinear extension. If $f$ is monotone, then so is $F$.

proof: Fix a variable index $i$; we'll show that $\frac{\partial F}{\partial x_i} \ge 0$ at all $x \in [-1,1]^n$. If this holds for all $i$, we're done. Since $F$ is multilinear, we can write this partial derivative as $\frac{1}{2}\left( F\restriction_{x_i=1} - F\restriction_{x_i = -1} \right)$, where $F\restriction_{x_i = a}$ means we assign $a$ to $x_i$ and leave the remaining variables free. So it suffices to show that $F\restriction_{x_i = 1} \ge F\restriction_{x_i = -1}$ for all $x\in [-1,1]^n$. Since $f\restriction_{x_i = 1} \ge f\restriction_{x_i = -1}$ on $\{-1,1\}^n$, and since $F\restriction_{x_i=a}$ is the multilinear extension of $f\restriction_{x_i=a}$, this reduces to the following claim:

  Let $f,g : \{-1,1\}^n \to \mathbb{R}$ be functions, and $F,G : [-1,1]^n \to \mathbb{R}$ their respective multilinear extensions. If $f \ge g$ point-wise, then $F \ge G$ point-wise as well.

proof: Recall that if $M$ is a multilinear function, then we can write
$$M(a) = \sum_{x \in \{\pm 1\}^n} M(x) \prod_{i=1}^n \left\{\begin{array}{rcl}\frac{1+a_i}{2} &:& x_i = 1\\ \frac{1-a_i}{2} &:& x_i = -1\end{array}\right.$$
From this formula, it directly follows that if $M(x) \ge 0$ for all $x \in \{-1, 1\}^n$, then $M(a) \ge 0$ for all $a \in [-1,1]^n$. The claim then follows by applying this fact to $M = F - G$, since for $x \in \{-1,1\}^n, (F - G)(x) = (f - g)(x) \ge 0$.


Any results on binary boolean CSP beyond the fixed-parameter tractability of almost 2SAT problem?

To my knowledge classifying this CSP variant is wide open. You can express a few fixed-parameter tractable problems in the setting (e.g. d-Hitting Set is roughly the case where you have positive clauses of size at most d plus negative assignments; roughly means that the CSP problem is slightly more general but easily reduces back to d-HS, or at least weighted d-HS). Even for constraints that you can implement via existentially quantified 2-CNF formulas it is open what the complexity is. The problem is that when implementing constraints in this way, while they are 2-CNF, you pay only one to delete the whole thing. Hence even simple constraints which are just the conjunction of two others can be hard (I may have example + reference later).


Are there problems without efficient algorithms, where existence theorems have proved such algorithms must exist?

Sure, there are lots of examples, at least in the spirit of your question.

Often one gets such a result from the probabilistic method. For example, one paper that I like that runs into the problem is on reconstructing graphs in the additive model.  Here, the authors show that there exists a set of $O(dn)$ queries that will (optimally) learn the target graph.  Given this set, the algorithm is efficient.  However, they use the probabilistic method to show the existence of this small set (for each problem size) that will work on all inputs, but do not explicitly construct it.  So the best they can do is just a brute-force search through an exponential family of queries because they don't have an explicit construction.


Parametrized Algorithm for Finding Bicliques

Parameterized by degeneracy or arboricity, it's FPT. More specifically, $O(d^3 2^d n)$ where $d$ is the degeneracy (or $a^3 2^{2a}$ for arboricity). See:

Arboricity and bipartite subgraph listing algorithms.
D. Eppstein.
Inf. Proc. Lett. 51:207-211, 1994.

Another parameterized paper has just been accepted to SWAT 2012, this time parameterized by longest induced path length:

Aistis Atminas, Vadim Lozin and Igor Razgon:
Linear time algorithm for computing a small biclique in graphs without long induced paths. SWAT 2012, to appear.

But my understanding is that whether this is FPT or not with the natural parameter (the size of the biclique) is a big open problem.


Formal representation of rings in computations

Your questions are related to a field (no pun intended) called "Computer Algebra". I myself was looking for comprehensive surveys when I was working on algebraic methods to calculate various graph centrality metrics. I could not find good surveys, but this book was partially helpful. The research papers on this "topic" are scattered all over and often not explicitly categorized as "computer algebra". Reading algorithmic papers on isomorphism, factoring (integers/polynomials) and graph algorithms based on matrix multiplication might give you more insights.


What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?

Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time you cover an element, update the cost of all sets that cover it. Then there are n total updates, so the total time for the algorithm using a priority queue in this way is $O(n \log n)$.
The linear time algorithm for the unweighted case mentioned by Neal Young in a comment is basically the same thing, just using a bucket queue as the priority queue instead of a comparison-based priority queue.
As for average case, you haven't provided enough information to answer that. Average over what input distribution?


Reference needed for lower bound on number of guards in three-dimensional art gallery guarding

To my knowledge, Seidel's construction has only been published in O'Rourke's book and nowhere else.

In one of his papers, Seidel even refers to O'Rourke's book for a description of his own construction. He writes on top of page 253 of his joint paper with Jim Ruppert:
"In his book [9, p. 255] O'Rourke describes n-vertex three-dimensional polyhedra that require $\Omega(n^{3/2})$ guards."

  Jim Ruppert, Raimund Seidel: On the Difficulty of Triangulating Three-Dimensional Nonconvex Polyhedra. Discrete & Computational Geometry 7: 227-253 (1992)


How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?

In terms of these complexity classes as a whole, not much is known that distinguishes characteristic 2 from other characteristics. The most frequently arising difference is that the permanent is easy in characteristic 2 (so not VNP-complete unless VP=VNP). (In contrast, the Hamiltonian Cycle polynomial is VNP-complete in all characteristics.)

The relationship of the VP vs VNP question in different characteristics to Boolean complexity classes depends on the characteristic, but in an obvious way (e.g. Boolean complexity classes defined in terms of a similar characteristic, like $\mathsf{Mod_n P}$).

Aside from these (and a few other similar examples like permanent), I'm not sure I know of any proven differences between the different characteristics. I'd be interested to see some!

(Another caveat to be aware of is the distinction between functions over $\mathbb{F}_2$ and formal polynomials over $\mathbb{F}_2$. As functions, $x^2 - x$ and $0$ are the same, but as formal polynomials over $\mathbb{F}_2$ these are distinct. VP and VNP are usually defined in terms of formal polynomials.)


On derandomizing polynomial identity testing

[tl;dr] A lot is known, and it is a very active area! [/tl;dr]

It is important to specify the representation of the input polynomials, since it they are given as lists of coefficients or nonzero monomials, the problem is trivial. Thus one usually assumes the polynomials to be given as arithmetic circuits (a.k.a. straight-line programs). And the general case actually boils down to testing whether a given polynomial is the zero polynomial.

There are two main settings that have been studied: the whitebox case in which one has the arithmetic circuit and can inspect it, and the blackbox case in which one knows some things about the circuit (size, formal degree, ...) but cannot inspect it, only evaluate it on some values.

Here are some of the restrictions on the circuits that have been studied:

Bounded depth: The depth of a circuit is the longest path from an input to the output gate. Testing circuits of depth $2$ is trivial, depth $3$ is very well understood (completely solved? I do not know...), depth $4$ is also well understood. There are results showing that solving the problem for depth-$3$ and depth-$4$ circuit is almost the same as solving the general case.
Top/bottom fan-in: For bounded-depth circuits, many results have been proved when the fan-in (or arity, that is the number of inputs to a given gate) of either the top gate or the bottom gates is bounded.
Other restrictions such as a bound on the number of times a variable is used have also been studied.

This survey by Nitin Saxena is a good source for these results. Note though that it is already more than one year (!) old, and this is a very active area. So the most recent results are not covered.

Finally, there are links between the derandomization of PIT and the derandomization of other problems:

Noether's Normalization Lemma, by Ketan D. Mulmuley;
Multivariate Polynomial Factorization, by Swastik Kopparty, Shubhangi Saraf and Amir Shpilka.


VC Dimension generalized to discrete, non-binary, unordered domains?

Yes - I think you are looking for "multiclass VC dimension," and there are a couple different generalizations of VC dimension to multiclass classification.  A good paper on this is by Ben-David et al. ('95). In addition to proving learnability results, they give a nice history and references to previous extensions of VC dimension to the multiclass case.  Another perhaps relevant work by Haussler and Long ('95) generalizes Sauer's lemma to more general versions of VC dimension.


What's the difference between online and incremental optimization?

This is discussed in section 2.2.3 of Jeffrey Hartline's thesis: http://www.cs.cornell.edu/w8/~jhartlin/finaldiss.pdf

Online problems are all about informational uncertainty: you don't know what inputs are coming tomorrow, and the difficulty is often information theoretic, not computational. On the other hand, there is no uncertainty in an incremental optimization problem as Hartline defines it: every parameter of the problem is known at the outset. Without computational restrictions, the problems can always be solved optimally.

So perhaps your definition is wrong, since indeed yours sounds like an online problem. The problem of "incremental optimization" seems to be defined in this 2008 thesis, and differs from your definition in that there is no uncertainty.


Is there an extension to the stable roommates problem with multiple roommates per room?

Switching from 2 to 3 "beds" makes the problem NP-complete :-)

See K. Iwama, S. Miyazaki, and K. Okamoto, "Stable roommates problem with triple rooms." Proc. 10th KOREA-JAPAN Joint Workshop on Algorithms and Computation (WAAC 2007), pp. 105–112, 2007

(an electronic edition can be downloaded from ResearchGate).

Abstract: In the stable roommates problem, we are given 2N men and each person's preference list. We are asked to find a stable matching, namely, a set of N pairs satisfying the stability condition. This problem is known to be solved in polynomial time; more precisely, there is a polynomial-time algorithm to find a stable matching for a given instance, or to report that a given instance has no stable matching. In this paper, we extend this problem into three-dimension, i.e., a matching is defined to be a set of triples, and show that this problem is NP-complete. ...

See also this survey: Kazuo Iwama and Shuichi Miyazaki. 2008. A Survey of the Stable Marriage Problem and Its Variants. In Proceedings of the International Conference on Informatics Education and Research for Knowledge-Circulating Society (icks 2008) (ICKS '08). IEEE Computer Society, Washington, DC, USA, 131-136.


Testing/Identifying a Topological Sorting

This can be done in nearly linear time.

Let the permutation be $\pi = (v_1,\dots,v_m)$, and let $k = k(\pi)$ be the number of steps needed to check a single edge $(u,v)$ against $\pi$.
It is then enough to check that each of the $M_i$ edges of $G_i$ is compatible with $\pi$, which can be done in $O(kM_i)$ time, or $O(k\sum M_i)$ overall.

By preprocessing $\pi$ one can reduce $k$ down to two lookups in an array containing $m$ entries each of $\log\, m$ size, and a comparison between two $(\log\ m)$-bit entries in the array; the array element $a[w]$ contains the index of $w$ in $\pi$ considered as an ordered list.  This means that $k = O(\log\, m)$ yielding $O((\log\, m)\sum M_i)$ time overall for the upper bound.

As @mjqxxxx points out, every edge of every graph may be relevant.  This creates a lower bound of $\Omega(K\sum M_i)$ steps, where $K$ is the least amount of work that needs to be done for every graph edge; it is possible that some approaches can amortize the cost so that $K = o(\log\, m)$.  This is still going to be $\Omega(\sum M_i)$ at best, so there is not much of a gap left.


If BQP contains NP, does this mean that P=NP?

No, $\mathrm{NP}\subseteq\mathrm{BQP}$ is not known to imply $\mathrm P=\mathrm{NP}$. Even the stronger assumption $\mathrm{NP}\subseteq\mathrm{BPP}$ is not known to yield a deeper collapse than $\mathrm{NP}=\mathrm{RP}$ and $\mathrm{PH}=\mathrm{ZPP^{RP}}=\mathrm{BPP}$; in particular, it is not even known to imply $\mathrm{NP}=\mathrm{coNP}$. (However, all these implications are likely true by virtue of their premises being false.)


BWT: is it possible to predict the next character in a sequence?

In general, no, but it's difficult to prove a negative given that there might be some data structure equivalent to a BWT that provides the prediction capability.

The L vector in the BWT is simply a list of the input string's characters sorted by their following context, i.e. the suffix that begins immediately after each character.  Its information content is inversely related to how well this following context predicts the character preceding it.

This predicability is present in many types of text and in many models for generating text, but it's easy to fool adversarially if you have some algorithm like you describe in your second paragraph.  For instance, if your algorithm has only read a portion of the input (you don't specify how it operates, so I'm guessing), I believe it's possible to extend a string in such a way as to spoil any context where you think the prediction is 100%.


Relation between group theory and information theory

Sadly, group structure is nearly so limited that there isn't much one can do with it to be of use in information theory, thus the literature is prone to be fairly sparse. Even Abelian groups aren't enough structure.

Even basic abstract algebra texts which have some basic coding theory applications generally provide examples using field theory or linear algebra. If there were useful examples for groups, they'd most likely be introduced there.

Hungerford, Thomas; Abstract Algebra: An Introduction
Rotman,J.J.; A First Course in Abstract Algebra, Third Edition

As most of Rotman's work was in group theory, if anyone would have had examples there, certainly he would. Steven Roman at UCI also did a good bit of textbook writing (separately) on coding theory and field theory and has a text Fundamentals of Group Theory: An Advanced Approach (Birkhauser), but not having read it, I suspect you'll find it barren of the group theoretical work you're looking for.

In the late 90's I seem to recall some work on binary codes defined by using codes over the alphabet $ \mathbb {Z}_4$. For some background (and possible references) see J.H. van Lint's Introduction to Coding Theory, Third Edition (Springer, 1999).

Once you take the algebraic step up to even finite fields, you're far more likely to find overlap with more coding theory. For this, try taking a look at Error-Correcting Linear Codes: Classification by Isometry and Applications (Springer) by Betten, Braun, et al. which may have some scant material on applications to groups as I recall.


What bound can we get using $k$-th moment inequality under 3-wise independence?

I guess that the number of random variables $t$ and the threshold $t$ are different parameters, as otherwise $\Pr[|Y| \geq t] = 0$.

Let $a_1, \dots, a_k, b_1, \dots, b_k\in_U \{\pm 1\}$ be iid random variables sampled uniformly at random from $\{\pm 1\}$ and $n=2^k$. Consider random variables $W_1,\dots, W_n$ of the form $c_1 \cdot c_2\cdot \dots \cdot c_k$ where each $c_i$ is either equal to $a_i$ or $b_i$ (e.g., one of random variables $W_i$ equals $a_1b_2b_3a_4b_5  \dots a_k$). We defined $n$ random variables $W_i$; note that they are $3$-wise independent.

Let $X_i = (W_i+1)/2$.
Then $X_i\in\{0,1\}$ and ${\mathbb E}[X_i] = 1/2$. Let $t=n/2$. We have,
$$\Pr(|\sum X_i - n/2| \geq t) = \Pr(|\sum W_i| \geq n) = \Pr(|\prod_{i=1}^k(a_i+b_i)| \geq n) = \Pr(a_i+b_i\neq 0 \text{ for every }i) = \frac{1}{2^k} = \frac{1}{2t}.$$
Here, we used that $\prod_{i=1}^k(a_i+b_i)$ equals $0$ if $a_i+b_i=0$ for some $i$, and equals $-n$ or $n$, otherwise.

Answer: in general, we cannot obtain a stronger upper bound than $O(1/t)$.

Update: here is an explanation why $W_1,\dots, W_n$ and consequently $X_1,\dots, X_n$ are 3-wise independent. Each of the words $W_i$ is encoded by a word of length $k$: the $r$-th letter in the word is $a$ if $c_r=a_r$ in the definition of $W_i$, and $b$, if $c_r=b_r$. Consider three random variables $W_i$, $W_j$ and $W_k$. Consider the corresponding words; denote them by $I$, $J$ and $K$. Let $r_1$ be the first position where they differ. Without loss of generality $I_{r_1} = a$, $J_{r_1} = b$, and $K_{r_1} = b$. Then let $r_2$ be the first position where $J$ and $K$ differ. WLOG, $J_{r_2} = a$ and $K_{r_2} = b$. Write $W_i = a_{r_1} \cdot W'_i$, $W_j = a_{r_2}\cdot W_j'$ and $W_k = b_{r_2}\cdot W_k'$. Note that $W_j$ and $W_k$ are independent since for $x,y\in\{\pm 1\}$, we have
$$\Pr(W_j = x, W_k = y) = \Pr(a_{r_2} = (x/W_j'), b_{r_2} = (y/W_k')) = 1/4.$$
Now we prove that $W_i$, $W_j$, and $W_k$ are independent. For  $x,y,z\in\{\pm 1\}$, we have
$$\Pr(W_i = x, W_j = y, W_k = z) = \frac{1}{4}\Pr(W_i = x| W_j = y, W_k = z) =
\frac{1}{4}\cdot \Pr(a_{r_1} = (x/W'_i)| W_j = y, W_k = z) =  \frac{1}{4}\cdot \frac{1}{2} = \frac{1}{8}.$$


Difference between infinite state machines and turing machines

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like.

Make the initial state accept if the empty string is in the language.
Create two states for the strings 0 and 1, which the initial state branches to depending on whether the first symbol is 0 or 1. Label these $q_0$ and $q_1$. If either of the strings 0 or 1 are in $L$, make the corresponding state accept.
For a given $n \geqslant 1$, and for each state $q_x$ for $x \in \{0,1\}^n$, create two states $q_{x0}$ and $q_{x1}$, to which the state $q_x$ branches depending on whether the next symbol is 0 or 1. If either $x0 \in L$ or $x1 \in L$ is in the language, make the corresponding state accept. Having performed this for all $x \in \{0,1\}^n$, proceed to the next value of $n$, ad infinitum.

This produces an infinite state machine which decides the language $L$. In particular, it decides $L$ regardless of whether $L$ is even computable, and even regardless of its position in the arithmetic hierarchy. So not only can you have infinite state machines which have power intermediate between FSMs and Turing machines, you can make it have as much or as little power as you like.

As to algorithms, note that the ISMs constructed this way have the same structure for any language: an infinite balanced binary tree. It in essence also represents the language directly, in that it effectively is equivalent to an infinite boolean string representing the characteristic function of the language $L$. As such, the subset of these ISMs which represent regular languages is not recursively enumerable: there is no way to conclude after a finite number of steps that the language recognised is regular, because for any candidate language that the ISM recognises, there could always be some exception — but the ISM might still represent some more complicated regular expression, so neither can one conclude in a finite number of steps that the language it decides is not a regular language. The complete lack of compression in the description of the language (which is necessary to be able to represent arbitrary languages using a common structure) makes it effectively impossible to decide such problems.


Rigorous and probably more correct version at the bottom.

I don't think so. Consider the case where A(L,M) consists of advice strings of even length. To decide if x is in L, the machine M gets advice yz where y and z are strings of equal length. M discards z and decides membership of x in L only depending on y. Let y be of length n, and let z range over some arbitrary subset S of strings of length n.

In such a case, A(L,M) cannot be in P/Poly since given a string yz, the machine has to test membership of z in S. But since the advice is of length poly(n), the machine cannot work correctly for every S by counting argument.

Another more rigorous version:

Let L be the trivial language containing all strings. The machine M ignores its advice and accepts every input. The task is now to construct the set of advice strings A(M) which cannot be in P/Poly subject to the constraint that strings in L of length $n$ get advice of length $O(poly(n))$.

For every length $i$, let $S_i \subseteq {0,1}^i$. Let $S = \cup_i S_i$. Construct a mapping $f: S \rightarrow Z^+$ such that $|s| \leq f(s)$. The mapping just enumerates the strings in $S$ in non-decreasing order of length. The string $s$ serves as advice to M for strings of length $f(s)$.

By choosing $S_i$ to be of superpolynomial description size (can be done because of counting arguments), we get that $S$ (which is also $A(M)$) lies outside P/Poly.


Concerning decidability of a problem on real numbers

I think it's undecidable, but I don't have a proof. Intuitively, if $s\neq qr+p$ for all $p,q\in\mathbb{Q}$ (i.e. if the answer is "NO"), then you will be always looking for a "next" pair $(q,p)$ such that $|s-(qr+p)|$ is smaller than before. You don't really have an argument to decide when to stop and return "NO" because, for all you know, there is a better approximation to $s$ of the form $qr+p$ than the one you already have.


Global properties of hereditary classes?

Hereditary properties are very "robust" in the following sense.

Noga Alon and Asaf Shapira showed that for any hereditary property ${\cal P}$, if a graph $G$ needs more than $\epsilon n^2$ edges to be added or removed in order to satisfy ${\cal P}$, then there is a subgraph in $G$, of size at most $f_{\cal P}(\epsilon)$, which does not satisfy ${\cal P}$.  Here, the function $f$ only depends on the property ${\cal P}$ (and not on the size of the graph $G$, for instance).  Erdős had made such a conjecture only about the property of $k$-colorability.

Indeed, Alon and Shapira prove the following stronger fact: given ${\cal P}$, for any $\epsilon$ in $(0,1)$, there are $N(\epsilon)$, $h(\epsilon)$ and $\delta(\epsilon)$ such that if a graph $G$ has at least $N$ vertices and needs at least $\epsilon n^2$ edges added/removed in order to satisfy ${\cal P}$, then for at least $\delta$ fraction of induced subgraphs on $h$ vertices, the induced subgraph violates ${\cal P}$.  Thus, if $\epsilon$ and the property ${\cal P}$ are fixed, in order to test if an input graph satisfies ${\cal P}$ or is $\epsilon$-far from satisfying ${\cal P}$, then one only needs to query the edges of a random induced subgraph of constant size from the graph and check if it satisfies the property or not.  Such a tester would always accept graphs satisfying ${\cal P}$ and would reject graphs $\epsilon$-far from satisfying it with constant probability.  Furthermore, any property that is one-sided testable in this sense is a hereditary property!  See the paper by Alon and Shapira for details.


Number of operations to compute product of pairwise sums over a commutative semiring

Not an answer to your exact question, but may be useful if you happen to have a semiring with cancellation: if you have an algorithm which works in any ring, you can apply that algorithm to the difference ring $S-S$ consisting of subtraction pairs $s - t$.  The result will have the form $s - t$ where $s,t \in S$, and the answer will be $d \in S$ s.t. $s = d + t$.  Thus, in addition to semiring operations, you'd need to perform a single cancellation step at the end.


How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming?

If you think of $1 - X_{uv}$ as the "distance" between $u$ and $v$, then you can impose the triangle inequality: $1 - X_{uw} \le 1 - X_{uv} + 1 - X_{vw}$, which can be rewritten $X_{uv} + X_{vw} - X_{uw} \le 1$. This forces (in integral 0-1 solutions) the vertices to group into cliques. You can then check that the degree of every vertex is $k-1$ to ensure they form $k$-cliques.


Oracle complexity of a problem in the Counting Hierarchy

Yes. Each time your $\sf NP$ machine want to query the $\sf PosSLP$ oracle, simply simulate the polynomial time oracle Turing machine underlying the inclusion $\sf PosSLP \subseteq {P}^{{PP}^{PP^{PP}}}$, passing its oracle queries to the $\sf {PP}^{PP^{PP}}$ oracle.


For an extreme example, chordal graphs can have as many as $\binom{n}{2}$ edges but chordal graphs that happen to also be bipartite can have only $n-1$ edges (they are forests). Or even more extremely, consider complete graphs versus (complete $\cap$ bipartite) graphs. But perhaps it makes sense to restrict your problem only to classes of graphs that are naturally sparse, as the planar and minor-closed graph families are.

It is not true that all minor-closed families are biparted; in particular, the graphs of treewidth $k$ are not. An $n$-vertex graph with treewidth $k$ has at most $\binom{k}{2}+k(n-k)$ edges, but (for large $n$ and small $k$) the complete bipartite graph $K_{n-k,k}$ has treewidth $k$ and is almost as dense with $k(n-k)$ edges.

One can extend the bounds from planar graphs to $k$-apex graphs (graphs such that you can delete $k$ vertices and get a planar graph), and their generalization to $(g,k)$-apex graphs for bounded genus $g$: these graphs have at most $(k+3)n+O(g)$ edges but their bipartite subclasses have at most $(k+2)n+O(g)$.

Moving beyond minor-closed properties but continuing with graphs related to planar graphs, the 1-planar graphs (graphs that can be drawn with at most one crossing per edge) can have at most $4n-8$ edges, but bipartite 1-planar graphs can have at most $3n-6$. See Czap and Hudák, "On drawings and decompositions of 1-planar graphs", Elect. J. Comb. 2013. And the graphs with book thickness $k$ have at most $(k+1)n-O(1)$ edges ($2n-3$ for the first page and $n-3$ for each subsequent page), but when they are bipartite the constant factor is lower because the first page is outerplanar. I suspect that similar things happen with other types of almost-planar graph.


what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

The Vehicle Routing Problem was introduced in G. B. Dantzig and J. H. Ramser, The Truck Dispatching Problem, Management Science Vol. 6, No. 1 (Oct., 1959), pp. 80-91.

The authors underline the differences with TSP in this way:

... The "truck dispatching problem" formulated in this paper may be considered as a generalization of the TSP ...

... The salesman may be required to return to the "terminal point" whenever he has contated $m$ of the $n-1$ remaining points, $m$ being a divisor of $n-1$. For given $n$ and $m$ the problem is to find loops such that all loops have a specified point in common and total loop length is a minimum. Since the loops have one point in commom, this problem may be called the "Clover Leaf Problem"...

... The TSP may also be generalized by imposing the condition that specified deliveries $q_i$ be made at every point $P_i$ (excepting the terminal point). If the capacity of the carrier $C$ is greater than $\sum_i q_i$, the probelm is formally identical with the TSP in its original form since the carrier can serve every delivery point on one trip which links all the points...

In the simplest VRP formulation, all trucks (vehicles) have the same capacity and only one product is to be delivered to each point $P_i$. Other common constraints are: time constraints (or total length of each route), time windows, precedence relations between points.

To summarize: the main difference between a TSP and VRP is that the salesman must return to the starting location after some points have been visited.

For what regards "It seems relatively easy to model TSR in the form of VRP and likewise inversely."; the reduction from TSP to VRP is immediate, the opposite direction VRP $\leq_m^p$ TSP is surely more complex (and probably it requires other intermediate reductions).


Computing every boolean function with a polynomial over $\mathbb{F}_3$?

Every function $\mathbb{F}_p^n \longrightarrow \mathbb{F}_p$ (where $p$ is prime) can be written as a polynomial. For the proof, consider all $p^n$ monomials, and show that they are linearly independent.


Yes, there is a connection between the spectrum of the graph and the size of the maximum cut. It might be easiest to see this with the normalized graph Laplacian, $L = I - D^{-1/2}AD^{-1/2}$, where $I$ is the identity, $A$ is the adjacency matrix of the graph $G = ([n], E)$ and $D$ is the diagonal matrix defined by $D_{ii} = d_i$, the degree of vertex $i$. The largest eigenvalue of $L$ is

$$\lambda_{n-1} = \max_x\frac{x^TLx}{x^Tx} = \max_{x}\frac{\sum_{(i, j) \in E}{(x_i - x_j)^2}}{\sum_{i}{d_i x_i^2}}.$$

Because $(x_i - x_j)^2 \leq 2x_i^2 + 2x_j^2$ by Cauchy-Schwarz, $\lambda_{n-1} \leq 2$. Equality is achieved if and only if for each edge $(i, j)$, $x_i = -x_j$, which means that $\lambda_{n-1}= 2$ only if the graph has a bipartite connected component, i.e. a connected component whose maximum cut is equal to the number of edges in the component.

For a robust version of this result, see Luca Trevisan's paper. He shows that

$$
\lambda_{n-1} \geq 2\frac{\text{MaxCut}}{m},
$$

(where $m$ is the number of edges of the graph) and if $\lambda_{n-1} \geq 2(1-\epsilon)$, then there exits a set of vertices $S$ and a partition $(S_1, S_2)$ of $S$ such that

$$
|e(S_1, S_2)| \geq \frac{1}{2}(1-\sqrt{16\epsilon})\text{vol}(S),
$$
where $\text{vol}(S) = \sum_{i \in S}{d_i}$ and $e(S_1, S_2)$ is the set of edges with one endpoint in $S_1$ and the other in $S_2$.

Note that the second bound does not necessarily lower bound the max cut in a useful way: it only lower bounds the maximum cut of the set $S$ in terms of $\text{vol}(S)$. This is unavoidable: think of a graph that's the disjoint union of an edge and a large graph with small maximum cut, say a clique. The maximum cut of the graph is very close to $m/2$, which is the minimum possible value of the max cut of a graph with $m$ edges. However, $\lambda_{n-1} = 2$, the maximum possible value of $\lambda_{n-1}$. In other words, while $\lambda_{n-1}$ is a relaxation of the maximum cut (up to appropriate rescaling), the gap is arbitrarily close to 2, and a 2-approximation to max cut is trivial.

Nevertheless, in the paper Luca uses the spectral result to design a recursive approximation algorithm for max cut. This is one cool thing about the paper: it uses a relaxation that, unlike the SDP relaxation of Goemans and Wiliamson, has trivial gap, but despite that an optimal solution to the relaxation actually provides enough guidance to achieve a non-trivial approximation factor.


What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

Here's a quick argument for why it works over rings. Given matrices $A$, $B$, $C$, we verify $A B = C$ by picking a random bit vector $v$, then checking if $ABv = Cv$. This clearly passes if $AB = C$.

Suppose $AB \neq C$ and $ABv = Cv$. Let $D = AB - C$. $D$ is a nonzero matrix for which $Dv = 0$. What's the probability that this occurs? Let $D[i',j']$ be a nonzero entry. By assumption, $\sum_{j} D[i',j] v[j] = 0$. With probability $1/2$, $v[j'] = 1$, so we have

$D[i',j'] + \sum_{j\neq j'} D[i',j] v[j] = 0$.

Any ring under its addition operation is an additive group, so there is a unique inverse of $D[i',j']$, i.e., $-D[i',j']$. Now, the probability of the bad event $-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$ is at most $1/2$. (One way to see this is the "principle of deferred decisions": in order for the sum to equal $-D[i',j']$, at least one other $D[i',j]$ must be nonzero. So consider the $v[j]$'s corresponding to these other nonzero entries. Even if we set all of these $v[j]$'s except for one of them  optimally, there is still equal probability for the last one being $0$ or $1$, but still only one of these values could make the final sum equal to $-D[i',j']$.)
So with probability at least $1/4$, we successfully find that $Dv \neq 0$, when $D$ is nonzero. (Note $v[j]$ and $v[j']$ are independently chosen for $j \neq j'$.)

As you see, the above argument depends on subtraction. So it won't work (for example) on arbitrary commutative semirings. Perhaps you could relax the multiplicative properties of the algebraic structure, and still get the result?


Best communication complexity lower bound of disjointness

In a recent paper, Braverman, Garg, Pankratov, and Weinstein compute the value of $\delta$ to be exactly some constant around 0.4827, up to sublinear factors. This gives a tight bound on the communication complexity of disjointness.

The constant itself was found using a computer algebra system, and as far as I'm aware can't be expressed simply.


A hypercube has $O(n\log n)$ edges and satisfies your property for $k\leq\frac{\log_2 n+1}{2}$:

S. Madhavapeddy, and I. H. Sudborough, "A topological property of hypercubes: node disjoint paths", Proc. IEEE SPDP, 532-539, 1990.


Maximizing the number of heads in $N$ tosses by choosing which coin to toss

I agree with D.W. that this should just be a dynamic programming question.
Assume that $P_B$ is known and that we have a prior on $P_A$ and that $N$ is known. (Without a prior on $P_A$ or a known $N$, I do not see how your objective or "optimal" are well-defined.)
Let optimal mean "maximizes expected number of heads" with the expectation over both the coin flips and the draw of $P_A$ from the prior. (This seems to me the only natural definition of (edit: achievable) "optimal" here.)

Let $Val(t,prior)$ be the expected number of heads of the optimal strategy starting at time $t$ with prior $prior$ on $P_A$. Then immediately
 $$ Val(N,prior) = \max\{ P_B, ~ \mathbb{E}P_A \} $$
since at the last step we should just choose the higher chance of flipping heads, and $\mathbb{E}P_A$ with respect to $prior$ is the probability of getting heads from flipping coin $A$. So we know how to choose the coin at the last step for any distribution on $P_A$.

At step $t < N$,
  $$ Val(t,prior) = \max\{ P_B + Val(t+1,prior), ~~ \text{val if flip $A$}\} $$
where
  $$ \text{val if flip $A$} ~~ = \mathbb{E}P_A ~~ + (\mathbb{E}P_A) Val(t+1,posterior(prior,heads)) ~~ + (1-\mathbb{E}P_A) Val(t+1,posterior(prior,tails)) . $$

Explanation: The value for flipping $B$ is $P_B$ for this coin flip, plus the value of the optimal strategy at time $t+1$ with the same prior on $P_A$ as we currently have. The value for flipping $A$ is the expected number of heads for this round, $\mathbb{E}P_A$, plus our expected value over the two possible cases. First, if the coin comes up heads (which happens with probability $\mathbb{E}P_A$), then we will update our prior to a posterior on $P_A$ conditioned on that event, and we will play the optimal strategy at time $t+1$ with that new distribution. Similarly if it comes up tails.

There are at the very most $O(n^3)$ cases to calculate because there are $N$ time steps, and at each time step $t$, we have a distribution on $P_A$ that consists of the original prior updated after observing $j=0,\dots,t$ heads and $k=0,\dots,t-j$ tails. But this should be reduced with your observation that we need only consider strategies that try $A$ for some amount of time, then (optionally) flip $B$ for the rest of the time.

Why this is optimal: Assume that the strategy is optimal at time $t+1$ for the specified prior distribution. But the "correct" prior distribution is always exactly the one we plug in to the formula: After observing a heads, the correct distribution over $P_A$ is precisely $posterior(prior,heads)$, and so on. When I say correct, what I mean is that the posterior gives the exact distribution over $P_A$ given that $P_A$ is drawn from the prior and these outcomes are observed. So we really are maximizing over the "average case" in each given scenario.


The definition of a logic $\mathcal{L}$ capturing a complexity class $\mathcal{C}$ requires that the problem of evaluating $\mathcal{L}$-formulas is itself in $\mathcal{C}$.  However, evaluating formulas of the logic you suggest is coNP-complete (in fact, even without the fixed points).

Membership. You can determine that $\mathfrak{A}\nvDash^* \varphi$ by guessing a linear order and checking that it makes the formula false.
Completeness. A graph is non-3-colourable if, and only if, every linear order $\leq$ on its vertices satisfies the property that, for every pair $x$, $y$ of vertices, at least one of the the vertex sets $\{z\mid z<x\}$, $\{z\mid x\leq z<y\}$ and $\{z\mid y\leq z\}$ contains an edge.  This property is definable without using the fixed point operator.

You could try to get around this by defining the formulas of the logic to be only the order-invariant $\mathrm{IFP}(\tau+<)$ formulas, i.e., those that are true for some linear order if, and only if, they are true for all. But it's an easy consequence of Trakhtenbrot's theorem that this class of formulas is undecidable.


The maximum of $I(X:Y)$ in your problem is $$H(Y) - H(Z) \cdot \bigg|\Pr[Y = 0|Z = 0] - \Pr[Y = 0|Z = 1] \bigg|. $$

Let me first demonstrate an example for which this maximum is attained. Denote $\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1]$. Sample $X$ uniformly at random from $[0, 1]$ and then sample $Z$ independently from $X$ according to the corresponding marginal distribution of $\mathcal{D}$. Next, define:
$$Y = \begin{cases} 0 & \mbox{if $X\le\alpha, Z = 0$ or $X\le \beta, Z = 1$},\\ 1 &\mbox{otherwise.}\end{cases}$$

So we have 3 jointly distributed random variables $X, Y, Z$. It is clear that $(Y, Z)\sim\mathcal{D}$ and $I(X:Z) = 0$. Let's compute $I(X:Y)$. As $I(X:Y) = H(Y) - H(Y|X)$, we only have to deal with $H(Y|X)$. Assume WLOG that $\alpha \le \beta$. Then if $X\le \alpha$ or $X > \beta$, then $Y$ is constant. If $\alpha < X \le \beta$, then $Y = 1- Z$. I.e., the conditional distribution of $Y$ given $X = r\in (\alpha, \beta]$ is equal to the conditional distrbitution of $1 - Z$ given $X = r\in(\alpha, \beta]$. But $Z$ is independent of $X$, which means that this conditional distribution is just the distribution of $Z$. In other words, $H(Y|X) = \Pr[\alpha < X \le \beta] \cdot H(Z) = (\beta - \alpha) H(Z)$, as required.

There is a technical problem that $X$ takes infinitely many values. However, we can assume that $X$ takes just $3$ values with probabilities $\alpha, \beta - \alpha, 1 - \beta$. I.e., we partition $[0, 1]$ into $3$ intervals $[0, \alpha], (\alpha, \beta], (\beta, 1]$, take a random point $P$ in $[0, 1]$ and let $X$ be the interval of the partition containing $P$. The rest of the argument works similarly.

Note that in this example $Y$ is a function of $X$ and $Z$.
First, let me show that the maximum in your problem is indeed attained when  $Y$ is a function of $X$ and $Z$.

Lemma. Assume that $X, Y, Z$ are 3 jointly distributed random variables satisfying $(Y,Z) \sim\mathcal{D}$ and $I(X:Z) = 0$.Then there are 3 jointly distributed random variables $X^\prime, Y^\prime, Z^\prime$ such that $(Y^\prime, Z^\prime)\sim\mathcal{D}$, $I(X^\prime:Z^\prime) = 0$, $I(X^\prime:Y^\prime) \ge I(X:Y)$ and $Y^\prime$ is a function of $X^\prime$ and $Z^\prime$.

Proof. Sample $(X_1, Z^\prime)$ according to the distribution of $(X, Z)$ and then sample $P$ uniformly from $[0, 1]$ and independently from $(X_1, Z^\prime)$. Set $X^\prime = (X_1, P)$. Let $x$ be the value of $X_1$ and $z$ be the value of $Z^\prime$. Define
$$Y^\prime  = \begin{cases} 0 & \mbox{if $P \le \Pr[Y = 0| X = x, Z = z]$},\\ 1 &\mbox{otherwise.}\end{cases}.$$
First of all, $X^\prime$ and $Z^\prime$ are independent and $Y^\prime$ is a function of $X^\prime$ and $Z^\prime$ by construction. Further, it is clear that the distribution of $(X_1, Y^\prime, Z^\prime)$ is identical to the distribution of $(X, Y, Z)$. In particular this means that $(Y^\prime, Z^\prime) \sim\mathcal{D}$. Moreover, this gives us the following $I(X^\prime:Y^\prime) = I(X_1, P:Y^\prime) \ge I(X_1:Y^\prime) = I(X:Y)$ and the lemma is proved. Once again, there is a technical problem with the fact that $P$ takes infinitely many values, but it is clear that $P$ can be ``discretized'' as above. $\blacksquare$

To finish the argument we have to show that for any $3$ jointly distributed random variables $X, Y, Z$ such that $(Y, Z)\sim\mathcal{D}, I(X:Z) = 0$ and $Y = f(X, Z)$ for some function $f$ it holds that:
$$I(X:Y) \le H(Y) - H(Z) \cdot |\beta - \alpha|,$$
where $\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1].$

Let $W$ be the set of values of $X$. Next, define:
$$W_0 = \{x\in W \mid f(x, 0) = 0\}, \qquad W_1 = \{x\in W \mid f(x, 1) = 0\}.$$
Note that $\alpha = \Pr[f(X, Z) = 0|Z = 0] = \Pr[f(X, 0) = 0|Z = 0] = \Pr[f(X, 0) = 0] = \Pr[X\in W_0]$ (in the third equality we use the fact that $Z$ and $X$ are independent). Similarly, $\beta = \Pr[X\in W_1]$. Now, assume WLOG that $\alpha \le \beta$. Note that $\Pr[X\in W_1\setminus W_0] \ge \beta - \alpha$. On the other hand, $X\in W_1\setminus W_0$ implies that $Y = 1 - Z$. Hence $H(Y|X) \ge (\beta - \alpha) H(Z)$ and
$$I(X:Y) = H(Y) - H(Y|X) \le H(Y) - H(Z) (\beta - \alpha).$$


Why does Odlyzko improvement of Shor's Algorithm reduces the number of trials to $O(1)$


Approximate counting problem capturing BQP

Emanuele: Unfortunately, we don't know of any black-box problem capturing BQP as simple as the one you mentioned capturing BPP.

Intuitively, this is because it's hard to talk about BQP without bringing in unitarity in one form or another.  The ability to sum both positive and negative numbers is what makes BQP more powerful than BPP, but then unitarity is what makes BQP less powerful than #P! :-)

Having said that, besides the Dawson et al. paper that Martin Schwarz linked to, you should definitely check out this and this by Janzing and Wocjan, which give "surprisingly classical-looking" promise problems that capture BQP.

Also, let S ⊆ {0,1}n, and consider a Boolean function f:S→{0,1}.  Then I have a conjecture from years ago which says that Q(f), the bounded-error quantum query complexity of f, is polynomially related to the minimum degree of a real polynomial p:Rn→R such that

(i) p(x)∈[0,1] for all x∈{0,1}n, and

(ii) |p(x)-f(x)| ≤ ε for all x∈S.

If this conjecture holds, then an "approximate counting problem capturing BQP" would simply be to approximate the value of a polylog(n)-degree polynomial p:Rn→R, at a specified point on the Boolean cube, given that p is bounded everywhere on the Boolean cube.  This might be about as close as one could get to an answer to your question.


Complexity of Localization in Wireless Networks

It is actually NP-hard. See the following paper for references.

Sriram V. Pemmaraju, Imran A. Pirwani: Good Quality Virtual Realization of Unit Ball Graphs. ESA 2007: 311-322


polygonal triangulation and 3-colorability

You seem to be confusing two concepts: triangulations of simple polygons are maximal outerplanar graphs (and every maximal outerplanar graph is Hamiltonian); maximal planar graphs are something else.

But anyway: no.

A maximal planar graph is 3-colorable iff it is Eulerian (if it is not Eulerian, then the odd wheel surrounding a single odd vertex requires four colors, and if it is Eulerian then a 3-coloring may be obtained by coloring a triangle and then extending the coloring in the obvious way to adjacent triangles).

For an example of an Eulerian maximal planar graph that is not Hamiltonian, glue nine octahedra together: one in the center and one attached to each of its faces. The dihedral angle of a regular octahedron is less than 120 degrees so there's plenty of room to do this without even having to distort anything.

If the graph of this polyhedron could have a Hamiltonian cycle, then it would visit the central octahedron's six vertices in an order that is also a Hamiltonian cycle, together with six paths connecting those six vertices. But each of those six paths can only visit one of the eight side octahedra that are glued onto the center, so two of the side octahedra must remain unvisited, contradicting the Hamiltonicity of the cycle.


Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases.


Function input to output size relationship. What is it? Any notable research on it?

I think it's improper to call this measure 'complexity'. A more apt name would be 'input to output size relation'.

Note that, strictly speaking, this is a property of the problem you are solving, not of the particular algorithm you use to solve the problem.

In the case of the compression problem, if you mean lossless compression of arbitrary binary data, then the average compression ratio is never less than 1 (and it's typically strictly greater than 1).


Fast sparse boolean matrix chain product

This was too long to be a comment -- I wonder if those matrices have structure that make them behave differently from random matrices. Products of random sparse matrices go to zero or become non-sparse quickly.
Here's a simple experiment -- take 200 random binary 50x50 matrices, and plot number of non-zeros as a function of number of matrices multiplied. Plots below show standard deviation over 2000 runs. First plot is for 2% sparsity, second plot is for 3%

(source: yaroslavvb.com)

(source: yaroslavvb.com)
this took 3 minutes on my laptop using standard matrix multiplication


Depends on your definition of NPI. If A is incomplete for Turing reductions, the answer is yes since SAT is not in $P^A$.

If A is just many-one incomplete then we don't know how to prove it. We have a relativized world with there is a set A in NP such that A is not NP-complete via many-one reductions but SAT can be computed by a single query to A. (Theorem 1.9 in this paper).


There are several notions of randomness in computability theory (/the arithmetic hierarchy; lookup "Martin-Lof randomness", "Kurtz random", "Schnorr random", ...), but I think the ones that are analogous to $\mathsf{BPP}$ become trivial in the setting of the arithmetic hierarchy. The reason is essentially that a randomized Turing machine with bounded error can be simulated by a deterministic one: the deterministic one simulates the random one with all settings of the randomness and then takes the majority vote. If the original machine took time $t(n)$ then the new machine takes time $2^{t(n)}$, which is why this trick tends not to work in the resource-bounded case.

(Though of course it works for any deterministic time-bounded class where if time bound $t(n)$ is allowed in the class then so is $2^{t(n)}$. In particular, this trick works in $\mathsf{DTIME}(\mathcal{E}^4)$, where $\mathcal{E}^4$ is the fourth level of the Grzegorczyk hierarchy of primitive recursive functions. But that's still a pretty big class.)


Lexicographically minimal topological sort of a labeled DAG

With multiple copies of the same label allowed, the problem is NP-hard, via a reduction from cliques in graphs. Given a graph $G$ in which you want to find a $k$-clique, make a DAG with a source vertex for each vertex of $G$, a sink vertex for each edge of $G$, and a directed edge $xy$ whenever $x$ is a vertex of $G$ that forms an endpoint of edge $y$. Give the vertices of $G$ the label value $1$ and the edges of $G$ the label value $0$.

Then, there is a $k$-clique in $G$ if and only if the lexicographically first topological order forms a sequence of $k$ $1$'s and $\tbinom{k}{2}$ $0$'s, with $i-1$ $0$'s following the $i$th $1$. E.g. a six-vertex clique would be represented by the sequence $110100100010000100000$. This is the lexicographically smallest sequence that could possibly begin a topological ordering of a labeled DAG given by this construction (replacing any of the $1$'s by $0$'s would give a sequence with more edges than could be found in a simple graph with that many vertices) and it can only be the beginning of a topological ordering when $G$ contains the desired clique.


For which algorithms is there a large gap between the theoretical analysis and reality?

The most glaring example is of course the Simplex method that runs quickly in practice, suggesting poly-timeness, but takes exponential time in theory.  Dan Spielman just got the Nevanlinna award to a large extent for explaining this mystery.

More generally, many instances of Integer-programming can be solved quite well using standard IP-solvers, e.g. combinatorial auctions for most distributions attempted on significant sized inputs could be solved -- http://www.cis.upenn.edu/~mkearns/teaching/cgt/combinatorial-auctions-survey.pdf


It is known that, for $G$ of bounded treewidth, the Tutte polynomial $T(G;x,y)$ can be evaluated at any $(x,y)$ using $O(n)$ arithmetic operations. If $G$ is connected, then $t(G)=T(G;1,1)$.


This paper by Régis Barbanchon might be of interest. From the abstract:

We prove that the Satisfiability (resp. planar Satisfiability) problem
is parsimoniously P-time reducible to the 3-Colorability (resp. Planar
3-Colorability) problem, that means that the exact number of solutions
is preserved by the reduction, provided that 3-colorings are counted
modulo their six trivial color permutations. In particular, the
uniqueness of solutions is preserved, which implies that Unique
3-Colorability is exactly as hard as Unique Satisfiability in the
general case as well as in the planar case...


If the learning algorithm is proper (i.e. it always produces a hypothesis from the class $F_n$), then it also gives a testing algorithm -- simply run the learning algorithm, and see whether the hypothesis it produced has error rate $<\epsilon$, which can be done with only $\approx 1/\epsilon^2$ samples. If it does, since the hypothesis is in $F_n$, this is a constructive proof that the function you are testing has distance at most $\epsilon$ from $F_n$. If the algorithm was a PAC learning algorithm for $F_n$, then when $f \in F_n$, it must generate such a hypothesis. So any proper learning algorithm can be converted to a testing algorithm with only an additional $\approx 1/\epsilon^2$ samples at most.

Moreover, if you are only worried about sample complexity and not computational efficiency, then without loss of generality you can always use a proper PAC learning algorithm. Since the sample complexity of learning is $\mathrm{VCDIM}(F_n)/\epsilon^2$, this means you can always test with at most this many samples.

However, generally testing is easier than learning. For example, linear functions in $d$ dimensions require $d$ samples to learn, but only a constant number of samples to test.


Counting length-k increasing subsequences in a permutation

According to Kim, finding one such sequence is equivalent to finding a maximum independent set in a permutation graph and can be done in $O(n\log n)$ time. The running time you're looking for suggests you already knew about that, but if not, looking at citing papers might help.

Update: actually, the complement of a permutation graph is also a permutation graph, and the complement of an independent set is a clique, so unless I'm missing something, maximising the number of increasing sequences of length $k$ in your permutation should be equivalent to partitioning a permutation graph into as many $K_k$'s as possible. Surely this has been studied, at least for triangles...


Smoothed analysis of approximation algorithms

The paper by Bläser, Panagiotou, and Rao deals with concentration of the tour produced by Christofides' algorithm. No average-case approximation ratio is claimed, except for some experimental results.

The paper by Röglin and Vöcking (Math. Program., 2007) and an earlier paper by Beier and Vöcking (SIAM J. Comput., 2006) roughly state that smoothed polynomial time is equivalent to randomized pseudo-polynomial time. Here, pseudo-polynomial means running-time polynomial in the input size and the magnitude of the coefficients that are perturbed. This rules out smoothed polynomial complexity for strongly NP-hard optimization problems (unless NP=ZPP).

Concerning smoothed analysis and approximation, there are only very few papers that address specific problems or algorithms (Englert, Röglin, and Vöcking for the 2-opt heuristic for TSP; Bläser, Manthey, and Rao as well as Curticapean and Künnemann for partitioning heuristics; Karger and Onak for multi-dimensional packing). However, I am not aware of any structural connections between inapproximability and smoothed analysis.


Multiple-sources dominator trees: compact representation and fast algorithm?

I think it's really hard to do that. First of all, for one source dominator tree, there are several dominator points for a vertex. If we want to use "Lengauer-Tarjan algorithm", we can't avoid using tree structure. But how can we save a tree with less than $o(n)$ space? It means that for $n$ source dominator tree, we have to use at least $o(n^2)$ space unless we create a new structure which can represent dominator's information more effective.

For a dag, I remember there is a another algorithm to find whether two vertices share the same dominator for one source. Maybe it will help, you may search uva12671 for more information. (Actually, I am thinking a developing problem about this recently.)

Finally, I am also fascinated by it. If anybody has a new idea, please contact me anytime.