Convergence and representation theorems for machine learning I come from a pure math background and am not very familiar with machine learning. So, I'll start with an example to compensate for my confused grasp of the terminology.

Let's say we have a function $f:X \to Y$, and we want to develop a neural network to compute this function. For instance, $X$ could be $\{0, 1, ... 255\}^N$ for some large $N$, and $Y$ could be $\{0, 1\}$, if we wanted to build a network that performs a binary classification on images of $N$ pixels. We have some algorithm which adjusts, maybe stochastically or maybe deterministically, the weights and parameters of our network, creating a sequence of networks which should converge to $f$.

What theorems exist to guarantee that we do indeed converge to $f$, or even that a network exists to represent $f$? If we don't want to make assumptions about $f$, we would need some theorem establishing that given any function $f$, and any initial network, the sequence of networks generated by the learning algorithm will converge to $f$.

I'm not just interested in neural nets, though. Are there textbooks on machine learning which cover this sort of thing in depth? What keywords should I be looking out for?

I recommend Neural Network Learning: Theoretical Foundations by Anthony and Bartlett. You'll find exhaustive answers to your questions there. Very briefly, theoretical learning problems tend to separate very cleanly into two orthogonal components: statistical and computational. Thus, a universal learner unconstrained by computational issues could construct the smallest Turing machine (or MATLAB program) consistent with the input data; such a learner would be near-optimal statistically in a well-defined sense.

Nobody studies such learners (beyond intro-class homework problems) because they are computationally infeasible (actually uncomputable, in my example). When computational constraints enter the picture, it becomes much more nuanced: often times, what is the obvious course of action for the statistician is dismissed out of hand as infeasible by the algorithmist.

In any case, the Anthony+Bartlett book seems like the perfect introduction for a mathematically inclined beginner.


Are there Conservation Laws in Complexity Theory? Let me start with some examples. Why is it so trivial to show CVP is in P but so hard to show LP is in P; while both are P-complete problems.

Or take primality. It is easier to show composites in NP than primes in NP (which required Pratt) and eventually in P. Why did it have to display this asymmetry at all?

I know Hilbert, need for creativity, proofs are in NP etc. But that has not stopped me from having a queasy feeling that there is more to this than meets the eye.

Is there a quantifiable notion of "work" and is there a "conservation law" in complexity theory? That shows, for example, that even though CVP and LP are both P-complete, they hide their complexities at "different places" -- one in the reduction (Is CVP simple because all the work is done in the reduction?) and the other in expressibility of the language.

Anyone else queasy as well and with some insights? Or do we shrug and say/accept that this is the nature of computation?

This is my first question to the forum: fingers crossed.

Edit: CVP is Circuit Value Problem and LP is Linear Programming.  Thanks Sadeq, for pointing out a confusion.

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

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

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

Note on Conservation Laws

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


Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$ Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq \mathsf{P}^{\mathsf{NP}^X}$ — but does not give a reference for this result.  Why does this hold?  Or where can a proof be found?

This question is partly motivated by my answer to the question “What is known about multi-prover interactive proofs with short messages?” by Joe Fitzsimons.

I posted this question on math.stackexchange.com on October 2, but I did not receive any answer and deleted the question on math following this post on meta.math.

The oracle goes back to Stockmeyer in 1983. Heller gave the stronger result that : $BPP = EXP^{NP}$ in a relativized world in 1986. Karpiniski and Verbeek (mentioned in the comments) reprove Heller's result.


What exactly are the classes FP, FNP and TFNP? In his book Computational Complexity, Papadimitriou defines FNP as follows:

Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced relation $R_L$ such that for all strings $x$: There is a string $y$ with $R_L(x,y)$ if and only if $x\in L$. The function problem associated with $L$, denoted $FL$, is the following computational problem:
Given $x$, find a string $y$ such that $R_L(x,y)$ if such a string exists; if no such string exists, return "no".
The class of all function problems associated as above with language in NP is called FNP. FP is the subclass resulting if we only consider function problems in FNP that can be solved in polynomial time.
(...)
(...), we call a problem $R$ in FNP total if for every string $x$ there is at least one $y$ such that $R(x,y)$. The subclass of FNP containing all total function problems is denoted TFNP.

In a venn diagram in the chapter overview, Papadimitriou implies that FP $\subseteq$ TFNP $\subseteq$ FNP.
I have a hard time understanding why exactly it holds that FP $\subseteq$ TFNP since problems in FP do not have to be total per se.
To gain a better understanding, I've been plowing through literature to find a waterproof definition of FP,FNP and sorts, without success.
In my very (humble) opinion, I think there is little (correct!) didactic material of these topics.
For decision problems, the classes are sets of languages (i.e. sets of strings).
What exactly are the classes for function problems? Are they sets of relations, languages, ... ? What is a solid definition?

Emil Jerabek's comment is a nice summary, but I wanted to point out that there are other classes with clearer definitions that capture more-or-less the same concept, and to clarify the relation between all these things.

[Warning: while I believe I've gotten the definitions right, some of the things below reflect my personal preferences - I've tried to be clear about where that was.]

In the deterministic world, a function class is just a collection of functions (in the usual, mathematical sense of the word "function", that is, a map $\Sigma^* \to \Sigma^*$). Occasionally we want to allow "partial functions," whose output is "undefined" for certain inputs. (Equivalently, functions that are defined on a subset of $\Sigma^*$ rather than all of it.)

Unfortunately, there are two different definitions for $\mathsf{FP}$ floating around, and as far as I can tell they are not equivalent (though they are "morally" equivalent).

$\mathsf{FP}$ (definition 1) is the class of functions that can be computed in polynomial-time. Whenever you see $\mathsf{FP}$ and its not in a context where people are talking about $\mathsf{FNP}, \mathsf{TFNP}$, this is the definition I assume.

In the nondeterministic world things get a little funny. There, it is convenient to allow "partial, multi-valued functions." It would be natural to also call such a thing a binary relation, that is, a subset of $\Sigma^* \times \Sigma^*$. But from the complexity point of view it is often philosophically and mentally useful to think of these things as "nondeterministic functions." I think many of these definitions are clarified by the following classes (whose definitions are completely standardized, if not very well-known):

$\mathsf{NPMV}$: The class of "partial, multi-valued functions" computable by a nondeterministic machine in polynomial time. What this means is there is a poly-time nondeterministic machine, and on input $x$, on each nondeterministic branch it may choose to accept and make some output, or reject and make no output. The "multi-valued" output on input $x$ is then the set of all outputs on all nondeterministic branches when given $x$ as input. Note that this set can be empty, so as a "multi-valued function" this may only be partial. If we think of it in terms of binary relations, this corresponds to the relation $\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$.
$\mathsf{NPMV}_t$: Total "functions" in $\mathsf{NPMV}$, that is, on every input $x$, at least one branch accepts (and therefore makes an output, by definition)
$\mathsf{NPSV}$: Single-valued (potentially partial) functions in $\mathsf{NPMV}$. There is some flexibility here, however, in that multiple branches may accept, but if any branch accepts, then all accepting branches must be guaranteed to make the same output (so that it really is single-valued). However, it is still possible that no branch accepts, so the function is only a "partial function" (i.e. not defined on all of $\Sigma^*$).
$\mathsf{NPSV}_t$: Single-valued total functions in $\mathsf{NPSV}$. These really are functions, in the usual sense of the word, $\Sigma^* \to \Sigma^*$. It is a not-too-hard exercise to see that $\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ (using Def 1 for FP above).

When we talk about potentially multi-valued functions, talking about containment of complexity classes isn't really useful any more: $\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$ unconditionally simply because $\mathsf{NPSV}$ doesn't contain any multi-valued "functions", but $\mathsf{NPMV}$ does. Instead, we talk about "c-containment", denoted $\subseteq_c$. A (potentially partial, multi-valued) function $f$ refines a (potentially partial multi-valued) function $g$ if: (1) for every input $x$ for which $g$ makes some output, so does $f$, and (2) the outputs of $f$ are always a subset of the outputs of $g$. The proper question is then whether every $\mathsf{NPMV}$ "function" has an $\mathsf{NPSV}$ refinement. If so, we write $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$.

$\mathsf{PF}$ (a little less standard) is the class of (potentially partial) functions computable in poly-time. That is, a function $f\colon D \to \Sigma^*$ ($D \subseteq \Sigma^*$) is in $\mathsf{PF}$ if there is a poly-time deterministic machine such that, on inputs $x \in D$ the machine outputs $f(x)$, and on inputs $x \notin D$ the machine makes no output (/rejects/says "no"/however you want to phrase it).

$\mathsf{FNP}$ is a class of "function problems" (rather than a class of functions). I would also call $\mathsf{FNP}$ a "relational class", but really whatever words you use to describe it you need to clarify yourself afterwards, which is why I'm not particularly partial to this definition. To any binary relation $R \subseteq \Sigma^* \times \Sigma^*$ there is an associated "function problem." What is a function problem? I don't have a clean mathematical definition the way I do for language/function/relation; rather, it's defined by what a valid solution is: a valid solution to the function problem associated to $R$ is any (potentially partial) function $f$ such that if $(\exists y)[R(x,y)]$ then $f$ outputs any such $y$, and otherwise $f$ makes no output. $\mathsf{FNP}$ is the class of function problems associated to relations $R$ such that $R \in \mathsf{P}$ (when considered as a language of pairs) and is p-balanced. So $\mathsf{FNP}$ is not a class of functions, nor a class of languages, but a class of "function problems," where "problem" here is defined roughly in terms of what it means to solve it.
$\mathsf{TFNP}$ is then the class of function problems in $\mathsf{FNP}$ - defined by a relation $R$ as above - such $R$ is total, in the sense that for every $x$ there exists a $y$ such that $R(x,y)$.

In order to not have to write things like "If every $\mathsf{FNP}$ (resp., $\mathsf{TFNP}$) function problem has a solution in $\mathsf{PF}$ (resp., $\mathsf{FP}$ according to above definition), then..." in this context one uses Definition 2 of $\mathsf{FP}$, which is:

$\mathsf{FP}$ (definition 2) is the class of function problems in $\mathsf{FNP}$ which have a poly-time solution. One can assume that the solution (=function) here is total by picking a special string $y_0$ that is not a valid $y$ for any $x$, and having the function output $y_0$ when there would otherwise be no valid $y$. (If needed, we can modify the relation $R$ by prepending every $y$ with a 1, and then take $y_0$ to be the string 0; this doesn't change the complexity of anything involved).

Here's how these various definitions relate to one another, $\mathsf{FNP} \subseteq \mathsf{FP}$ (definition 2, which is what you should assume because it's in a context where it's being compared with $\mathsf{FNP}$) is equivalent to $\mathsf{NPMV} \subseteq_c \mathsf{PF}$. $\mathsf{TFNP} \subseteq \mathsf{FP}$ (def 2) is equivalent to $\mathsf{NPMV}_t \subseteq_c \mathsf{FP}$ (def 1).


Submodular functions: reference request I would be very much interested in references to the theory of submodular functions (from basics to advanced).

In particular, I am studying approximations to hard optimization problems and I want to develop my foundations in submodular functions as they are relevant to the optimization problems I have been studying.

Thanks in advance.

The references I use (and like) are selected chapters in Schrijver's 3-volume Combinatorial Optimization: Polyhedra and Efficiency (Springer) and Vygen's Combinatorial Optimization (Springer). There is a book devoted to submodular functions by Fujishige: Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics, North-Holland (2nd edition from 2005).


What is the fastest algorithm for calculating nth term of Fibonacci sequence? If we exclude methods that include precalculating of all Fibonacci numbers up to a sufficiently large number of n what would be the fastest  algorithm for calculating nth term of Fibonacci sequence ?

I guess that Iterative and Matrix algorithms should be faster than Analytic and Recursive algorithms , ( see this paper ) .

On this page I have found five different algorithms . According to author the fastest is a Matrix algorithm that uses  O(log n) arithmetic operations .

According to this Project Nayuki link, Fast doubling is even faster than Fast Matrix, because redundant calculations are removed.


Method of Algorithm Study I am a Computer Science student who is greatly intrigued by algorithms.

However I am curious whether computer scientists who study algorithms teach themselves to formally analyze algorithms and prove the correctness of algorithms as is done in the CLR book, or do they mostly focus on the technique and design of the algorithms.

Theoretical computer scientists both design algorithms and prove their correctness and running time. For some algorithms, the correctness and running time are evident, while others require proof.
For the latter, without a proof it's hard to know whether the algorithm actually does what it should.
There are countless examples of small subtleties in algorithms that make enormous differences for performance (e.g., take a look at union-find data structures in CLRS).

An alternative could be running the algorithm and experimenting with it.
This is often an excellent first step when you try to figure out if you actually have a good algorithm or not.
Experimenting is especially useful when a rigorous analysis seems hard, or when you're still trying to figure out the exact formulation of the algorithm's task (e.g., think of the Netflix challenge, where you want to recommend movies to users given data about their history. It's not even clear what it is exactly that you want your algorithm to do).

Ultimately, though, a clear understanding of what the algorithm guarantees is sought after, and for the most part, you need a proof for that.


Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded? Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity.

Background/Motivation: Coming from information theory, I recently learned about a connection of entropy and Kolmogorov complexity: Loosely speaking, entropy of a random variable is the expected rate at which the Kolmogorov complexity of a long sample sequence increases per sample. [Elements of Information Theory, p. 154] Kolmogorov complexity can therefore capture the notion of entropy, but it is more general than that. Hereby, and in the following, whenever I write complexity, I implicitly refer to the complexity given the length of the output.

For non-zero entropy, the Kolmogorov complexity of initial segments of an infinite sequence of samples from a random variable is therefore unbounded. I was wondering whether this is equivalent to the fact that an infinite sequence of samples is uncomputable. This led me to the hypothesis in the title: Is a binary sequence computable if and only if the Kolmogorov complexity of its initial segments is bounded?

If the hypothesis was true, then computability could be understood as an indicator that the "amount of information" in a sequence is finite. In some sense, the initial segment complexities would allow a more finely graded characterization of infinite sequences than just "computable" and "uncomputable". We could get a notion of "information content" and "information rate" of infinite sequences by analyzing the size of the bound or, in the unbounded case, the rate/type of growth, as in the entropy case above. My question boils down to whether "computable" and "uncomputable" are regions on this scale.

If the hypothesis is true, I'd be interested in whether this perspective is useful for TCS research. If yes, are there references elaborating this idea? If not, why not?

What I found in literature: It is shown that a sequence is Martin-Löf random iff there is a constant $c$ so that there are infinitely many initial segments with complexity greater than $n - c$ where $n$ is the segment length. [Randomness, p. 18]

This means that random sequences have unbounded initial segment complexity. Since they are not computable, the hypothesis is true at least for this case. If I am not mistaken, a similar argument could even be made for a weaker form of randomness, since Mises-Wald-Church random sequences cannot have initial segment complexity of O(log n). [The complexity of stochastic sequences]

What's missing for a proof:

$\Leftarrow$:
Assume a sequence is computable. We know that a program generate_bit(n) exists that generates any bit of the sequence. Now, we can build a program generate_initial_segment(n) = concat(map(1..n, generate_bit)) that, given the segment length $n$, generates the initial segment up to position n by invoking generate_bit $n$ times and concatenating the results. The Kolmogorov complexity of this task is therefore bounded by the length of this program. ☐

$\Rightarrow$: I struggle to prove/disprove this direction, namely: If initial segment complexity is bounded, is a sequence always computable?

Update: The last two pages of A variant of the Kolmogorov concept of complexity prove this direction.

Chaitin  in his 1976 paper

Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029.

studied sets such that there exists  b ∈ℕ  with

$$\forall n\quad C(A\upharpoonright n)\leq C(n)+b.$$

where $C$ denotes the plain Kolmogorov complexity. These sets are known as C-trivial sets. Chaitin showed they coincide with the computable sets.

Interestingly, this is not so for the prefix-free Kolmogorov complexity version, the K-trivial sets.


Conjectures implying Four Color Theorem Four Color Theorem (4CT) states that every planar graph is four colorable. There are two proofs given by [Appel,Haken 1976] and [Robertson,Sanders,Seymour,Thomas 1997]. Both these proofs are computer-assisted and quite intimidating.

There are several conjectures in graph theory that imply 4CT. Resolution of these conjectures probably requires a better understanding of the proofs of 4CT. Here is one such conjecture :

Conjecture : Let $G$ be a planar graph, let $C$ be a set of colors and $f : C \rightarrow C$ a fixed-point free involution. Let $L = (L_v : v \in V(G))$ be such that

$|L_v| \geq 4$ for all $v \in V$ and
if $\alpha \in L_v$ then $f(\alpha) \in L_v$ for all $v \in V$, for all $\alpha \in C$.

Then there exists an $L$-coloring of the graph $G$.

If you know such conjectures implying 4CT, please list them one in each answer. I could not find a comprehensive list of such conjectures.

4CT is equivalent to:

Coloring a hypergraph induced by a finite family of discs (not necessarily interior disjoint but also discs that might have arbitrary overlaps) with at most four colors $[1]$.
The proposition that every planar triangulation with more than three vertices is the union of two connected bipartite graphs, each with no isthmus $[2]$.
A combinatorial problem about the three-dimensional vector cross product algebra $[3]$.
The proposition that the grammar G is totally ambiguous $[4]$.
For any positive integer $n$, there exists at least a signable path joining two permutations of $S_n$.
An algebraic equivalent of the four-color theorem is presented. The equivalent is the assertion of non-membership of a family of polynomials in a family of polynomial ideals over a particular finite field $[6]$.

Smorodinsky S. On the chromatic number of geometric hypergraphs.
Mabry R. Bipartite Graphs and the Four-Color Theorem.
Kauffman L.H. Map coloring and the vector cross product.
Cooper B. J. et al. Toward a language theoretic proof of the four color theorem.
Eliahou S. et al. Signed permutations and the four color theorem.
Howard L. An Algebraic Reformulation of the Four Color Theorem.


Complexity of finding a graph separator with a given property Are there any known results on the complexity of finding a separator (of any size) satisfying a given property?

I know that a clique separator is easy (polynomial time) to find and also know that many papers consider the problem of finding small separators or separators that leave connected components of size at most a fraction of the size of the original graph. But what if one need a separator with other properties, say, a cubic, bipartite or 2-connected separator? It's also easy to create properties which are NP-hard to decide, hence it would be interesting to distinguish between the P and NPC cases.

Edit: Someone (which is not a user of this website) just told me that the problem is polynomial if the property is "has a universal vertex" and NP-complete if the property is "induces an independent set" or "induces a complete bipartite graph".

Our paper:

http://arxiv.org/abs/1110.4765

shows that many of these problems are fixed-parameter tractable, i.e., we can decide in time f(k)*O(n+m) if an s-t separator of size k exists. This is true for example for the problem of finding a connected s-t separator, or a separator that is an independent set, or a separator that induces a bipartite graph. A forthcoming paper addresses the problem of finding a 2-connected s-t separator.


Partition Number of a Matrix Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known either $$p<r^{\log^dr}\mbox{ or }p<\sigma^{\log^c\sigma}\mbox{ or }p<(\sigma^{\log^c\sigma}r^{\log^dr})$$ hold true for some $c,d>0$?

Can $p<\sigma^{c}$ be true?

The log of the partition number is a lower bound on the deterministic communication complexity and the square of the log of the partition number is an upper bound. In other words, if $CC$ is the communication complexity, then we know that $\log_2 p \leq CC \leq (\log_2 p)^2$: this is Theorem 2.11. in the Kushilevitz-Nisan monograph. It is an open problem whether $CC = \Theta(\log p)$, and the biggest known gap is a factor $2$.

So $p < r^{\log^d r}$ for a constant $d$ implies that the communication complexity is at most $\log^{2d+2} r$. In other words there exists such a constant $d$ if and only if the log rank conjecture is true. I believe the best we know is $p < r^{C\sqrt{r}}$ for a constant $C$, by a recent result of Lovett.


Is there a sensible notion of an approximation algorithm for an undecidable problem? Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them.  For example, the halting problem is undecidable, but practical progress can be made on creating tools for detecting potential infinite loops in your code.  Tiling problems are often undecidable (e.g., does this polyomino tile some rectangle?) but again it is possible to advance the state of the art in this area.

What I am wondering is if there is any decent theoretical method of measuring progress on solving undecidable problems, that resembles the theoretical apparatus that has been developed for measuring progress on NP-hard problems.  Or does it seem that we are stuck with ad hoc, I-know-progress-when-I-see-it assessments of how much particular breakthroughs advance our understanding of undecidable problems?

Edit: As I think about this question, it occurs to me that perhaps parameterized complexity may be relevant here.  An undecidable problem may become decidable if we introduce a parameter and fix the value of the parameter.  I'm not sure if this observation is of any use, though.

In the case of the halting problem, the answer is "not yet". The reason is that the standard logical method for characterizing how hard a program's termination proof is (eg, ordinal analysis) tends to lose too much combinatorial and/or number-theoretic structure.

The state of the art in practical termination analysis of imperative programs is something called "rank-function synthesis" (Byron Cook has a forthcoming book, Proving Program Termination, on the subject from CUP). The idea is to compute a linear function of the program's variables' values now and at the previous step, which serves as a termination metric. (One cool thing about this method is that it uses Farkas's lemma, which gives a neat geometric viewpoint to what's going on.) The interesting thing is that the tools built on this approach can do things like show the termination of the Ackerman function (which is non primitive recursive), but you can construct non-nested while loops which can defeat them (which only needs $\omega$ to show termination).

This means that there isn't a neat relationship between the proof-theoretic strength of the metalogic in which you show termination (this is very important in rewriting theory, for example) and the functions that techniques like rank-function synthesis can show termination for.

For the lambda calculus, we have a precise characterization of termination in terms of typability: a lambda term is strongly normalizing if and only if it is typeable under the intersection type discipline. Of course, this means that full type inference for intersection types is impossible, but it may also give a way of comparing partial inference algorithms.


Regularity Lemma for Sparse Graphs Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets such that most pairs of sets form bipartite expanders (the number of sets in the partition and the expansion parameter depend on the approximation parameter):

http://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemma

There are versions of this lemma for "well-behaving" sparse graphs, see, e.g.:

http://www.estatistica.br/~yoshi/MSs/FoCM/sparse.pdf

http://people.maths.ox.ac.uk/scott/Papers/sparseregularity.pdf

What surprises me about these formulations is that they only guarantee that most pairs of sets in the partition form bipartite expanders, and these bipartite expanders may be empty. So, in general sparse graphs, it's quite possible that all edges between different parts in the partition of the vertices don't belong to an expander.

I wonder whether there are formulations that give that most edges between parts are from an expander, or whether there's no hope for such a formulation.

Below is a long-winded answer, but tl;dr in the general case there is no hope for such a formulation, but for many of the particular classes of sparse graphs that have regularity lemmas this formulation exists.

For background, there are two popular versions of the SRL.  They are: for any fixed $\varepsilon > 0$ and any $n$-node graph $G = (V, E)$, one can partition $V = V_0 \cup V_1 \cup \dots \cup V_p$ into $p = O_{\varepsilon}(1)$ parts so that ...

  (Combinatorial Phrasing) (1) $|V_0| \le \varepsilon n$ and the sizes of any $V_1, \dots, V_p$ differ by at most $1$ ($V_0$ is called the "exceptional set"), and (2) all but $\varepsilon p^2$ pairs of the remaining parts $(V_i, V_j)$ satisfy
  $$\left|d(S, T) - d(V_i, V_j)\right| < \varepsilon \text{ for all } S \subseteq V_i, T \subseteq V_j$$
  (here $d(\cdot, \cdot)$ gives the density between the parts, i.e. the fraction of edges that are present).
  (Analytic Phrasing) Letting
  $$\mathop{disc}(V_i, V_j) := \max \limits_{S \subseteq  V_i, T \subseteq V_j} |V_i||V_j|\left|d(V_i, V_j) - d(S, T)\right|,$$
  we have
  $$\sum \limits_{i, j =0}^p \mathop{disc}(V_i, V_j) < \varepsilon n^2.$$

The "combinatorial phrasing" (I just made these names up, they are not standard) is the original and probably more famous one, whereas the "analytic phrasing" is more modern and related to graph limits, etc (I think it was popularized here).  To my eye the analytic one is the right formalization of "graph approximated by union of bipartite expanders," since it gives a control on the total "error" of such an approximation, and there is not an exceptional set in which to hide mass.  But at this point this is just cosmetic, because it's an easy but important lemma that these two phrasings are equivalent.  To get from Combinatorial to Analytic, just union bound the contribution to discrepancy of the irregular parts and exceptional set.  To get from Analytic to Combinatorial, just move any part that contributes too much discrepancy to the exceptional set and apply Markov's Inequality to control its mass.

Now to sparse regularity.  The goal of sparse regularity is to replace the $\varepsilon$ in the respective inequalities with $\varepsilon d(G)$, where $d(G)$ is the fraction of all possible edges present in $G$.  Critically, with this change, the two phrasings are no longer equivalent.  Rather, the Analytic phrasing is stronger: it still implies Combinatorial exactly as before, but Combinatorial does not generally imply Analytic, because (as anticipated in the OP) one can potentially hide a lot of density in the exceptional set or between the non-regular pairs of parts.  Indeed, this separation is formal: the lower bound graphs for the dense SRL (say, this one) imply that the Analytic Phrasing doesn't extend in general to sparse graphs, but the paper by Scott linked in the OP shows that the Combinatorial Phrasing actually does extend to all sparse graphs with no conditions.

The survey linked in the OP mostly talks about an SRL for "upper-regular" sparse graphs, which roughly means that the graph has no cuts that are denser than average by more than a constant factor.  For these particular graphs, the Combinatorial and Analytic phrasings are equivalent, because there can't be too much extra mass hidden in the exceptional parts so their contribution to discrepancy can be union bounded like in the dense case.  So these graphs have an "approximated by union of bipartite expanders" interpretation.

Finally, I should mention that there are many other hypotheses in the literature that also imply equivalence between these phrasings.  For example, $L_p$ Upper Regularity (defined here) is more general than Upper Regularity and is still enough to imply equivalence.  However, for this graph class and others, I am only aware of associated weak regularity lemmas.


What kind of string is produced by successive application of argmax M Fix a version of Solomonoff's universal distribution $\mathbf M$ and consider the following procedure for generating an infinite binary sequence $\omega$.

Start with some $\omega_0$. Each subsequent element is given by $\omega_n=\arg \max_a\mathbf M(a|\omega_{1:n-1})$.

What are the properties of $\omega$? For example, is it necessarily computable? Does the answer depend on the choice of $\mathbf M$?

UPDATE

The equivalent formulation is the following but it does not really help me advance with the problem.

Is there a universal lower semicomputable $\lambda$-supermartingale $t$ and a binary sequence $\tilde\omega$ such that $t$ always "goes up" along $\tilde\omega$ but never succeeds?

This type of problem arises when a player plays against a reactive environment and the sequence the player observes is not exogenous. A more general question is what is the short-run behavior of $\mathbf M$ since asymptotic results do not seem to help here.

It is computable.
Although $M$ is incomputable, since $M(x)\sim 2^{-K(x)}$, the sequence $\omega$ generated by $argmax M$ would have quite low Kolmogorov complexity.
If the sequence is generated by $argmin M$, then it would be Martin-lof random.


Are register based machines on von neumann architecture diametrically opposed to functional programming style? We are so used to von neumann architecture and say a register machine like the x86. (Also with   programming languages built for those machines x86 assembly, C, etc)  Is that approach to computing completely separate from a language and system like haskell?

What would a machine look like that was based functional programming paradigms look like? and  one not running on a register or stack machine.

This article is relevant to my question:

http://www.stanford.edu/class/cs242/readings/backus.pdf

Many hardware designs for executing functional programs have been proposed:

The Lisp Machine
Steele and Sussman's Scheme chip design
The Reduceron, by Naylor and Runciman

and more (lots are cited in the Reduceron papers).


Understanding a Mechanism Design Proof I have been struggling with the technical details of a proof concerning auction theory in this paper:  http://users.eecs.northwestern.edu/~hartline/omd.pdf

Specifically, Theorem 2.5:  The necessary and sufficient conditions for a truthful mechanism.

Even more specifically, the forward direction of the proof, given on page 6.  Defining a truthful value as $v_i$, and a general, possibly false, value (e.g., a bid) as $b_i$, the author goes on to postulate two additional quantities, $z_1$ and $z_2$.

He then stipulates that $v_i = z_1$, $b_i = z_2$, which yields an inequality based on the previous work of the paper.

He also stipulates that $v_i = z_2$, $b_i = z_1$, which yields a similar but different inequality based on the previous work of the paper.

Okay, fair enough.  He then subtracts one inequality from the other and proceeds to derive his desired result on the basis of the consequent algebra.  I don't understand why that subtraction is justified-- he seems to be subtracting two inequalities that are based on entirely different (in fact, opposite) assumptions, and every time I see it I am thrown violently out of the train of thought.

I'm pretty sure I've seen this basic approach else (Shoham and Leyton-Brown's book?  I don't have it close at hand to check) so it seems to be a common idea, but I cannot get past it.  Can anyone help me to understand why that is valid, or explain to me what I am missing?

(I've tried proving the desired result by assuming three values-- a true value $v_i$, and two bids, $b_1$ and $b_2$-- to get his desired result, but also failed.  So it may not only be common, but necessary to do it the author's way.  But I still don't understand it.)

Update:  I knew I had seen something similar in Shoham and Leyton-Brown's book.  It is not exactly the same, but it is very similar and deals with the same equation and subject matter.  It is Case 1 of Theorem 10.4.3.

Starting from the context of truthful mechanisms, they first assume a truthful $v_i$ and a false $v_i'$ and derive that the payment based on $v_i$ is lesser than or equal to the payment based on $v_i'$, e.g., $P_i(v_i) \leq P_i(v_i')$.  They then assume the opposite, a truthful $v_i'$ and a false $v_i$, and derive the opposite result, that the payment based on $v_i'$ is less than the payment based on $v_i$, e.g., $P_i(v_i') \leq P_i(v_i)$.  Okay, that makes sense.

They then hold that the payments based on $v_i$ and $v_i'$ must be equal, as though they are saying that $P_i(v_i) \leq P_i(v_i')$ and $P_i(v_i') \leq P_i(v_i)$ are simultaneously true, even though they are the result of not just different, but opposite assumptions.

The answer is that the mechanism must be truthful for every set of possible types: the mechanism does not know which are the true types ahead of time. So for a pair of types $v_i$ and $v_i'$, the mechanism must be truthful if an agent's true type is $v_i$: i.e. his utility must be greater if he bids $v_i$ than if he bids $v_i'$. But the mechanism must also be truthful if the agent's true type is $v_i'$! After all, as far as the mechanism is concerned, it might be! So in this case, an agent's utility must be greater if he bids $v_i'$ as compared to $v_i$.

The point is that truthfulness imposes many different inequalities on the same mechanism simultaneously: one for every type an agent might have, and for every deviation he might consider. All of them hold. This proof uses only two of these inequalities


Nonterminal descriptional complexity of regular languages Recently I became interested in grammar complexity of regular language. Prior to searching for literature, I tried to investigate it on my own, proving two lemmas from comment below.
I am aware of an old Grushka's article and a more recent paper by Dassow and Stiebe. I've also found Wolfsteiner's thesis.
What is the state of art of the study of grammar complexity? Could you explain simply the connection between grammar complexity and formal proof theory?

Lemma 1. Consider $L = (ab)^* + (ba)^*$:

There exists CFG with two variables which generates $L$
There exist no CFG with one variable which generates $L$

For proving (1) we may just consider the following CFG $$ S \rightarrow bAa \mid A , \, A \rightarrow abA \mid \varepsilon$$
The second proposition is a bit more tricky. Suppose that there exists CFG $G = (\{S\}, \{a, b\}, P, S)$ such that $L = L(G)$. Every production is $S \rightarrow \alpha$ for some $\alpha \in \{a, b, S\}^*$. Say, $\alpha = w_1 S w_2 S \ldots w_k S w_{k+1}$. Then $$u_1, \ldots u_k \in L \Rightarrow w_1 u_1 w_2 u_2 \ldots w_k u_k w_{k+1} \in L,$$ because as $L$ is generated by $G$, one can derive this word by using $S \rightarrow w_1 S w_2 S \ldots w_k S w_{k+1}$ and then deriving every $u_i$ from $S$'s. By using that we can prove that in right-hand side of every production $S$ can't be followed immediately by any symbol:

if $S$ is followed by $a$, we have subword $Sa$ in $\alpha$, then we can derive $ba$ from $S$, thus we can derive the word which contains two $a$'s in the row, which obviously doesn't lie in $L$;
if $S$ is followed by $b$, having subsword $Sb$ of $\alpha$ we can derive $ab$ from $S$ and thus obtain the word which contains two $b$'s in the row;
if we have subword $SS$ of $\alpha$, we can derive $ab$ from the first $S$ and $ba$ from the second.

Also $S$ can't follow neither letter nor $S$ in right-hand side of every production for the same reason. So $G$ can only have productions of sort $S \rightarrow S$ and $S \rightarrow w$ for $w \in L$. Thus $L(G)$ is finite, which is contradiction. $\Box$
I'd also like to suggest the following
Lemma 2. Let $w_1, \ldots w_n$ be some words. The language $w_1^* + \ldots + w_n^*$ is generated by CFG with one variable iff words $w_1, \ldots w_n$ commute pairwise, i. e. $w_i w_j = w_j w_i$ for every $i,j$.


Is it possible to include an optimization algorithm's own running time in the cost? Fix $f(\_; \_)$, which represents a class of optimization problems, ie, for a specific $P$, $f(\_; P)$ is a function we'd like to optimize.

Now, we have an algorithm $A$ that takes as input $P, a, b$, runs for $t$ CPU cycles, and outputs $x$ such that $a{\cdot}f(x; P) + b{\cdot}t$ is minimized.

edit (much cut): As Sasho points out, it is very tricky to define in what sense $A$ "minimizes" $a{\cdot}f(x; P) + b{\cdot}t$. I'm pretty convinced now that the criterion I gave earlier (see older version of this question) is no good. Let me try a different one similar to the one from the notes Sasho linked to.

Let $\mathcal{A}$ be the set of algorithms that take in $a, b, P$ and give out some $x$. Also say that the $P$s have "sizes" which are integers.

Say then that $A$ is optimal iff for every $A' \in \mathcal{A}$ and $a, b \in R$ there exists an $N \in Z$ such that

  $\forall{n} \ge N, ~~ \operatorname*{max}_{P \text{ with size ≤ n }}\{a{\cdot}f(x_P; P) + b{\cdot}t\} \leq \operatorname*{max}_{P \text{ with size ≤ n }}\{a{\cdot}f(x'_P; P) + b{\cdot}t'\}$

where $x, t$ are the result and running time of $A(a,b,P)$ and $x', t'$ are the result and running time of $A'(a,b,P)$.

Maybe that will work, not sure. Let me give an example.

Example: Say we take the problem of finding the smallest element in a list. Say we are given a list of size $n$, which we know contains some permutation of $1 ... n$, and we are asked to give an index at which lies a value that is as small as possible (ie, if the list were $[2, 1, 3]$ the best we could output would be $2$, then $1$, then $3$).

Say accessing the list (random access) takes $1$ step, everything else takes $0$ steps. Now our algorithm ($A$) will be:

If a > b:
    Search through the list 1 by 1 looking for the number 1,
    then output that index.
Else:
    Output 1.

For a list of size $\leq n$, the worst this can do is $min(a + b{\cdot}(n-1), a{\cdot}n)$ (note that the comparison, somewhat unrealistically, takes no time). Any algorithm guaranteed of finding a value no less than $k$ must see at least $n - k$ elements of the list, giving a worst-case score of $a{\cdot}k + b{\cdot}(n - k)$. Differentiate that wrt $k$ gives $a - b$, and substituting $1$ or $n$ for $k$ gives $a + b{\cdot}(n-1)$ or $a{\cdot}n$ respectively, so by induction $A$ scores at least as well. So, according to the above optimality constraint, $A$ is optimal.

Question: Does this problem, of including both an algorithm's own running time, and the result of another problem, in its score, have a name? Or does something similar have a name? Can such an algorithm usually exist in theory? Any other information I could check out?

(This question was inspired by a friend of mine who's computer freezes up for several minutes when he runs optimization algorithms).

Analyzing algorithms on real word machines is complicated but there has been some work done in this area in terms of how an algorithm behaves based on access to memory hierarchy. External Memory or memory hierarchy access based analysis are much more useful in understanding how an algorithm grows for large data-sets and in modern machines on most problems external memory access is the one which creates most latency AFAIK. You should check out work done on Cache Oblivious algorithms and algorithms for External Memory for understanding the run time cost of your problem.

I am not aware of work done on CPU cycles but someone who knows about this can pitch in.


Learning triangles in the plane I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ contains all of the positive and none of the negative points; by assumption, the sample admits at least 1 consistent triangle).

The best they (or I) could do is an algorithm that runs in time $O(m^6)$, where $m$ is sample size. Can anyone do better?

As @TsuyoshiIto suggests, there is an $O(n\log n)$-time algorithm for this problem, due to Edelsbrunner and Preparata.  In fact, their algorithm finds a convex polygon with the minimum possible number of edges that separates the two point sets.  They also prove an $\Omega(n\log n)$ lower bound for the more general problem in the algebraic decision tree model; however, it's not clear whether this lower bound applies to the triangle case.

A full description of the algorithm is too long to post here, but here's the basic idea.  Let $C$ be the convex hull of the positive points.  For each negative point $q$, consider the lines through $q$ that are tangent to $C$.  These lines split the plane into four wedges, one of which contains $C$; let $W(q)$ be the wedge opposite the one that contains $C$.  Finally, let $F$ (the "forbidden region") be the union of all wedges $W(q)$.  Any separating triangle must separate $C$ from $F$.  Both $C$ and $F$ can be constructed in $O(n\log n)$ time.

Label the edges of $F$ alternately clockwise and counterclockwise.  Edelsbrunner and Preparata further prove that if a separating triangle exists, then there is a separating triangle whose edges are collinear with clockwise edges of $F$.  In $O(n)$ additional time, we can find the (necessarily clockwise) edge of $F$ first hit by a ray from each clockwise edge $e$; call this edge the "successor" of $e$.  The successor pointers partition the clockwise edges into cycles; if there is a separating triangle, one of these successor cycles has length 3 (and none have length more than 4).

See the original paper for more details:

Herbert Edelsbrunner and Franco P. Preparata.  Minimum polygonal separation.  Information and Computation 77(3):218–232, 1988.


Automated transformation into spigot algorithm? Is there any research on transforming 'standard' algorithms into spigot algorithms?

I'd be happiest with automated transformations, but happy to learn about any research in this area.

For my purposes, I'd like to be able to transform a Haskell function into a spigot algorithm to improve garbage collection behavior.

Deforestation is a technique for eliminating intermediate data structures when composing functions together (in a lazy language). It improves the memory usage of programs, and is used by the GHC Haskell compiler.

A more general notion is fusion, which combines multiple traversals of a data structure into a single traversal. Fusion rules have been developed for programs written in terms of map and fold.  (If this is the kind of thing you are looking for, I can provide some references (as can google).)

Other transformations can be found on the program transformation wiki.


What are the best current lower bounds on 3SAT? What are the best current lower bounds for time and circuit depth for 3SAT?

As far as I know, the best known "model-independent" time lower bound for SAT is the following. Let $T$ and $S$ be the running time and space bound of any SAT algorithm. Then we must have $T \cdot S \geq n^{2 \cos(\pi/7) - o(1)}$ infinitely often. Note $2 \cos(\pi/7) \approx 1.801$. (The result that Suresh cites is a little obsolete.) This result appeared in STACS 2010, but that is an extended abstract of a much longer paper, which you can get here: http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Of course, the above work builds on a lot of prior work which is mentioned in Lipton's blog (see Suresh's answer). Also, as the space bound S gets close to n, the time lower bound T gets close to n as well. You can prove a better "time-space tradeoff" in this regime; see Dieter van Melkebeek's survey of SAT time-space lower bounds from 2008.

If you restrict yourself to multitape Turing machines, you can prove $T \cdot S \geq n^{2-o(1)}$ infinitely often. That was proved by Rahul Santhanam, and follows from a similar lower bound that's known for PALINDROMES in this model. We believe you should be able to prove a quadratic lower bound that is "model-independent" but that has been elusive for some time.

For non-uniform circuits with bounded fan-in, I know of no depth lower bound better than $\log n$.


Many-one reductions vs. Turing reductions to define NPC Why do most people prefer to use many-one reductions to define NP-completeness instead of, for instance, Turing reductions?

Two reasons:

(1) just a matter of minimality: being NPC under many-one reductions is a formally stronger statement and if you get the stronger statement (as Karp did and as you almost always do) then why not say so?

(2) Talking about many-one reductions gives rise to a richer, more delicate, hierarchy.  For example the distinction NP vs co-NP disappears under Turing reductions.

This is similar in spirit to why often one uses Logspace-reductions rather than polytime ones.


Graph encoding algorithms that you know of ? Is there any compilation of graph encoding algorithms? I know about Prufer and Huffman encoding. But papers say, prufer is not good enough to represent Minimum Spanning Trees in the sense it may represent different MSTs with the same string.

Update: It would be a very good future reference if every one could mention the graph encoding algorithm they know of. You can also provide a link/url to a paper.

As a start:

Prufer Encoding
Huffman Encoding
Succinct Trees
Ultra-succinct Representation of Ordered Trees

Thanks

If you have a binary encoding of the vertices of the graph you can represent the edges with the characteristic boolean function $\chi_E$ of the edge set $E$, i.e. $\chi_E(x,y) = 1 \Leftrightarrow$ there is an edge between the vertices encoded by $x$ and $y$.
This boolean function can be represented by e.g. Ordered Binary Decision Diagrams.

It is known that this OBDD representation is not larger than classical representations (adjacency matrix or adjacency lists) and for special graph classes (e.g. cographs and interval graphs) the OBDD size is smaller then the explicit representation (Nunkesser,Woelfel: Representation of Graphs by OBDDs). So you can hope that for good structured graphs the implicit representation is better.

In the case of trees I have shown (with the tools from the above paper) that the OBDD size is generally not better than the explicit representation and you can easily construct a tree so that the OBDD size is large.

Algorithms are called symbolic or implicit if they have access to the input graph only by this functional representation and perform functional operations to solve the problem. There is a good PhD thesis from Sawitzki about this topic but it is in german (PDF).

I think this is a kind of heuristical approach because you can't guarantee that there is a good implicit representation of the graph and so a fast symbolic alghorithm. Even if there exist a good implicit representation it is very hard to find this good one.


Count satisfying assignments of CNF formulas over all possible negation assignments Consider the set of all CNF instances that can be generated by adding negations to a single monotone CNF instance. How hard is it to compute the sum of the counts of satisfying assignments for the set?

More formally, consider a CNF formula over a boolean variable set $V$ described by $\phi = C_1 \wedge C_2 \wedge \dots \wedge C_m $, where each clause $C_j$ is a disjunction over a subset of $V$, and let $|\phi|$ denote the count of the satisfying assignments of $\phi$. Let $l_j$ denote the length of $C_j$. From each $C_j$ one can create $2^{l_j}-1$ other clauses by negating one or more of the literals that appear in it. One can therefore generate formulas $\phi_k$ where $k=1,\dots,2^{\sum_jl_j}$ with the same "structure" (i.e., the same factor graph topology) as $\phi$. How hard is it to compute $\sum_k |\phi_k|$?

Naively, one might expect that this should be as hard as counting the satisfying assignments of the hardest instance in the set. Is this correct? Or are there any interesting special cases where this intuition may be wrong? What about the restricted problem of getting the total count modulo some integer greater than 1? Does this problem have a name?

For example, if $\phi$ is a 3SAT formula, I would expect the problem to be #P-hard. On the other hand, if $\phi$ is an XORSAT formula, each $|\phi_k|$ is easy to evaluate, but there is an exponentially large number of them.

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


How is SDP an extension of spectral algorithms? In one of his lectures, Uri Feige described semidefinite programming (SDP) as

  ... an algorithmic technique that extends both linear programming and spectral algorithms.

I know the basic definition of SDP and understand it as linear programming extended by the possibility of saying "take these variables, arrange them into a matrix. Now, the matrix has to be positive semidefinite". Is this interpretation correct/useful? How is this an extension of spectral algorithms?

This is not a precise statement so it's hard to give a precise answer, but I think what is meant is that SDPs are powerful enough to express both linear programs, and problems like "compute the leading eigenvector of a symmetric matrix". So spectral algorithms that use the latter as a starting point can be interpreted as SDP rounding algorithm.

To see that SDPs can compute leading eigenvectors, let's take $A$ to be a symmetric matrix, and recall that the leading eigenvectors of $A$ are $\arg \max\{v^\top A v: \|v\|_2 = 1\}$. You can write $v^\top Av$ as $\mathrm{tr}(Avv^\top)$, and observe that $vv^\top$ is a PSD matrix of trace $1$. Then it's easy to check that the leading eigenvalue of $A$ is $\lambda_{\max} = \max\{\mathrm{tr}(AX): \mathrm{tr}(X) = 1, X \succeq 0\}$, which is the solution to an SDP, and every eigenvector of an optimal solution $X$ to this SDP will be a leading eigenvector of $A$. Similar tricks work for the minimum eigenvalue.

Let me give an example from spectral graph theory. Suppose $L$ is the normalized Laplacian of a graph. Then its smallest non-trivial eigenvalue is

$\lambda_2(L) = \min\{v^\top L v: \|v\|_2 = 1, \sum_i{\sqrt{d_i} v_i} = 0\},$

where $d_i$ is the degree of vertex $i$. (This is because $(\sqrt{d_1}, \ldots, \sqrt{d_n})$ is the eigenvector of eigenvalue $0$). You can rewrite this as the SDP

$\min\{\mathrm{tr}(LX): \mathrm{tr}(X) = 1, \mathrm{tr}(DX) = 0, X \succeq 0\}$,

where $D$ is the matrix with entries $D_{ij} = \sqrt{d_id_j}$. Cheeger's inequalities relate $\lambda_2$ to the conductance of the graph, and the proof of the inequalities can be seen as a rounding algorithm for the SDP.


Hamiltonicity of k-regular graphs It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).

For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?

The particular case I am interested in is 6-regular graphs, with the additional condition that the graph have an odd number of vertices. If this case could be shown to be NP-complete (or polynomial) it would have impact in a graph drawing problem described in http://arxiv.org/abs/1009.0579 . The "odd number of vertices" condition is because what I really want to know is, for 6-regular graphs, whether the graph contains either a Hamiltonian cycle or a bipartite 2-factor; but having an odd number of vertices eliminates the possibility of a bipartite 2-factor leaving only the possibility of a Hamiltonian cycle.

First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number of vertices.

The solution is a refinement of the idea suggested in the other answer.

First part

Claim: Given a $k$-regular graph $G$ with even number of vertices, one can compute a graph $H$ which is $(k+1)$-regular, and $H$ is Hamiltonian iff $G$ is Hamiltonian.

Proof:
Take two copies of the $k$-regular graph $G$, let call them $G_1$ and $G_2$. For a vertex $v \in V(G)$, let $v_1$ and $v_2$ be the corresponding copies. Create a clique with $k+2$ vertices for $v$. Pick two vertices $v'$ and $v''$ in this clique, and remove the edge between them. Next, connect $v_1$ to $v'$ and $v_2$ to $v''$. Let $C(v)$ denote this component for $v$.

Repeat this for all the vertices of $G$, and let $H$ denote the resulting graph.

Clearly, the graph $H$ is $k+1$ regular. We claim that $H$ is Hamiltonian if and only if $G$ is Hamiltonian.

One direction is clear. Given a Hambiltonian cycle in $G$, we can translate it into a cycle in $H$. Indeed, whenever the cycle visits a vertex $v$, we interpret it as moving from $v_1$ to $v_2$ (or vice versa) while visiting all the vertices in $C(v)$.
As such, this results in a Hamiltonian cycle in $H$. (Note, that this is where we are using the fact that the original number of vertices is even - if the cycle is odd this breaks down.)

As for the other direction, consider a Hamiltonian cycle in $H$. It must be that $C(v)$ is visited by a portion of the cycle that starts in $v_1$, visits all the vertices of $C(v)$ and leaves from $v_2$ (or the symmetric option). Indeed, the Hamiltonian cycle can not enter and leave from the same $v_i$. As such, a Hamiltonian cycle in $H$ as a natural interpretation as a Hamiltonian cycle in $G$.
QED.

Second part

As noted below  by Tsuyoshi any 3-regular graph has even number of vertices. As such, the problem is hard for a $3$-regular graph with even number of vertices. Namely, the above reduction shows the problem is hard for any $k$-regular graph, although the resulting graph has an even number of vertices.

We observe, that this implies that the following problem is NP-hard.

Problem A: Deciding if a k-regular graph $G$ with even number of vertices has an Hamiltonian cycle going through a specific edge $e$.

However, if $k$ is even then given an instance $(G, e)$ we can reduce it to desired problem. Indeed, we replace the edge $e$ by a clique of $k+1$ vertices, as before deleting one edge in the clique, and connecting its two endpoints to the endpoints of $e$, and removing $e$ from the graph. Clearly, for the new graph $H$:

$H$ is $k$-regular.
$H$ is Hamiltonian iff $G$ is Hamiltonian with a cycle using $e$.
$H$ has $|V(G)| + k+1$ vertices => $H$ has odd number of vertices.

Note,  that a $k$-regular graph, for $k$ odd, must have an even number of vertices (just count the edges), As such, there are no $k$-regular graphs with odd number of vertices, with $k$ being odd.

Result

It is NP-Hard to decide if a $k$-regular graph has a Hamiltonian cycle for $k\geq 3$. The problem remains NP-Hard even if the graph has an odd number of vertices.

Of course, it is always possible I made some stupid mistake...

Exercise

If we want to go from a graph that is $k$-regular to a graph that is (say) $2k$-regular then the graph resulting from applying the above reduction repeatedly results in a graph with a size that depends exponentially on $k$. Show, that given a $k$-regular graph $G$,  and $i >2$, one can construct a graph $H$ that is $(k+i)$-regular and its size is polynomial in $k,i$ and $n$, where $n$ is the number of vertices of $G$. Furthermore, $G$ is Hamiltonian if and only if $H$ is Hamiltonian.

(I am posting this as an exercise, not a question, since I know how to solve this.)


When is a problem specified on a TM contained in non-uniform classes such as P/poly? In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, they mention that the input to the TM they encode in the tiling problem must be an integer $N$ in binary rather than unary, otherwise each instance will have a different input size and hence the problem would "trivially be in P/poly" rather than NP. Hence instead they must prove the problem is NEXP-complete rather than NP-complete.

While I understand why the proof with a binary input gives NEXP-completeness, I don't understand why if $N$ is input in unary then the problem is trivially hard for P/poly? Unfortunately the model of computation they specify is in terms of TMs rather than circuits so it's not clear to me how this relates to non-uniform circuit families.

If $N$ were written in unary, then the language would be a unary language, i.e., a subset of $\{0,1\}^*$.   Every unary language is in P/poly.  That's because a P/poly machine is allowed a separate advice string, one per length of the input.  The advice string for length $n$ could just describe whether the input $1^n$ should be accepted or not.  Or, to put it another way, P/poly allows you to specify a separate circuit per input length; so you could use the "always output no" circuit for lengths $n$ such that $1^n$ is not part of the language, otherwise the "always output yes" circuit.  See https://en.wikipedia.org/wiki/P/poly.


Homotopy type theory and Gödel's incompleteness theorems Kurt Gödel's incompleteness theorems  establish the "inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic".

Homotopy Type Theory provides an alternative foundation for mathematics, a univalent foundation based on higher inductive types and the univalence axiom.
The HoTT book explains that types are higher groupoids, functions are functors, type families are ﬁbrations, etc.

The recent article "Formally Verified Mathematics" in CACM
by Jeremy Avigad and John Harrison
discusses HoTT with respect to
formally verified mathematics and automatic theorem proving.

  Do Gödel's incompleteness theorems apply to HoTT?

And if they do,

  is homotopy type theory impaired by Gödel's incompleteness theorem
  (within the context of formally verified mathematics)?

HoTT "suffers" from Gödel incompleteness, of course, since it has a computably enumerable language and rules of inference, and we can formalize arithmetic in it. The authors of the HoTT book were perfectly aware of its incompletness. (In fact, this is quite obvious, especially when half of the authors are logicians of some sort).

But does incompleteness "impair" HoTT? No more than it does any other formal system, and I think the whole issue is a bit misguided. Let me try an analogy. Suppose you have a car which can't take you everywhere on the planet. For instance, it can't climb vertically up a wall. Is the car "impaired"? Of course, it can't get you to the top of the Empire State building. Is the car useless? Far from it, it can take you too many other interesting places. Not to mention that the Empire State building has elevators.


On the definition of pseudoentropy $\mathbf{Definition.}$ A random variable $X$ has pseudoentropy $k$ if it is computationally indistinguishable from a random variable $Y$ with $H(Y) = k$, where $H(Y)$ is the Shannon entropy of $Y$.

By this definition, can we say that any random variable has pseudoentropy equals to its Shannon entropy, just because it is computationally indistinguishable from itself? The caveat here is whether or not the definition of computational indistinguishability is still valid when there is only one random variable, not two.

Yes, we can always say that $X$ has pseudoentropy at least $H(X)$. You can take $Y$ to be a completely separate, independent random variable that has the same distribution as $X$. Then $X$ and $Y$ are computationally indistinguishable (indeed they are "completely" indistinguishable): $\Pr[A(X) = 1] = \Pr[A(Y) = 1]$ for all algorithms $A$.

Instead of thinking of psuedoentropy as a property of a random variable, maybe it is more helpful to think of it as a property of a distribution. Not a big difference but emphasizes that, for instance, $X$ and $Y$ are never correlated in the definition.


Centroid in $\ell_2$ distance Given points $x_1, x_2, \cdots, x_n \in \mathbb{R}^d$. What is the complexity of computing
$$
argmin_{x}\left(\sum_{i=1}^n ||x_i-x||_2\right)
$$

This is the geometric median problem. There is a nearly linear time algorithm based on interior point methods due to Cohen et al.: to find a $(1+\varepsilon)$-approximation their algorithm runs in time $O(nd\log^3(n/\varepsilon))$. Note that some approximation is necessary, because the optimal solution may not be rational and doesn't have to be a simple function of the input. See the paper for references to prior work.


Polynomial evaluation at all different points I have a polynomial $f(x_1,\ldots,x_{50})$ of 50 variables over binary field $GF(2)$. I want
to evaluate at all $2^{50}$ points and check how many of them are 0.  Ofcourse we can evaluate at all points and check them. Can we do faster than this using some memory?

This problem is in general #P-complete, as you can for example encode a SAT instance as a polynomial over GF(2) and reduce #SAT to this problem. So all the standard hardness results apply to this.
If you're happy with finding the fraction of evaluation points over which the polynomial vanishes, up to an additive constant $\epsilon$, then you can trivially evaluate at enough random points and take the empirical estimate.


Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$? Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ?

I have found a proof for this statement but something feels wrong about it. Here it goes :

Let $L \in \textbf{PCP}[poly(n), O(1)]$. There is a verifier $V$ for $L$ which flips $poly(n)$ random coins and reads $q$ bits from the certificate, where $q$ is a constant.

The proof query of $q$ bits can return $2^q$ possible values. My idea is to build a $\textbf{coRP}$ algorithm $V'$ for $L$ by simulating $2^q$ copies of $V$, where each copy is given a different answer to the certificate query. $V'$ accepts if at least one of the copies of $V$ accepts.

If the input is in $L$ then there exists a certificate so that $V$ accepts with perfect completeness. The queried bits from that certificate are necessarily in our $2^q$ possible values, so at least one of the simulated copies of $V$ accepts with perfect completeness.

If the input is not in $L$, then all copies have probability < 1 of accepting. Thus $V'$ has some probability $\rho < 1$ of accepting.

Using amplification, we can then boost $\rho$ to $\frac{1}{2}$ to match the definition of $\textbf{coRP}$.

Is this proof correct ?

Recall PCP theorem, $PCP(log(n), 1)$ is NP already and actually $PCP(poly(n),1)$ is $NEXP$.

The problem of your proof is that you cannot simulate a coRP algorithm on a string with length only $2^q$. Though it will only access q bits, the bits it accesses to depend on the random coins. You should not think of a specific coin outcome but all of them on a input. That is basically why your proof doesn't work.


SDP and chromatic number upper bounds Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?

SDPs usually provide relaxations, so for a minimization problem you'll get a lower bound. The Lovasz theta function does provide such a lower bound on chromatic number (see wiki). Upper bounds can be provided by rounding schemes (constructive or otherwise). In general, if you have an upper bound $U$ on the integrality gap of the SDP, you can scale the objective of the SDP by $U$ and you'll get an upper bound as well. However, there exist graphs for which the Lovasz theta gives a lowerbound of $k = O(1)$ and the chromatic number is at least $n^{1 - 2/k}$. There is some hope that higher levels of the Lasserre hierarchy can give stronger relaxations. However, notice that chromatic number is  hard to approximate within $n^{1 - \epsilon}$ (see this) in general (i.e. if you're not just interested in the promise problem where the yes instance has constant chromatic number). So, for any SDP, integrality gaps better than $n^{1-\epsilon}$ will either be restricted to cases where the SDP relaxation has  constant value or will be nonconstructive (i.e. superpolynomial time rounding or superpolynomial size relaxation), unless P=NP.


"Relatives" of the shortest path problem Consider a connected undirected graph with non-negative edge weights, and two distinguished vertices $s,t$. Below are some path problems that are all of the following form: find an $s-t$ path, such that some function of the edge weights on the path is minimum. In this sense they are all "relatives" of the shortest path problem; in the latter the function is simply the sum.
Note: We are looking for simple paths, that is, without any repeated vertices. Since I did not find standard names for these problems in the literature, I named them myself.

Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest  and smallest edge weights on the path is minimum.
Smoothest path: find an $s-t$ path, such that the largest step size on the path is minimum, where a step size is the absolute value of the weight difference between two consecutive edges.
Path with minimum altitude: Let us define the altitude of a path by the sum of the step sizes along the path (see the definition of step size above). Find an $s-t$ path with minimum altitude.
Path with minimum prime weight: assuming that all edge weights are positive integers, find an $s-t$ path, such that its weight is a prime number. If there is such a path, find one with the smallest possible prime weight.

Question: what is known about these path problems? (And others that could be conceived in a similar spirit, applying a different function of the weights.) In general, is there any guidance that which functions of the edge weights can be minimized in polynomial time, and which are NP-hard?
Note: it is interesting, for example, that while the sum of the weights is easy to minimize (it is the classical shortest path problem), but minimizing the closely related average of the weights on the path is NP-hard. (Assign weight 2 to all edges incident to $s$ and $t$, and weight 1 to all others. Then a min average weight path will be a longest $s-t$ path).

Here is an answer to the first problem:

  Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest  and smallest edge weights on the path is minimum.

A paper from 1984 shows that whenever we can decide
feasibility (does there exist a solution in the unweighted
case) for some combinatorial optimization problem in
polynomial time, then we can also find in polynomial
time a solution that minimizes the differenc between the
largest and smallest cost coefficient (in the weighted case):

  S. Martello, W.R. Pulleyblank, P. Toth, D. de Werra
  Balanced optimization problems
  Operations Research Letters 3, 1984, Pages 275-278

This implies a polynomial time algorithm to your question.


What is the number of languages accepted by a DFA of size $n$? The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:

Define a DFA as $(Q,\Sigma,\delta,q_0,F)$, where everything is as usual and $\delta:Q\times\Sigma\to Q$ is a (possibly partial) function. We need to establish this since sometimes only total functions are considered valid.
For every $n\geq 1$, define the (equivalence) relation $\sim_n$ on the set of all DFAs as: $\mathcal{A}\sim_n\mathcal{B}$ if $|\mathcal{A}|=|\mathcal{B}|=n$ and $L(\mathcal{A})=L(\mathcal{B})$.
The question is, then: for a given $n$, what is the index of $\sim_n$? That is, what is the size of the set $\{L(\mathcal{A})\mid\mathcal{A}\textrm{ is a DFA of size }n\}$?

Even when $\delta$ is a total function, it doesn't seem to be an easy count (for me, at least). The graph might not be connected, and the states in the connected component containing the initial state might all be accepting, so, for example, there are many graphs of size $n$ accepting $\Sigma^*$. Same with other trivial combinations for the empty language and other languages whose minimal DFA has fewer than $n$ states.
(A naïve) recursion doesn't seem to work either. If we take a DFA of size $k$ and add a new state, then, if we want to keep determinism and make the new graph connected (to try to avoid trivial cases), we have to remove a transition to connect the new state, but in that case we may lose the original language.
Any thoughts?
Note. I updated the question again, with a formal statement and without the previous distracting elements.

I think that this question has been studied previously. Mike Domaratzki wrote a survey on research in this area:
"Enumeration of Formal Languages", Bull. EATCS, vol. 89 (June 2006), 113-133: http://www.eatcs.org/images/bulletin/beatcs89.pdf


A PAC-like analogue for 1-class classification? This is more of a philosophical question -- I am looking for a reasonable mathematical formulation of 1-class learning.

In the PAC model, it's very natural to formulate our demand on the learner: produce a hypothesis with low generalization error.

What might be a reasonable formalization of 1-class learning? This may also be called "anomaly detection": in the training phase, the learner only gets to see positive ("normal") examples, but in the test phase he needs to predict whether a given new example is positive ("normal") or negative (an anomaly). The formal details are quite open-ended -- what's a reasonable assumption on the training sample (generated from some distribution, etc)? What's a reasonable success criterion?

I think there is a model called "Learning from Positive Examples (Only)" or you can additionally allow unlabeled data (I don't remember the details).  A search for these terms should bring up various papers and models.  Here is one.


Can one automate algorithmic analysis? Has anyone thought about the possibility of a programming language, and a compiler, such that the compiler can automatically do worst-case asymptotic analysis? The use case I have in mind is a programming language where I write code, and compile. The compiler tells me that my code runs in O(n^2) (for example). It does this by doing what the smart people who do algorithmic analysis do, possibly counting loops and so on.

Because of halting problem issues, and since one can have programs that work by dovetailing, for example Levin's algorithm for SAT that runs in polynomial time iff P=NP, I suspect that one may have to design the programming language to be sufficiently restrictive to allow something like this. Are there negative results, which rule out certain kinds of programming languages from having such compilers.
I would also be interested in systems that give not an exact asymptotic analysis, but an "interesting" upper bound.
I am specifically NOT interested in black box and statistical methods that sample from inputs of particular length, and find out how long the program takes. These methods are very interesting, but they are not what I'm looking for. I am interested in exact methods that may give approximate bounds.

I would be very grateful if someone could point me to some references on work in this direction.

Implicit Complexity has taught us that (some) complexity classes can be classified by type systems, in the sense that there are type systems that only accept polynomial programs, for example. One more practical-minded offshoot of this research is RAML (Resource Aware ML), a functional programming language with a type system that will give you precise information of the running times of its programs. It is more precise, in fact, than big-O complexity, are constant factors are also included, parametrized by a cost model for the base operations.

You may think that this is cheating: surely some algorithms have a complexity that is very hard to compute precisely, so how could this language easily determine the complexity of its programs? The trick is that there are many ways to express a given algorithm, some which the type-system will reject (it rejects some fine programs), and some, maybe, that it accept. So the user doesn't get the world for free: he or she doesn't have to compute cost estimations anymore, but need to figure how to express code in a way that is accepted by the system.

(It is always the same trick, as with programming languages with only terminating computations, or provable security properties, etc.)


Cover Time of Directed Graphs Given a random walk on a graph the cover time is the first time (expected number of steps) that every vertex has been hit (covered) by the walk. For connected undirected graphs, the cover time is known to be upper bounded by $O(n^3)$. There are strongly connected digraphs with cover time exponential in $n$. An example of this, is the digraph consisting of a directed cycle $(1, 2, ..., n, 1)$, and edges $(j, 1)$, from vertices $j = 2, ..., n − 1$. Starting from vertex $1$, the expected time for a random walk to reach vertex $n$ is $\Omega(2^n)$. I have two questions :

1) What are the known classes of directed graphs with polynomial cover time ? These classes might be characterized by graph-theoretic properties (or) by properties of the corresponding adjacency matrix (say $A$). For example, if $A$ is symmetric then cover time of the graph is polynomial.

2) Are there more simple examples (like the cycle example mentioned above) where the cover time is exponential ?

3) Are there examples with quasi-polynomial cover time ?

I would appreciate any pointers to good surveys/books on this topic.

Clearly polynomial mixing time implies polynomial cover time. (Well, not in general. We need the stationary probability at least $1/poly(n)$ at each vertex.) So check Mihail's paper Conductance and convergence of Markov chains-a combinatorial treatment of expanders which proves rapid mixing of regular directed graphs and general Markov chains based on conductance.

Also see the paper Pseudorandom walks on regular digraphs and the RL vs. L problem by Reingold, Trevisan, and Vadhan. Following Mihail's work. They defined the parameter $\lambda_\pi(G)$ which is equivalent to $\lambda_2(G)$, the second largest eigenvalue in absolute value, when the graph $G$ is time-reversible, and remains well-defined for general Markov chains. This parameter is then used to bound the mixing time of $G$.


Graphs in which all shortest paths are unique I'm looking for undirected, unweighted, connected graphs $G=(V,E)$, in which for every pair $u,v \in V$, there is a unique $u \rightarrow v$ path that realizes the distance $d(u,v)$.

Is this class of graphs well-known? What other properties does it have? For example, every tree is of this kind, as well as every graph without an even cycle. However, there are graphs containing even cycles that are of this kind.

According to Information System on Graph Classes and their Inclusions, these graphs are studied under the name “geodetic graphs.”


Minimum communication cost for zero knowledge proofs of three colorability Goldreich et al.'s proof that three colorability has zero knowledge proofs uses bit commitment for an entire coloring of the graph in each round [1].  If a graph has $n$ vertices and $e$ edges, a secure hash has $b$ bits, and we seek error probability $p$, the total communication cost is

$$O(ben \log(1/p))$$

over $O(1)$ rounds.  Using a gradually revealed Merkle tree, the total communication can be reduced to $O(be \log n \log (1/p))$ at the cost of increasing the number of rounds to $O(\log n)$.

Is it possible to do better than this, either in terms of total communication or number of rounds?

http://www.wisdom.weizmann.ac.il/~oded/X/gmw1j.pdf

Edit: Thanks to Ricky Demer for pointing out the missing factor of $e$.

So here is the right paper for my purposes:

Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf

To get the strongest result, we need to accept zero knowledge arguments rather than proofs (computationally bounded prover); these are what I am interested in but did not know the terminology.

Assuming sufficient cryptographic assumptions, the paper gives zero knowledge arguments with total communication $O(b \log^c n \log (1/p))$ for $c = O(1)$.

This result is tightened to $O(1)$ rounds by Ishai et al., "On Efficient Zero-Knowledge PCPs", http://www.cs.virginia.edu/~mohammad/files/papers/13%20ZKPCPs.pdf.


Complexity of Membership-Testing for finite abelian groups Consider the following abelian-subgroup membership-testing problem.

  Inputs:

  A finite abelian group $G=\mathbb{Z}_{d_1}\times\mathbb{Z}_{d_1}\ldots\times\mathbb{Z}_{d_m}$ with arbitrary-large $d_i$.
  A generating-set $\lbrace h_1,\ldots,h_n\rbrace$ of a subgroup $H\subset G$.
  An element $b\in G$.

  Output: 'yes' if $b\in H$ and 'no' elsewhere'.

Question: Can this problem be solved efficiently in a classical computer? I consider an algorithm efficient if it uses $O(\text{polylog}|G|)$ time and memory resources in the usual sense of classical Turing machines. Notice that we can assume $n= O(\log|G|)$ for any subgroup $H$. The input-size of this problem is $\lceil \log|G|\rceil$.

A bit of motivation. Intuitively it looks like the problem can be tackled with algorithms to solve linear systems of congruences or linear diophantine equations (read below). However, it seems that there are different notions of computational efficiency used in the context of computations with integers, such as: strongly versus weakly polynomial time, algebraic versus bit complexity. I am not an expert on these definitions and I can not find a reference that clearly settles down this question.

  Update: the answer to the problem is "yes".

  In a late answer, I proposed a method based on Smith normal forms which is efficient for any group with the prescribed form.
  An answer by Blondin shows that in the particular case where all $d_i$ are of the form $d_i= N_i^{e_i}$ and $N_i, e_i$ are "tiny integers" then the problem belongs to $\text{NC}^3\subset \text{P}$. Tiny integers are exponentially small with the input size: $O(\log\log|A|)$.

  In my answer I used "orthogonal subgroups" to solve this problem, but I believe this is not necessary. I will try to provide a more direct answer in the future based a row Echelon forms method I am reading.

Some possible approaches

The problem is closely related to solving linear system of congruences and/or linear diophantine equations. I briefly summarise these connection for the sake of completion.

Take $A$ to be the matrix whose columns are the elements of the generating set  $\lbrace h_1, \ldots, h_n \rbrace$. The following system of equations

$$
Ax^{T}=
\begin{pmatrix}
h_1(1) & h_2(1) & \ldots & h_n(1)\\
h_1(2) & h_2(2) & \ldots & h_n(2)\\
\vdots & \vdots & \cdots & \vdots\\
h_1(m) & h_2(m) & \ldots & h_n(m)
\end{pmatrix}

\begin{pmatrix}
x(1)\\
x(2)\\
\vdots\\
x(n)
\end{pmatrix}
=
\begin{pmatrix}
b(1) \\
b(2) \\
\vdots\\
b(m)
\end{pmatrix}
\begin{matrix}
\mod d_1\\
\mod d_2\\
\vdots\\
\mod d_m
\end{matrix}
$$

has a solution if and only if $b\in H$.

If all cyclic factors have the same dimension $d=d_i$ there is an algorithm based on Smith normal forms that solves the problem in polynomial time. In this case, an efficient algorithm from  [1]
finds the Smith normal form of  $A$: it returns a diagonal matrix $D$ and two invertible matrices $U$ and $V$ such that $D=UAV$. This reduced the problem to solving the equivalent system system $DY=Ub \mod d$ with $D$ diagonal. We can decide efficiently if the system has a solution using the Euclidean algorithm.

The above example suggest that the problem can be solved efficiently using similar techniques in the general case. We can try to solve the system doing modular operations, or by turning the system into a larger system of linear diophantine equations. Some possible techniques to approach the problem that I can think of are:

Computing the Smith normal forms of $A$.
Computing the row Echelon form of $A$.
Integer Gaussian elimination.

Verifying whether $b \in \langle h_1, \ldots, h_n\rangle$ (where $h_i$ are vectors according to the OP's comments) is equivalent to verifying whether there is a solution to this system:
$$
\begin{pmatrix}
h_{1}(1) & \cdots & h_{n}(1) & d_1^{e_1}      & 0 & \cdots & 0 \\\\
\vdots  & \ddots & \vdots  & \vdots & \vdots  & \vdots & \vdots  \\\\
h_{1}(m) & \cdots & h_{n}(m) & 0      & 0 & \cdots & d_m^{e_N}
\end{pmatrix}
\begin{pmatrix}
x(1) \\\\
\vdots \\\\
x(n) \\\\
y(1) \\\\
\vdots \\\\
y(m)
\end{pmatrix}
\equiv
\begin{pmatrix}
b(1) \\\\
\vdots \\\\
b(m)
\end{pmatrix}
$$

In your case $e_1, \ldots, e_N$ are tiny numbers (ie. their value is logartihmic in the input size). Unfortunately, it doesn't seem like we can assume that $d_1, \ldots, d_n$ are tiny.

If they are, then you can find a solution to the system in $\text{NC}^3$ from a result of McKenzie & Cook [1]. This paper shows that solving linear congruences modulo an integer with tiny factors (LCON) is in $\text{NC}^3$. Moreover, this problem is $\text{NC}^1$-equivalent to the abelian permutation group membership problem (AGM). McKenzie's doctoral thesis is fully devoted to those problems [1]. More recently, those problems were considered by Arvind & Vijayaraghavan [3].

[1] Pierre McKenzie & Stephen A. Cook. The parallel complexity of Abelian permutation group problems. 1987.

[2] Pierre McKenzie. Parallel complexity and permutation groups. 1984.

[3] V. Arvind & T. C. Vijayaraghavan. Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes. 2010.


Verifying Shor's quantum error correction code I know that Shor's 9 bit code can correct phase or bit flip, but I'd like to show that it can correct any type of error on a single qubit. I know that an arbitrary error can be expressed with the error base (phase flipe and bit flip), but I'm lacking the understanding of how does this assist me in deducing that any arbitrary error can be corrected?

Since I don’t understand what you don’t understand, I will try to give a quite formal description, hoping it will help.

$\newcommand{ket}[1]{\left|#1\right>}$
Let’s suppose the error is the unitary $U$ applied on the $k$th qubit.
We have
$$\begin{align}
U&=aI+bX+cY+dZ\\&=aI+bX+icXZ+dZ,
\end{align}$$
with $a,b,c,d$ being real numbers, $I$ is the identity, $X, Y, Z$ the Pauli operators. $X$ is a bit-flip, and $Z$ is a phase-flip.
$Y=iXZ$ is a combination of phase and bit-flip.

Let’s look at a coherent version of Shor error correction, one where there is no measurement, but a set $A$ of 8 ancilla qubits, initially in the $\ket{0}$ state. Their final state, if measured in the computational basis, contains the code syndrome. The error correction is described by a unitary $V$ acting the 9 qubits of the code ($B$) and the 8 ancilla qubits. Since the code corrects both bit-flips and phase-flips, we have:
$$
\begin{align}
V⋅(I\otimes I)\ket{\psi}_B\ket{0}_A&=\ket{\psi}_B\ket{0}_A\\
V⋅(X_k\otimes I)\ket{\psi}_B\ket{0}_A&=\ket{\psi}_B\ket{\phi_{k,X}}_A\\
V⋅(Z_k\otimes I)\ket{\psi}_B\ket{0}_A&=\ket{\psi}_B\ket{\phi_{k,Z}}_A\\
\end{align}
$$
The action of $Y_k=iX_kZ_k$ is also corrected, since it is a phase-flip followed by a bitflip $^*$ :
$$
\begin{align}
V⋅(I_k\otimes I)\ket{\psi}_b\ket{0}_a&=iV⋅(X_k\otimes I)⋅(Z_k\otimes I)\ket{\psi}_b\ket{0}_a\\
&=\ket{\psi}_b\ket{\phi_{k,Y}}_a\\
\end{align}
$$

If we apply this to an arbitrary error $U_k$ on the $k$th qubit, we have :
$$V⋅(U_k\otimes I)\ket{\psi}_b\ket{0}_a=\ket{\psi}_b\left(a\ket0_a+b\ket{\phi_{k,X}}_A+c\ket{\phi_{k,Y}}_A+d\ket{\phi_{k,Z}}_A\right) $$
and the vector $\ket{\psi}_b$ is recovered.


Reference for unpublished but quoted manuscript Is there a place to locate the reference
"[Smi88] D. V. Smirnov, ``Shannon's Information Methods for Lower Bounds for Probabilistic Communication Complexity,'' Master's thesis, Moscow University, 1988"
mentioned in this paper http://cs.au.dk/~bromille/Papers/asym.pdf?

I assume you've looked online, though I'd be amazed if a 1980s master's thesis was online.

Ask one of the authors: they should have read the thesis before citing it, which suggests that at least one of them has access to a copy or, at least, had access at the time they wrote the paper. If that fails, try asking your university library.

Also, although the citation doesn't mention it, be prepared for the thesis to be in Russian.


Combinators for the Primitive Recursive Functions It is well-known that the S and K combinators are Turing Complete. Are there combinators that suffice to yield (only) the primitive recursive functions?

Yes, but you have to consider typed combinators. That is, you need to give $S$ and $K$
the following type schemas:
$$
\begin{array}{lcl}
K & : & A \to B \to A \\
S & : & (A \to B \to C) \to (A \to B) \to (A \to C)
\end{array}
$$
where $A, B$, and $C$ are meta-variables which can be instantiated to any concrete type at each use.

Then, you want to add the type $\mathbb{N}$ of natural numbers to the language of types, and add the following combinators:
$$
\begin{array}{lcl}
z & : & \mathbb{N} \\
succ & : & \mathbb{N} \to \mathbb{N} \\
iter & : & \mathbb{N} \to (\mathbb{N} \to \mathbb{N}) \to \mathbb{N} \to \mathbb{N}
\end{array}
$$

The equality rules for the additions are:
$$
\begin{array}{lcl}
iter\;i\;f\;z & = & i \\
iter\;i\;f\;(succ\;e) & = & f(iter\;i\;f\;e)
\end{array}
$$

It's much easier to read the programs you write, if you just write programs in the simply-typed lambda calculus, augmented with the numerals and iteration. The system I've described is a restriction of Goedel's T, the language of higher-type arithmetic. In Goedel's T, the typing for iteration is less limited:
$$
\begin{array}{lcl}
iter & : & A \to (A \to A) \to \mathbb{N} \to A
\end{array}
$$
In T, you can instantiate $iter$ at any type, not just the type of natural numbers. This takes you past primitive recursion, and lets you define things like Ackerman's function.

EDIT: Xoff asked how to encode the predecessor function. It follows via a standard trick. To explain, I'll use lambda-notation for this (which can be eliminated with bracket-abstraction), since that's far more readable. First, assume that we have pairs and the more general type for $\mathit{iter}$. Then, we can define:

$$
\begin{array}{lcl}
pred' & = & \lambda k.\;iter \;(z, z) \; (\lambda (n, n').\; (succ\;n, n))\;k\\
pred  & = & \lambda k.\;snd(pred'\;k)
\end{array}
$$

If you just have the nat-type iterator, then you need to exploit the isomorphism that $\mathbb{N} \simeq \mathbb{N} \times \mathbb{N}$, which is annoying but poses no fundamental obstacle.


What is an accessible introduction to Percolation Theory? What is the best place to start for someone in Computer Science with a graduate level background in linear algebra, probability theory, and graph theory?

I can't give you a comparison of different options but I can at least tell you that I (having that background) really liked Grimmett's book.

As an aside: would this have been better as a comment?  I was debating with myself and could not decide.


find the densest subgraph of size k What is "the best" algorithm to find the densest subgraph of size k?

i.e. a subgraph of size k with the maximum number of edges inside for an unweighted and undirected graph.

For fixed k, the straightforward brute-force algorithm takes $O(n^k)$ time with n the number of nodes. I'm looking for something, like $O(2^kn)$ or so. Maybe using a recursive algorithm or dynamic programming.

An answer to your problem tells you whether there exists a clique of size k. So, any such algorithm for your problem must be at least as slow as clique algorithms. See the wikipedia section on FPT and clique for more.


Why does the construction step of Aho-Corasick take linear time in the number of nodes? The original paper's analysis of this, as far as I can tell is this:

"THEOREM 3. Algorithm 2 requires time linearly proportional to the sum of the lengths of the keywords.
PROOF. Straightforward."

But it's not at all obvious.

Using for reference, Aho and Corasick, Efficient string matching: an aid to bibliographic search (Communications of the ACM, 18(6):333–340, 1975) (PDF).

Algorithm 2 is mostly creating a trie or "keyword tree" in the paper.

Important Note: They make the assumption that $g(s, a) = \texttt{fail}$ if either $a$ is undefined, or  $g(s, a)$ hasn't been defined yet. You can think of this function as an edge, it either points to the next state or returns $\texttt{fail}$. Assume evaluating and assigning to functions, such as $g$ or $output$, takes constant time.

Example:

Let's consider the intuition for a single keyword $x$. Use the last graph on page 335 with his, hers and she. Let's add "hello" and verify that it takes linear time in the length. We can generalize from there.

For this example, let $y = \text{hello}$.

$s = 0$, the initial state. First, we find out that $g(0, \text{h}) = 1$ so we
set $s = 1$. Next we check $g(1, \text{e})$, which takes us to $s = 2$.

Now $g(2, \textit{l}) = \texttt{fail}$, there is no edge for $\textit{l}$, we have to create a state, $s = 10$ and set $g(2, \textit{l}) = 10$. State $10$ corresponds to the string $\text{hel}$.

Again $g(10, \textit{l}) = \texttt{fail}$, we create a new state $s = 11 \text{(hell)}$. The same happens for $\textit{o}$ : $g(11, \textit{o}) = \texttt{fail}$, make a new state $12 \text{(hello)}$.

We've finished $\text{hello}$, as a last step we set $output(12) = \text{hello}$.

Rough Analysis:

Calling $g(s,a)$, assigning values, and creating new states are constant time. Since we perform a constant number of each operation per letter, the complexity is $\mathcal{O}(|\text{y}|)$.

Algorithm 2 does this for each key word. Notice that the same bound holds for each keyword added, regardless of what $g(s,a)$ returns for each letter. Then the total time complexity is $\mathcal{O}(\displaystyle \sum_i^k{|y_i|})$, proportional to the sum of the length of the keywords.

The algorithm also sets a self-loop for any unused symbols, or $g(0, a) = 0$ for all $a$ that weren't the first letter of a keyword. We only need to consider letters in the set of keywords, so this step is still bounded by the sum length.


Effective algorithm of searching the "nearest" doubly stochastic matrix Given a data matrix $D$, is there any effective algorithm to solve the optimization problem

$\min_Q || D - Q ||_F$

such that

$Qe=e$,
$e^TQ=e^T$, and
$Q_{i,j} \geq 0 $  $\forall i,j$,

where $||\cdot||_F$ is the Frobenius norm of matrix.

p.s. I also posted this question on the Mathematicss exchange.

This is a special case of the following problem: given a polytope $P$ specified by linear constraints and a point $x$ find $y \in P$ that minimizes $\|x - y\|_2^2$.

If you are ok with a small additive approximation to $\|x - y\|_2^2$, you can try using the Frank-Wolfe algorithm. This is a sort of gradient descent algorithm. You start from a point $y_0 \in P$ (in your case this could be say the $n \times n$ matrix with $1/n$ in every coordinate) and in each steps you compute $y_{i+1}$ from $y_i$ as follows:

Let $w = x - y_i$.
Let $v$ be the vertex of $P$ that maximizes $w^Tz$ for $z \in P$ (can be found by LP).
Find the point on the line through $y_i$ and $v$ that is closest to $x$ (this is quadratic optimization in a single variable). This point is $y_{i+1}$.

Ken Clarkson has analyzed this simple algorithm. In $t$ steps, the additive approximation is bounded by $d(P)^2/t$, where $d(P)$ is the diameter of $P$. In your case, I believe $d(P) \leq \sqrt{n}$, as the vertices of $P$ are permutation matrices and they all have Frobenius norm $\sqrt{n}$. So in $O(n/\epsilon)$ iterations of the above algorithm you can get $Q$ such that  $\|D - Q\|_F^2 \leq \|D - Q^*\|_F^2 + \epsilon$, where $Q^*$ is the optimal solution.