Is it known whether counting $q$-dimensional $p$-matching is $\#W[1]$-Hard? The $q$-Dimensional $p$-Matching is defined as follows:

Given disjoint universes $U_1,\ldots,U_q$, think
of an element in $U_1\times\ldots\times U_q$ as a set that contains exactly one element
from each universe $U_i$.

Now, given a family ${\cal S}\subseteq U_1\times \ldots\times U_q$ and a parameter $k\in\mathbb{N}$,
determine if there exists a subfamily of $k$ pairwise-disjoint sets in ${\cal S}$.

We abbreviate by $\#q$-Dimensional $p$-Matching (or $\#(q,p)$-matching in short) the counting version of the problem, asking how many matchings exist in $\cal S$.

In their famous paper from 2004, Flum and Grohe have developed the $\#W$ hierarchy, the counting equivalent of the $W$ hierarchy for parameterized problem.

Among their results in the paper, they have shown that counting the number of $k$-paths is $\#W[1]$-complete, and conjectured that counting the number of matchings of size $k$ in a bipartite graph is hard as well.

I'm unaware of any results addressing this conjecture, but was wondering about even a weaker result:

  Is #$q$-Dimensional $p$-Matching (counting the number of instances in a $(q,p)$-matching instace) $\#W[1]$-complete, where the parameter is $p+q$?

Such result would be weaker than the FG's conjuncture, as counting bipartite matchings is the same as $\#(2,p)$-matching.

Related result:

Recent result by Bläser and Curticapean shows that weighted counting of $k$-matching in bipartite graphs is $\#W[1]$-complete.

Our recent paper shows that counting k-matchings is #W[1]-hard even in bipartite graphs. This answers your question.

Radu Curticapean, Dániel Marx: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. CoRR abs/1407.2929 (2014)


List of Pivot rules for simplex methods Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed throughout the years.

But I have not encountered a comprehensive, systematic list of pivot rules in literature. Though comprehensiveness might be infeasible, one could hope for a list that at least contains rules that have been researched attention and discussion in the scientific community.

Do you know about such a list? Conversely, what prevents people from assembling such a list or survey?

A starting point might be this survey:

T. Terlaky and S. Zhang, "Pivot Rules for Linear Programming:A Survey on Recent Theoretical Developments", Annals of Operations Research, 46, 203 - 233, 1993.(Technical Report, pdf)


A fsm with temporal events I have defined a finite state machine

    Q = {Σ, S, s0, δ, F}

    where

    Σ = {'[r]equest', '[o]ut', '[i]n', '[e]nd'}

    S = {'[R]eady', '[I]nitiating', '[W]aiting', 'Re[C]eived', 'Re[S]etting'}

    s0 = R,

    F = {R}

    δ =  (q ∈ S and x ∈ Σ)

     q      x      q
    -------------------
     R      r      I
     I      o      W
     W      i      C
     C      e      S
     S      ∈      R

However, I have a transition from  W to S via a temporal event†. How should I represent it?
If I add an epsilon-move
     W    ∈      S
it is not intuitive that it is a temporal event.

†possibly a timeout

This was a comment first, but Suresh asked me to turn it into an answer:

Maybe you want to take a look at timed automata. These are finite automata equipped with clocks; time can pass, clocks can be reset, transitions can be restricted to occur within a given time by clock guards etc. Here are some nice introductory slides: lsv.ens-cachan.fr/~bouyer/files/bouyer_chennai.pdf

(This is actually the framework that Vor is using in his answer. His solution makes use of a clock that is reset and a guard for the epsilon transition.)


Is $AC^0$ with bounded fanout weaker than $AC^0$? In the survey "Small Depth Quantum Circuits" by D. Bera, F. Green and S. Homer (p. 36 of ACM SIGACT News, June 2007 vol. 38, no. 2), I read the following sentence:

  The classical version of $QAC^0$ (in which $AND$ and $OR$ gates have at most constant fanout) is provably weaker than $AC^0$.

A reference for this claim is missing. I will call this class $AC^0_{bf}$, where $bf$ stands for "bounded fanout". (The Complexity Zoo is down and I can't verify if such class has already a name in the literature).
If we assume unbounded fanout for the input bits, then these circuit seem to be equivalent to constant depth formulae up to a polynomial increase in the size, so the above claim doesn't make sense.
Instead, if we assume bounded fanout for the input bits too, then I cannot think of any language that separates this class from $AC^0$. A possible candidate could be the language $X := \{x | \mbox{weight}(x) = 1 \}$, i.e., the language of the strings with only one 1. It is easy to show $X \in AC^{0}$, but I didn't manage to prove that $X \notin AC^{0}_{bf}$.

The questions are:

  Is $AC^0_{bf}$ actually weaker than $AC^0$? If it is, any idea or any reference on how to prove it? And what is a language that separates those two classes? What about $X$?

A bound on fan-out of input bits and gates will make the size of the circuit linear. Let $k$ be a bound on the fan-out of the gates and inputs. It is a DAG with max out degree bounded by $k$ and max path of length $d$. The number of available wires in each level can increase $k$ times, and the number of available wires at top is $kn$, so the total number of wires in the circuit is at most $kn \sum_{i=0}^d k^i \leq k^{d+1} n$ which is $O(n)$.

Any $\mathsf{AC^0}$ function which requires super-linear size will separate the class of functions with bounded fan-out (applied also to input bits) from $\mathsf{AC^0}$. Here are some examples:

[CR96]: An $\mathsf{AC^0}$ function that need super-linear size is the $\frac{1}{4}$-approximate selector. A $\frac{1}{4}$-approximate selector is any function whose value is:

$0$ whenever the number of $1$s is at most $\frac{n}{4}$,
$1$ whenever the number of $0$s is at most $\frac{n}{4}$,
can be either $0$ or $1$ otherwise.

[Ros08] shows that the $k$-clique has $\mathsf{AC^0}$ functions complexity $n^{\Theta(k)}$ ($n^2$ input bits are possible edges of a graph with $n$ vertices). This gives a super line size lowerbound for $k\gt 2$.
It is probably possible to generalize the example in 2 can to existence of any nontrivial (requiring more than one bit) fixed induced substructure in a given unordered structure, e.g.:

existence of a path of length 2 in a given graph,
$\#_1(x)=2$,

since they require super constant number of gates depending on a bit which is not possible in $\mathsf{AC^0_{bf}}$.
The easiest example is a duplicator gate, i.e. a gate that creates $\omega(1)$ copies of its input bit. This is not possible in $\mathsf{AC^0_{bf}}$ since only $O(1)$ of gates can depend on each input bit.

Also any $\mathsf{AC^0_{bf}}$ circuit of size $S$ can be turned into a formula of size at most $k^dS$ and therefore has a $\mathsf{AC^0_{bf}}$ formula of size $k^{2d+1}n$ so any function of superlinear $\mathsf{AC^0}$ formula complexity will not be in $\mathsf{AC^0_{bf}}$.

References:

[CR96] S. Chaudhuri and J. Radhakrishnan, "Deterministic Restrictions in Circuit Complexity", 1996

[Ros08] Benjamin Rossman, "On the Constant-Depth Complexity of k-Clique", 2008

[Juk] Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", draft


Why do Agda and Coq disagree on strict positivity? I've stumbled across a confusing disagreement between Agda and Coq that is not obviously related to the most well known distinctions between their type theories (e.g., (im)predicativity, induction-recursion, etc.).

In particular, the following definition is accepted by Agda:

  data Ty : Set0 -> Set0 where
    c1 : Ty ℕ
    c2 : Ty (Ty ℕ)

whereas the equivalent Coq definition is rejected because the appearance of [Ty _] as an index of itself in c2 is considered to violate strict positivity.

  Inductive Ty : Set -> Set :=
    | c1 : Ty nat
    | c2 : Ty (Ty nat).

In fact, this case is almost verbatim an example from Coq'Art Section 14.1.2.1 of violating strict positivity:

  Inductive T : Set -> Set := c : (T (T nat)).

But I don't see the reasons for this difference between the type theories.  The classic example of proving False using a negative occurrence of a type in a constructor argument is clear to me, but I can't see how one might derive a contradiction from this style of indexing (regardless of otherwise strictly positive constructor arguments).

Poking around the literature, Dybjer's early Inductive Families paper makes an offhand comment about Paulin-Mohring's solution in the CID paper having slightly different restrictions, and vaguely suggests the differences might be related to impredicativity, but doesn't elaborate further.  Dybjer's paper seems to allow this, while Paulin-Mohring's clearly prohibits it.

Apparently I'm not the first to notice this difference of opinion, and some believe this definition shouldn't be permitted in either system (https://lists.chalmers.se/pipermail/agda/2012/004249.html), but I haven't found any explanations of why it is either sound in one system but not the other, or just a difference of opinion.

So I suppose I have several questions:

Is this an example of a monotone, but non-strictly-positive type? (In Coq; clearly Agda considers it strictly positive)
Why does Agda permit this while Coq rejects it?  It is simply an idiosyncratic difference in the interpretation of "strictly positive," is there a subtle difference between Coq and Agda that makes it sound in Agda and unsound in Coq, or is it a matter of taste driven by particular theoretical preferences?
Is there a meaningful difference between the first definition above, and the equivalent inductive-recursive definition below?

Inductive-recursive definition:

  mutual
    data U : Set0 -> Set0 where
      c : (i : Fin 2) -> U (T i)
    T : Fin 2 -> Set0
    T zero = ℕ
    T (suc zero) = U ℕ

I'm happy to have pointers to relevant literature.

Thanks in advance.

The issue seems to be confusion resulting from a confluence of two factors:

I was using a stale version of Agda (2.3.0.1).  It appears that prior to 2.3.2, Agda simply wasn't checking strict positivity of the indices of constructor results (see the bug I linked elsewhere in the thread).
A closer reading of Dybjer's Inductive Families paper suggests that he may have intended that the inductive type being defined not be bound when typing the indices of a constructor result.  Section 3.2.1 gives the scheme for inductive constructors in prose, and apparently I misread the language describing the binding environments of each portion of the scheme.

This closer reading is of course consistent with the check that Coq and (recent versions of) Agda perform, that prohibit any appearance of T in its own indices.


Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "packing" and "covering" problems in nearly linear time, and how the algorithms are instantiations of the "learning from experts" abstract framework.
Kale's thesis has an excellent presentation, but I find it very difficult to directly jump into the abstract framework, and I would prefer to start from an example of a simple problem for which it's absolutely obvious what to do, and then move to more general problems, progressively adding "features" to the algorithm and to its analysis.
For example:

How does Plotkin-Shmoys solve the linear programming relaxation of unweighted vertex cover? Weighted vertex cover? Set cover? Bipartite matching?
What is the simplest example in which the Arora-Kale algorithm is doing something interesting? How does it compute the largest eigenvalue of the Laplacian of a graph?

(Computing the largest eigenvalue of the Laplacian is equivalent to the problem of solving a weaker version of the Goemans-Williamson SDP relaxation of Max Cut, in which, instead of requiring each vector to be of length one, you want the sum of the squares of the norms to be |V|.)

Luca, since a year has passed, you probably have researched your own
answer.  I'm answering some of your questions here just for the
record.  I review some Lagrangian-relaxation algorithms for the
problems you mention, and sketch the connection to learning (in
particular, following expert advice).  I don't comment here on SDP
algorithms.

Note that the particular algorithms that you mention do not run in
nearly linear time.  (There is a nearly linear-time algorithm for
explicitly given packing or covering problems.  See
Beating Simplex for Fractional Packing and Covering Linear Programs.)
The algorithms you have in mind typically have variants that run in a
nearly linear number of iterations, but each iteration typically
requires at least linear time as well.  I discuss some of these
algorithms below.

Some useful functions

Before we start, here are some functions that we will use in the proof sketches.
(If you are interested in the algorithms, but not the proof details, you can skip ahead.)
For any vector $y$, define $\mbox{Lmax}(y)$ to be $\ln \sum_i \exp(y_i)$.
This function is an upper bound on $\max_i y_i$:
$$\max_i y_i ~\le~ \mbox{Lmax}(y) ~\le~ \max_i y_i + \ln m.$$
Analogously, define $\mbox{Lmin}(y)$ to be $-\mbox{Lmax}(-y)$,
a lower bound on $\min_i y_i$.

For convenience in what follows,
we use $g(y)$ to denote the gradient $\nabla \mbox{Lmin}(y)$ of Lmin.
We use $G(y)$ to denote the gradient $\nabla \mbox{Lmax}(y)$ of Lmax.

Explicitly, $g_i(y)$ is $\exp(-y_i)/\sum_{i'} \exp(-y_{i'})$
while $G_i(y)$ is $\exp(y_i)/\sum_{i'} \exp(y_{i'})$.

Lmin and Lmax are smooth in the following sense:
for any vectors $d\in[0,\varepsilon]^n$ and $y\in R^n$,
$$\mbox{Lmin}(y+d) ~\ge~ \mbox{Lmin}(y)
~+~ (1-O(\varepsilon))\, d \cdot g(y)$$
and
$$\mbox{Lmax}(y+d) ~\le~ \mbox{Lmax}(y)
~+~ (1+O(\varepsilon))\, d \cdot G(y).$$

Note that both of the gradients have 1-norm equal to 1:
$|G(y)| = |g(y)| = 1$.  (Throughout we use $|z|$ to denote the 1-norm.)

Note also that, for a matrix $A$,
the gradient of the function $x\mapsto \mbox{Lmin}(Ax)$ with respect to $x$
is (by the chain rule) $(g(Ax))^T A$.
More explicitly, the partial derivative of the function with respect to $x_j$
is $\sum_i A_{ij} \exp(-A_i x) / \sum_i \exp(-A_i x)$.
Likewise,  the partial derivative of Lmax$(Ax)$
with respect to $x_j$ is $\sum_i A_{ij} \exp(A_i x)/\sum_i \exp(A_i x)$.

Fractional Set Cover

Fix a Set-Cover instance.
Let $A$ denote the element/set incidence matrix.
Thus, $A_{es} = 1$ if $e\in s$, else 0,
and $A_e x$ is the extent that  fractional cover $x$ covers element $e$.

The LP is $\min\{ |x| : A x \ge 1; x \ge 0\}$.
Given $\varepsilon\in (0,1)$, the algorithm is

Initialize all $x_s = 0$.  Let $N=\log(n)/\varepsilon$.
Repeat until $\min_e A_e x \ge N$:

2.1. Choose $s$ maximizing the partial derivative of Lmin$(Ax)$ w.r.t. $x_s$.
      (Explicitly, choose $s$ maximizing $\sum_{e\in s} \exp(-\sum_{s'\ni e} x_{s'})$.)

2.2. Increase $x_s$ by $\varepsilon$.
Return $x/\min_{e} A_e x$.

The algorithm returns a $(1+O(\varepsilon))$ approximate solution
in $O(|x^*|\log(n)/\varepsilon^2)$ iterations, where $n$ is the number of elements
and $x^*$ is the optimal fractional set cover (trivially $|x^*|\le n$).
(A similar algorithm appears in the paper Chandra mentioned.
Vertex Cover is of course a special case.)

(Remark: Note that the iteration bound does not depend on the number
of sets, just the number of elements.  Thus, the algorithm can be used
with an implicitly defined set system, as long as, given weights on the
elements, one can efficiently find a set of maximum (or near-maximum) total weight.
This kind of oracle is the same as the separation oracle required to apply
the ellipsoid algorithm to the dual problem. For packing problems such
as set packing, you need an oracle that, given weights on the elements,
returns a set minimizing the total weight.  For problems such as
multi-commodity flow, you might, for example, need to find a path
minimizing the sum of some given edge weights.)

Here's a sketch of the proof of the performance guarantee.
In each iteration, the partial derivative w.r.t. the chosen $s$
is at least $1/|x^*|$, where $x^*$ is the optimal fractional set cover.

(To see why, recall that the gradient of Lmin$(Ax)$ with respect to $x$ is $(g(Ax))^T A$.
If we were to choose a set $s'$ at random from the distribution $x^*/|x^*|$,
the expected value of the partial derivative with respect to $x_{s'}$
would thus be $(g(Ax))^T \,A x^*/|x^*|$.
Since $Ax^* \ge 1$, this is at least $|g(Ax)|/|x^*|$.
Since $|g(Ax)|=1$, this is at least $1/|x^*|$.
Thus, there must exist some $s$ giving partial derivative at least $1/|x^*|$.
Since the algorithm chooses $x_s$ in each iteration to maximize
the partial derivative, it achieves a partial derivative of at least $1/|x^*|$.)

Then, the step size $\varepsilon$ is chosen just small enough so that
no coordinate of $A x$ increases by more than $\varepsilon$.
Thus, because of the smoothness of Lmin,  increasing $x_s$
to $x_s+\varepsilon$ increases $\mbox{Lmin}(Ax)$ by at least
$(1-O(\varepsilon))\varepsilon/|x^*|$.

In this way, the algorithm maintains the invariant
$$\mbox{Lmin}(Ax) \ge (1-O(\varepsilon)) |x|/|x^*| - \ln n.$$
(Note that Lmin$(\overline 0)$ equals $\ln n$.)

At termination, in the invariant, the $\ln n$ term is $O(\varepsilon)$ times the left-hand side,
so by calculation one gets $\min_e A_e x \ge  (1-O(\varepsilon)) |x|/|x^*|$.
After the normalization in the last line of the algorithm,
this implies $|x| \le (1+O(\varepsilon))|x^*|$.

FWIW, the inequalities involved in proving the invariant are essentially
the same as those involved in proving the Chernoff bound.
(In fact, this algorithm can be derived by applying the
method of conditional probabilities to a randomized-rounding
scheme that repeatedly samples sets from the distribution $x^*/|x^*|$
(with replacement), increasing $x_s$ for each sampled set $s$.
This derandomization of that gives the algorithm:
the underlying invariant is just that the pessimistic estimator stays below 1.
The exponential penalties in the pessimistic estimator come from the
using the Chernoff bound in the analysis of the rounding scheme.
This basic idea is explained further in the paper Chandra mentioned.)

Fractional Weighted Set Cover (and general fractional Covering)

To handle problems such as Weighted Set Cover efficiently,
we modify the algorithm to use non-uniform increments
(an idea due to Garg and Konemann).

The LP is $\min\{ c\cdot x : (\forall e) \sum_{s\ni e} x_s \ge 1\}$,
where $e$ ranges over the elements, $s$ ranges over the sets,
and all variables are non-negative.
To present the algorithm, first rewrite the problem as a general covering problem.
Let $A_{es} = 1/c_s$ for $e\in s$ and $A_{es} = 0$ otherwise.
Then (with a change of variables, scaling each $x_s$ by $c_s$),
the LP is $\min\{ |x| : A x \ge 1; x \ge 0\}$,
which we can view as a general covering LP.
Here is the algorithm:

Initialize all $x_s = 0$.  Let $N=\log(n)/\varepsilon$.
Repeat until all covering constraints have been deleted:

2.1. Choose $s$ maximizing the partial derivative of Lmin$(Ax)$ w.r.t. $x_s$.
     (Explicitly, choose $s$ maximizing $\sum_{e\in s} \exp({-\sum_{s'\ni e} x_{s'}})/c_s$.)

2.2. Increase $x_s$ by $\delta$, where $\delta$ is chosen maximally such that, for every remaining covering constraint $e$, the increase in $A_e \cdot x$ is at most $\varepsilon$.

2.3 Delete all covering constraints $e$ such that $A_e\cdot x \ge N$.
Return $x/\min_e A_e\cdot x$.

The algorithm returns a $(1+O(\varepsilon))$-approximate solution
in $O(n\log(n)/\varepsilon^2)$ iterations, where $n$ is the number of covering constraints.
(Each iteration increases some remaining $A_e x$ by $\varepsilon$; this can happen
only $N/\varepsilon$ times to a constraint before it is deleted.)
The proof of correctness is via essentially the same invariant as for Set Cover.

Weighted Vertex Cover is a special case.

Maximum Fractional Bipartite Matching

Given a graph $G=(U,W,E)$,
the natural LP for the problem is $\max\{|x| : \forall v.\, \sum_{e\ni v} x_e \le 1\}$.

In matrix representation, this is a packing LP $\max\{|x| : Ax \le 1; x \ge 0\}$
with 0-1 coefficients ($A_{ve} = 1$ if $v\in e$).
Such problems do not require non-uniform increments, so a simple algorithm analogous to the unweighted Set Cover algorithm (but for packing) will do:

Initialize all $x_e = 0$.  Let $N=\log(n)/\varepsilon$.
While $A x < N$:

2.1. Choose $e$ minimizing the partial derivative of Lmax$(Ax)$ w.r.t. $x_e$.
      (Explicitly, choose $e$ to minimize $\sum_{v\in e} \exp(\sum_{e'\ni v} x_{e'})$.)

2.2. Increase $x_e$ by $\varepsilon$.
Return $x/\max_{v} A_v x$.

The algorithm returns a $(1-O(\varepsilon))$-approximate solution in $O(n\log(n)/\varepsilon^2)$ iterations.
(This is because each iteration increases $|x|$ by $\varepsilon$,
and finally, before normalization, $|x| = O(N n)$.)

Just for fun, here is a curious alternative algorithm for Perfect Bipartite Matching.
Recall that $G=(U,W,E)$.  Let $n=|U|=|W|$.

Initialize all $x_e = 0$.  Let $N=4\ln(n)/\varepsilon$.
Repeat $n\,N$ times:

2.1. Choose $u$ uniformly at random from $U$.
 2.2. Choose $w$ such that $(u,w)\in E$ minimizing $\sum_{e\ni w} x_e$.
 2.3. Increase $x_{uw}$ by $\varepsilon$.
Return $x/N$.

If $G$ has a perfect matching, the algorithm returns
an $x$ such that $|x|=n$, and, with high probability,
for all vertices $u\in U$, $1-O(\varepsilon) \le \sum_{e\ni u} x_e \le 1+O(\varepsilon)$,
and for all vertices $w\in W$, $\sum_{e\ni w} x_e \le 1+O(\varepsilon)$.
If you are interested in the details of the proof, please ask...

Mixed Packing and Covering

You may have asked about bipartite matching hoping for an example
of a mixed packing and covering problem, that is, one of the form
$$\exists x?~ Px \le p; Cx \ge c; x \ge 0.$$
Here's one algorithm for such problems.
First, normalize so that $p=\overline 1$ and $c=\overline 1$.

Let $m$ be the number of constraints (rows in $P$ plus rows in $C$).

Initialize all $x_j = 0$.  Let $N=2\ln(m)/\varepsilon$.
While $P x < N$:

2.1. Choose $j$ so that the partial derivative of Lmax$(Px)$ with respect to $x_j$ is at most the partial derivative of Lmin$(Cx)$ with respect to $x_j$.  (Explicitly, choose $j$ such that $$\frac{\sum_i P_{ij} \exp(P_i x)}{\sum_{i}\exp(P_i x)} \le \frac{\sum_i C_{ij} \exp(-C_i x)}{\sum_{i}\exp(-C_i x)}.)$$

2.2. Increase $x_j$ by $\delta$, where $\delta$ is chosen maximally such that no constraint $P_i x$ or remaining constraint $C_i x$ increases by more than $\varepsilon$.

2.3. Delete all covering constraints $i$ such that $C_i x \ge N$.
Return $x/\max_i P_i x$.

Assuming the given problem is feasible, the algorithm
returns an $x$ such that $Px\le 1$
and $Cx\ge 1-O(\varepsilon)$.
The number of iterations is $O(m\ln(m)/\varepsilon^2)$,
because each iteration increases some constraint by $\varepsilon$,
and this can happen for each constraint at most $N$ times.

The proof of correctness is via the invariant
$$\mbox{Lmax}(Px) \le 2\ln(m) + (1+O(\varepsilon)) \mbox{Lmin}(Cx).$$
The invariant implies
$$\max Px \le 2\ln(m) + (1+O(\varepsilon)) \min Cx.$$
At termination the left-hand side is $\Omega(\log(m)/\varepsilon)$,
proving the performance guarantee.

In Step 2.1, the desired $j$ must exist as long as the original problem is feasible.
(This is because, for any feasible $x^*$, and any $x$,
if we were to choose a random $j'$ from the distribution $x^*/|x^*|$,
the expected value of the partial derivative of Lmax$(Px)$ with respect to $x_{j'}$
would be at most $1/|x^*|$ (see the previous proof sketch for Set Cover).
Likewise, the expected value of the partial derivative of Lmin$(Cx)$ with respect to $x_{j'}$
would be at least $1/|x^*|$.
Thus, there is an $j$ such that the partial derivative of Lmax$(Px)$ with respect to $x_{j'}$
is at most the partial derivative of Lmin$(Cx)$.)

Then the invariant is maintained in each iteration because,
by the choice of $x_j$ and $\delta$,
and the smoothness of Lmin and Lmax,
increasing $x_j$ to $x_j+\delta$
increases Lmax$(Px)$
by at most $1+O(\varepsilon)$
times the increase in Lmin$(Cx)$.

Learning (following experts / boosting)

One reference for understanding this connection is
Adaptive game playing using multiplicative weights, by Freund and Schapire.
Here is a quick summary to give the technical idea.

Consider the following repeated game.  In each round $t$:

You choose a probability distribution $p^t$ on $[n]$ (the $n$ so-called experts).
Knowing $p^t$, the adversary then chooses a payoff vector $a^t\in [0,1]^{n}$.
You receive payoff $p^t\cdot a^t$ for the round.

The game stops after some number of rounds.
Your goal is to minimize your regret
in comparison to any single expert (i.e., pure strategy) $i$.
That is, your goal is to minimize $(\max_i \sum_t a^t_i) - \sum_t p^t\cdot a^t$.

Fix any $\varepsilon>0$.
Let vector $y^t$ denote $\varepsilon \sum_{s \le t} a^s$, that is,
$\varepsilon$ times the vector sum of the payoff vectors up to time $t$.
Recall that $G(y)$ is the gradient of Lmax$(y)$.

Here's the basic strategy we will analyze:
On round $t$, choose $p^t$ to be $G(y^{t-1})$.

By inspection, this gives you payoff $a^t \cdot G(y^{t-1})$ in round $t$.

Because of the smoothness property of $F$,
$$\mbox{Lmax}(y^t) \le \mbox{Lmax}(y^{t-1}) + (1+O(\varepsilon))  \varepsilon a^t \cdot G(y^{t-1}).$$
That is, in each round, $\mbox{Lmax}(y^t)$ can't increase by more than $\varepsilon(1+O(\varepsilon))$ times your payoff.
Since $\mbox{Lmax}(\overline 0) = \ln n$,
this maintains the invariant that $\mbox{Lmax}(y^t)$
is at most your total payoff times $\varepsilon(1+O(\varepsilon)$,
plus $\ln(n)$.
On the other hand, your regret in comparison to the best expert $i$
is $\max_i \sum_t a^t_i$, i.e., $\varepsilon^{-1} \max_i y^t_i$,
which is in turn at most $\varepsilon^{-1} \mbox{Lmax}(y^t)$.

Thus, your regret is at most $\varepsilon^{-1} \ln(n)$, plus $O(\varepsilon)$ times your total payoff.

Remark: I think, as Freund and Schapire point out, a "boosting" algorithm (in learning theory) is also implicit in this analysis.  See their paper for more details.

Minimizing total payoff

You can derive a similar strategy for the setting where the goal is to minimize,
rather than maximize, the total payoff.
Your regret, which you still want to minimize, is $\sum_t p^t\cdot a^t - \min_i a^t_i$.
In that case, the corresponding strategy is to choose $p^t$ to be the gradient of $\mbox{Lmin}(y^t)$.
With this strategy your regret is again at most
$\varepsilon^{-1} \ln n$ plus $O(\varepsilon)$ times your total payoff.

Connection to Lagrangian-relaxation algorithms

To see the connection to Lagrangian-relaxation algorithms, fix a Set-Cover instance.
Consider the latter type of game (with the goal of minimizing payoff),
where the experts correspond to the elements $e$ of your set system.
In each round, choose the probability distribution $p^t$
to be the gradient of Lmin$(y^t)$ as above,
and have the adversary choose the payoff vector $a^t$ as a function of $p^t$ as follows:
choose the set $s^t$ maximizing $\sum_{e\in s} p^t_e$,
then let $a^t_e = 1$ if $e\in s^t$, and $a^t_e = 0$ otherwise.

Given the correct stopping condition (discussed below),
this process gives you exactly the Set-Cover algorithm discussed at the start.

The performance guarantee of the algorithm follows from the regret bound as follows.
Let $X_s$ be the number of times the adversary chose set $s$ during the play.
Let $x^*$ be the optimal fractional set cover.
Let $T=|X_s|$ be the number of rounds played.
The regret bound implies
$$\textstyle \sum_t a^t\cdot p^t \le  \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$

Using the definition of $a^t$, the $t$th payoff
(the $t$th term in the sum on the left)
equals $\sum_{e\in s^t} p^t_e$.
The adversary chose $s^t$ to minimize this payoff.
If the adversary had instead chosen $s^t$ randomly
from the distribution $x^*/|x^*|$, the expectation of
the payoff would have been
$$ \sum_s \frac{x^*_s}{|x^*|} \sum_{e\in s} p^t_e
~=~
\frac{1}{|x^*|} \sum_e p^t_e \sum_{s\ni e} x^*_s
~\ge~
\frac{1}{|x^*|} \sum_e p^t_e
 ~=~
\frac{1}{|x^*|}.$$
(Above we use that $\sum_{s\ni e} x^*_s \ge 1$ for all $e$, and $|p^t| = 1$.)
Since each payoff is at least $1/|x^*|$, the regret bound implies
$$ \frac{T}{|x^*|} \le  \varepsilon^{-1}\ln(m) + \min_e \sum_t a_e^t.$$
By the definition of $X$,
we have $|X| = T$ (each round chooses one set),
and $\sum_t a_e^t = \sum_e [e\in s^t] = \sum_{s\ni e} X_s$,
giving
$$\frac{|X|}{|x^*|} \le  \varepsilon^{-1}\ln(m) +\min_e \sum_{s\ni e} X_s.$$
We make the process stop when $\min_e \sum_{s\ni e} X_s = \Omega(\varepsilon^{-2}\ln m)$,
so then (rearranging terms)
$$\frac{|X|}{\min_e \sum_{s\ni e} X_s}~ \le~ (1+O(\varepsilon)|x^*|.$$
That is, normalizing $X$ gives a fractional set cover
of size at most $(1+O(\varepsilon))$ times optimum.

Remark: In a sense, this learning theory interpretation
generalizes the algorithmic interpretation.  However, some
of the algorithmic techniques necessary for efficiency
(such as non-uniform increments and dropping satisfied
covering constraints) don't seem to carry over into the
learning theory setting naturally.  Likewise, algorithms for
mixed packing and covering LPs (e.g. these)
don't seem to have natural analogues in the learning-theory setting.


An intuitive justification - Metric Embedding Based Approximation Algorithms Recently, I started (independent) learning of the theory of metric embeddings from the Fall 2003 course  offered at CMU .

I had a very basic question from the very  first lecture  of this course which I would like to get more intuition about. On page, $5$, the notes say that this technique can be used in a straightforward way to give an $\alpha$ approximation algorithms for problems like TSP if (say) the following hold.

(i) The metric embeds into a tree.
(ii) The embedding has distortion at most $\alpha$

What I am not sure about is whether the solution generated by using the embedding is even valid - because for all I know, it could be that the TSP solution on the tree uses only from among those edges which were contracted.

To be more precise, I feel more comfortable accepting that if we have got a mapping $f$ from the  original space $(X,d)$ to the tree metric $(V, d')$ which expands all the pairwise distances, then I can use the TSP solution on this tree as an approximate solution to the TSP problem on the original metric with approximation factor same as the expansion of the mapping $f$. I am not sure about how approximation factor can be the same as (or even related to) the distortion of the mapping $f$.

Thanks
-Akash

The way I remember it is that you also get a lower bound on the expected cost in the embedding. Namely for any two points $x$, $y$ at distance $d(x,y)$ in the original metric, their distance $d'(x,y)$ in the embedding satisfies $d(x,y) \leq d'(x,y)$. If I'm not mistaken, the first lecture mentions that too.

Then, everything is straightforward.

Look at the optimal TSP instance $I$ of the graph $G$. Then consider the embedding of $I$ (call it $I'$) into the tree metric. $I'$ is also an instance of TSP for the tree metric, and its cost is bounded by $E[cost(I')] \leq \alpha \cdot cost(I)$.

Therefore, if you compute $J'$, which is the optimal TSP for the tree metric, $E[cost(J')] \leq E[cost(I')] \leq \alpha \cdot cost(I)$.

Lift $J'$ back into your initial graph, which gives you an instance $J$. Thus, $cost(J) \leq E[cost(J')]$. And thus, using the previous chain of inequalities,  $cost(J) \leq \alpha \cdot OPT$.


Given a subset of of the hypercube and an affine transform of it, find the affine map This is a follow up to this resolved question.
Suppose we are given a set of bitvectors $A\subseteq\mathbb{F}_2^d$ and an invertible affine transformed copy of it
$$B=\{Mx + s\mid x\in A\}$$
for some full rank $M\in\mathbb{F}_2^{d\times d}$ and $s\in\mathbb{F}_2^d$.

Given $A$ and $B$ what are the randomized and quantum complexities of finding an $M$ and an $s$ so that $MA + s = B$ (let us assume SETH for the purposes of this post)?

Does this connect to any problems studied in tcs?

From D.W.'s comment, we see that your problem is equivalent to the same problem with $s=0$ (and with $d$ only increased by 1). The resulting problem is precisely the Linear Code Equivalence Problem over $\mathbb{F}_2$, just phrased slightly differently. (Usually CodeEq is phrased as "you have two $d \times n$ generator matrices of linear codes, is there a permutation of the $n$ columns which makes the two generator matrices have the same row-span?" In your case, the action by $GL(d,2)$ is the action which preserves the row-span, and the fact that you are only interested in a set of vectors means you essentially have an action of $S_n$ on the columns.)

Here's what's known about its complexity:

This problem is at least as hard as Graph Isomorphism (essentially goes back to Luks '93 "Permutation groups and polynomial-time computation", see Miyazaki, though it is often cited to Petrank-Roth '97)
As with GI, it is in $\mathsf{NP} \cap \mathsf{coAM} \cap \mathsf{SZK}$, by essentially the same proof as for GI.
It's no harder than Tensor Isomorphism [GQ19]
The best known worst-case upper bound is $2^{O(n)}$ (due to Babai, cf. [BCGQ11])
There is an algorithm by Sendrier 2000 that may work well in practice, depending on what kinds of codes you are looking at.


How to define the formal and informal semantics of an algorithm as accurately as possible? I am currently researching ways to define the semantics of programs for some ideas I have for a new programming language. Most ways to define semantics involve mapping the programming language syntax representation of a program to some semantic specification. I dislike this approach, because the syntax restricts what semantics you are able to express and it often results in the under and over specification of the semantics.

Instead of thinking of a programming language in terms of syntax constructs and their corresponding semantics, I want to focus on semantics first, syntax, although important to be able to best read and write programs and ultimately necessary to formulate the semantics, is of lesser importance. But in order to do so, I need a language that is capable of defining the semantics as accurately as possible. This semantic language should not be a programming language by itself, because its main purpose is defining semantics accurately, not computations. So I think most formal semantic specifications do not comply to these requirements, because they focus on extracting semantics out of existing programs instead of defining them as accurately as possible in the first place. Therefore I would like to ask the following question:

  "Are there any languages or methods that focus mainly on expressing formal and
  informal semantics of an algorithm as accurately as possible?"

During my research I was reading "Formal Syntax and Semantics of Programming Languages" by Kenneth Slonneger which include some chapters about the different ways to define the semantics for a programming language. In chapter 11 (Axiomatic Semantics), page 397, he states that "Extensive literature has dealt with the difficult problem of accurate specifications of algorithms.". But I have a difficult time finding literature that is specific about "accurate specifications of algorithms". Therefore my second question is as follows:

  "Do you know about any literature that specificly talks about how to
  define accurate specifications of algorithms?"

Edit: To make more clear what I mean by "expressing semantics of an algorithm as accurately as possible" I will give an example. If with axiomatic semantics the following pre and post conditions were given:

pre  = m >= 0 and n >= 0
post = minimum <= m and minimum <= n and minimum >= 0

Then the following function would comply:

minimum m n = 0

But this does not capture the intent the person writing the specification had.

  "Do you know of methods that could capture this intent more accurately?"

I don't know how you can define the informal semantics as accurately as possibly, but there does exist machinery for defining semantics that is purely, well, semantic.

Your semantics could be based on mathematical functions, relations, or domains. Indeed, the style of semantics known as Denotational Semantics builds upon these (and other) semantic notions by mapping the syntax in a compositional fashion to some semantic domain.

If you don't want syntax for your programming language, then start directly with the semantic domains (for example, those from Domain Theory). In this setting, each type in your programming language will be represented by a semantic domain and algorithms will then be functions from one type to another.


How Much Computing Power would be Required to Fully Simulate a Cubic Meter? Imagine you want to simulate a cubic meter down to the particle. By following the Standard Model and other basic physical equations, how much computing power would be required to do this, in say, a day?

Would a quantum computer help you in this task? Could you somehow directly simulate the particles?

Thanks

tricky question! there is some diverse crosscutting research into this question, and will attempt to outline it, but will in the end take the position here that the question is contradictory/ impossible at heart (and anticipating some this may be a controversial conclusion). here are two key recent references from a physics pov addressing your question.

Gate count estimates for performing quantum chemistry
on small quantum computers / Wecker et al
Quantum Algorithms for Quantum Field Theories / Jordan, Lee, Preskill

a rough complexity theory estimate of "simulating particle physics" is to count the number of particles, and there are about $O(n^2)$ interactions between particles, and many supercomputer simulations of particle dynamics fit this. so as a rough bound, one would pick the smallest particles, but, wait! the standard model has many subatomic particles! so one might use neutrinos, one of the smallest known stable particles, as an estimate... but then what about unstable particles such as quarks/ leptons?

there is also the whole other problematic accuracy/ precision problem of the butterfly effect long known in computational physics aka "sensitive dependence on initial conditions".

Aaronson write in his essay Is There Anything Beyond Quantum Computing?:

  Is there any such problem that couldn’t be solved efficiently by a quantum computer, but could be solved efficiently by some other computer allowed by the laws of physics?

so he sketches out weird physics such as black holes or quantum gravity that might not be simulable by a quantum computer. but flipping this whole essay on its head (in a manner it which it was unintended), what he is describing are frontier areas of physics that currently do not have complete/ definite physical theories known by humans (at best, only plausible candidates/ approximations floating around.) eg:

black holes
time curves
quantum gravity

(adding to his list)

dark matter/ energy
virtual particles, vacuum energy

so the problem comes in your title that you literally want to fully simulate a cubic meter of space. but the standard model is actually ultimately/ technically widely acknowledged/ conceded by physicists themselves (if pressed!) as an incomplete model of reality due to all the extreme/ problematic "edge cases" listed above, and others not known. even the standard model itself is problematic in that new particles/ tiny forces and revisions are added/ modified all the time, nearly "regularly", even the famous/ celebrated Higgs particle recently.

so actually its a major open question of physics whether the basic rules of reality are computable. this ties in with the digital physics research agenda.

so physicists generally regard the idea that physics of reality is computable as something of an "approximation" that physical theories are in the continual process of evolving/ finetuning but "very thorough/ precise models" are ultimately not to be confused with accurate simulations.

also relevant to this question/ impinging is that there is new "cutting edge/ borderline" physics theory/ research and experiments to attempt detect if we are "living in a hologram" ie some kind of "simulation". it is theorized that cosmic rays might have detectable properties indicating this, or other very sensitive experiments could reveal kinds of "digitization artifacts", etc.; one example:

The Measurement That Would Reveal The Universe As A Computer Simulation / MIT tech review


Resources for Church's paper "An Unsolvable Problem of Elementary Number Theory"? I'm trying to understand and breakdown into simple English Church's paper for "An Unsolvable Problem of Elementary Number Theory" but I'm not finding anything useful online, only citations and links to the full paper.

Does anyone know any resources I can get to help me understand this paper?

The article "The Church-Turing Thesis" of the Standford Encyclopedia of Philosophy might help and/or provide references to texts that might be useful to you. The article by Joachim Breitner Church’s undecidability result might help you as well.


Oracular separations between poly- and log-depth quantum circuits The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory.

  Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any quantum algorithm be compressed to $\mathrm{polylog}(n)$ depth, provided we're
  willing to do polynomial-time classical postprocessing? (This is known
  to be true for Shor's algorithm.) If so, building a general-purpose
  quantum computer would be much easier than is generally believed!
  Incidentally, it's not hard to give an oracle separation between $\mathsf{BQP}$
  and $\mathsf{BPP}^{\mathsf{BQNC}}$, but the question is whether there's any concrete function "instantiating" such an oracle.

It has been conjectured by Jozsa that the answer to the question is yes in the ''measurement-based model of quantum computation": where local measurements, adaptive local gates and efficient classical post-processing are allowed. See also this related post.

Question. I would like to know about the currently-known oracular separations between this classes (or, at least, the oracle separation to which  Aaronson is referring to).

I apologize; I was too glib when I wrote that.  While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it.  Maybe your post will help motivate me to finally kill this problem off!


Why is label pruning possible with hub labeling? Hub labeling (HL) computes superlabels using the vertices visited by the forward and reverse Contraction Hierarchies (CH) search. Those labels are then pruned (see HL, sec. 4.2) to generate strict labels.

I don't understand how there can be labels that can be pruned. From my understanding the shortcuts added by CH should make sure that in both forward and reverse searches we will either

reach a node via a shortest path or
not reach a node at all.

How is it possible that we reach some nodes via a path that is longer than the shortest path? Could anyone provide a minimal example?

I have emailed the authors and they kindly supplied me with the following example:

Let the nodes be contracted in alphabetical order then the red edge will be added during contraction.

Now look at the upward search from A (i.e. we can only visit nodes that have been contracted later). A will settle B with distance 1 and D with distance 2. Since we are not allowed to visit C via D (as this is not upward) we must settle C via B with distance 6. However, as can clearly be seen from the non-contracted graph, the A-C distance is 5 (via D).

This means that we now have an incorrect distance label for C at A.


Decide the existence of a string homomorphism Consider the following problem:

  Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y.

It is easy to show that this problem is in $NP$. Are there other things we can say about this problem? e.g. Is it in $coNP$, or even $P$?

This problem seems very natural, so I am not surprised if it has been studied thoroughly. However I could not find this problem in literature.

It's discussed in one of the very first papers about strings and complexity, namely, Dana Angluin, Finding patterns common to a set of strings, J. Comput. System Sci.
21 (1980), 46-62.  Look at Theorem 3.6.  The problem is NP-complete.

It's also in A. Ehrenfeucht, G. Rozenberg, Finding a homomorphism between two words is NP-complete, Inform. Process. Lett. 9 (1979) 86–88.


Efficient algorithm for existence of permutation with differences sequence? This question is motivated by this post, Can you identify the sum of two permutations in polynomial time? , and my interest in computational properties of permutations.

A differences sequence $a_1, a_2, \ldots a_n$  of a permutation $\pi$ of numbers $1, 2, \ldots n+1$ is formed by finding the difference between every two adjacent numbers in the permutation $\pi$. In other words, $a_i= |\pi(i+1)-\pi(i)|$ for $1 \le i \le n$

For example, sequence $1, 1, 3$  is the differences sequence of permutation $2 3 4 1$.  While, sequences $2, 2, 3$ and $ 3, 1, 2$ are not the differences sequence of any permutation of numbers $1, 2, 3, 4$.

  Is there an efficient algorithm to determine whether a given sequence is the differences sequence for some permutation $\pi$, or is it NP-hard?

EDIT: We get computationally equivalent problem if we formulate the problem using circular permutations.

EDIT2: Cross posted on MathOverflow, How hard is reconstructing a permutation from its differences sequence?

EDIT3 Awarded the bounty to the proof sketch and I would accept the answer after getting the complete formal proof.

EDIT 4: Marzio's nice $NP$-completeness proof has been published in the Electronic Journal of Combinatorics.

This is a sketch of a possible reduction to prove that it is NP-hard:

1) $a_i$ subsequences made of 1s (e.g. $...11111...$) (I call them 1SEQ) force a subsequence of increasing or decreasing numbers in the permutation;

2) if a value of $2$ is put in a long 1SEQ,  it forces a hole (a missing number) and doesn't change the direction of the 1SEQ. For example: $1112112111$ forces two holes:

 a_i seq.:     1 1 1  2  1 1  2   1  1  1  forces
 permutation: 1 2 3 4 _ 6 7 8 _ 10 11 12 13 (or its decreasing equivalent)
 (from 4 you cannot go back to 2,
 from 8 you cannot go back to 6)

The holes must be filled in the rest of the permutation.

3) using a large enough 1SEQ, followed by a 1SEQ with some holes, followed by another large 1SEQ you can build a forced line;

4) putting together many forced lines you can build a permutation grid graph in which the nodes correspond to the missing numbers in the underlying forced permutation.

For example the sequence 1111111112111111111112111111111, forces the following 5x7 permutation grid graph:

29 30 31 32 33 34 35
22 23 24    26 27 28
15 16 17 18 19 20 21
 8  9 10    12 13 14
 1  2  3  4  5  6  7

(or its symmetric version). Note that if the grid has size $w \times w$ and $a,b$ are two missing numbers in the same vertical column then $|a-b|=kw$.

5) the Hamiltonian cycle on grid graphs problem is NP-complete; so given a grid graph $G$ (with holes) you can build the equivalent permutation grid graph;

6) from the last number of the permutation you can "jump" to a number corresponding to a hole (a node in $G$), and with a fixed sequence of moves you can simulate the traversal of $G$; this requires a rather complex gadget - the "selection gadget" - that must be created in another part of the permutation grid graph;

7) you can fill all the holes (i.e. complete the permutation) if and only if the original grid graph has an Hamiltonian cycle

EDIT: July, 27 2013

I tried to formally prove the NP completeness of the problem: I introduced a new problem (Crazy Frog problem) which is NPC.
The Permutation Reconstruction from Differences problem is equivalent to the "1-D Crazy Frog problem without blocked cells" (which is also NPC).

For the details of the reduction see my question/answer  on cstheory
"Two Hamiltonian path variants" or download a draft of the proof "When a frog meets a permutation" :)) (I'm still checking/completing it)


What is the complexity of this weighted b-edge matching problem? I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:

Input: An undirected multigraph $G = (V, E)$ without
loops, an edge partition $(E_1,E_2)$ such that $E_1 \cup E_2 = E$, capacity functions $b_l , b_u : V \to \mathbb{N}_0$,
a weight function $w : E \to  \mathbb{N}_0$ and target integers $r_1,r_2$.

Question: Are there subsets of edges $E_1' \subseteq E_1$ and $E_2' \subseteq E_2$ such that

$\sum_{e\in E_1'} w(e) \geq r_1$ and $\sum_{e\in E_2'} w(e) \geq r_2$; and
$b_l (v) \leq | (E_1' \cup E_2') \cap \delta (v)| \leq b_u(v)$ holds for each vertex $v \in V$ ($\delta (v)$ is the set of edges incident to vertex $v$)?

Is this problem solvable in polynomial-time or NP-hard?

Without the edge partition we have the standard problem which is solvable in
polynomial-time (see Gabow [1] or Anstee [2]). This variant seems to be similar to
the Directed Two-Commodity Integral Flow problem which is NP-hard but I couldn't figure out a reduction to this variant.

[1] Gabow, H. N.   1983.   An efficient reduction technique for degree-constrained subgraph and  bidirected  network  flow problems.  In Proceedings of the fifteenth annual ACM symposium on Theory of computing, 448–456.

[2] Anstee, Richard P. "A polynomial algorithm for b-matchings: an alternative approach." Information Processing Letters 24.3 (1987): 153-157.

Assuming $x(e)=1$ in Condition 2, the problem is NP-complete.

Clearly it is in NP.  We show NP-hardness by reduction from Subset Sum:

Lemma 1. The problem is NP-hard.

Proof. The proof is by the following reduction from Subset Sum.  Given a Subset-Sum input $(y, T)$, where $y=(y_1, y_2, \ldots, y_n)$ is a sequence of integers, and $T$ is the target, the reduction outputs the following instance of the problem defined by OP.

For each given integer $y_i$, create two new vertices $v_i$ and $v'_i$, and add two copies of edge $e_i=(v_i, v'_i)$, each with weight $w(e_i) = y_i$.  Put one copy of $e_i$ in $E_1$ and the other in $E_2$, and make $b_\ell(v_i) = b_u(v_i) = b_\ell(v'_i) = b_u(v'_i) = 1$.  Finally, take $r_1 = T$ and $r_2 = (\sum_i y_i) - T$.  This completes the reduction.

Given any subsequence of $y$ that sums to $T$, there is a corresponding solution $(E'_1, E'_2)$ to the created instance, where, for each $i$, if $y_i$ is in the subsequence we put the copy of $e_i$ that is in $E_1$ in $E'_1$, and otherwise we put the copy of $e_i$ that is in $E_2$ in $E'_2$.  Then each vertex has one chosen edge incident to it, the total weight of edges in $E'_1$ is $T$, and the total weight of edges in $E'_2$ is $(\sum_i y_i) - T$, as required.

Conversely, consider any solution $(E'_1, E'_2)$ to the created instance.  Form a corresponding solution to the Subset-Sum instance by choosing the elements $y_i$ of $y$ such that $e_i$ is in $E'_1$.  It sums to at least $T$ by Condition 1. And it sums to at most $T$ because, for each edge $e_i$ that is not in $E'_1$, it must be that $e_i$ is in $E'_2$ (by Condition 2), and the total weight of such edges must be at least $(\sum_i y_i) - T$ (by Condition 1).  $~~\Box$


FO(TC) lower bounding games? Is anyone aware of any games/algebraic structures that provide lower-bounding methodologies for $FO(TC)$ formulae? I am aware of EF games as they apply to first-order and second-order statements, but would like to be able to determine lower bounds for $FO(TC)$ queries on finite models. Any help in this direction would be appreciated!

As mentioned above: question answered by reference to FO(TC) games presented in Finite Model Theory by Ebbinghaus and Flum.


Who introduced nondeterministic computation? I have two historical questions:

  Who first described nondeterministic computation?

I know that Cook described NP-complete problems, and
that Edmonds proposed that P algorithms are "efficient" or "good" algorithms.

I searched this Wikipedia article and
skimmed "On the Computational Complexity of Algorithms,"
but couldn't find any reference to when nondeterministic computation was first discussed.

  What was the first reference to the class NP? Was it Cook's 1971 paper?

I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.


Reversing the CPS transformation? A quick Google search didn't turn up anything obvious, so I'm asking here.

Converting direct style programs to continuation-passing style is a well-studied program transformation. However, I'm interested in the reverse transformation -- I'd like to take a program in CPS, and convert it to direct-style. Obviously the identity trasnformation works, in a vacuous sense, but I'm interested in transformations that are "as direct-style as possible".

I think your looking for Back to Direct Style by Olivier Danvy


Casual tours around proofs Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique.

My question is not about the technique itself (of course worthy of immense praise), but it's about the style of the paper.
In the abstract, he writes:

  The proof will be described from the perspective of someone trying to
  discover it.

Awesome!
In the Background section he adds:

  This article is a discussion about how to discover the proof – a
  casual tour around it. Not all details will be given, but you will see
  where all the pieces came from, and how they ﬁt together. The path
  will be littered with my own biased intuitions about complexity theory
  – what I think should and shouldn’t be true, and why. Much of this
  intuition may well be wrong; however I can say it has led me in a
  productive direction on at least one occasion.

This is amazing and it's the first time that I have seen it. I have always wondered why authors of paper don't write how they got to the proof, including the failed approaches they tried before getting to the track that led the solution. When I saw Ryan's paper on the arXiv, I felt very motivated to read it.
I consider it a revolutionary paper from this point of view. Most of the time the only thing you can do with a paper is verifying its correctness.

The question is the following:

are you aware of other papers in TCS where a breakthrough result is presented in a "casual tour" rather than a series of technical lemmas?

I am talking about publications in journals, not blog posts or technical reports.

Also, I tagged it as big-list, with the hope that it will actually be.

Tim Gowers is a fan of this kind of thing.  See specifically his exposition of Razborov's method of approximations.

In his introduction, Gowers references my expository article on forcing, which is a (not entirely successful) attempt to do the same thing for forcing.  Forcing is normally thought of as a technique in logic and set theory, but it has found its way into TCS occasionally.  It comes up in the study of bounded arithmetic and propositional proof complexity (Krajíček and Takeuti are two researchers who have pursued this connection), and the concept of a generic oracle is related to the concept of a generic filter.


Generalisations of the Fundamental Theorem of Statistical Learning to different tasks and losses The fundamental theorem of statistical learning gives an equivalence between uniform convergence of the empirical risk to learning in the PAC framework.
I have only seen this stated in the case of binary classification with the 0-1 loss.
Does a result of this form hold in more general settings? For example: margin-based classification rules, regression, multi-class classification, ...?
Another statement of this question could be: under what circumstances does uniform convergence of the empirical risk imply PAC learning? (I am most interested in this direction of implication.)
Please provide references if you have them.

Turns out the answer is yes and can be found in Part 3 (eg chapter 19) of Neural Network Learning: Theoretical Foundations, by Anthony and Bartlett.


Bounds on the smaller eigenvalues of the adjacency matrix of a graph Are there any known (non-trivial) bounds (combinatorial in nature, based on poly-time computable properties of a graph) on the third, down to the smallest, eigenvalue of an (un-weighted) adjacency matrix? For example we know that the largest eigenvalue admits the following bounds
$$\max(\sqrt{d_{\max}}, d_{\text{ave}})\le \lambda_{\max}=\lambda_1 \le d_{\max}$$
Anything of the above flavor for $\lambda_i$, $i\ge 3$?
(Given that these can be negative, (lower) bounding $|\lambda_i|$ might seem more appealing.)

You might like this recent paper: http://arxiv.org/abs/1211.0589v1

The paper shows, e.g., that "for any finite graph with $n$ vertices and all $k ≥ 2$, the
$k$th largest eigenvalue" of the graph's Laplacian, i.e. $L=I-A/d$, "is at most $1−\Omega(\frac{k^3}{n^3})$", where $A$ is the adjacency matrix and $d$ a bound on the degree.


Is Parity-P contained in PP? This question was asked by Jan Pax on the Foundations of Mathematics mailing list.
Certainly $P^{\oplus P} \subseteq P^{\#P} = P^{PP}$
but I suspect from the answers to this question that it's not known whether $\oplus P \subseteq PP$ (otherwise, $PP$ would be one possible answer to that question).  If it's not known, is there an oracle separation?

Scott Aaronson gives an oracle where $\oplus$P = PEXP which implies the oracle you want. http://eccc.hpi-web.de/report/2005/040/download/ (Theorem 12 in the appendix)


general statement what kinds of problems can be solved more efficiently is there a general statement what kinds of problems can be solved more efficiently using quantum computers (quantum gate model only)? do the problems for which an algorithm is known today have a common property?

as far as i understand quantum computing helps with the hidden subgroup problem (shor); grover helps speedup search problems. i have read that quantum algorithms can provide speed-up if you look for a 'global property' of  a function (grover/deutsch).

is there a more concise and correct statement about where quantum computing can help?
is it possible to give an explanation why quantum physics can help there (preferably something deeper that 'interference can be exploited')? and why it possibly will not help for other problems (e.g. for NP-complete problems)?

are there relevant papers that discuss just that?

(sorry, new here. hope that question is appropriate & understandable and there is not too much wrong in my statements...)

My limited understanding is that problems in which cyclic groups or their products play a central role usually have very good (exponential to polynomial complexity) speedups when quantum algorithms are used.

This is due to the fact that the complex Fourier transform plays a central role in the representation of quantum states.

The fact that Grover's search doesn't have this impressive speedup is also due to the fact that it is not tightly related to cyclic groups.


Optimality of Greedy algorithm for minimization Knapsack Problem Given items with weight $w_i$ and profits $p_i$, minimization Knapsack problem is to pick a subset of items $I$, s.t. $\sum_{i\in{I}}{w_i} \geq W$ and $\sum_{i\in{I}}{p_i}$ is minimized.

The greedy algorithm simply sorts items based on ratio $\frac{p_i}{w_i}$. It scans and sum up the sorted items in increasing order, until $\sum{w_i}\geq{W}$. Then outputs $\sum{p_i}$.

If the distribution of $p_i$ is known (say, following zipf distribution) and $w_i$ is randomly distributed, and independently with value of $p_i$, then what is the average optimality ratio which is ratio of $\sum_{i\in{I}}{p_i}$ to the optimal results.

Note: in worst case, this greedy algorithm can be arbitrarily bad, according to
following book. P412, Knapsack Problems, By Hans Kellerer, Ulrich Pferschy, David Pisinger.

I didn't understand the question very well, but I think you're asking about the ratio of the greedy solution to the optimal solution when the problem instances are taken out of a certain probability distribution. I don't have a theoretic solution to this problem, but if you need the answer for practical reasons, then I think a Monte-Carlo simulation would give reliable results.  You can approximate knapsack to the desired precision using the well-known dynamic programming algorithm to obtain an approximate value of the optimal solution and then compare it to the greedy algorithm. You generate a number of random instances, and see where the ratio usually falls.
In order to have more reliable estimates, you can establish confidence intervals for the fraction of instances whose greedy/optimal ratio falls within a given interval, etc.


Efficient algorithm for testing planarity of the union of two planar graphs Let $G_1 = (V,E_1)$ and $G_2 = (V,E_2)$ both be planar graphs.

Is there an efficient algorithm to check whether the union $G = (V,E_1\cup E_2)$ is planar?
That is, an algorithm more efficient than the obvious one of running the standard linear planarity test on the union.

You might be interested in an online algorithm, which is one that processes the input in a serial manner. Here is a paper with fast algorithms that tests planarity after adding an edge or a vertex, and does so much faster than $O(m+n)$ time (it does so in $O(\log{n})$):

http://epubs.siam.org/doi/abs/10.1137/S0097539794280736?journalCode=smjcat

You will be interested in the edge-addition version of this. And you could ask your question with any two edge sets, but since you seem to have info that both $G_1$ and $G_2$ are planar, you can start with the one which is larger, knowing it is planar, then add edges from the other graph one at a time.

In a 'worst case' where $|E_1| = |E_2| = m$, you would have to decide when this $\frac{m}{2}O(\log{n})$ is better or worse than just applying a $O(m+n)$ planarity test.


How do I construct an optimal affix code? An affix code is a code that is simultaneously a prefix and suffix code. That is, no codeword is neither the prefix nor the suffix of any other codeword. Affix codes can be instantaneously decoded in both directions (forward and backward).

I want to create one that optimally compresses a given input symbol distribution, given a set of output symbols.

The Huffman algorithm (which creates prefix codes) comes closest, but due to its greedy strategy, it seems unsuitable for modification to this purpose.

How can optimal affix codes be found?

I really don't think that there is a known algorithm to be optimal. In fact, there is a major conjecture about how effective a set of code words can be, see: http://arxiv.org/abs/0709.2598
(the name I knew for affix code is fix-free code). If an algorithm was proved to be optimal, then most probably it would also solve (or disproof) this conjecture as well.


Counting/Enumerating Minimal Edge Covers A Minimal Edge Cover is an Edge Cover such that no other Edge Cover is a proper subset of it.

  Questions

   Which is the complexity of counting Minimal Edge Covers? Do we know any non-trivial upper bound on their number? Is there any clever algorithm in literature to enumerate them?

  Empirically, I'm observing that the number of Minimal Edge Covers seems to be always odd: so far in my experiments I've never met a graph having an even number of them. Is this a theoretically proven fact? If not, has their parity been investigated in literature?

Counting edge covers is #P-complete. You can find a proof here Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT. See also the stack-exchange discussion. One can probably modify the proof to show #P-completeness for minimal edge covers.
enumerating (minimal) edge covers can be done with polynomial delay as the hypergraph has bounded degree (see New Results on Monotone Dualization and Generating Hypergraph Transversals)
the following Low-Exponential Algorithm for Counting the Number of Edge Covers on Simple Graphs claims an $O(1.465575^{(m−n)} × (m + n))$ time algorithm. I am wondering whether one cannot do better.


Is convex optimisation in P? Consider a convex optimisation problem in the form

$$\begin{align}
f_0(x_1, \ldots, x_n) &\to \min \\
f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$

where $f_0, f_1, \dots, f_m$ are convex functions. Without loss of generality, we can assume that $f_0$ is linear.

Nesterov and Nemirovskii mention in their book "Interior point polynomial algorithms in convex programming" that there is an algorithm which is able to solve any convex program in polynomial time in the following sense. We want to have a solution within a relative accuracy $\varepsilon$ at the cost of $O(p(n,m) \ln (n/\varepsilon))$ computations of the values and $O(q(n,m) \ln(n/\varepsilon))$ computations of the subgradients. Then, for the ellipsoid method, it is claimed that

$$p(n,m) = n^3 (m+ n), \qquad q(n,m) = n^2$$

At first glance, this seems to imply that a convex optimisation problem can be solved in polynomial time using the ellipsoid method (let us assume for simplicity that the oracles for computing the values and the subgradients require $O(1)$ time for the considered class of convex optimisation problems).

However, I totally don't understand, whether the $O(\cdot)$ expressions are somehow dependent on the functions $f_i$, e.g., on their Hessians, or not. In this case, the complexity may have an exponential blowup due to curvature properties of the functions. Moreover, it is mysteriously claimed that "ellipsoid method doesn't work well in practice". There seems to be no consensus in the internet whether the answer to my question is affirmative or negative, see e.g. this discussion on MathOverflow.

I have searched on every book on convex optimisation I could find, and I have gotten an impression that this $O(\cdot)$ indeed depends on the problem, but could not find any clear confirmation of this guess. So my only hope is to directly ask people who are doing research in this field.

Interior point methods that have been developed later seem to explicitly account for the curvature using the notion of self-concordant barriers. But when people say that these methods are efficient in practice, they usually don't specify this on the level of complexity.

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

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

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

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

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

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


On $n$ dimensional manifolds and lattices EDIT (By Tara B):  I'd still be interested in a reference to a proof of this, as I had to prove it myself for my own paper.

I'm looking for the proof of Theorem 4 that appears in this paper:

An Infinite Hierarchy of Intersections of Context-Free Languages by Liu and Weiner.

  Theorem 4: An $n$-dimensional affine manifold is not expressible as a finite union of affine manifolds each of which is of dimension $n-1$ or less.

Does anyone knows a reference to the proof?
If the manifold is finite and we define a natural order on the elements, is there any similar statement in terms of lattices?

Some background to understand the theorem:

Definition: Let $\mathbb{Q}$ be the set of rational numbers. A subset $M\subseteq \mathbb{Q}^n$ is an affine manifold if $(\lambda x+(1-\lambda)y)\in M$ when $x\in M$, $y\in M$, and $\lambda\in\mathbb{Q}$.

Definition: An affine manifold $M'$ is said to be parallel to an affine manifold $M$ if $M'=M+a$ for some $a\in \mathbb{Q}^n$.

Theorem: Each non-empty affine manifold $M\subseteq \mathbb{Q}^n$ is parallel to a unique subspace $K$. This $K$ is given by $K=\{x-y:x,y\in M\}$

Definition: The dimension of a non-empty affine manifold is the dimension of the subspace parallel to it.

Here is a measure-free proof which works for affine manifolds over an arbitrary infinite field $\mathbb F$ (the result is false for finite fields).

By induction on $n\ge0$, we will show that an affine manifold $A\subseteq\mathbb F^m$ of dimension $n$ is not a finite union of affine manifolds of dimension less than $n$.

The statement is clear for $n=0$: a point is not a (finite) union of empty sets.

Assume the statement holds for $n$, we will show it for $n+1$. Let $A=\bigcup_{i<k}A_i$, where $\dim(A)=n+1$ and $\dim(A_i)\le n$. Consider an arbitrary affine submanifold $B\subset A$ of dimension $n$. Since $B=\bigcup_i(B\cap A_i)$, the induction hypothesis implies that $\dim(B\cap A_i)=n$ for some $i<k$, i.e., $B=A_i$. Since there are only $k$ sets $A_i$, and $B$ was arbitrary, it follows that $A$ has only finitely many submanifolds of dimension $n$. However, this is a contradiction: if we fix any such submanifold $B_0$ and a vector $v$ parallel to $A$ but not to $B_0$, there are infinitely many affine submanifolds of $A$ of the form $B_0+av$, where $a\in\mathbb F$.


References to programming languages based on conditional logics Conditional logics are logics which augment traditional logical implication with modal operators corresponding to other notions of condition (for example, the causal conditional $A\; \square\!\!\!\!\to B$ reads "$A$ causes "B", or probabilistic conditioning "$A|B$", which reads "$A$ given $B$").

Typically these logics are studied model-theoretically, but I've wondered about their applications to programming language design (for example, to type imperative actions).

I'd appreciate references to their proof theory (ie, sequent calculus/natural deduction), or to programming languages with types based on these kinds of modal operators.

Thanks!

EDIT: The Stanford Encyclopedia of Philosophy has a nice introduction to the subject.

Check these references:

Programming languages CondLP and CondLP+:

Gabbay, Giordano,  Martelli, Olivetti, Sapino, Conditional reasoning in logic programming,  Journal of Logic Programming, Volume 44, Issues 1-3, 1 July 2000, Pages 37-74

Claudia, Oliveira, The implementation of CondLP, Lecture Notes in Computer Science, 1996, Volume 1085/1996, 713-715

Gabbay, Giordano, Martelli, Olivetti, Conditional logic programming, Proc. 11th Int. Conf. on Logic Programming, Santa Margherita Ligure, pages 272–289, 1994.

References to proof theory:

Olivetti, Pozzato, Schwind, A sequent calculus and a theorem prover for standard conditional logics, Journal ACM Transactions on Computational Logic (TOCL), Volume 8 Issue 4, August 2007


What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD I have been thinking about Pspace in conjunction with searching for a Natural Notion of Stablilty for Complex Dynamical Systems.

A natural question in this direction is the Nash equilibrium. Surprizingly, it appears that Games in Normal Form have Nash equilibria which is PPAD complete. This has led myself to wonder about the inclusion relationships of various associated Complexity Classes.

Thanks in advance.

Strictly speaking, PSPACE contains decision problems, while the others are search problems, so they live in different zoos, but FPSPACE would of course contain all the other problems. Then PPAD is contained in both PPA and PPP, whose relationship is unknown, but were separated by an oracle in Beame et al: Relative complexity of NP search problems. Here the PLS class was not considered, that was separated by an oracle later in Morioka: Relative complexity of local search heuristics and the iteration principle from all the other three classes. (For me this latter paper was too hard to read.) Without oracles, nothing is known.


Semantic equivalence using a model of computation of two languages I am relatively new to the field of language semantics. However i had a question pertaining to language equivalence (i did read about the question, however my approach is slightly different and hence this question).

If i have two languages $A$ and $B$ and both languages can be expressed using a model a computation like $\pi$-Calculus. If i have to prove that the 2 languages are equivalent, then would it be need to show that the 2 $\pi$-Calculus constructs (starting from the most atomic elements of the language to then the composition of the elements etc) of the two languages are equivalent, is this correct?

How do we prove equivalence between two $\pi$-Calculus representation of the languages?. Can i use bisimulation in $\pi$-Calculus to prove the same or have i missed something and is there another formal proof to do the same?

Let me clarify the setting, which has nothing to do with $\pi$-calculus or bisimulation.

The first thing you have to realise that it does not make much sense to talk about a programming language without reference to the notion of program equivalence you intend to impose on the language. That's because

We usually identify certain programs (e.g. f(x:int) = { x+1 } is considered the same as  f(y:int) = { y+1 }).
The notion of program equivalence to be used depends highly on what you are doing with these languages, e.g. sometimes we care about program time- or space complexity, sometimes we don't.

So the general setup you are interested in is this: you are given 3 language $(A, \cong_A)$, $(B, \cong_B)$ and $(T, \cong_T)$, each comprising of a set of programs ($A$, $B$ and $T$)  with associated notions of program equivalence ($\cong_A$, ...). In addition, you have two mappings:

$trans_A : A \rightarrow T$.
$trans_B : B \rightarrow T$.

They map ("compile") from source languages $A$ and $B$ to target $T$. Typically you want these two translation functions to be at least sound. That means that for all $A$-programs $P, Q$, we have: $trans_A(P) \cong_T trans_A(Q) \Rightarrow P \cong_A Q$, and likewise for $trans_B$.

Now you want to argue that $(A, \cong_A)$ and $(B, \cong_B)$ are equivalent as languages. That's what you use the target $(T, \cong_T)$ for. There are many ways that this can be done, details depend on what concept of language equivalence you are interested in. One approach could be to say

For each $A$-program $P_A$ there is a $B$-program $P_B$ such that $trans_A(P_A) \cong_T trans_B(P_B)$.
Vice versa.

None of the above is $\pi$-calculus specific, but you
 can instantiate $T$ with $\pi$-calculus and $\cong_T$ with any chosen notion of equivalence on $\pi$-calculus such as strong or weak bisimulation, maximum consistent theory, reduction congruence, or whatever else makes sense for your application.

I said that there are many alternative ways of doing this. You could for example impose constraints on $trans_A$ and $trans_B$ so the translation preserves chosen constraints (e.g. termination, or compositionality).


What can we say about a fixed point for a provability predicate in deductively defined theory that satisfies diagonalisation lemma I am wondering whether this is the right site to ask this question, but since it involves proof and diagonalisation, hopefully it is the right place.

I am curious and trying to reason about what consequences we get if we use the predicate in the diagonalisation lemma as the provability predicate. I don't think I succeeded, I would appreciate if anyone could lend some help.

So here it is:

  Suppose Pr is a provability predicate for a deductively defined theory T, where T is a theory satisfying the diagonalisation lemma. Suppose A is a FIXED POINT for Pr in T, that is, that $T\vdash Pr(\ulcorner A\urcorner)\equiv A$.

My question is: What can we say about the formula A? Is it provable in the theory T? Is it refutable in the theory T? (That is, is its negation provable in T?) Could it be either provable or refutable?

I tried to reason as follow: (To be honest I have not yet got the hang of it, I find this topic a bit confusing, so there should be many flaws in my reasoning, please kindly correct my mistakes)

Since $T\vdash Pr(\ulcorner A\urcorner)\equiv A$ so $T\vdash A$. In words, since T can show that $\ulcorner A\urcorner$ is provable iff $A$, so T can show A. So A is provable in T. I don't think it sounds correct, but I have no idea how to fix it.

To grasp the concept better, I think it is easier for me to think of an example, but I am still struggling to find one. I am trying to find examples of formulas which are fixed points for Pr in the theory of Peano Arithmetic.

What I can think of about properties of numbers are like eveness, primeness. So suppose Pr represents there is a proof that $\ulcorner A\urcorner$ is even, and A is "I am even". Is my example correct? Again, I am really doubtful about my own example.

Also, if anyone has any better way to understand the topic, I would be more than happy to learn.

Many many thanks in advance, I really appreciate any helps.

The formula $A$ is provable, this is almost exactly the content of Löb's Theorem.

The proof (which can be found on the Wikipedia page) is a bit contorted, as it requires an additional application of diagonalization to build and analyze the formula:

$$ \Psi \equiv Pr(\lceil\Psi\rceil)\rightarrow A $$


Arithmetic complexity of matrix powering Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables.

We know that size of smallest formula that computes $\mathsf{Tr}(M^d)$ where $d\in\Bbb N$ could be exponentially large in $n$ and $m$ at least when $n=m^2$.

Could it be possible that the smallest circuit size can be polynomial while formula size is exponential at least for case $n=m^2$?

Do the answers differ much if we seek monotone circuits and formulas?

It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with polynomial formula size [Ben-Or and Cleve]. (For $m=2$, it is not as powerful [Allender and Wang]). [Update: As far as I know, this is only true for iterated matrix multiplication $tr(M_1 M_2 \dotsb M_d)$, rather than matrix powering $tr(M^d)$. When $m$ is allowed to grow these two are essentially equivalent, but for fixed $m$, e.g. $m=3$ I don't know if $3 \times 3$ matrix powering is poly-formula-size-complete.]

If $m$ can grow but $d$ is fixed, then this is the same as matrix multiplication, up to $O(\log d) = O(1)$ factors. Since circuits for matrix multiplication can be converted to bilinear circuits with only a factor 2 blow-up in size, circuit and formula size here are essentially the same, and the question boils down to the classic open question of the exponent of matrix multiplication.

If both $m$ and $d$ can grow, then this is equivalent in power to the determinant (corresponding to the Boolean class $\mathsf{DET}$ and the algebraic class $\mathsf{VP}_{ws}$). So here the question becomes about the circuit/formula complexity of the determinant. Both of these are well-known open questions (obviously there are cubic circuits; the best known upper bound on formula size of the determinant is quasi-polynomial).

Most (perhaps even all) nontrivial algorithms for matrix multiplication use cancellations in a crucial way, so I would expect there is a difference between the monotone case and the unrestricted case. Also, note that the equivalence between matrix powering and determinant in the last case is necessarily non-monotone (since matrix powering is a polynomial with all nonnegative coefficients, but the determinant is not).


Hardness of additive approximation to Graph Coloring problem. In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the assumption of $P \neq NP$), it's easy to show that for any constant $k$, there is no approximate algorithm $A$ to Graph Coloring such that $\chi(G) \leq A(G) \leq \chi(G) + k$.

But i can't see how to show/prove this.

As i see, it isn't so direct, because for any $k$, there are graphs such that $\chi(G) \leq k$, so for them $\chi(G) + k \geq 2 \cdot \chi(G)$ and it would be $(2 + \epsilon)$-approximative, for some $\epsilon \geq 0$, for these graphs.

So i'm asking for some help/advice on how to show/prove this.

Let $G$, with $\chi(G) \geq 3$ (otherwise you have an exact algorithm).

Now construct a graph $H$ consisting of $k$ copies $G_1,\ldots,G_k$ of $G$, with all possible edges between $u$ and $v$ for $u \in G_i$, $v \in G_j$, $i\not=j$.

Now use the additive constant algorithm for the graph $H$, which will find a coloring of, at most, $k\cdot\chi(G) + k$ colors. Since the colors in each copy of $G$ will be distinct, by the Pigeonhole principle, you have one of the copies with at most $\chi(G)+1$ distinct colors, which is better than a 2-approximation.


Graph problems with good characterization but not known to be in $P$ A decision problem has good characterization if it is in $NP \cap coNP$. Many natural graph problems have good characterizations. For instance, Kuratuwski's Theorem gives good characterization of planar graphs. Konig's Theorem gives good characterization of bipartite graphs. Tutte's Theorem gives good characterization of graphs that have perfect matching. Euler's Theorem gives good characterization of Eulerian graphs. All these recognition problems have polynomial-time algorithms.

Is there a natural graph problem that has good characterization but not known to be in $P$? A pointer to a survey of such problems would be appreciated.

In one of my blog posts, I mentioned four problems (Factoring, Parity Games, Stochastic Games, A Lattice Problem) that are known to be in $NP \cap coNP$ but not known to be in $P$.

Parity Games and Stochastic Games can be considered as "graph problems".

Also, The Two Bicliques Problem is in $NP \cap coNP$. This is a natural graph problem that is not known to be in $P$.


Viapath as a maximum flow problem Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \ $  different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a maximum flow problem. Does anyone
have a pointer for this ? Also any references to problems that can be reformulated, in not completely obvious ways, to maximum flow problems would be valued.

The reduction is the following.

Consider a graph as directed (that means, each edge $(u,v)$ is actually a pair of arcs pointing in the opposite directions). Split each vertex $v \in V$ to 2 different vertices $v_{in}$ and $v_{out}$ and fix the adjacent edges such that all in-arcs ends in $v_{in}$ and all out-arcs starts from $v_{out}$. Also add an arc $(v_{in}, v_{out})$ of unit capacity for each such pair. This guarantees that the flow will not pass through any original vertex more than once (which is necessary for path simplicity).

Then add a sink $t$ and arcs $(a_{out},t)$ and $(b_{out}, t)$ of unit capacity. Find a maximum flow from $x_{out}$ to $t$. If a simple path $a-x-b$ exists in the original graph, the parts $x-a$ and $x-b$ will not share a vertex (except from $x$) and the maximum flow will have size 2 so you will be able to reconstruct the answer from the flow. The opposite is true, too.

Upd.: The aforesaid was written under assumption that "simple path" means "a path with no repeated vertices". In other case there is no need for vertices splitting.


Is there any sparse language known to be in NPI under the $P \neq NP$ assumption ? I wonder to know wether there are sparse language (even constructed by delayed diagolanization) in NPI under the assumption that $P \neq NP$.

I don't know whether you are asking an open problem, or whether it has already been resolved. Yet the following paper can shed some light on this problem:

Kurtz, S. A. 1985. Sparse sets in NP-P: relativizations. SIAM J. Comput. 14, 1 (Feb. 1985), 113-119. DOI= http://dx.doi.org/10.1137/0214008

Basically, it states that, even assuming P≠NP, there is an oracle relative to which no sparse sets in NP-P exists.

On the other hand, the following paper:

T. Baker, J. Gill, and R. Solovay, "Relativizations of the P=?NP Question", SIAM J. Computing (1975), 431-442. DOI= http://dx.doi.org/10.1137/0204037

demonstrates an oracle relative to which sparse sets in NP-P exists.

Since $NPI \subset NP-P$, this proves that, either way, the proof does not relativize.

EDIT: In addition, there exist sparse sets in NP-P if and only if $E \neq NE$:

Hartmanis, J., Sewelson, V., and Immerman, N. 1983. Sparse sets in NP-P: Exptime versus nexptime. In Proceedings of the Fifteenth Annual ACM Symposium on theory of Computing STOC '83. ACM, New York, NY, 382-391. DOI= http://doi.acm.org/10.1145/800061.808769

(Journal version available here: http://dx.doi.org/10.1016/S0019-9958(85)80004-8)


Algorithmic Vector Problem I have an algebraic problem related to vectors in the field GF(2).
Let $v_1, v_2, \ldots, v_m$ be  (0,1)-vectors of dimension $n$, and $m=n^{O(1)}$. Find a polynomial time algorithm that finds a (0,1)-vector $u$ of the same dimension such that $u$ is not the sum of any $(\log n)^{O(1)}$ vectors among $v_1,v_2, \ldots, v_m$. The addition of vectors is over the field GF(2), which has two elements 0 and 1 ($0+1=0+1=1$, and $0+0=1+1=0$).

It is easy to see the existence of such a vector u by a simple counting argument.  Can we find $u$ in a polynomial time?  It is trivial to find $u$ in exponential time.   I will send a $200 check award for the first correct solution.

There seems to be a typo; I assume you mean to find $u \in \{0,1\}^n$ which is not the sum of $(\log
    n)^{O(1)}$ vectors among $v_1,\dots, v_m$ (not $n$).

It's not clear to me if any constant in $(\log n)^{O(1)}$ works for you.  If you can settle for sums of less than $\log m$ vectors maybe there's something to be done. But If you want this quantity to be $(\log m)^{1+\delta}$, then I think it is quite hard (I have been working on this problem for a long time).

Still you may be interested to know that this is an instance of the Remote Point Problem of Alon, Panigrahy and Yekhanin ("Deterministic Approximation Algorithms for the Nearest Codeword Problem ") for certain parameters.  Let $m > n$ and $v_1,\dots,v_m$ be the columns of the parity check matrix of a linear code in $\{0,1\}^m$ of dimension $d = m - n$ (if this matrix didn't have full rank, the problem would be trivial). Then your problem is equivalent to finding $u \in \{0,1\}^n$ that is $(\log n)^{O(1)}$-far from the code.  This setting of parameters, where the dimension is very close to m, is not studied in the paper.  However, they can only achive remoteness $\log m$ up to dimension $d = cm$ for some constant $c$.  In fact, I don't think we know of any polynomial-sized certificate that allows us to prove that some vector is more than $\omega(\log m)$-far from a space of dimension $\Omega(m)$, let alone find it.

Another connection is with learning parities in the mistake-bound model. If one can efficiently learn $(\log n)^{O(1)}$-parities (defined on ${0,1}^m$) with mistake bound strictly less than $n$, then one can set arbitrary values to the first $n - 1$ bits of $u$ and ``force a mistake'' on the last bit by setting it to the opposite value to that predicted by the learner. This seems much stronger though.

The problem is also related to separating EXP from certain reductions to sparse sets.


What is the complexity of computing optimal prefix free codes, when the frequencies are similar? It is well known that there is a worst case optimal algorithm to compute the Huffman code in time $\theta(n\lg n)$. This is improved in two orthogonal ways:

Optimal prefix free codes can be computed faster if the set of distinct frequencies is small (e.g. of size $\sigma$): sort the frequencies using [Munro and Spira, 1976] so that to take advantage of the small value of $\sigma$, and compute the Huffman tree in linear time from the sorted frequencies. This yields a solution in $O(n\lg\sigma)$
There is an $O(n 16^k)$ algorithm to compute equivalent codes where $k$ is the number of distinct codewords lengths [Belal and Elmasry].

Is there a way to combine those techniques, in order to improve on the current best complexity of $O(n\min\{16^k,\lg\sigma\})$?

THE $O(nk)$ RESULT FROM STACS 2006 SEEM TO BE WRONG, Elmasry published on ARXIV in 2010 (http://arxiv.org/abs/cs/0509015) a version announcing
     - $O(16^kn)$ operations on unsorted input and
     - $O(9^k \log^{2k-1} n)$ operations on sorted input

I see an analogy with the complexity of computing the planar convex hull, where algorithms in $O(n\lg n)$ (sorting based, as the $O(n\lg n)$ algorithm for Huffman's code) and in $O(nh)$ (gift wrapping) were superseded by Kirkpatrick and Seidel's algorithm in $O(n\lg h)$ (later proved to be instance optimal with complexity of the form $O(nH(n_1,\ldots,n_k)$). In the case of Prefix Free codes, $O(n\lg n)$ versus $O(nk)$ suggests the possibility of an algorithm with complexity $O(n\lg k)$, or even $O(nH(n_1,\ldots,n_k)$ where $n_i$ is the number of codewords of length $i$, using the analogy of an edge of the convex hull covering $n_i$ points to a code length covering $n_i$ symbols.
A simple example shows that sorting the (rounded) logarithmic values of the frequencies (in linear time in the $\theta(\lg n)$ word RAM model) does not give an optimal prefix free code in linear time:

For $n=3$, $f_1=1/2-\varepsilon$ and $f_2=f_3=1/4+\varepsilon$
$\lceil\lg f_i\rceil=2$ so log sorting does not change order
yet two codes out of three cost $n/4$ bits more than optimal.

Another interesting question would be to reduce the complexity when $k$ is large, i.e. all codes have distinct lengths:

for instance when $k=n$ the frequencies are all of distinct log value. In this case one can sort the frequencies in linear time in the $\theta(\lg n)$ word RAM, and compute the Huffman code in linear time (because sorting their log values is enough to sort the values), resulting in overall linear time, much better than the $n^2$ from the algorithm from Belal and Elmasry.

It took a few years (five!), but here is a partial answer to the question:

http://arxiv.org/abs/1602.00023

Optimal Prefix Free Codes With Partial Sorting
Jérémy Barbay
(Submitted on 29 Jan 2016)

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in time within O(n(1+lgα))⊆O(nlgn), where the alternation α∈[1..n−1] measures the amount of sorting required by the computation. This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of size n and alternation α. Such results refine the state of the art complexity of Θ(nlgn) in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort a multiset depending on the queries on it (known since 1988).


What are the historical roots of Milner's bigraphs? Robin Milner defined bigraphs as a type of graphical structure with graph-like structure but where the nodes can be nested.  They generalise process calculi like CCS and the $\pi$-calculus, but Milner seems to have intended for them to be used much more generally: the seminar notes from shortly before his death detail recent developments.

Looking back instead of forward, the prologue of Milner's 2009 textbook The Space and Motion of Communicating Agents, does not provide much of a historical background.  Milner explicitly acknowledged its roots in Mobile Ambients and the Pi calculus.  Yet the model is so general that there are bound to be strong links to older models.

  Are there historical predecessors of bigraphs?

Focusing on the syntactic elements rather than the way they are used to capture evolving systems, an obvious precedent is A. B. Kempe, A Memoir on the Theory of Mathematical Form, Philosophical Transactions of the Royal Society of London 177, 1–70, 1886.  Kempe's paper may have introduced vertex and edge coloured graphs (I am ignorant of earlier usage but would welcome pointers).  Kempe also appears to have had some of the same kinds of general applications in mind that Milner envisaged.  Are there other predecessors that should be mentioned?

(Edit: now marking this a community wiki, in the hope of attracting further answers.)

Much of the category theoretic groundwork for bigraphs was done in terms of Reactive Systems:

Leifer, J. J. and Milner, R. (2000). Deriving bisimulation congruences for reactive systems. In Palamidessi, C., editor, Proceedings of the 11th International Conference on Concurrency Theory (CONCUR'00), volume 1877 of Lecture Notes in Computer Science, pages 243-258. Springer-Verlag. (link)

This was the result that showed that bisimulation is a congruence in the presence of sufficient RPOs.

As you correctly noted, there are definitely links with various ambient calculi - particularly in capturing the notion of "place".

The Chemical Abstract Machine (Cham) has also been cited as significant - probably in terms of the semantics of reactions as well as a few other concepts (such as membranes) that look familiar when viewed from the bigraphs world.  This to me probably shows the clearest sign of being an ideological ancestor of bigraphical reactive systems in many ways.

Finally, I think it's worth just looking at the thread of Milner's work from CCS, to pi-calculus, to reactive systems, to bigraphs.  You see a definite trend within that strand of work, in the introduction of additional abstractions or the ability to explicitly encode certain information that was perhaps otherwise only implicitly included in previous modeling formalisms.

This is by no means complete, but I think it's definitely fair to see the development of bigraphs as a natural progression from many, many different ideas.


About generalized planar graphs and generalized outerplanar graphs Any planar, respectively, outerplanar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$,
respectively, $|E'|\le 2|V'|-3$, for every subgraph $G'=(V',E')$ of $G$.
Also, (outer-)planar graphs can be recognized in polynomial time.

What is known about graphs $G=(V,E)$ such that $|E'|\le 3|V'|-6$
(resp. $|E'|\le 2|V'|-3$) for every subgraph $G'=(V',E')$ of $G$? Is it possible to
recognize them in polynomial time?

Edit (after Eppstein's nice answer): Any planar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$ for every subgraph $G'=(V',E')$ of $G$ with at least three vertices $|V'|\ge 3$. So, "generalized planar graphs" would be those satisfying this property, and recognizing them in polynomial time seems to be an (interesting) open question.

In the notation of Lee and Streinu (citation below) the second class you list are the (2,3)-sparse graphs. They give an algorithm to test whether a graph is (k,l)-sparse in polynomial time. However, the situation with planar graphs and $|E'|\le 3|V'|-6$ is a little more complicated, because that inequality is not true for all sets of vertices (if it were true, no two vertices could be connected by an edge, because $3\cdot 2-6=0$). So the class of (3,6)-sparse graphs (in their notation) consists only of empty graphs.  Probably their algorithms can be extended to graphs for which the inequality holds for all sets of more than two vertices.

Lee, Audrey; Streinu, Ileana (2008), "Pebble game algorithms and sparse graphs", Discrete Mathematics 308 (8): 1425–1437, doi:10.1016/j.disc.2007.07.104, arxiv:math/0702129.