Genetic Algorithm to Draw a Graph? Position assignment problem I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large).

I have a directed graph (a flow-chart) that I would like to visualize on 2-D plane in a way that it is very clear, understandable and easy to read by human-eye. Therefore; I will be assigning (x,y) positions to each vertex. I'm thinking of solving this problem using simulated annealing, genetic algorithms, or any such method you can suggest

Input: A graph G = (V,E)
Output: A set of assignments, {(xi, yi) for each vi in V}. In other words, each vertex will be assigned a position (x, y) where the coordinates are all integers and >= 0.

These are the criteria that I will use to judge a solution (I welcome any suggestions):

Number of intersecting edges should be minimal,
All edges flow in one direction (i.e from left to right),
High angular resolution (the smallest angle formed by two edges
incident on the same vertex),
Small area - least important.

Furthermore; I have an initial configuration (assignment of positions to vertices), made by hand. It is very messy and that's why I'm trying to automate the process.

My questions are,

How wise would it be to go with local search techniques? How likely
would it produce a desired outcome?
And what should I start with? Simulated annealing, genetic algorithms
or something else?
Should I seed randomly at the beginning or use the initial
configuration to start with?
Or, if you already know of a similar implementation/pseudo-code/thing, please point me to it.

Any help will be greatly appreciated. Thanks.

I don't think it is wise to use local search techniques. There are many (fast) methods which work pretty good for many classes of graphs. Of course you can also test local search methods.

A few comments:

  Number of intersecting edges should be minimal

Is your graph planar? If yes, there are many good methods for planar graphs (e.g. dominance drawings).

Is it a general digraph? In this case a hierarchical approach may be suitable (more information later).

  All edges flow in one direction (i.e from left to right)

Does it contain cycles? If yes, this is not possible.

A great source for graph drawing algorithms is Graph Drawing: Algorithms for the Visualization of Graphs.

In my opinion a good first approach to this problem is the hierarchical approach. Check the paper by Sugiyama et. al Methods for Visual Understanding of Hierarchical System Structures (chapter 9 in 1 describes such methods).

If you go with the local optimization methods, I would definitely use the initial configuration to start with (since it should be close to a good local optimum).


Complexity of reachability in linear dynamical systems over finite fields Let $A$ be a matrix over the finite field $\mathbb{F}_2 = \{0,1\}$ and $x$, $y$ be vectors of the space $\mathbb{F}_2^n$. I am interested in the computational complexity of deciding whether there exists $t \in \mathbb{N}$ such that $A^t x = y$, i.e., in the reachability problem for linear dynamical systems over finite fields.

The problem is clearly in $\mathbf{NP}$ (guess $0 \le t < 2^n$ and compute $A^t$ in polynomial time by repeated squaring). Me and my colleagues were also able to prove the $\mathbf{NP}$-completeness of the related problem of establishing whether there exists $t \in \mathbb{N}$ such that $A^t x \ge y$, where $\ge$ is componentwise inequality.

This problem seems quite natural, but I have not been able to find references to its computational complexity in the literature, probably because I am not aware of the exact terminology. Do you know if the problem with the equality is $\mathbf{NP}$-complete or if it is actually in $\mathbf{P}$?

For clarity, I'm going to generalize your question to be over characteristic $p
> 0$ (with base field $\mathbb{F}_q$) instead of the specific case of $p=q=2$.
I'll take $p$ and $q$ as a fixed constants;
I'll leave it to the reader to figure out what the exact dependence on these parameters is,
as there are some tradeoffs that can be made.
The end result here is that your problem is roughly equivalent to the discrete
log problem for finite fields of characteristic $p$.

To be more specific,
let the ordinary discrete log problem over extensions of $\mathbb{F}_q$ be,
given an extension field $\mathbb{F}$ of $\mathbb{F}_q$, and $a,b \in \mathbb{F}$,
find any integer $t$ so that $a = b^t$,
or report that none exists.
Let the strong discrete log problem over extensions of $\mathbb{F}_q$ be,
given $\mathbb{F},a,b$ as before, find integers $z,m$ so that
$a = b^t$ for an integer $t$ iff $t = z \pmod{m}$,
or report that no $t$ exists.
Then the following reductions exist:

There is a deterministic mapping reduction from discrete log over extensions of $\mathbb{F}_q$ to your problem.
There is an efficient, deterministic algorithm which solves your problem
when given access to an oracle computing the strong discrete log problem
over extensions of $\mathbb{F}_q$.

Accordingly, I'd consider it unlikely that somebody will post a proof of
$\mathsf{NP}$-hardness or a proof that your problem is in $\mathsf{P}$ in the
near future.

Remark: The strong discrete log problem over extensions of $\mathbb{F}_q$
can be Turing-reduced to the following ostensibly weaker form
(though still seemingly stronger than the ordinary discrete log problem):
Given an extension field $\mathbb{F}$ of $\mathbb{F}_q$, and $a,b \in \mathbb{F}$,
find the least, non-negative integer $t$ so that $a = b^t$.
This follows from the fact that the order of $b$ is one plus the smallest
non-negative $t$ so that $b^{-1} = b^t$.

First reduction:
The claim is that the ordinary discrete log problem over extensions of $\mathbb{F}_{q}$ mapping-reduces to this problem.
This follows the fact that multiplication in $\mathbb{F}_{q^n}$ is a linear transformation
when we view $\mathbb{F}_{q^n}$ as an $n$-dimensional vector space over $\mathbb{F}_q$.
Hence a question of the form $a = b^t$ over $\mathbb{F}_{q^n}$
becomes $\vec{a} = B^t\vec{e}$ over $\mathbb{F}_q$, where $\vec{a},\vec{e}$ are $n$-dimensional vectors,
and $B$ is an $n\times n$ matrix, all over $\mathbb{F}_q$.
The vector $\vec{a}$ can be easily computed from $a$, $B$ from $b$, and
$\vec{e}$ is just the representation of $1 \in \mathbb{F}_{q^n}$, which can be
written down efficiently.
This appears to still be a hard case of the general discrete log problem,
even with $p=q=2$ (but growing $n$, of course).
In particular, people are still competing to see how far out they can compute it.

Second reduction:
The claim is that your problem reduces to the strong discrete log problem over extensions of $\mathbb{F}_q$.
This reduction has a few pieces to it, so forgive the length.
Let the input be the $n$-dimensional vectors $x,y$ and $n\times n$ matrix $A$, all over $\mathbb{F}_q$;
the goal is to find $t$ so that $y = A^tx$.

The basic idea is to write $A$ in Jordan canonical form (JCF),
from which we can reduce testing $y = A^tx$ to the strong discrete log problem
with some straightforward algebra.

One reason for using a canonical form under similarity of matrices
is that if $A = P^{-1}JP$, then $A^t = P^{-1}J^tP$.
Hence we can transform $y = A^tx$ to $(Py) = J^t(Px)$,
where now $J$ is in a much nicer format than the arbitrary $A$.
The JCF is a particularly simple form, which enables the rest of the algorithm.
So from now on, assume that $A$ is already in JCF,
but also allow that $x,y,$ and $A$ may have entries in an extension field of
$\mathbb{F}_q$.

Remark: There are some subtleties that arise from working with the JCF.
Specifically, I'll assume that we can do field operations within any extension
of $\mathbb{F}_q$ (no matter how large) in one time step,
and that we can compute the JCF efficiently.
a priori, this is unrealistic, because working with the JCF may require
working in an extension field (the splitting field of the characteristic polynomial)
of exponential degree.
However, with some care, and using the fact that we're working over a finite field,
we can circumvent these issues.
In particular,
we will associate with each Jordan block a field $\mathbb{F}'$ of degree at most $n$ over $\mathbb{F}_q$
so that all the entries in the Jordan block and the corresponding elements of $x$,$y$
all live within $\mathbb{F}'$.
The field $\mathbb{F}'$ may differ from block to block,
but using this ``mixed representation'' allows for an efficient description of the JCF,
which moreover can be found efficiently.
The algorithm described in the remainder of this section only needs to work
with one block at a time,
so as long as it does its field operations within the associated field $\mathbb{F}'$,
the algorithm will be efficient.
[end remark]

The use of JCF gives us equations of the following form,
with each equation corresponding to a Jordan block:
$$
\begin{bmatrix}
  y_1 \\
  y_2 \\
  y_3 \\
  \vdots \\
  y_{k-1} \\
  y_{k} \\
\end{bmatrix}
=
\begin{bmatrix}
\lambda & 1       &         &        &         &         \\
    & \lambda & 1       &        &         &         \\
    &         & \lambda & 1      &         &         \\
    &         &         & \ddots &         &         \\
    &         &         &        & \lambda & 1       \\
    &         &         &        &         & \lambda \\
\end{bmatrix}^t
\begin{bmatrix}
  x_1 \\
  x_2 \\
  x_3 \\
  \vdots \\
  x_{k-1} \\
  x_{k} \\
\end{bmatrix}$$

The algorithm will handle each block separately.
In the general case, for each block, we'll have a query for our strong discrete log oracle,
from which the oracle will tell us a modularity condition, $t = z \pmod{m}$.
We'll also get a set $S \subseteq \{0,1,\cdots,p-1\}$ so that
$\bigvee_{s\in S}\left[ t = s \pmod{p} \right]$
must hold.
After processing all the blocks,
we'll need to check that there is a choice of $t$ that satisfies the conjunctions of all these conditions.
This can be done by making sure there is a common element $s$ in all the sets $S$
so that the equations $t = s \pmod p$ and $t = z_j \pmod{m_j}$ are all simultaneously satisfied,
where $j$ ranges over the blocks.

There are also some special cases that arise throughout the procedure.
In these cases,
we'll get conditions of the form $t > \ell$ for some value of $\ell$,
or of the form $t = s$ for some specific integer $s$, from certain blocks,
or we might even find that no $t$ can exist.
These can be incorporated into the logic for the general case without issue.

We now describe the subprocedure for handling each Jordan block.
Fix such a block.

Begin by focusing on just the last coordinate in the block.
The condition $y = A^tx$ requires that $y_k = \lambda^t x_k$.
In other words, it's an instance of the discrete log problem in some field extension of $\mathbb{F}_q$.
We then use an oracle to solve it,
which either results in no solution,
or else gives a modularity condition on $t$.
If "no solution" is returned, we return indicating such.
Otherwise,
we get a condition $t = z \pmod{m}$,
which is equivalent to $y_k = \lambda^t x_k$.

To handle the other coordinates,
we start with the following formula
(see, eg, here):
$$
\begin{bmatrix}
\lambda & 1       &         &        &         &         \\
    & \lambda & 1       &        &         &         \\
    &         & \lambda & 1      &         &         \\
    &         &         & \ddots &         &         \\
    &         &         &        & \lambda & 1       \\
    &         &         &        &         & \lambda \\
\end{bmatrix}^t
=
\begin{bmatrix}
\lambda^t & \binom{t}{1}\lambda^{t-1} & \binom{t}{2}\lambda^{t-2} & \cdots & \cdots & \binom{t}{k-1}\lambda^{t-k+1} \\
 & \lambda^t & \binom{t}{1}\lambda^{t-1} & \cdots & \cdots & \binom{t}{k-2}\lambda^{t-k+2} \\
 &  & \ddots & \ddots & \vdots & \vdots\\
 &  & & \ddots & \ddots & \vdots\\
 &  & &  & \lambda^t & \binom{t}{1}\lambda^{t-1}\\
 &  &  &  &  & \lambda^t
\end{bmatrix}$$
First, let's take care of the case in which $x_k = 0$.
Since we already have the modularity condition which implies $y_k = \lambda^t x_k$,
we can assume that $y_k = 0$ also.
But then we can just reduce to focusing on the first $k-1$ entries of $x$ and $y$,
and the top left $(k-1)\times (k-1)$ submatrix of the Jordan block.
So from now on, assume that $x_k \ne 0$.

Second, we'll handle the case in which $\lambda = 0$.
In this case,
the powers of the Jordan block have a special form,
and force either $t = z$ for some $z \le k$,
or else $t > k$, with no other conditions.
I won't belabor the cases, but suffice it to say that each can be checked for efficiently.
(Alternatively, we could reduce to the case where $A$ is invertible; see my comment on the question.)

Finally, we arrive at the general case.
Since we already have the modularity condition which implies that $y_k = \lambda^t x_k$,
we can assume that condition holds, and use $y_k x_k^{-1}$ as a stand-in for $\lambda^t$.
More generally, we can use $y_kx_k^{-1}\lambda^{-z}$ to represent $\lambda^{t-z}$.
Thus we need to check if the following system holds for some choice of $t$:
$$
\begin{bmatrix}
  y_1 \\
  y_2 \\
  y_3 \\
  \vdots \\
  y_{k-1} \\
  y_{k} \\
\end{bmatrix}
=
\begin{bmatrix}
y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1} & \binom{t}{2}y_kx_k^{-1}\lambda^{-2} & \cdots & \cdots & \binom{t}{k-1}y_kx_k^{-1}\lambda^{-(k-1)} \\
 & y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1} & \cdots & \cdots & \binom{t}{k-2}y_kx_k^{-1}\lambda^{-(k-2)} \\
 &  & \ddots & \ddots & \vdots & \vdots\\
 &  & & \ddots & \ddots & \vdots\\
 &  & &  & y_kx_k^{-1} & \binom{t}{1}y_kx_k^{-1}\lambda^{-1}\\
 &  &  &  &  & y_kx_k^{-1}
\end{bmatrix}
\begin{bmatrix}
  x_1 \\
  x_2 \\
  x_3 \\
  \vdots \\
  x_{k-1} \\
  x_{k} \\
\end{bmatrix}
$$
Observe that whether the equation holds depends only on $t \pmod{p}$;
this is because the dependence on $t$ is only polynomial,
$t$ must be an integer,
and the above equations are over a field of characteristic $p$.
Hence we can just try each value of $t \in \{0,1,\ldots,p-1\}$ separately.
The set $S$ we will return is just the choices of $t$ for which the system is
satisfied.

So now, except for some special cases, the per-block subprocedure has found a modularity condition $t = a \pmod{m}$,
and a set $S$ so that one of $t = s \pmod{p}$ must hold for some $s \in S$.
These conditions are equivalent to $y = A^tx$ within this specific Jordan block.
So we return these from the subprocedure.
The special cases either conclude that no $t$ can exist (in which case the subprocedure immediately returns an indication of that),
or else we have a modularity condition $t = a \pmod{m}$ and some special condition like $t = s$ for an integer $s$,
or $t > \ell$ for some integer $\ell$.
In any case, the conditions involved are all equivalent to $y = A^tx$ within this Jordan block.
So, as mentioned above, the subprocedure just returns these conditions.

This concludes the specification of the per-block subprocedure,
and of the algorithm as a whole.
It's correctness and efficiency follow from the preceding discussion.

Subtleties with using JCF in second reduction:
As mentioned in the second reduction, there are some subtleties that arise from
working with the JCF.
There are a few observations for mitigating these problems:

Extensions of finite fields are normal.
This means that if $P$ is a an irreducible polynomial over $\mathbb{F}_q$,
then any extension of $\mathbb{F}_q$ containing a root of $P$
contains all the roots of $P$.
In other words, the splitting field of an irreducible polynomial $P$
of degree $d$ has degree only $d$ over $\mathbb{F}_q$.
There is a generalization of the Jordan canonical form,
called the primary rational canonical form (PRCF),
which does not require field extensions to be written down.
In particular, if $A$ is a matrix with entries in $\mathbb{F}_q$,
then we can write $A = P^{-1}QP$ for some matrices $P,Q$ with entries in $\mathbb{F}_q$,
where moreover $Q$ is in PRCF.
Additionally, if we pretend that the entries $A$ live in a field $\mathbb{F}'$
extending $\mathbb{F}_q$ which contains all the eigenvalues of $A$,
then $Q$ will in fact be in JCF.
Thus we can view computing the JCF of $A$ as a special case of computing the PRCF.
Using the form of the PRCF,
we can factor computing the JCF of $A$ as

computing the PRCF of $A$ over $\mathbb{F}_q$
computing the PRCF of each block $C$ (borrowing the notation from the Wikipedia article) in the PRCF of $A$,
over an extension field $\mathbb{F}'$,
where $\mathbb{F}'$ is chosen to contain all the eigenvalues of $C$

The key advantage with this factorization is that the characteristic
polynomials of the blocks $C$ will all be irreducible,
and hence, by our first observation,
we can choose $\mathbb{F}'$ to have degree the size of $C$ (which is at most $n$) over $\mathbb{F}_q$.
The downside is that now we have to use different extension fields to
represent each block of the JCF, so the representation is atypical and complicated.

Thus, given the ability to compute the PRCF efficiently,
we can compute a suitable encoding of the JCF efficiently,
and this encoding is so that working with any particular block of the JCF can be done within
an extension field of degree at most $n$ over $\mathbb{F}_n$.

As for computing the PRCF efficiently,
the paper
"A Rational Canonical Form Algorithm" (K. R. Matthews, Math. Bohemica 117 (1992) 315-324)
gives an efficient algorithm to compute the PRCF when the factorization of the characteristic
polynomial of $A$ is known.
For fixed characteristic (such as we have),
factoring univariate polynomials over finite fields can be done in deterministic polynomial time
(see eg "On a New Factorization Algorithm for Polynomials over Finite Fields" (H. Niederreitter and R. Gottfert, Math. of Computation 64 (1995) 347-353).),
so the PRCF can be computed efficiently.


Soft Truth Values in the PSL model This might sound like a trivial question. But since am starting out with my research in an area that is entirely new to me, I would really appreciate it if someone could kindly elucidate what Soft truth values mean.

I came across this in the context of PSL(Probabilistic Soft Logic).
This paper stated that;

  PSL uses first order logic rules as a template language for graphical models over random variables with soft truth values from the interval [0,1].

Any clarifications in this regard will be much appreciated.

The question is quite broad, so my answer will also probably be broad.

Traditional logic is Boolean, in the sense that every sentence evaluates to either true or false.

However, there are many contexts in which satisfaction is not Boolean. Examples of this include probabilistic reasoning (captured by PSL that you mentioned), fuzzy logic, quantitative reasoning, knowledge, belief, and trust representations, and many more.

In many such contexts, "truth" is defined as e.g., a value in $[0,1]$, and this is sometimes referred to as "soft truth values". The interpretation of such values can differ according to the usage. For example, a sentence with truth value $2/3$ can mean "the sentence is true with probability $2/3$" (i.e. it is true in $2/3$ of the models), or it could mean "the belief level I have in this sentence is $2/3$" (for some well defined concept of belief).

Or it could mean something like $2/3$ of the agents in this multiple agent system think the sentence is true (which is used to represent e.g. voting scenarios).

For some self-propaganda, I have some work on the topic of quantitative reasoning in temporal logic which you can use as a starting reference.


Why does ML's Value Restriction stop you from capturing parametric values? Here the MLton manual explains ML's value restriction. Specifically, it disallows functions to take on multiple parametric instantiations if they have a closure over local variables.

  Edit: note from the answer that the MLton manual is wrong about the
  value restriction. See instead Real World Ocaml.

Why is this a problem in ML when C# can easily form closures over parametric variables?

For example, this code is invalid, because ML will not allow this function to parameterize over int and string in the same program, because it has a let binding.

val f = let in fn x => x end
val _ = (f "foo"; f 13)

However, I can easily make a C# function which captures a parameterized variable, and parametrically instantiate it over both int and string. I've made the example more convincing, because a literal translation of the above ML is a trivial C# program.

class Program {

    static Func<A> foo<A>(Func<A,A,A> fn, A initial, A accumulate) {
        A cur = initial;
        return () => {  cur = fn(cur,accumulate); return cur;};
    }

    static void Main(string[] args) {
        var my_bar_a = foo( (x,y) => { return x+y;}, 0, 1);
        var my_bar_b = foo( (x,y) => { return x+y; }, ":", "-");

        Console.WriteLine("a: " + my_bar_a().ToString());
        Console.WriteLine("a: " + my_bar_a().ToString());
        Console.WriteLine("b: " + my_bar_b().ToString());
        Console.WriteLine("b: " + my_bar_b().ToString());
        Console.WriteLine("a: " + my_bar_a().ToString());
        Console.WriteLine("b: " + my_bar_b().ToString());
    }
}

output as expected:

a: 1
a: 2
b: :-
b: :--
a: 3
b: :---

Why does ML prevent us from doing this?

Your C# example doesn't trigger the value restriction at all. Here it is in OCaml:

# let foo f init acc =
    let cur = ref init in
    (fun () -> cur := f !cur acc ; !cur) ;;
val foo : ('a -> 'b -> 'a) -> 'a -> 'b -> unit -> 'a = <fun>

# let my_bar_a = foo (+) 0 1 ;;
val my_bar_a : unit -> int = <fun>
# let my_bar_b = foo (^) ":" "-" ;;
val my_bar_b : unit -> string = <fun>

# my_bar_a () ;;
- : int = 1
# my_bar_a () ;;
- : int = 2
# my_bar_b () ;;
- : string = ":-"
# my_bar_b () ;;
- : string = ":--"
# my_bar_a () ;;
- : int = 3
# my_bar_b () ;;
- : string = ":---"

Note that your initial example shouldn't trigger it either:

let f = fun x -> x in f "plop", f 2 ;;
- : string * int = ("plop", 2)

f here is a non mutable value, it can be safely generalized.

The ML value restriction doesn't stop you from capturing parametric values as long as, given a unique reference, it will only be instantiated with a unique type. This is the case in your C# example: the reference cell is created for each new function.

I'm not extremely fond of the MLTON manual. You can read Real World OCaml for a decent introduction to the value restriction here. OCaml also has extensions to the value restriction when type parameters are in covariant position, which you can read about in Jacque Garrigue's paper.


Assessing complexity of a language using subset relations What makes a language hard in a computational sense is neither simply that it contains very few words(e.g. is finite) or that it contains a lot of words(e.g. is infinte) but rather an intricate selection of a subset of $\Sigma^*$.

I would try to formalize this intuition as the following statement:

Let $A,B$ be two languages which are complete w.r.t to some class $\mathcal{C}$. Then for every language $C$ it holds that
$$ A \subseteq C \subseteq B \implies C \text{ is complete w.r.t $\mathcal{C}$} $$

What can we say about the truth value of this statement or interesting special cases such as NP. Maybe it implies only lower bounds(hardness)?
I would be rather suprised if even the lower bounds of $A$ and $B$ don't apply to $C$.

One natural example to explore might be HAMCIRC and HAMPATH. If the hypotheses holds then we could state that any set of graphs $G$ for which every element has a hampath and every graph with a hamcirc is contained in it, it follows that $G$ is NP-complete.

The statement is unlikely to be true since we can deduce NP-hardness for Graph Isomorphism from it (which would imply a collapse of PH to its second level) as follows:

Let SGI be the Subgraph Isomorphism problem which is known to be NP-complete. Then GI is a subset of SGI. Now, take HAMCIRC and define a slightly different version:

ISO-HAMCIRC = $\{ (G_1, G_2) | G_1 \text{ is isomorph to } G_2 \text{ and } G_1 \in \text{HAMCIRC} \}$

It is trivial to see that ISO-HAMCIRC is NP-complete as well.

It follows that ISO-HAMCIRC $\subseteq$ GI $\subseteq$ SGI and therefore GI would be NP-hard assuming the hypothesis holds.


Simple example of halting-unprovable Turing machine Is there a simple example of a Turing machine $M$, such that whether $M$ halts or not on the empty input cannot be proved within the current mathematical system?

Specifically, I'm curious whether there exists an example simple enough that the state transition of the Turing machine can be drawn as a reasonably-sized diagram.

Take the "current mathematical system" $S$ and an undecidable sentence $P$ for $S$. Consider the Turing machine $T$ which enumerates all theorems of $S$ and halts if it ever enumerates either $P$ or $\lnot P$. System $S$ cannot decide whether $T$ halts.

Note that such a $T$ does not halt.


Minimising the root-set of a spanning hyperforest of a hypergraph I am interested in the complexity of a problem involving spanning hyperforests (a union of hypertrees, which covers all of the vertices) of a $k$-hypergraph. I describe the relevant definitions for hypergraphs below, but the following is the problem on

  SPANNING HYPERFOREST ROOT SET. For a directed hypergraph $D$ and an integer $k \geqslant 1$, determine whether there exists a spanning hyperforest for $D$ which has a root-set of size at most $k$.

Remarks.

It is not difficult to show that SPANNING HYPERFOREST ROOT SET is in NP: in particular, if a root-set of the suitable size is provided, then a spanning hyperforest with that root-set can be found in polynomial time.
It is also trivial to find a value of $k$ for which $(D,k)$ is a YES instance: for instance $k = \lvert V(D) \rvert$ (in which case the empty hypergraph is a spanning hyperforest with root set $k$).
Considered as an optimisation problem, it is usually easy to find values $k < \lvert V(D) \rvert$ for which $(D,k)$ remain YES instances, though it is not clear how easily one can find the optimum.

Question.

Is SPANNING HYPERFOREST ROOT SET also NP-hard? Is this true in the special case where the input hypergraph is "symmetric", in the sense that for any edge $e = (t(e), h(e))$ and for any $v \in s(e) := t(e) \cup h(e)$, there is also an edge $e' = (s(e) {\,\smallsetminus\,} \{v\}, v)$?

Relevant definitions.

In the following, I am broadly following the definitions of "Flows on hypergraphs" [free PDF link] by Cambini, Gallo, and Scutellà.

A hypergraph is a pair $G = (V,E)$, where $E \subseteq \mathcal P(V)$. If each $e\in E$ has the same cardinality $k$, we call $G$ a $k$-uniform hypergraph (or $k$-hypergraph).
A directed hypergraph is a pair $D = (V,E)$, where in our setting we let $E \subseteq \mathcal P(V) \times V$ be the set of hyper-edges. For each edge $e \in E$, we let $t(e) = \pi_1(e) \subseteq V$ be the "tail" of the edge, and $h(e) = \pi_2(e) \in V \smallsetminus t(e)$ be the "head" of the edge. Thus we consider hypergraphs where each edge has exactly one head (more general definitions are common).
We may associate a "symmetric" directed hypergraph $D_G = (V,E')$ of this sort to any hypergraph $G = (V,E)$, by replacing each undirected edge $e \in E$ with a collection of directed variants $E'_e = \{ (e{\,\smallsetminus\,} v, v) \,\vert\, v \in e \}$ and letting $E' = \bigcup_{e \in E} E'_e$.
A directed cycle in a directed hypergraph $D = (V,E)$ is just a vertex sequence $(v_0,v_1,\ldots,v_\ell)$ for which $v_{i+1} \ne v_i$ for $0 \leqslant i < \ell$, $v_0 = v_\ell$, and for which for each $0 \leqslant i < \ell$ there is an edge $e_\ell$ for which $v_i \in t(e_i)$ and $v_{i+1} = h(e_i)$.
A hyperforest is a directed hypergraph in which all vertices have in-degree either zero or one, and which has no cycles in the above sense. (N.B. I am diverging here from the terminology in my reference above, which does not explicitly consider whether the hypergraph is connected; but this cannot be taken for granted in my setting.) The set of nodes of in-degree zero we call the "root set" of the hyperforest.
A spanning hyperforest $T$ for a directed hypergraph $D = (V,E)$, is simply a subgraph $T \subseteq D$ of the hypergraph which contains all of the vertices $V$ and which is a hyperfohrest.

This answer addresses the NP-hardness of the SPANNING SYMMETRIC HYPERFOREST ROOT SET (SSHRS) problem (given an undirected hypergraph $G$ and a number $k$, is there a spanning hyperforest with root set of size at most $k$ in the symmetric directed hypergraph $D_G$).

We prove that this problem is hard by reduction from the MAXIMUM UNIQUELY RESTRICTED BIPARTITE MATCHING (MURBM) problem (see https://link.springer.com/article/10.1007/s00453-001-0004-z for hardness). A uniquely restricted matching in a graph $B$ is a matching $M$ such that the induced subgraph of $B$ over the vertices of $M$ has exactly one perfect matching ($M$ itself). The MURBM problem asks for a given bipartite graph $B$ and a given number $n$ whether there exist a uniquely restricted matching in the graph with at least $n$ edges.

Note that a matching is uniquely restricted if and only if there exists no cycle in the graph whose edges alternate between being in the matching and not being in the matching. (This is easy to show, so the proof will not be included here).

The reduction from MURBM to SSHRS is simple: we are given a MURBM instance consisting of bipartite graph $B$ and number $n$. Suppose $B$ has vertex parts $V_1$ and $V_2$. Define $N(v)$ to be the set of neighbors of $v$ in $B$. Then define a hypergraph $G = (V, E)$ with vertices $V = V_1$ and edges $E = \{N(v)~|~v\in V_2\}$. Next, define $k = |V_1| - n$. In other words, construct the hypergraph $G$ whose bipartite graph model is $B$. Output $G$ and $k$ as the SSHRS instance output of the reduction.

The logic behind the reduction is this:

Choosing a spanning hyperforest in $D_G$ is equivalent to choosing a set of edges in $D_G$ subject to certain constraints. But choosing a set of edges in $D_G$ (subject to certain constraints) is equivalent to choosing a set of edges in $G$ and choosing a vertex to be the head from each (subject to certain constraints). Since a hyperforest allows no cycles, the same edge of $G$ directed in different ways cannot be used (as two such "duplicate" edges form a cycle). Since in a hyperforest the vertices have max in-degree one, the same vertex cannot be chosen as the head of multiple different edges. In other words, the choice of edges in $G$ and heads of those edges that comprises a choice of spannning hyperforest is equivalent to the choice of a matching in the bipartite graph model of $G$ (subject to certain constraints). But by construction, the bipartite graph model of $G$ is exactly the bipartite graph $B$, so choosing a spanning hyperforest in $D_G$ is equivalent to choosing a matching in $B$ subject to certain constraints.

What are those constraints? Well a hyperforest cannot have any cycles, and must have vertex in-degrees of at most 1. The vertex in-degree constraint is already met by any matching, so the only constraint is to have no cycles. But a cycle in the hyperforest corresponds to a cycle in the bipartite graph model of $G$ such that every second edge is in the corresponding "matching". Thus, the cycle-free condition of the hyperforest is equivalent to the condition that there exists no cycle in the graph whose edges alternate between being in the matching and not being in the matching.

Thus, hyperforests in $G$ correspond to uniquely restricted matchings in $B$. All that's left is to show that the parameters also match: that having a hyperforest with root set size at least $k$ corresponds to having a matching of size at least $n$. Every vertex in a spanning hyperforest has in-degree either 0 or 1, so the number of in-degree-1 vertices is equal to the total in-degree in the spanning hyperforest. But the total in-degree is also equal to the number of edges since each edge has exactly one head. Thus, the number of in-degree-1 vertices in the spanning hyperforest is equal to the number of edges. We also know that the size of the matching equals the number of edges in the hyperforest. Thus the size of the matching equals the number of in-degree-1 vertices in the hyperforest. Furthermore, the number of roots is by definition the number of in-degree-0 vertices. Thus, the size of the root set plus the size of the matching is equal to the number of vertices $|V| = |V_1|$. Therefore, the hyperforest has root set size at most $k = |V_1| - n$ if and only if the matching has size at least $n$.


Why do computer scientists on the whole work under the assumption that P ≠ NP? Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove $P = NP$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing $P = NP$ as possibly true. However, I often see people working within the framework of it not being true and I was wondering why? It seems more conservative to assume that $P = NP$ in many fields. I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if $P = NP$ was proven to be true, so why is this not assumed? While it is unlikely to be proven either way any time soon, it just seems somewhat odd to rely so heavily on the a conjecture like that. It almost seems paramount to assuming that Goldbach's conjecture is invalid as there is no proof for it either.

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.
Other than this, this topic has been discussed at several other places, see https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP or https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/.

Update: Or the very recent Chapter 3 here: http://www.scottaaronson.com/papers/pnp.pdf


Giving a finite collection of infinite words "complex" enough with respect to automata measure We consider acceptance by Büchi automata. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ of infinite words, such that for every other infinite word $\eta$ there exists some $\xi_i$ such that for every Büchi automaton $\mathcal A$ with
$$
 |L(\mathcal A) \cap \{\xi_i, \eta\}| = 1
$$
(i.e. the automaton separates both words: accepts one, but not the other) then $\mathcal A$ must have at least $n$ states?

Observation. One neccessary condition on the collection of infinite words $\{\xi_1, \ldots, \xi_k\}$: for a given $n$ we must have at least $2^{n-2}$ of them ($k \ge 2^{n-2}$), i.e. one for each prefix of length $n-2$, for otherwise if some prefix $u \in X^{n-2}$ is not among the finite collection, then we can separate $u1^{\omega}$ easily by an automaton having fewer then $n$ states from every word in $\xi_1, \ldots, \xi_k$, simply read upon the first position $i \le n-2$ where it differs from a given $\xi_j$ and then reject or accept according to the sign there, which could be achieved by a Büchi automaton with $i+2$ states.

But besides this observation, I do not see if this is possible?

Motivation: If we define
$$
 d(\xi, \eta) = 1/2^n
$$
where $n := \min\{ |\mathcal A| \mid |L(\mathcal A) \cap \{\xi,\eta\}| = 1 \}$ for $\xi \ne \eta$, and $d(\xi,\xi) := 0$, then this gives a metric, and the above question asks if the resulting metric space is totally bounded.

It is possible. Consider all languages $L_1,\dots,L_m$ recognizable by automata with at most $n$ states.

Now to each $x=x_1\dots x_m\in\{0,1\}^m$ we associate a (possibly empty) language $$L_x=\bigcap_{1\leq i\leq m} L_i^{x_i},$$ where $L^0$ is the complement of $L$ and $L^1=L$.

Let $Y=\{x\in\{0,1\}^m~|~ L_x\neq\emptyset\}$.
For each $x\in Y$, we choose $\xi_x\in L_x$. This gives a finite family $\{\xi_x~|~x\in Y\}$, we show that this family satisfies the wanted property.

Take any $\eta\in X^{\mathbb N}$, and for each $i\leq m$ let $y_i$ be defined as $0$ if $\eta\notin L_i$ and $1$ if $\eta\in L_i$.
We have $y=y_1y_2\dots y_m\in Y$, since nonemptiness of $L_y$ is witnessed by $\eta$. We show that $\xi_{y}$ satisfies the condition. Indeed, for any $L$ recognized by an automaton with at most $n$ states, $L$ does not separate $\eta$ from $\xi_y$, by definition of $\xi_y$.

Notice that this family is optimal in size, since if some signature $x\in Y$ is not represented by some $\xi_x$, the property fails. Its size is at most doubly exponential in $n$.


what is the equivalence class of a given polytree representing a directed graphical model? Let $T$ be a binary tree, where the internal nodes are $Y_1,...,Y_n$ and the leafs are $X_1,...,X_m$. (The $Y$s and the $X$s will eventuall represent a random variable in a Bayesian network.)

We can turn this binary tree into a polytree by directing all the edges downward toward the leafs from the root. What we get is a graphical model or a Bayesian network.

My main question - what other polytrees over the $Y$s and the $X$s can we have such that the marginal distribution $p(X_1,...,X_m)$ is the same like the marginal distribution in the original polytree I just described?

I am guessing we may be able to redirect some edges such that they point to a different node, and still get the same independence assumptions (and hence the same marginal distribution), but I am not sure what would be the permitted inversions.

Thanks!

You can pick any other node as root and redirect nodes away from it to get Markov equivalent model. Markov equivalent means that two graphical models correspond to identical spaces of distributions.

Let "unshielded collider" be structure of the form A->B<-C

Theorem: Two directed acyclic graphs D1 and D2 are Markov equivalent if and only if D1 and D2 have the same vertex set, same adjacencies, and same unshielded colliders.

See Ch.4 of Meek's "Related Graphical Frameworks: Undirected, Directed Acyclic and Chain Graph Models"
http://repository.cmu.edu/cgi/viewcontent.cgi?article=1206&context=philosophy


Balls & Bins: A punishment and reward game Consider a game where one has a set of bins $(b_1, b_2, ...)$, and each bin has an associated initial count of balls $(c_1, c_2, ...)$.  The rules of the game are as follows:

(1) Once a bin has a threshold number of balls $Q$ (the threshold is uniform for all bins), the bin may be capped, and capping is irreversible.  However, one is not obligated to cap the bin once this condition is met.  Capping must be SEQUENTIAL.  One cannot simultaneously cap two bins to avoid e.g. a situation where capping one bin drops the number of balls in the other bin below the threshold $Q$ necessary for capping.

(2) Once a bin is capped, a bin-specific set of "punishments" or "rewards" can be specified for at most $k$ other bins.  For example, we might say that, in capping bin $3$, we need to subtract two balls from bin $1$ and add seven balls to bin $5$.  So to each bin we assign a two $k$-tuples: the first, e.g. {1,5}, with values from the previous example, specifies the bins to be "punished" or "rewarded", and the second, e.g. {-2, 7}, again from the provided examples, species how many balls to add or remove from each of the bins in the first tuple.

(3) Negative values for bin ball counts are permissible, and a bin may initiate (i.e. have some $c_i$ value) $\leq 0$.

(4) We add the constraint that punishments or rewards must be symmetric.  If capping some bin $b_i$ means subtracting one ball from bin $b_j$, it must also be the case that capping bin $b_j$ means subtracting one ball from bin $b_i$.

(5) We add the constraint that the total number of punishments or rewards a bin may receive is at most $k$.  By the symmetry condition from (4), this correspondingly implies that the total number of punishments or rewards a bin may deliver is at most $k$.

Consider now the decision problem: provided some set of bins $(b_1, b_2, ...)$, initial ball counts $(c_1, c_2, ...)$, and access to all of the dependencies elaborated on in rule (2), can all of the bins be capped?

This problem is trivially in $NP$, but for what smallest value of $k$ is it $NP$-complete?  Can the decision problem be $NP$-complete for $k=2$?  Is there an easy reduction from an $NP$-complete problem or a problem solvable in polynomial time?

Update // Added further constraints (4) + (5), where (5) is implied by (4).  That should be it.

Here's an argument that it's polynomial for $k=2$.

If $k=2$, each bin can only be connected to two other bins, and thus the graph falls into paths and cycles. We can thus just worry about a cycle. In fact, we can guess which bin is capped first. Since there are only a polynomial number of guesses, we can try all of them, and reduce the problem to the case where the graph is a path.

Now, whether a bin can be capped only depends on whether or not you've capped its neighbors. That is, for bin $1$, we have one of the following constraints:

bin $1$ can be capped only before you've capped bin $2$,
bin $1$ can be capped only after you've capped bin $2$,
bin $1$ can be capped any time,
bin $1$ can never be capped.

For case 1, you might as well cap bin $1$ as the first thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 2, you might as well cap bin $1$ as the last thing you do. Now, you have a path of length $n-1$, and you can use recursion.

For case 3, capping bin $1$ will either add or subtract balls from bin $2$. If it adds them, make it the first bin you cap. If it subtracts them, make it the last bin you cap. In either case, you've reduced the problem to a path of length $n-1$.

For case 4, you've solved the problem: it's impossible to win.

This gives an algorithm of time $O(n^2)$. For a cycle of length $n$, we need to test $n$ different paths, breaking the cycle in every possible place. And for a path of length $n'$, in constant time, we can convert the problem to the same problem on a path of length $n'-1$.


Stochastic Gradient Descent with integer arithmetics Most implementations of stochastic gradient descent (SGD) rely on floating points.
Is there implementations using infinite or finite precision integer arithmetics ?

see eg Neural network training with constrained integer weights
Plagianakos, V.P.;   Vrahatis, M.N.;

An Integer Recurrent Artificial Neural Network
for Classifying Feature Vectors
Roelof K Brouwer PEng, Ph

the general idea in various implementations is to represent/approximate real numbers $x \in[0..1]$ as integers in the form $x \cdot 10^m$ where $m$ is some integer exponent.


Natural Transformations and Parametricity In Theorems for Free!, Wadler says that the characterization of parametricity can be re-expressed in terms of lax natural transformations and this will be the subject of a further paper. Which paper is he referring to?

The categorical approach to paramtericty I know uses dinatural transformations as in Functorial Polymorphism by Bainbridge, Freyd, Scedrov and P.J. Scott. What is the connection between lax natural transformation and dinatural transformation formulations of parametricity?

Unfortunately, the remark of Wadler is too cryptic for me to tell what use he wanted to make of "lax natural transformations".  Here is a guess.  Relation-preservation squares can often be recast as lax commutative squares.  This is how they used to be written in old automata theory papers/books.  See paragraph 1.2 in my Notes on Semigroups.  To do this kind of thing, you have to mix up relations and morphisms and pretend that they are the same.  I am also not sure that it buys you anything new.  It is just uglier notation for saying the same thing as relation-preservation.

Please feel free to explore the connection, but I am not confident that you will find anything new by doing it.


Research and open challenges in Programming Language Theory In the spirit of some general discussions like this one, I'm opening this thread with the intention to gather opinions on what are the open challenges and hot topics in research on programming languages. I hope that the discussion might even bring to surface opinions regarding the future of research in programming languages.

I believe that this kind of discussion will help new student researchers, like myself, interested in PL, as well as those who are already somewhat involved.

I think the overall goal of PL theory is to lower the cost of
large-scale programming by way of improving programming languages and
the techincal ecosystem wherein languages are used.

Here are some high-level, somewhat vague descriptions of PL research
areas that have received sustained attention, and will probably
continue to do so for a while.

Most programming language research has been done in the context of
sequential computation, and by now we have arguably converged on a
core of features that are available in most modern programming
languages (e.g. higher-order functions, (partial) type-inference,
pattern matching, ADTs, parametric polymorphism) and are well
understood. There is as yet no such consensus about programming
language features for concurrent and parallel computation.
Related to the previous point, the research field of typing systems
has seen most of its activity being about sequential computation.
Can we generalise this work to find tractable and useful typing
disciplines constraining concurrent and parallel computation?
As a special case of the previous point, the Curry-Howard
correspondence relates structural proof theory and functional
programming, leading to sustained technology transfer between computer
science and (foundations of) mathematics, with e.g. homotopy type theory being
an impressive example. There are many tantalising hints that it can be
extended to (some forms of) concurrent and parallel computation.
Specification and verification of programs has matured a lot in
recent years, e.g.  with interactive proof assistants like Isabelle
and Coq, but the technology is still far away from being usable at
large scale in everyday programming. There is still much work to be
done to improve this state of affairs.
Programming languages and verification technology for novel forms of computation. I'm
thinking here in particular of quantum computation, and the biologically inspired
computational mechanisms, see e.g. here.
Unification. There are many approaches to programming languages,
types, verification, and one sometimes feels that there is a lot of
overlap between them, and that there is some more abstract approach
waiting to be discovered. In particular, biologically inspired
computational mechanisms are likely to continue to overwhelm us.

One problem of PL research is that there are no clear-cut open
problems like the P/NP question where we can immediately say if a
proposed solution works or not.


Minimum order of partite in a bipartite graph I want to create a bipartite graph where the first partite $U$ contains $L$ vertices with degree $k$ and the second partite $V$ contains $N$ other vertices with degree $a$. I need to find the minimum number of $N$ so that every pair of the $L$ vertices have a common neighbour.

A different formulation of my problem is the following:

Assume we have $L$ distinct numbers.
I want to calculate the minimum number of sets of size $a$ that are needed so that all unordered pairs of numbers are contained in at least one of the sets.
I understand that finding the sets is similar to the set cover problem: http://en.wikipedia.org/wiki/Set_cover_problem (right?), but is there an easier/faster way to calculate the minimum number without calculating the sets, given $L$ and $a$?

This is an upper bound on $N$ for the second formulation:

Assume that I pick $N$ uniformly random sets.

The probability of a pair of elements not to be covered by a specific set is
$$1-\left(\frac{a}{L}\right)^2$$

Therefore the chance that it is not covered by any set is:
$$\left(1-\left(\frac{a}{L}\right)^2\right)^N$$

Using the union bound, the chance that some pair will not be covered is at most:

$$P={L \choose 2}\left(1-\left(\frac{a}{L}\right)^2\right)^N$$

This means that if $P<1$, there exists some proper covering using $N$ sets. Notice that:

$$P={L \choose 2}\left(1-\left(\frac{a}{L}\right)^2\right)^N<L^2e^{-N(\frac{a}{L})^2}$$

Therefore it is enough to demand $L^2e^{-N(\frac{a}{L})^2}<1$, which gives us a bound on $N$:

\begin{align}
L^2e^{-N(\frac{a}{L})^2}<1\\
-N(\frac{a}{L})^2<-2\ln L\\
N>2\ln L\cdot(\frac{L}{a})^2
\end{align}

Which means that there exists a proper covering using $2\ln L\cdot(\frac{L}{a})^2$ sets of size $a$.

Now notice that every set covers $a\choose 2$ pair of elements, while $L\choose 2$ pairs exist, so a lower bound for $N$ would be:
$$\frac{L\choose 2}{a\choose 2}\approx (\frac{L}{a})^2$$

So the upper bound is tight up to factor $O(\log L)$. (If I had to bet, I'd say the lower bound is loose while the upper is asymptotically tight).

This means that if your goal is to compute the value of the optimal $N$ - answering $(\frac{L}{a})^2\sqrt{\log L}$ would give an approximation ratio of $O(\sqrt{\log L})$.


Encoding of binary trees as a regular language? There are many ways of representing binary trees as strings.  For example, I could encode a tree as either nil or a pair of trees, such as

(nil, ((nil, nil), nil))

This representation has a simple CFG:

S -> nil
S -> (S, S)

My question is whether there exists some representation of binary trees as a string such that the set of all binary tree encodings is a regular language.  I have a suspicion that this cannot be done due to some pumping-lemma-based argument, but I have no idea how to go about showing this.

Does such a representation exist?

As Peter Shor mentions in a comment, the number of full binary trees with $n+1$ leaves is given by the $n$-th Catalan number $C_n$. It is known that the Catalan numbers have generating function

$C(x) = \frac{1-\sqrt{1-4x}}{2x}$.

On the other hand, it is known (Chomsky, Schützenberger; 1963) that regular languages have rational generating functions.

Clearly, $C$ is not rational. This implies that there is no regular encoding of full binary trees where each tree has a unique representation.

(Note that the generating function of arbitrary binary trees is not rational, either.)


Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms? Suppose that, for each $\epsilon > 0$, there is an Turing machine $M_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a + o(1)})$? (Here, the $o(1)$ term is measured in terms of $n$, the input length.)

Does it make a difference if the algorithms $M_{\epsilon}$ are computable, or efficiently computable, in terms of $\epsilon$?

Motivation: in many proofs, it is easier to construct algorithms of time $O(n^{a + \epsilon})$ than the limiting algorithm $O(n^{a + o(1)})$. In particular, you need to bound the constant term in $O(n^{a + \epsilon})$ to pass to the limit $O(n^{a+o(1)})$. It would be nice if there is some general result you can invoke to pass to the limit directly.

The question is similar to the questions about constructive existence of the limit of a sequence of (constructive) objects. Usually if you can uniformly construct those objects (here $M\epsilon$) efficiently enough then you can show the existence of the limit constructively.

For example, assume that we have a TM $N(k,x)$ which runs $M_{|k|^{-1}}$ on $x$ and its running time is $O(n^{a+|k|^{-1}})+O(|k|)$ (here the bounds are also uniform, e.g. something like $O(2^k.n^{a+|k|^{-1}})$ would not work). Then we can combine this uniform simulator with the function $(k,x)\mapsto x$ to obtain the machine $N(x,x)$ that runs in time $O(n^{a+o(1)})$.

PS: $O(n^{a+o(1)})$ is a little bit ambiguous because of nesting of asymptotic notations, I am interpreting it as $n^{a+o(1)}$. Also we need $a$ to be not too small, e.g. at least $1$.


Calculus of constructions: Why forall when pi exists? I'm studying the calculus of constructions from ATAPL, Chapter 2. I'm trying to understand the Type Equivalence rule, which describes the meaning of the new type family Prf a. The rule states:
Γ ⊢ T :: *         Γ, x:T ⊢ t: Prop
---------------------------------------[QT-ALL]
Γ ⊢ Prf (all x:T.t) ≡ Πx:T. Prf t :: *

This rule seems to state that types of the form of Prf(all ...) is equivalent to Π types. Combining this with the information that:

Prf: Πx:Prop.* [Prof needs Prop as input]
The only constructor of Prop is of the form all ...

implies that the only well-typed occurrence of Prf we can have is of the form Prf (all ...), which is equivalent to the Pi-type encoding (as given by QT-ALL).
Thus, I see no benefit gained by adding the Prf/Prop mechanism. I believe we gain something to do with impredicativity, as we can use all x:T.t : Prop to quantify over Prop itself. I don't know enough theory to judge whether this is possible or impossible just using Pi types.
Clearly, I am missing something. Could I please have an explanation of what we gain by introducing Prf/Prop that we did not already have with Pi types?
I've added a picture of the full definition here:

It is false that the only well-typed occurrence of Prf has to be of the form Prf(all ...). For example, in the context with a variable p : Prop we can form the type Prf(p) which is not of the stated form. Another possibility is that we have a Prf(t) for some closed term t : Prop which is not of the form all ... but it normalizes to it.
The purpose of Prf is to decode, or coerce, the elements of Prop to types. That is, the elements of Prop are not actual types, so if we want to use them as if they were types, they first have to be coerced to types, which is what Prf does. The rule QT-All states that all decodes to Π.
To put it differently, Prop is a Tarski universe and Prf is the type family that decodes its elements as types.


What is the categorical semantics of subtyping? Starting from Curry-Howard-Lambek, there has been a nice trinity of type theories, logics, and categories. I'm curious what categorical semantics you get when you add (coercive) subtyping to a type theory -- it seems like this has not been explored very much, if at all.

In general, adding coercive subtyping to a type theory does not ruin its meta-theoretic properties such as strong normalization, so its categorical semantics should be something of actual interest, I think!

Semantically, a coercion $c : A \leq B$ is just a morphism $c : A \to B$, which gets added to the interpretation of terms at the appropriate points. The  basic problem this creates is the issue of coherence: are you guaranteed that a term will have a unique meaning, given that the same term can potentially have coercions hidden in many possible places in the program?

One of the first treatments of this issue was John Reynolds' 1980 paper, Using Category Theory to Design Implicit Conversions and Generic Operators, which shows how you can give a categorical semantics to a system of coercions and use it to ensure that it is coherent.

If you're interested in coercive subtyping for rich (e.g., dependent) type theories, then Zhaohui Luo is the go-to guy.


Deciding whether a graph contains a complete balanced bipartite graph Is it known whether the following problem is in P or is NP-complete?

Problem: given an input graph $G$ on $n$ vertices, decide whether $G$ contains a complete $n/2 \times n/2$ bipartite graph.

If the vertex pair $(u, v)$ is not in $E$ then they can't be on opposite sides of the partition, so they must be in the same half. Create a union-find data structure and merge every vertex pair which is not an edge. Then you just need to solve the partition (subset-sum) problem to group some disjoint sets into a set of size $\frac{|V|}{2}$. The union-find phase can be done in $O(V^2 \alpha(V))$ and the pseudo-polynomial algorithm for subset sum takes $O(V^2)$ so this is in P. (Thank you to those who corrected an earlier error).

In the other direction, an oracle for balanced bipartite subgraph would give a pseudo-polynomial algorithm for the partition problem.

FWIW the generalisation which takes a parameter $K$ and asks whether there's a subgraph of $G$ which is a complete $K \times K$ bipartite graph is NP-complete by reduction from CLIQUE. Hat tip to Mohammad Al-Turkistany who cited a reference which proves this even when $G$ is known a priori to be bipartite: David S. Johnson, The NP-completeness column: An ongoing guide. Journal of Algorithms, 8(3):438–448, 1987.


Does hyper-computational power of infinite time Turing machines also require infinite memory? Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?

I think we have a reference here to Joel Hamkin's model of infinite time computation, not just some made up idea of infinite time machines. In that model time is measured by ordinal numbers. The machine has access to an infinite tape. After $\omega$ steps, every cell of the tape has been potentially written to, and we can't throw away any cell because its content may be needed during further computation. So yes, you'd need infinite space, but that's not a problem when you've got infinite time already.


Matrix vector multiplication algorithm using minimal number of additions Consider the following problem:

  Given a matrix $M$
  we want to optimize the number of additions in
  the multiplication algorithm for computing $v \mapsto Mv$.

I find this problem interesting because of its ties with
the complexity of matrix multiplication
(this problem is a restricted version of matrix multiplication).

What is know about this problem?

Is there any interesting results
relating this problem to the complexity of matrix multiplication problem?

The answer to the problem seems to involve
finding circuits with only addition gates.
What if we allow subtraction gates?

I am looking for reductions between this problem and other problems.

Motivated by

Automated optimization of 0-1 matrix vector multiplication
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

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

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

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

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

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


minimum distance r-dominating set on tree Given a graph G = (V,E) with edge and vertex weights. The minimum distance r-dominating set problem for a graph G = (V,E) requires to find a set S $\in$ V of smallest vertex-weight such that every vertex v not in S, there is a vertex u in S such that d(u,v) $\leq$  r. Distance is defined by the length of shortest path on graph. Does anyone know papers that solve this problem on a $\textbf{tree}$?

The problem is solved in the paper P. Slater. R-domination in graphs. J. ACM, 23(3):446–450, July 1976. It considers an even more general problem using dynamic programming.


When is a non-unitary quantum system only theoretical? Suppose we construct a non-unitary quantum system α in hilbert space. It entails that this system would have no direct parallel in quantum circuitry as it is a requirement that all quantum gates are unitary and therefore the function constructed from them is also unitary. But does this mean that we cannot practically implement α?

A potential parallel is found in the simulation of classical computations on a quantum computer, achieved by simulating an information-destroying NAND gate using an information-preserving Toffoli gate. If a non-unitary quantum system was such because it implemented a 'quantum NAND gate', it would be possible to redesign it as a unitary system using a Toffoli gate. It is not clear to me (and I cannot immediately find literature on this) if there are clearly defined bounds on what non-unitary operations can be simulated using unitary equivalents.

Is there a clearly defined subset of non-unitary quantum systems where α is practically implementable? Is it, perhaps, universal?

Look at John Preskill's Lecture Notes; particularly Section 3.2.

As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, so you no longer necessarily have a pure state of your system.

For non-unitary quantum operations, if you assume that the environment doesn't remember anything, then the most general thing you can do is a unitary operation followed by throwing away some part of the system.

If you assume that the environment has memory, things get much more complicated. But note that here, your operations aren't consistent because the outcome of an operation will depend on what the input was the last time you performed the operation. I don't know if you want to include this class of operations. While they are important in physics, they aren't very useful for quantum computation.


Status of Raghavendra's algorithm for solving linear systems in finite fields In 2012, Lipton wrote a blog entry about a new algorithm for solving linear systems over finite fields by Prasad Raghavendra.

The link to Raghavendra's draft paper on the topic is now dead, and I can't find anything on the subject on Raghavendra's website.

Is the result correct? Is a write-up available anywhere?

Thanks!

This is a paper that seems to improve upon the result. https://arxiv.org/pdf/1209.3995.pdf


Oracle relative to which BPP = EXP An oracle construction relative to which BPP = EXP is usually attributed to Heller (Mathematical System Theory Vol. 17, 1984). Unfortunately I don't have the paper available in my library. Could someone explain how it goes? If it is easier to give an oracle where NP = EXP that would fine already.

I would write this as a comment, but there was a limitation on the number of characters. So I'll put it here.

The paper title is "Relativized Polynomial Hierarchies Extending Two Levels." When you do not have access to an article, your best bet is to search for books/articles that reference your indented paper. The best place, IMO, is Google Scholar and Google Books.

The Complexity Zoo attributes the proof that "There exist oracles relative to which EXP = NP = ZPP" to this paper. Yet this is incomplete, since other references cite the following papers as well [off-topic: I updated Zoo to cover the new references as well]:

Heller, H. 1984. On relativized polynomial and exponential computations. SIAM J. Comput. 13, 4 (Nov. 1984), 717-725. DOI= http://dx.doi.org/10.1137/0213045
Heller, H. 1986. On relativized exponential and probabilistic complexity classes. Inf. Control 71, 3 (Dec. 1986), 231-243. DOI= http://dx.doi.org/10.1016/S0019-9958(86)80012-2

There's also the following paper:

 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

cited by several references as having influence on the relativized ZPP = EXP result (see for instance "Comparing Notions of Full Derandomization" by Lance Fortnow).

Specially, while the paper you cited only proves the existence of an oracle $B$ such that

${(\Sigma _1^p)^B} \subset {(\Sigma _2^p)^B} = (\Pi _2^B)$,

The paper #1 above continues by proving:

${(\Sigma _2^p)^B} = (\Pi _2^B) = \mathbf{EXP}^B = \mathbf{NEXP}^B$

and paper #2 above completes it by showing the relations between relatizied EXP and (if I'm not mistaken) RP.

Joining forces, the relativized BPP = NEXP is deduced.

PS: Please provide me with an email address of yours. I want to send you some docs.


What are some standard books/papers on Information Theory? I have started Information Theory classes just recently and was wondering what would be a standard book to purchase. I know I can go for basic introductory books but I also like to purchase standard books that I can use throughout my career for future reference purposes. I get some threads in forums about introductory books or basic books on information theory, but I can't find any about standard books on information theory.
P.S.:By standard book I mean like Cormen is for Algorithms

This is a list of recommended books, videos and web sites copied from the Further Readings section of my book on information theory (given at the end of this post).

Applebaum D (2008). Probability and Information: An Integrated Approach. A thorough introduction to information theory, which strikes a good balance between intuitive and technical explanations.

Avery J (2012). Information Theory and Evolution. An engaging account of how information theory is relevant to a wide range of natural and man-made systems, including evolution, physics, culture and genetics. Includes interesting background stories on the development of ideas within these different disciplines.

Baeyer HV (2005). Information: The New Language of Science Erudite, wide-ranging, and insightful account of information theory. Contains no equations, which makes it very readable.

Cover T and Thomas J (1991). Elements of Information Theory. Comprehensive, and highly technical, with historical notes and an equation summary at the end of each chapter.

Ghahramani Z (2002). Information Theory. Encyclopedia of Cognitive Science. An excellent, brief overview of information.

Gleick J (2012). The Information. An informal introduction to the history of ideas and people associated with information theory.

Guizzo EM (2003). The Essential Message: Claude Shannon and the Making of Information Theory. Master’s Thesis, Massachusetts Institute of Technology. One of the few accounts of Shannon’s role in the development of information theory.
See http://dspace.mit.edu/ bitstream/handle/1721.1/39429/54526133.pdf.

Laughlin, SB (2006). The Hungry Eye: Energy, Information and Retinal Function, Excellent lecture on the energy cost of Shannon information in eyes. See http://www.crsltd.com/guest-talks/ crs-guest-lecturers/simon-laughlin.

MacKay DJC (2003). Information Theory, Inference, and Learning Algorithms. The modern classic on information theory. A very readable text that roams far and wide over many topics. The book’s web site (below) also has a link to an excellent series of video lectures by MacKay. Available free online at http://www.inference.phy. cam.ac.uk/mackay/itila/.

Pierce JR (1980). An Introduction to Information Theory: Symbols, Signals and Noise. Second Edition. Pierce writes with an informal, tutorial style of writing, but does not flinch from presenting the fundamental theorems of information theory. This book provides a good balance between words and equations.

Reza FM (1961). An Introduction to Information Theory. A more comprehensive and mathematically rigorous book than Pierce’s book, it should be read only after first reading Pierce’s more informal text.

Seife C (2007). Decoding the Universe: How the New Science of Information Is Explaining Everything in the Cosmos, From Our Brains to Black Holes. A lucid and engaging account of the relationship between information, thermodynamic entropy and quantum computing. Highly recommended.

Shannon CE and Weaver W (1949). The Mathematical Theory of Communication. University of Illinois Press. A surprisingly accessible book, written in an era when information theory was known only to a privileged few. This book can be downloaded from http://cm. bell-labs.com/cm/ms/what/shannonday/paper.html

For the complete novice, the videos at the online Kahn Academy provide an excellent introduction.

Additionally, the online Scholarpedia web page by Latham and Rudi provides a lucid technical account of mutual information: http://www.scholarpedia.org/article/Mutual_information.

Finally, some historical perspective is provided in a long interview with Shannon conducted in 1982: http://www.ieeeghn.org/wiki/ index.php/Oral-History:Claude_E._Shannon.

Finally, my book is called Information Theory: A Tutorial Introduction (2015). Chapter 1 can be downloaded from here:
http://jim-stone.staff.shef.ac.uk/BookInfoTheory/InfoTheoryBookMain.html


Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits? I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in [1], Lemma 3 in [2], Decomposition Lemma in [3], also mentioned in [4]). My question is: Is homogeneity required if we apply this theorem to monotone circuits (i.e. circuits that compute over the semiring of non-negative reals)?
The statement of the theorem is: Let $f$ be a polynomial of degree $deg(f)$ computed by an arithmetic circuit** with $t$ gates. The polynomial $f$ can be written as $f = g_1 \cdot h_1 + \ldots + g_t \cdot h_t$, where $deg(g_i) \le 2deg(f)/3$ and $deg(h_i) \le 2deg(f)/3$.
** with some restrictions
This theorem is proved by repeatedly finding a gate $v$ that computes a polynomial $f_v$ where $deg(f)/3 \le deg(f_v) \le 2deg(f)/3$ and writing the polynomial as $f = f_v \cdot h + f_{v=0}$, where $h$ is some polynomial that must be of degree at most $2deg(f)/3$ and $f_{v=0}$ is the polynomial obtained by setting the gate $v$ to zero.
All statements of this theorem that I have seen require homogeneity of the circuit, which I guess is required for non-monotone circuits. However, to my understanding of the proof it should also work for non-homogeneous monotone circuits. (It should work when for polynomials $g$ and $h$ it holds that $deg(g+h) = \max(deg(g), deg(h))$ and $deg(g \cdot h) = deg(g) + deg(h)$.) Am I missing something?
[1] Hyafil, L. (1979). On the parallel evaluation of multivariate polynomials. SIAM Journal on Computing, 8(2), 120-123.
[2] Valiant, L. G. (1979, April). Negation can be exponentially powerful. In Proceedings of the eleventh annual ACM symposium on Theory of computing (pp. 189-196).
[3] https://arxiv.org/pdf/1803.05380v1.pdf
[4] https://arxiv.org/pdf/1710.09502.pdf

No, homogeneity is not required when applying this theorem to monotone circuits, and in fact homogeneity is a quite technical restriction that can be removed even in the general case by weakening the theorem a bit. I'll try to explain some things that made this more clear to me. (and hopefully being wrong in the internet will be more provocative than asking a question)
For completeness, the definition of monotonicity is that the subset of field elements used by the circuit cannot produce $0$ by additions and multiplications. The definition of homogeneity is that all gates of the circuit compute a homogeneus polynomial, i.e., a polynomial whose all monomials have the same degree.
The reason why homogeneity is quite technical restriction is that if $f$ is a polynomial that can be computed by an arithmetic circuit of size $t$, then the polynomial $f_d$ consisting of degree $d$ monomials of $f$ can be computed by a homogeneous arithmetic circuit of size $O(d^2 t)$. (This is for example stated as Lemma 2 in the Hyafil's paper.) This means that we can remove the homogeneity requirement from the theorem if we allow a blow up of a factor $O(d^3)$ in the number of terms.
Now, let's see what we need to assume so that the proof works:
First, given a circuit computing a polynomial $f$ with degree $deg(f)$, we need to find a gate $v$ computing a polynomial $f_v$ with degree $deg(f)/3 \le deg(f_v) \le 2deg(f)/3$. We need to assume fan-in 2 for this, but no other assumptions are required, as for any polynomials $g,h$ it holds that $deg(g) + deg(h) \ge deg(g \diamond h)$, where $\diamond$ is either the sum or the product.
Now that we have found the gate $v$, we write the polynomial $f$ as $f = f_v \cdot h + f_{v=0}$, where $f_{v=0}$ is the polynomial obtained from the circuit by setting $v$ to zero. No assumptions are required to see that the polynomial $f_{v=0}$ can be computed with one gate less than $f$, and any assumptions we made about the original circuit that are closed under setting a gate to zero also hold for the circuit computing $f_{v=0}$ (in particular, monotonicity or homogeneity).
One more important thing is that we have to guarantee that the degree of $f_{v=0}$ is at most $deg(f)$.
This holds if we cannot remove $v$ from the circuit without affecting the output and if for all gates in the circuit it holds that $deg(g \diamond h) \ge \max(deg(g), deg(h))$, where $\diamond$ is the operation computed by the gate and $g$ and $h$ the inputs.
This inequality holds for monotone polynomials and for homogeneous polynomials whenever $g \diamond h$ is non-zero, and here we indeed need to assume either monotonicity or homogeneity in order to make the proof work.
What is left is to show that there is such polynomial $h$ with $deg(h) \le 2deg(f)/3$.
The existence of $h$ follows by the observation that the polynomial $f_{v=0}$ is the same as the polynomial $f$, except that some monomials with a factor $f_v$ are missing. This can be proved by induction by separating the polynomials computed by each gate to two parts, the part coming from $v$ and the other part.
The degree of $h \cdot f_v$ is at most $deg(f)$ because the degrees of $f_{v=0}$ and $f$ are at most $deg(f)$.
Now, $deg(h) \le 2deg(f)/3$ follows from the facts that $deg(f_v) \ge deg(f)/3$ and $deg(h \cdot f_v) = deg(h) + deg(f_v)$, which is because the polynomials are over a field, which is a standard assumption in arithmetic circuits [1].
This would complete the proof of the version of the theorem that I stated in the question, but that version is missing an important property: if we assume either homogeneity or monotonicity, can we assume homogeneity or monotonicity of $f_v$ and $h$? For monotonicity, we see that the process of separating $h$ from $f$ by induction is closed under monotone arithmetic. For homogeneity, we have that $f_v$ and $f_{v=0}$ are homogeneous, so $h$ cannot be non-homogeneous because then $f$ would be non-homogeneous.
To summarize, the assumptions of this theorem are:

The polynomials are over a field. This is a standard assumption in arithmetic circuits [1].
The gates of the circuit have fan-in 2.
The circuit is homogeneous or monotone, or we have some other argument to guarantee that $deg(f + g) = \max(deg(f), deg(g))$ for $+$ gates with inputs $f$ and $g$.

[1] Shpilka, Amir, and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Now Publishers Inc, 2010.


Maximize graph with k cut edge operations I have undirected graph with N nodes each with some weight. There are M edges and in exactly K operations I want to maximize the XOR sum of connected components of the graph. ((n1 XOR n2 XOR n3) + (c1 XOR c2 XOR c3)).
(There can be multiple edges between 2 nodes.

I've tried attempting it with Minimum spanning tree with cut edge but couldn't succeed. Any help?

I guess this problem is NP-hard.

It is known that finding the minimum k-cut that separates k specified vertices is NP-hard (https://en.wikipedia.org/wiki/Minimum_k-cut). Therefore, given a minimum k-cut instance as well as k specified vertices, we can assign weight-1 to all the k specified vertices, and weight-0 to other vertices. Finally we apply the blackbox algorithm for your XOR problem to binary-search for the minimum k-cut size.


Reference request --- minimizing a non-increasing submodular function with (upper bound) cardinality constraint Suppose a set function $f(S)$ is submodular and non-increasing, meaning that for any $S'\subset S$, $f(S') \geq f(S)$. The problem is to minimize $f(S)$ s.t. $|S| \leq k$.

I am wondering if there are some references discussing approximation algorithms regarding this problem.

The reference I can find now discussed a similar problem: minimize a non-decreasing submodular function under (lower bound) cardinality constraint (i.e., $|S| \leq k$). But it is not obvious to me how to adapt the result to the previous problem.

Edit: the exact form of $f$ is known.

If the only thing that you know about $f$ is that it is non-increasing, then there is a simple adversary argument to show that you need to examine the value of $f$ on at least ${n \choose k}$ inputs (e.g., all ${n \choose k}$ different sets of cardinality $k$) in the worst case.  For instance, consider functions $f$ that are $+\infty$ on all sets of cardinality $<k$, and with arbitrary values on the sets of cardinality $k$, and $-\infty$ on all sets of cardinality $>k$.  A similar argument shows that no useful approximation is possible, either.

So, to make the problem tractable, you need to restrict the class of allowable functions in some way.


Structural equality of Pi Types with heterogeneous equality? I'm trying to implement a proof of the following type:

(X X' : Type0) -> (Y : (X -> Type0)) (Y' : (X' -> Type0) -> (X Type0~=~Type0 X')
-> ( Y (X -> Type0)~=~(X' -> Type0) Y' )
-> ((x : X) -> Y x) Type0~=~Type0 ((x' : X') -> Y' x')

i.e. if we have two function types with equal domain and codomain, then the pi types are themselves equal.

I'm using (z Z~=~W w) to denote McBride's Heterogeneous equality between (z : Z) and (w : W).

I'm wondering, can we prove this:

with dependent pattern matching?
using just the J axiom for heterogeneous equality?
Using J and K for heterogeneous equality?

I can see how I can start with a proof that ((x : X) -> Y x) ~=~ ((x : X) -> Y x), but if I use J to rewrite X to X', then (Y x') is ill typed.

I think I can see how to do it with dependent pattern matching, because matching on the proof of (X ~=~ X') rewrites X' to X both in the goal type and in the context for the goal. And I know that dependent pattern matching can be decomposed to eliminators + Axiom K a la Goguen et al. But it's not immediately clear to me how to do the proof directly, and whether it relies on K.

I am not aware that J or K exists for heterogeneous equality. It does not need an elimination principle, because it can be simply defined as a sigma type:

coe : ∀{i}{A B : Set i} → A ≡ B → A → B

HEq : ∀ {i}{A B : Set i} → A → B → Set _
HEq {_}{A} {B} x y = Σ (A ≡ B) λ p → coe p x ≡ y

To do anything with HEq, it is enough to consider J and K for propositional equality. Dependent pattern matching is usually equivalent to J + K, although in Agda we can have pattern matching which is equivalent only to J.

So the question boils down to whether we can prove your lemma with J, or we need K as well. I prefer to work with uniqueness of identity proofs (UIP) instead of K (they are logically equivalent), so let's do that.

UIP : ∀ {i}{A : Set i}{x : A}{p : x ≡ x} → p ≡ refl

The answer is that we need UIP. Writing the lemma in Agda:

lem :
  ∀ (A₀ A₁ : Set)
    (A₀₁ : HEq A₀ A₁)
    (B₀ : A₀ → Set)
    (B₁ : A₁ → Set)
    (B₀₁ : HEq B₀ B₁)
  → HEq (∀ x → B₀ x) (∀ x → B₁ x)
lem A₀ A₁ (p , A₀₁) B₀ B₁ (q , B₀₁) = ?

It jumps at us that

A₀₁ : coe p A₀ ≡ A₁
p   : Set ≡ Set

In the absence of UIP, it is not provable that A₀ ≡ A₁, and therefore lem is not provable either. We can make it work with UIP. Agda code with intentionally puritan J usage:

{-# OPTIONS --without-K #-}

open import Data.Product

infix 4 _≡_
data _≡_ {a} {A : Set a} (x : A) : A → Set a where
  refl : x ≡ x

postulate
  UIP : ∀ {i}{A : Set i}{x : A}{p : x ≡ x} → p ≡ refl

J :
  ∀ {α β}{A : Set α} {x : A}(P : ∀ y → x ≡ y → Set β)
  → P x refl → {y : A} → (w : x ≡ y) → P y w
J P pr refl = pr

tr : ∀ {i j}{A : Set i}(B : A → Set j){a₀ : A}{a₁ : A}(a₂ : a₀ ≡ a₁) → B a₀ → B a₁
tr B p x = J (λ x _ → B x) x p

coe : ∀{i}{A B : Set i} → A ≡ B → A → B
coe = tr (λ x → x)

ap : ∀{i j}{A : Set i}{B : Set j}(f : A → B){a₀ a₁ : A}(a₂ : a₀ ≡ a₁)
     → f a₀ ≡ f a₁
ap f p = tr (λ a₁ → f _ ≡ f a₁) p refl

sym : ∀ {i}{A : Set i}{x y : A} → x ≡ y → y ≡ x
sym p = tr (λ y → y ≡ _) p refl

HEq : ∀ {i}{A B : Set i} → A → B → Set _
HEq {_}{A} {B} x y = Σ (A ≡ B) λ p → coe p x ≡ y

lem :
  ∀ (A₀ A₁ : Set)
    (A₀₁ : HEq A₀ A₁)
    (B₀ : A₀ → Set)
    (B₁ : A₁ → Set)
    (B₀₁ : HEq B₀ B₁)
  → HEq (∀ x → B₀ x) (∀ x → B₁ x)
lem A₀ A₁ (p , A₀₁) B₀ B₁ (q , B₀₁) =
  tr (λ p → (A₀₁ : coe p A₀ ≡ A₁) → HEq (∀ x → B₀ x) (∀ x → B₁ x))
     (sym (UIP {p = p}))
     (λ A₀₁ →
          refl ,
          J (λ A₁ A₀₁ → ∀ B₀ B₁ (q : (A₀ → Set) ≡ (A₁ → Set))
                      → coe q B₀ ≡ B₁
                      → ((x : A₀) → B₀ x) ≡ ((x : A₁) → B₁ x))
            (λ B₀ B₁ q B₀₁ →
               tr (λ q → coe q B₀ ≡ B₁ → ((x : A₀) → B₀ x) ≡ ((x : A₀) → B₁ x))
                  (sym (UIP {p = q}))
                  (λ B₀₁ → ap (λ f → ∀ x → f x) B₀₁)
                  B₀₁)
            A₀₁ B₀ B₁ q B₀₁)
     A₀₁

This might seem a handful, but after some practice such code is a mechanical exercise which generally follows the compilation of pattern matching.

At this point we might ask if a variant of the lemma is provable only with J. The following is such, for example.

lemJ :
  ∀ (A₀ A₁ : Set)
    (A₀₁ : A₀ ≡ A₁)
    (B₀ : A₀ → Set)
    (B₁ : A₁ → Set)
    (B₀₁ : tr (λ X → X → Set) A₀₁ B₀ ≡ B₁)
  → (∀ x → B₀ x) ≡ (∀ x → B₁ x)
lemJ A₀ A₁ A₀₁ B₀ B₁ B₀₁ =
  J (λ A₁ A₀₁ → ∀ B₀ B₁ (B₀₁ : tr (λ X → X → Set) A₀₁ B₀ ≡ B₁)
              → ((x : A₀) → B₀ x) ≡ ((x : A₁) → B₁ x))
    (λ B₀ B₁ B₀₁ → ap (λ f → ∀ x → f x) B₀₁)
    A₀₁ B₀ B₁ B₀₁


Are there established cryptographic hardness assumptions for chaotic systems? I found this paper of Cuomo and Oppenheim, where they use a Lorenz system to define an encryption scheme for signals. There is also this blog post describing and implementing the technique. The technique uses an interesting property of the Lorenz system known as "synchronization," which as far as I know occurs in other dynamical systems as well. Moreover, the chaotic nature of these systems intuitively makes guessing the parameters of the system infeasible, so a natural shared secret key is the set of constants used to define the system.

I was wondering if there has been any theoretical work in cryptography that deals with dynamical systems. Specifically, are there established cryptographic hardness assumptions for specific dynamical systems? It seems like it would be a different flavor of hardness assumption from the usual ones, because the methods naturally introduce some noise into the decrypted message.

Personally, I wouldn't bother with chaos-based encryption.  I have yet to see any scheme based upon chaos that strikes me as very promising from either a practical or a theoretical perspective.  The work on using chaos for encryption that I've seen ranks pretty high on my "bogometer".  I never see any sort of security proof or plausible evidence of security, and many such systems turn out to be broken when you take a close look.  And I find it hard to see any benefit over standard well-known approaches (e.g., CBC mode encryption; information-theoretic work based upon Wyner's wiretap channel; etc.).

But if you want to find something in this space, you might look at the following paper:

Semantic Security for the Wiretap Channel.  Mihir Bellare, Stefano Tessaro, and Alexander Vardy.  CRYPTO 2012.

It has plenty of theoretical/foundational content, and is in the vicinity of the sort of thing you mention.


Sorting using ring operations Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time.

Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done in linear time using $\{\times,+,-,\bmod\}$ operations in unit cost RAM model where ring operations can be performed on arbitrarily large words in unit time?

I am thinking of using only $!=0$ comparison using modulo operations. If $x>y$, then $x\bmod y\neq x$. If $x<y$, then $x\bmod y=x$ holds. So using $x-y==0$ followed by $x - (x\bmod y)==0$ will tell if $x<y$. I do not wish to have bit operations. I want more like $\mathsf{BSS}$ model.

Let me clarify my sorting problem further.

Say I have been given list of $n$ different integers $a_0,\dots,a_n$ with each $a_i\in(0,2^m-1)$. I can write down the list in a long integer form $$G=a_0+a_12^m+\dots+a_n2^{nm}$$

There is an unique permutation $\sigma\in S_{n+1}$ such
$$N=a_{\sigma(0)}+a_{\sigma(1)}2^m+\dots+a_{\sigma(n)}2^{nm}$$ is minimum.

How many ring operations (with $\bmod$) would it take in worst case for converting integer $G$ to $N$?

This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible.

I think you're going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory indexing? Comparisons? If you allow bitwise binary operations (including shifts) and either hashing or unbounded memory then it's all over, even without multiplication or division:

def sort(intlist):
    backtrans = {}
    bits = 0
    for x in intlist:
        y = 1<<x
        if y in backtrans:
            backtrans[y][1] += 1
        else:
            backtrans[y] = [x,1]
        bits |= y
    while bits:
        y = bits &~ (bits - 1)
        x,reps = backtrans[y]
        for i in range(reps):
            yield x
        bits &=~ y

There's also a linear time sorting algorithm (for large enough machine words) by Albers and Hagerup 1997 but I'm not sure which operations it needs or whether it could be adapted to use only arithmetic and not bit manipulation. The reference is:

Albers, Susanne; Hagerup, Torben (1997), "Improved parallel integer sorting without concurrent writing", Information and Computation 136 (1): 25–51.


What's a good advanced textbook/resource for studying the complexity of counting and combinatorics? I'm taking a class in enumerative combinatorics. The professor focusses on the complexity of solving combinatorics problems like partitions etc. I'm using Enumerative Combinatorics but it does not talk about complexity. What's a good book/website/resource that touches on enumerative (or even extremal) combinatorics and complexity of counting?

If I understood correctly, you're looking for a book (chapter) on counting complexity. In this case, I'd recommend the book of Sanjeev Arora and Boaz Barak, which has a chapter on counting complexity. A draft of it can be found here.

Concerning Extremal Combinatorics, Wiki suggests reading Extremal and Probabilistic Combinatorics by Noga Alon and Michael Krivelevich which contains pointers to some resources (mainly graph-related).


Complexity of listing all minimal cut sets / connected 2-partitions of a graph I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm that ideally would have the complexity linear in the number of cut sets, however, I only find papers describing algorithms that would generate all minimal cut sets between a fixed vertex pair. I would then have to run any algorithm for each pair and remove duplicates, so I am searching for a better approach. Does someone of you know any upper/lower bounds of the complexity of this problem (or even better, an optimal algorithm)? I would also be interested in results concerning special graphs, e.g. max degree k or so.

Best,
Vany

dear all. There is no contradiction here. The problem of listing or enumerating all cutsets is a counting problem which is #P-hard. The class #P consists of all the problems that can be solved by a non-deterministic counting Turing machine in polynomial time. Therefore, the class #P is useful for classifying counting problems. On the other hand, the class NP is suitable for classifying  decision problems. A decision version of your problem would be, for instance: Is there a cutset with cardinality less than $k$? Obviously, if you can enumerate all the cutsets in polynomial time, then you can also say in polynomial time if there exists a cutset with cardinality less than $k$. In other words, the counting version is at least as hard as the decision version.  Therefore, if a counting problem is #P-hard, then it is NP-hard (I am talking about the same counting problem, not its decision version). However, the converse is an open question. In other words, for the time being, saying that this problem is #P-hard is a stronger statement than saying that it is NP-hard.


Asymptotic complexity of sorting using k-comparisons Sorting using 2-elements comparisons has an asymptotic worst-case complexity of $n \log_2(n)$ (reached by mergesort, heapsort, binary insertion, ford-johnson at least), which is optimal.

If we sort using comparisons that sort k elements as building blocks, the information theoretic lower bound is $n \log_{k!}(n)$.
We can easily reach $n \log_k(n)$ with k-ary insertion.

Question: Where is the optimal complexity between $n \log_k(n)$ and $n \log_{k!}(n)$ ?

Appropriate refs would be appreciated too.

Edit : because it wasn't clear :

I'm interested about the complexity in $n$, with $k=O(1)$. It has the asymptotic behavior of $\alpha n\log_2(n)$ with $\alpha \in [\frac{1}{\log_2(k)},\frac{1}{\log_2(k!)}]$, and i'd like more precision about $\alpha$.

As I was told by Abhishek Methuku, this has been studied already, in fact several times, see e.g. http://www.researchgate.net/publication/3042594_Sorting_n_objects_with_a_k-sorter

For $k$ large, the answer is close to $n \log_{k!}(n)$ but e.g. $k=3$ seems to be open.


QPIP minimal client quantum capabilities It is conjectured that classical (BPP) client blind quantum computing is implausible according to Aaronson et al:

https://www.researchgate.net/publication/316538667_On_the_implausibility_of_classical_client_blind_quantum_computing

What are the minimal quantum capabilities that a classical client must have in order to verify a single BQP quantum prover with the following requirements?

Information-secure communication (no cryptographic assumptions)
Only the size of the input is revealed to the quantum prover
Single prover server

My understanding is that the paper above leaves this as an open problem.

According to this paper:

https://arxiv.org/pdf/1509.09180.pdf

The client only needs the ability to prepare random single-qubit pure states.

You may also look at this paper for more information:

https://link.springer.com/article/10.1007/s00224-018-9872-3


Partition a graph into node-disjoint cycles Related problem: Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The edge set of a graph can be partitioned into cycles if and only if every vertex has even degree."

My Problem: I wonder has anybody studied the partition a graph into node-disjoint cycles. That is, partition the vertices $V$ of a graph $G$ into $V_1, V_2, \cdots, V_k$, and each subgraph induced by $V_i$ is hamiltonian.

Is it NP-hard or easy?

More related problem:
Partition into triangle is NP-complete. (Page 68 of "Computers and intractability")

Thank you for your advise in advance. ^^

A partition into vertex-disjoint cycles is the same thing as a 2-regular subgraph, more commonly known as a 2-factor. It can be found (if it exists) in polynomial time by an algorithm based on matching. E.g. see this link.

ETA Nov 2013: It seems from comments below that the reduction from the source linked above is wrong. However, the statement that the problem can be reduced to perfect matching remains correct. The correct reduction is in W. T. Tutte (1954), "A short proof of the factor theorem for finite graphs", Canadian J. Math. 6: 347–352.

Replace each vertex $v$ with degree $d$ by a complete bipartite graph $G_v=K_{d,\,d-2}$, and represent each edge $uv$ of the original graph by an edge from one vertex of $G_u$ to one vertex of $G_v$ (on the side of the bipartition with $d$ vertices) in such a way that each vertex of $G_v$ on that side of the bipartition has exactly one such edge incident to it.

Then a perfect matching in the modified graph has to match the $d-2$ vertices on their side of the bipartition of $G_v$ with $d-2$ out of the $d$ vertices on the other side, leaving exactly two free vertices that need to be matched with their neighbors in other subgraphs $G_u$. In this way, the perfect matchings of the modified graph correspond 1-for-1 with cycle covers of the original graph.


Commitment schemes with verification in NC0 Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$?  If so, what is the minimum possible depth of the circuit for verification?

Applebaum et al prove the existence of a commitment scheme where commitment can be done in $NC^0$ and where verification can be done with a $NC^0$ circuit plus a single AND gate of unbounded fan-in.  See

Cryptography in NC0.  Benny Applebaum, Yuval Ishai, Eyal Kushilevitz.  Section 7.

However, this does not show how to do the verification in $NC^0$, i.e., in constant depth.  Is there a plausible construction to achieve that goal?

For a result of a similar flavor, see also

Cryptography with Constant Input Locality.   Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.  Journal of Cryptology, 2009, 22:429-469.

which gives a plausible construction of a commitment scheme with similar properties; but again their verification scheme involves a $NC^0$ circuit plus a single AND gate of unbounded fan-in.

Motivation. I came across this problem when thinking about how to obfuscate a particular function that uses the verification component of a commitment scheme, but I realized this might be of broader interest.

No. $\;\;\;\;$ There is also no secure commitment scheme where the verification

routine can be done with bounded fan-in in depth $\:o(\hspace{.02 in}\log(\hspace{.02 in}\log(k)))\:$,

since such circuits have input locality $\:(\hspace{.02 in}\log(k))^{o(1)}$,$\:$ which means one can

efficiently brute-force the bits that might affect the verification circuit's output.


Subtypes as subsets of SML datatypes One of the few things that I dislike about Okasaki's book on purely functional data structures is that his code is littered with inexhaustive pattern matching. As an example, I'll give his implementation of real-time queues (refactored to eliminate unnecessary suspensions):

infixr 5 :::

datatype 'a stream = Nil | ::: of 'a * 'a stream lazy

structure RealTimeQueue :> QUEUE =
struct
  (* front stream, rear list, schedule stream *)
  type 'a queue = 'a stream * 'a list * 'a stream

  (* the front stream is one element shorter than the rear list *)
  fun rotate (x ::: $xs, y :: ys, zs) = x ::: $rotate (xs, ys, y ::: $zs)
    | rotate (Nil, y :: nil, zs) = y ::: $zs

  fun exec (xs, ys, _ ::: $zs) = (xs, ys, zs)
    | exec args = let val xs = rotate args in (xs, nil, xs) end

  (* public operations *)
  val empty = (Nil, nil, Nil)
  fun snoc ((xs, ys, zs), y) = exec (xs, y :: ys, zs)
  fun uncons (x ::: $xs, ys, zs) = SOME (x, exec (xs, ys, zs))
    | uncons _ = NONE
end

As can be seen rotate isn't exhaustive, because it doesn't cover the case where the rear list is empty. Most Standard ML implementations will generate a warning about it. We know that the rear list can't possibly be empty, because rotate's precondition is that the rear list one element longer than the front stream. But the type checker doesn't know - and it can't possibly know, because this fact is inexpressible in ML's type system.

Right now, my solution to suppress this warning is the following inelegant hack:

  fun rotate (x ::: $xs, y :: ys, zs) = x ::: $rotate (xs, ys, y ::: $zs)
    | rotate (_, ys, zs) = foldl (fn (x, xs) => x ::: $xs) zs ys

But what I really want is a type system that can understand that not every triplet is a valid argument to rotate. I'd like the type system to let me define types like:

type 'a triplet = 'a stream * 'a list * 'a stream

subtype 'a queue of 'a triplet
  = (Nil, nil, Nil)
  | (xs, ys, zs) : 'a queue => (_ ::: $xs, _ :: ys, zs)
  | (xs, ys, zs) : 'a queue => (_ ::: $xs, ys, _ ::: $zs)

And then infer:

subtype 'a rotatable of 'a triplet
  = (xs, ys, _) : 'a rotatable => (_ ::: $xs, _ :: ys, _)
  | (Nil, y :: nil, _)

subtype 'a executable of 'a triplet
  = (xs, ys, zs) : 'a queue => (xs, ys, _ ::: $zs)
  | (xs, ys, Nil) : 'a rotatable => (xs, ys, Nil)

val rotate : 'a rotatable -> 'a stream
val exec : 'a executable -> 'a queue

However, I don't want full-blown dependent types, or even GADTs, or any of the other crazy things certain programmers use. I just want to define subtypes by “carving out” inductively defined subsets of existing ML types. Is this feasible?

These kinds of types -- where you define a subtype (basically) by giving a grammar of the acceptable values -- are called datasort refinements.

They were introduced by Tim Freeman and Frank Pfenning, in their 1991 PLDI paper, Refinement Types for ML.
Rowan Davies studied type inference for refinement types in his PhD thesis, Practical Refinement Type Checking. He also implemented it as an extension to SML, but I don't know if it is available online.
Joshua Dunfield studied how to combine datasort refinements with fancier lightweight type dependency in his thesis, A Unified System of Type Refinements. He also implemented it in his Stardust language, which is available online:

http://www.mpi-sws.org/~joshua/stardust/