Are there any annotated formal verification systems for pure functional programming languages? ACSL (Ansi C Specification Language), is a specification for C code, annotated with special comments, that allows C code to be formally verified.

I have not looked into it, but I imagine that the formal methods used in ACSL verifiers would be similar to Hoare Logic. For pure functional languages though, such as Haskell, I can't imagine what sort of formalism would be used for formal verification.

Has anyone made something similar to ACSL, but for a pure functional language? If not, has there been any research into specification-annotated style formal verification for functional languages?

I know that there's dependent typing, which many languages (Agda, Idris, etc...) support, but in Haskell dependent typing is difficult without doing some (unreadable?) type-wizardry. With that in mind, and since Haskell has so much better library support than Agda and Idris, I believe such a system for functional formal verification might be useful, but I don't know if research has been done on this or not.

You might want to check out Liquid Haskell, which allow working with type refinements rather than dependent types. Type refinements can be seen as a restricted logical language that allow you to express Hoare-style properties of the inhabitants of various datatypes. Another possible candidate is the $F^*$ language, which offers similar constructs.

There seems to be a close correspondence between refinement types and the ACSL like notations.

Finally I can only suggest taking a closer look at Agda and Idris, as they can compile to Haskell, and are aimed at providing the user with a usable programing language (especially Idris). I suspect it's possible to integrate Haskell libraries into Idris code without too much trouble.


Observational Equivalence of open terms in PCF The notion of observational equivalence is rather intuitive, but formally I'm having some doubts in the particular case of open terms.

Lets consider the simple case where  the terms M and N are free variables, M = x and N = y. Choosing the program context C[-] = (λxy.[-]) v w we have,
C[M] = (λxy.x) v w →* v
C[N] = (λxy.y) v w →* w
So by definition M and N wouldn't be observationally equivalent.

However, consider any adequate denotational semantics of PCF. Then by definition of adequacy, ⟦M⟧ = ⟦N⟧ implies M and N observationally equivalent. The denotations of both (open) terms are,
⟦M⟧ = ⟦x ⊢ x⟧ = id
⟦N⟧ = ⟦y ⊢ y⟧ = id
From what we conclude M and N  to be observationally equivalent.

So, surely I must be going wrong somewhere, and I suspect it to be some trivial mistake. But where?

Got the answer, thanks to jonsterling on reddit for the insight.

The error is that both M and N written as full judgements, must be weakened to have the same environment, and one that fits C[-]. So the question becomes whether  ⟦M⟧ = ⟦x,y ⊢ x⟧ and ⟦N⟧ = ⟦x,y ⊢ y⟧ are observationally equivalent.  And the contradiction above disappears.


Mathematical explanation of recursion and lambda (referenced in The Little Schemer) In the preface of Friedman and Felleisen's book The Little Schemer it states:

  We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a reader who understands that page has little need for that book.

Has anyone got an online link to the equivalent of this mathematical summary of The Little Schemer in a single page? Presumably this would cover recursion,  lambda and the y-combinator.

What Sam said.

Also, it's really well under a page.  If you're familiar with evaluation contexts, you can specify the call-by-value lambda calculus like this:

Terms

$$M ::= x \mid (M \, M) \mid (\lambda x . M)$$

Values

$$V = (\lambda x . M)$$

Evaluation contexts

$$E ::= [\:] \mid ([\:] M) | (V [\:])$$

The (only) reduction rule:

$$E[((\lambda x . M) V)] \to E[M.\mathrm{subst}(V,x)]$$

where $.\mathrm{subst}$ denotes capture-avoiding substitution.

Again, though, the background knowledge involved in reading this definition is by no means self-evident. There are many free places on the web to read about it. For a tidy and well-typeset presentation, you might also be interested in Felleisen/Flatt/Findler's book, Semantics Engineering with Redex.

Holey Moley! I just googled for it, and got the full PDF online. Well, that won't last...


Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length? S-T CONNECTEDNESS

Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$

Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$.

S-T CONNECTEDNESS problem is known to be #P-complete ([Valiant, L. G. (1979). The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3), 410-421.]).

I'm interested in those instances of S-T CONNECTEDNESS in which all simple paths between $s$ and $t$ are of the same length. Is anything known about the complexity of the problem on these instances? In particular, does the problem remain #P-complete?

Remark: In the Valiant's reduction, there are many simple paths between $s$ and $t$ of different lengths.

After polynomial time preprocessing, you may assume that every edge in $E$ lies on some simple $s$-$t$-path.

If all simple paths between $s$ and $t$ are of the same length, then $G$ is series-parallel, with $s$ as left terminal and $t$ as right terminal vertex. This can be seen easily, since the forbidden subgraphs for series-parallel graphs (= subdivisions of diamonds) create two paths of different lengths between $s$ and $t$.
In a series-parallel graph, the number of spanning subgraphs containing a simple $s$-$t$-path can be determined in polynomial time by dynamic programming.

In the dynamic program, we build up the graph by series and parallel compositions. For every resulting subgraph $G'$, we compute the number $p^+(G')$ of spanning subgraphs that do contain a simple path from its left terminal to its right terminal and the number $p^-(G')$ of spanning subgraphs that do not contain such a path.

In a series composition on $G_1$ and $G_2$, we get $p^+(G)=p^+(G_1)\cdot p^+(G_2)$.
In a parallel composition on $G_1$ and $G_2$, we get $p^-(G)=p^-(G_1)\cdot p^-(G_2)$.
In both cases, the missing value $p^+(G)$ or $p^-(G)$ for $G=(V,E)$ can be computed from $p^+(G)+p^-(G)=2^{|E|}$.


$⊕P$-completeness of $⊕2SAT$ Is $⊕2SAT$ - the parity of the number of solutions of $2$-$CNF$ formulae $\oplus P$ complete?

This is listed as an open problem in Valiant's 2005 paper https://link.springer.com/content/pdf/10.1007%2F11533719.pdf. Has this been resolved?

Is there any consequence if $⊕2SAT\in P$?

It is shown to be $\oplus P$-complete by Faben:
https://arxiv.org/abs/0809.1836
See Thm 3.5. Note that counting independent sets is same as counting solutions to monotone 2CNF.


What are the uses of Limits and Colimits of Category Theory in every day problems? I am interested in knowing how we can use the concepts of Limits and Colimits in modeling problems in every day life? Could anyone provide (Software) engineering examples, perhaps? Or describe intuitively in general for what sorts of modeling problems we can use these concepts? Thank you.

Take some relations $R_0\subseteq A_0\times A_1$, $R_1\subseteq A_1\times A_2$. Let $\pi_1:R_0\to A_1$, $\pi_0:R_1\to A_1$ be projections with domains restricted to relations $R_0$, $R_1$. Then the pullback of $\pi_0$, $\pi_1$ is the join of $R_0$ and $R_1$ in the SQL sense.


What is the state of the art in theory of "Software transformations preserving behavior"? I am interested in the field that could perhaps be referred to as "Automated Refactory" or "Preservation of Software Properties" after a transformation/change/refactory.

Saying we have an instruction/set of instructions I with some functional property P and some transformation T so that I' = T(I). Is there any research/work/papers that models P (just some properties, a group of, ...) and preservation/changes of those properties between I and I' for a set of transformations T?

First of all, what is the correct name for this fiels? Then, I would like to know if a theory to model this problem exists, which one is the most used (or the most referred to) and if any application of that system/metric/model (libraries, IDE plugins, ...) has been released.

If you can give any name, paper, ... whatever that is considered "fundamental" in this field, I will dig into this on my own.

I think what you are looking for, in the context of verified transformations in a proof assistant, is known as "refinement", wherein a very-high level, inefficient implementation of some algorithm is gradually refined down into an efficient, low-level implementation, proving that the transformations preserve certain properties along the way.  Various tools have been developed to help the user do this without being overcome by tedious book keeping.

In terms of the state of the art, I think Lammich's tool in Isabelle/HOL has been used successfully in at least two significant developments (a verification of Hopcroft's algorithm by Lammich and Tuerk, and a verified implementation of an LTL model checker by Esparza, Lammich et al).  Ironically, I was also reading this paper this morning, about a similar tool, newly developed, in Coq, courtesy of the dependent_types subreddit on Reddit.


Complexity of "is a graph a product" This question arises out of pure curiosity (it came up while thinking about unshuffling a string, but I'm not sure if it's actually related) so I hope it's appropriate.

There are various graph products, and I'm interested in any of them here. What is the complexity of determining whether a graph $K$ is isomorphic to a non-trivial product? (Certainly for the Cartesian product, $K = K \square 1$ where $1$ is the graph with one vertex.)

I've looked at the pages "factor graph" and "graph factorization" on Wikipedia, but neither seem to be related. Is this problem known under another name?

Check the paper Wilfried, Imrich; Iztok, Peterin, Recognizing Cartesian products in linear time. Discrete Math., 307, 3-5, Page(s): 472--483, 2007. I think that Imrich has more papers for other products.


Is there an equivalent to derandomization for quantum algorithms? With some randomized algorithms you can derandomize the algorithm, removing (at a possible cost in run time) the use of random bits and maximizing some lower bound on the objective (usually computed using the fact that the theorems are about the expected performance of the random algorithm). Is there an equivalent for quantum algorithms? Are there any well-known results of "dequantization"? Or is the underlying state space too big for this sort of technique?

There are certain classes of quantum gates which can be simulated efficiently with a classical computer. If no entanglement is present, a computation with pure states (i.e. not random states) can be simulated efficiently. Classical gates reversible gates are a subset of quantum gates, and so can obviously be simulated efficiently. These two examples are pretty trivial, however there are a number of non-trivial gate sets known.

Valiant gates as mentioned in Joshua's answer
Clifford group gates (see arXiv:quant-ph/0406196)
Match gates (see arXiv:0804.4050)
Commuting gates, etc.

Basically, most sets of operators which generate only some small subspace of $SU(2^N)$ tend to be simulable, while any that generate $SU(2^N)$ are as hard as general quantum simulation of N qubits.

It seems very unlikely that quantum mechanics is efficiently simulable, and so such a dequantization program will likely be impossible in general. There is however a regime where this has worked, which is with interactive proofs. Several different kinds of interactive proof systems with quantum verifiers have been shown to have the same power if the quantum verifier is replaced with a purely classical verifier. For an example of this, see Jain, Ji, Upadhyay and Watrous's proof that QIP=PSPACE (arXiv:0907.4737).


Is this problem mappable to 3SAT or is it weaker than 3SAT? Consider a variant of a satisifiability problem.

Given n dimensions (n >= 3, n < 10,000 think of n as large but finite)
The range of each dimension is either an interval over the integers or an interval over the fixed-point decimals (which can be mapped to be the integers).
Given a truth predicate which can use these operations:

  (<, =>, ==, !=, *, +, -, /, if/then, and}

Example in Prolog of a predicate of truth:

Predicate(V1, V2, V3) :-
   V2 =< V3,
   V1 * 5 =< V3,
   V1 * 50 >= V3.

Is this mappable to 3SAT?
Is this less hard than 3SAT?
What are pragmatic and efficient solutions to select some true point (or set of points) in the space?

And one way of trying to solve such a problem is to do a form of backtracking, or what is also called "branch-and-bound". (Sorry, this was too long for a comment.)

Here's one possible heuristic:

(1) Choose some variable $x$ that is "most" constrained in some sense (maybe it occurs the most often). Suppose its integer range is $[L,R]$, and let $M$ be the midpoint of that interval. Now try to recursively solve the problem when $x < M$ is assumed, and separately when $x \geq M$.

(2) In each recursive call, relax the predicate to be a linear program (i.e., the solutions to the variables are over the rationals), and include all range constraints such as $x \geq L$ and $x \leq R$. Check if the resulting linear program is still feasible over the rationals. If it isn't feasible over the rationals, then it won't be feasible over the integers either, so you can stop and backtrack. If it is feasible over the rationals, continue with step (1).

Note: not all possible constraints (e.g. quadratic polynomials like $x(1-x) = 0$) can be neatly expressed as linear constraints; one possible "solution" to this is to simply leave those constraints out (or, replace these "hard" constraints with linear constraints that are consequences of the hard constraint being true... for example, $x(1-x)=0$ has the consequence that $x \geq 0$ and $x \leq 1$).

That's about as much detail as a CS theory site can give you ;)


Is the 3-sphere recognition problem NP-complete? It is known that determining whether or not a given triangulated 3-manifold is a 3-sphere
is in NP, via work by
Saul Schleimer in 2004: "Sphere recognition lies in NP"
arXiv:math/0407047v1 [math.GT].
I am wondering if this has been established to be NP-complete in the last five or six years?
Analogous problems, such as the 3-manifold knot genus problem, have been shown NP-complete.

If it's NP-complete, then wouldn't you have proved that no set of (uniformly) polynomial-time computable invariants of 3-manifolds distinguishes 3-spheres from other 3-manifolds. I would be very surprised if this is known.


Refinements of pair approximation for network analysis When considering interactions on networks, it is usually very hard to calculate the dynamics analytically, and approximations are employed. Mean-field approximations usually end up ignoring the network structure completely, and so are seldom a good approximation. A popular approximation is the pair approximation, which considers the correlations inherent between adjacent nodes (intuitively we can think of it as a type of mean-field approximation on edges).
The approximation is exact if we are considering Cayley graphs, and very good if we are looking at $k$-regular random graphs. In practice it also provides good approximations for cases when we have a random graph with average degree $k$ and a tight distribution of degree around $k$. Unfortunately, a lot of the networks and interactions that are of interest, are not well modeled by these sort of graphs. They are usually well-modeled by graphs with very different degree distributions (like scale-free networks, for instance), with specific (and high) clustering coefficients, or specific average shortest-path distance (for more, see Albert & Barabasi 2001).
Are there refinements of pair approximation that work well for these types of networks? Or are there other analytic approximations available?

An example of interactions on networks
I thought I would give an example of what I mean by interactions on networks. I will include a relatively general example from evolutionary game theory.
You can think of each node as an agent (usually represented just by a strategy), that plays some fixed game pairwise with each other agent it has an edge to. Thus, a given network with a some assignment of strategy to each node produces a payoff for each node. We then use these payoffs and the network structure to determine the distribution of strategies among the nodes for the next iteration (A common example might be for each agent to copy the neighbor with the highest payoff, or some probabilistic variant of this). The questions we are usually interested in corresponding to knowing the numbers of agents of each strategy and how that changes overtime. Often we have stable distribution (which we then want to know, or approximate) or sometimes limit-cycles or even more exotic beasts.
If we do mean-field approximation on this sort of model, we use get the replicator equation as our dynamic, which blatantly ignores the network structure and is only accurate for complete graphs. If we use pair approximation (as Ohtsuki & Nowak 2006) we will get slightly different dynamics (it will actually be replicator dynamics with a modified payoff matrix, where the modification depends on the degree of the graph, and the specifics of the update step) which matches simulation well for random graphs, but not for other networks of interest.
For a more physics like example: replace the agents by spins and the call the payoff matrix an interaction Hamiltonian, then cool your system while performing periodic random measurements.
Notes and related questions

Straightforward generalizations of pair approximation of the sort that consider a type of mean-field approximation on triples, or quadruples of nodes) are unwieldy and still don't take into account very different degree distributions or average shortest-path distance.

Sources for Algorithmic Evolutionary Game Theory

The way you formulate your question makes it sound like you care about dynamics, but since what you are looking for seems to be a steady state solution, ground states seem like a much more productive route to go down.

Since you want to go beyond pairwise approximation, the most natural candidate technique seems to be matrix product states, which is a pretty hot topic at the moment for dealing with quantum ground states. The way this approach works is basically by introducing maximally entangled pairs between nodes, and at each node introducing a projector. By adding higher dimensional systems you'll capture more features of the graph. I know your problem probably isn't quantum, but I don't see why this technique still shouldn't work. You should be able to simply replace the entangled states with $\frac{1}{2}(|00\rangle \langle 00| + |11\rangle \langle 11|).$

Also, I'm not sure if this is the kind of thing you are looking for or not, but there are some recent results on realizibility of scale-free networks, showing that they exhibit two phase transitions which seems to have just been accepted to PRL. A preprint entitled "All scale-free networks are sparse" can be found as arXiv:1106:5150.


Exponential blowup in Simple Proof of a theorem of Statman by Mairson I'm studying "A simple proof of a theorem of Statman" by H.G. Mairson.

At page 4, he encodes set/type theory in lambda calculus.
In particular, note che "op" trick in the definition of $eq_{k+1}$.

Mairson stress the fact that this trick is essential, because writing $subset_{k+1}$ twice would cause exponential blowup in term size.
I'm asking why! That would not just double the term size?

Ok, I think I've got it.

$eq_{k+1}$ calls (indirectly) $eq_k$, so, if I call $subset_{k+1}$ twice, I fall in an exponential blowup because of the two recursive calls of $eq_k$: it is simple to see with a "linear recurrence relation of constant order".


Is this generalization of context free grammars known and strict? Let $\Sigma$ be an finite alphabet and $(N, \circ)$ a semigroup. The semigroup operation on $N$ can be extended to $\mathscr{P}(N)$: $N_1 \circ N_2 := \{ \; n_1 \circ n_2 \; | \; n_1 \in N_1, \; n_2 \in N_2 \; \}$ for $N_1, N_2 \subseteq N$.

Want to define:

A finite set $\mathcal{S} := \{ S_1, S_2, ..., S_k \}$ with $S_i \subseteq N$ is called a finite system of $N$. For $w \in \{1, .., k\}^+$ we have the homomorphism $\mathcal{S}(w) := S_{w_1} \; \circ \; ... \; \circ \; S_{w_{|w|}}$.
A set $M \subseteq \mathscr{P}(N)$ has a finite generating set, iff there is a finite system $\mathcal{S}$ of $N$ so that $\forall m \in M: \exists w_1, ..., w_j \in \{1,...,|S|\}^+: m = \mathcal{S}(w_1) \; \cup \; ... \; \cup \; \mathcal{S}(w_j)$

An equivalent definition is:

Consider the semiring $R := (\mathscr{P}(N), \cup, \circ)$.
A set $M \subseteq R$ has a finite generating set if there is a finite set $S \subseteq R$ so that every subsemiring of $R$ that contains $S$ also contains $M$.

Applied to formal languages:

Let $w^{-1}L := \{ \; v \; | \; wv \in L \; \}$ for a language $L \subseteq \Sigma^*$ and $w \in \Sigma^*$.
A language $L \subseteq \Sigma^*$ has a finite generating set, iff
$M_L := \{ \; w^{-1}L \; | \; w \in \Sigma^* \; \}$ has a finite generating set.

Clearly, all context free languages have a finite generating set. There are also languages that don't have a finite generating set, e.g. $L_1 := \{ \; w\#v \; | \; v, w \in \Sigma^*, \; v \not\in w^* \; \} $. This can be shown easily by using that $M_1 := \{ \; \mathbb{N}_0 \setminus k \mathbb{N} \; | \; k \in \mathbb{N} \; \}$ does not have a finite generating set.

For $\Sigma = \{ a, b \}$ and $L \subseteq \Sigma^*$ we have the identity: $w^{-1}L = \{ a \} \circ (wa)^{-1}L \; \cup \; \{ b \} \circ (wb)^{-1}L$.

As a fun fact: if we limit $j$ from the definition above to $1$ and consider infinite sets $M \subseteq \mathscr{P}(\Sigma^*)$ with $\forall m \in M: \varepsilon \in m$ that have a finite generating set, we can always find $m_1, m_2 \in M, \; m_1 \neq m_2$ so that $m_1 \subseteq m_2$. This is because the subsequence ordering on $\{ 1,...,|\mathcal{S}| \}^*$ is a well quasi ordering.

Does anybody know

whether this generalization of context free languages has been explored?
an example of a language that is not context free but has a finite generating set?
better terminology?

It seems obvious that languages with finite generating sets are more powerful than context free grammars (the elements of a finite system don't even have to be decidable), but I wasn't able to construct a counter example.

However, if $M_L$ itself is finite, $L$ is even regular and the sets of $M_L$ are decidable!

I have posted this question on math.stackexchange without any response.

I think the answer to your question can be found in Theorem 3.1 of [1], where it is credited to Wechler [2]. An algebra is stable if it is closed under left quotient.

  A language is context-free iff it belongs to a finitely generated
  stable algebra.

[1] Berstel, J.; Boasson, L. Towards an algebraic theory of context-free languages. Fund. Inform. 25 (1996), no. 3-4, 217--239.

[2] Wechler, Wolfgang. Characterization of rational and algebraic power series. RAIRO Inform. Théor. 17 (1983), no. 1, 3-11.


Maximum cardinality subgraphs meeting a Jaccard overlap threshold Consider two undirected connected graphs $G_0$ and $G_1$. The graphs are subgraphs of a given connected graph $G$ and share at least one node.

I want to find two subgraphs $G_0'\subseteq G_0$ and $G_1'\subseteq G_1$ such that they are connected, and the Jaccard index of their node sets is greater than a threshold $\alpha$ (fixed, between 0 and 1), that is $J=\frac{\left\vert V_0' \cap V_1'\right\vert }{\left\vert V_0' \cup V_1'\right\vert} \geq \alpha$ and these subgraphs are such that the sum $\left\vert V_0'\right\vert+ \left\vert V_1'\right\vert$ is maximized.

Starting from $G_0' = G_0,G_1' = G_1$, for the purpose of increasing $J$, while keeping connectedness of both graphs, I know I can unilaterally decrease the denominator of J by progressively removing as many nodes as possible that are in the nodes set difference $S=(V_0 \cup V_1) \setminus (V_0 \cap V_1)$, and are leaves of a spanning tree of $G_0'$ or $G_1'$. However it might be the case that no such leaf exists, yet I can obtain a higher overlap cutting bigger parts of possibly both graphs and renouncing to part of the intersection, yet having a lower $\left\vert V_0'+V_1'\right\vert$.

An example with an optimal solution (the intersection of the two subgraphs is highlighted in gray):

Can you think of an efficient algorithm that explores the subsets with some guarantee, maybe exploiting the upper bound $J \leq \frac{\min(\left\vert V_0'\right\vert,\left\vert V_1'\right\vert)}{\max(\left\vert V_0'\right\vert,\left\vert V_1'\right\vert)}$. Is this problem tractable?

The problem is NP-hard if $\alpha$ is part of the input. We can reduce the Steiner tree problem to this. Given a graph $G$ and terminal vertices $T$, consider $G_0$ to be a complete graph on $T$, and $G_1=G$.

Let $|T|=k$ and the size of the minimum Steiner tree of $T$ in $G$ be $h$.

If $\alpha=k/h$, we claim that $V_0'=T$. Assume not, then $|V_0'|<k$.
$|V_0'|+|V_1'|\geq k+h$, so $|V_1'|> h$. But then $|V_0'|/|V_1'|<\alpha$. A contradiction. Also, $|V_1'|=h$, as anything larger violates $|V_0'|/|V_1'|\geq \alpha$. $V_1'$ also gives us the vertices of a minimum Steiner tree on $T$. We can obtain $h$ by guess every possible $h$, there are only $n$ possibilities. Hence we reduce Steiner tree problem to your problem.


Parametrized Algorithm for Finding Bicliques Given an $n$ vertex undirected graph, what is the best known runtime bound for finding a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the
$\binom{n}{k}\mbox{poly}(n)$ time algorithm of "guessing" one side of the biclique and see if there are at least $k$ other vertices incident to all of them?

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

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

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

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

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


Is the complexity of this covering problem known? Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex set $S\subseteq V$ of minimum size such that $S\cap X\neq\emptyset$ for every critical set $X$.

The problem has the following rumour-spreading interpretation: Vertex $i$ spreads the rumour to its neighbour $j$ if and only if all other neighbours of $i$ are already informed. The question is then how many vertices do I have to inform initially to make sure that everybody is informed in the end.

The problem is known as the propagation problem. Aazami has proved in his PhD thesis that the weighted version is NP-complete even when the graph is planar and the node weights are in $\{0,1\}$. The complexity for the unweighted version seems to be an open problem.


Lower bounds on alternative models of multiparty communication complexity I'm a newcomer to communication complexity, and so far I've read the chapter in Arora-Barak and some papers giving lower bounds in various applications.

A priori the definition of multiparty communication complexity is strange. Forgetting the fruitful applications of the "number on the forehead" model, I would imagine people first thought to have each player see only their own input and not all but their own inputs. The computation of the protocol would happen in parallel, and communication could be player-to-player or broadcast.

I have reason to believe that lower bounds in such a model will aid me in proving lower bounds in a problem I'm currently looking at. Does this model have a name? What is known about it?

The "number in hand" model is the one I was thinking of, and there is quite a bit of literature about it. In particular I found this paper of Jeff Phillips, Elad Verbin, and Qin Zhang from SODA 2012 [1]. In particular they prove lower bounds on the problem I was interested in using, the undirected graph connectivity problem, of $\Omega(nk / \log^2(k))$. Here $k$ is the number of edges provided to each player and $n$ is the number of vertices in the graph.

[1] http://arxiv.org/abs/1107.2559


Head variables of terms after application We work in the Church-style simply typed lambda calculus. All terms shall be considered in long normal form. Any term of type $A_1\rightarrow A_2\ldots\rightarrow A_n \rightarrow 0$ is of the form $\lambda y_1 y_2 \ldots y_n . y_i u_1 u_2 \ldots u_m$. In this case, we shall say that $i$ is the index of this term.

My question is, does every term of a type with multiple components (that is, $n$ is greater than $1$ in the example above) behave as a function with respect to indices? Namely, given two terms of the same index of type $A_1$ above, would both return terms of type $A_2\ldots\rightarrow A_n \rightarrow 0$ with the same index?

Here's a counterexample to your conjecture.

$$
\begin{array}{lcl}
M & : & ((0 \to 0 \to 0) \to 0 \to 0 \to 0) \to 0 \to 0 \to 0 \\
M & = & \lambda\,f\,x\,y.\;f\;(\lambda\,a\,b.\;f\;(\lambda\,u\,v.\;u)\;a\;b)\;x\;y
\end{array}$$

This beta-normal, eta-long with index 1. Now, consider the two following terms, both also of index 1:

$$
\begin{array}{lcl}
N & = & \lambda\,p\,x\,y.\;p\;x\;y \\
N' & = & \lambda\,p\,x\,y.\;p\;y\;x \\
\end{array}
$$

Now, $M\;N$ reduces to $\lambda\,x\,y.\;x$ (index 1) and $M\;N'$ reduces to $\lambda\,x\,y.\;y$ (index 2).


To what extent is "advanced mathematics" needed/useful in A.I. research? I am currently studying mathematics. However, I don't think I want to become a professional mathematician in the future. I am thinking of applying my knowledge of mathematics to do research in artificial intelligence. However, I am not sure how many mathematics courses I should follow. (And which CS theory courses I should follow.)

From Quora, I learned that the subjects Linear Algebra, Statistics and Convex Optimization are most relevant for Machine Learning (see this question). Someone else mentioned that learning Linear Algebra, Probability/Statistics, Calculus, Basic Algorithms and Logic are needed to study artificial intelligence (see  this  question).

I can learn about all of these subjects during my first 1.5 years of the mathematics Bachelor at our university.

I was wondering, though, if there are some upper-undergraduate of even graduate-level mathematics subjects that are useful or even needed to study artificial intelligence. What about ODEs, PDEs, Topology, Measure Theory, Linear Analysis, Fourier Analysis and Analysis on Manifolds?

One book that suggests that some quite advanced mathematics is useful in the study of artificial intelligence is Pattern Theory: The Stochastic Analysis of Real-World signals by David Mumford and Agnes Desolneux (see this page). It includes chapters on Markov Chains, Piecewise Gaussian Models, Gibbs Fields, Manifolds, Lie Groups and Lie Algebras and their applications to pattern theory. To what extend is this book useful in A.I. research?

I do not want to sound condescending, but the math you are studying at the undergraduate and even graduate level courses is not advanced. It is the basics. The title of your question should be: Is "basic" math needed/useful in AI research? So, gobble up as much as you can, I have never met a computer scientist who complained about knowing too much math, although I met many who complained about not knowing enough of it. I remember helping a fellow graduate student in AI understand a page-rank-style algorithm. It was just some fairly easy linear algebra to me, but he suffered because he had no feeling for what eigenvalues and eigenvectors were about. Imagine the things AI people could do if they actually knew a lot of math!

I teach at a math department and I regularly get requests from my CS colleagues to recommend math majors for CS PhD's becase they prefer math students. You see, math is really, really hard to learn on your own, but most aspects of computer science are not. I know, I was a math major who got into a CS graduate school. Sure, I was "behind" on operating systems knowledge (despite having decent knowledge of Unix and VMS), but I was way, way ahead on "theory". It is not a symmetric situation.


Complexity of minimising polynomial formula size Let $f(x_1,\dots,x_n)$ be a degree $d$ polynomial in $n$ variables over $\mathbb{F}_2$, where $d$ is constant (say 2 or 3). I would like to find the smallest formula for $f$, where "formula" and "formula size" are defined in the obvious way (eg. the smallest formula for the polynomial $x_1 x_2 + x_1 x_3$ is $x_1(x_2+x_3)$).

What is the complexity of this problem - is it NP-hard? Does the complexity depend on $d$?

[ More formally, a formula (aka "arithmetic formula") is a rooted binary tree, each of whose leaves is labelled with either an input variable or the constant 1. All the other vertices of the tree are labelled with $+$ or $\times$. The size of the formula is the number of leaves used. The formula computes a polynomial recursively: $+$ vertices compute the sum of their children over $\mathbb{F}_2$, $\times$ vertices compute the product. ]

You can reduce the co-NP-Complete TAUTOLOGY problem (given a Boolean formula, is it a tautology?) to the problem of minimizing formula size (since a formula is a tautology iff it's equivalent to TRUE). Moreover, TAUTOLOGY for 3DNFs (analogously to SAT for 3CNFs) is co-NP-Complete.


space-bounded TMs and oracles In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions).

Is such a construction useful? Does it yield any particularly absurd results?

I think one surprising fact is that in this model Savitch's theorem doesn't "obviously" relativize. That is, one can see that $PSPACE^P=EXPTIME$ and $NPSPACE^P=NEXPTIME$ in this model, and we don't currently know that $EXPTIME=NEXPTIME$ (and Savitch's theorem in this context does not seem to give it).  I'd be interested in whether this can be pushed to "provably" non-relativizing.

One can also observe that $NL^{NL}=NL^L=NP$ in this model.

However, I think that this model is at least worth thinking about, with respect to issues of relativization in the space hierarchy theorem.  Also, in some sense, I want $L^A$ to make poly-sized queries to $A$.


Is any chordal graph an incomparability graph? I was confused by Wikipedia's definitions of "chordal graph", "interval graph", "string graph", "comparability graph", "incomparability graph" and the complements of these.
Wikipedia says "The complement of any interval graph is a comparability graph". So is any chordal graph an incomparability graph?

Is there a book or survey that contains detailed description of these sorts of different perfect graphs?

I believe the answer to your question, and to most questions like this, is to be found on http://graphclasses.org/

There's also a book that has much of this (including an appendix at the back with some of the main subset relations between graph classes): Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.

The answer to your specific question is no. The graph shown in http://commons.wikimedia.org/wiki/File:SubdividedTriangle.png (a central triangle with three more triangle attached to its edges) is chordal, but its complement http://en.wikipedia.org/wiki/File:Forbidden_interval_subgraph.svg is not a comparability graph.


How and why does Recrypt function work? The general aproach presented by Craig Gentry in 2009 to create a fully-homomorphic encryption system is roughly the follow:

Create a scheme that can evaluate some functions (increasing the noise in the ciphertext)
Change you decryption function to be one of these functions that can be evaluated
Use a function Recrypt to somehow decript and encrypt again the ciphertext to eliminate the noise introduced by the homomorphic operations.

The idea seems wonderfull, but, I don't understand well how and why this Recrypt function work...

For example, in the section 4.3 of the paper Computing Arbitrary Functions of Encrypted Data, he explains it like that:

Imagine that we have a list of public keys $p_1, p_2, .. $ and a private key $s_1$, then, we encrypt $m$ using $p_1$ generating $c_1$.

Then, we encrypt each bit of $s_1$ using $p_2$ generating a vector of ciphertexts $\overline{s_1}$.

Then, Recrypt  encrypts each bit of $c_1$ using $p_2$ generating the array $\overline{c_1}$ and evaluate the decryption citcuit $D$ in $\overline{c_1}$, $\overline{s_1}$ and $p_2$.

It seems like recrypt tries to decrypt the $\overline{c_1}$ with a wrong key (since it was encrypted with $p_2$, I was expecting something like $s_2$...).

Could someone here just try to explain how this Recrypt works? I don't know what I'm missing...

If my question is unclear, please, let me know.

Thanks.

At a high-level (ignoring the messier details), recryption that boosts bounded-depth homomorphism to unbounded-depth homomorphism works as follows:

Suppose you have a public-key "somewhat-homomorphic" encryption scheme with procedures:

$(PK, SK) \leftarrow Gen(1^{secparam}; coins)$: generates encryption/decryption keys
$c \leftarrow Enc(PK, m; coins)$: encrypts message $m$ as ciphertext $c$ under key $PK$
$m \leftarrow Dec(SK, c)$: decrypts ciphertext $c$ using key $SK$ to message $m$
$c^* \leftarrow Eval(C, c_1, ..., c_k)$: given ciphertexts $c_1, ..., c_k$ and a circuit description $C$, computes $c^* = Enc(C(m_1, ..., m_k))$

where "somewhat-homomorphic" means $Eval$ can only correctly (and succinctly) compute ciphertexts $c^*$ when the circuit $C$ has bounded depth (in some well-defined sense).

Correctness just means that w.h.p. over honest $(PK, SK) \leftarrow Gen$, for all $C, \{m_i\}_i$, we have $C(m_1, ..., m_k) = Dec(SK, Eval(C, Enc(PK, m_1; coins_1), ..., Enc(PK, m_k; coins_k)))$.
I.e. that if you use the scheme 'honestly,' you get correct decryption of (possibly $Eval$'d) ciphertexts.

That said, the observation is that the $Dec$ procedure, when written as a circuit, is a bounded-depth computation. Therefore, we can run $Eval$ on $C = \langle Dec\rangle$ when given (say) $SK_1$ and $Enc(PK_1, m)$ with BOTH encrypted under $PK_2$

To use this, we augment the $Gen$ procedure to first honestly generate two key-pairs $(PK_1, SK_1), (PK_2, SK_2)$. Then, $Gen$ creates a "recryption" key $RK_{1\rightarrow 2} = Enc(PK_2, SK_1)$ -- that is, the encryption of the key $SK_1$ under $PK_2$.

The scheme begins with the keys above, messages $\{m_i\}$ and a circuit $C$, and first creates ciphertexts $c^{(1)}_i = Enc(PK_1, m_i)$.

In order to recrypt, (conceptually) we can then doubly-encrypt the $\{c^{(1)}_i\}$ under $PK_2$. That is, create $c^{(2)}_i = Enc(PK_2, c^{(1)}_i) = Enc(PK_2, Enc(PK_1, m_i))$.

Then, under key $PK_2$, we perform (for each $i$) $Eval(\langle Dec\rangle, RK_{1\rightarrow 2}, c^{(2)}_i)$ obtaining a ciphertext $c^*_i$. By the correctness of $Eval$ and $Dec$, we have $c^*_i = Enc(PK_2, C(first\_plaintext, second\_plaintext)) = Enc(PK_2, Dec(SK_1, c^{(1)}_i)) = Enc(PK_2, m_i)$.

The 'messier details' in fact show that these $\{c^*_i = Enc(PK_2, m_i)\}$ are "fresh" ciphertexts under $PK_2$, meaning we have the full "bounded-depth" of $Eval$ available to us. Therefore, if $Eval$ can support at least the depth of the $Dec$ circuit, plus one, then you are able to perform unbounded-depth homomorphic computation (by further assuming circular security, and posting both $RK_{1\rightarrow 2}$ and $RK_{2\rightarrow 1}$, then toggling between the two keys with each recryption). In other words, you compute one step of the computation of some given circuit $C$, then you recrypt, and repeat.

P.S. If you go through significantly more effort (involving program obfuscation techniques), you can also obtain FHE without the circular security assumption. See: http://eprint.iacr.org/2014/882


Monotone arithmetic circuits The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have exponential size lower-bounds for monotone Boolean circuits.

  What do we know about monotone arithmetic circuits?
  Do we have similar good lower-bounds for them?
  If not, what is the essential difference that doesn't allow us to get similar lower-bounds for monotone arithmetic circuits?

The question is inspired by comments on this question.

Lower bounds for monotone arithmetic circuits come easier because they forbid cancellations. On the other hand, we can prove exponential lower bounds for circuits computing boolean functions even if any monotone real-valued functions $g:R\times R\to R$ are allowed as gates (see e.g. Sect. 9.6 in the book).

Even though monotone arithmetic circuits are weaker than monotone boolean circuits (in the latter we have cancellations $a\land a=a$ and $a\lor (a\land b)=a$), these circuits are interesting because of their relation to dynamic programming (DP) algorithms. Most of such algorithms can be simulated by circuits over semirings $(+,\min)$ or $(+,\max)$. Gates then correspond to subproblems used by the algorithm. What Jerrum and Snir (in the paper by V Vinay) actually prove is that any DP algorithm for the Min Weight Perfect Matching (as well as for the TSP problem) must produce exponentially many subproblems. But the Perfect Mathching problem is not of "DP flawor" (it does not satisfy Bellman's Principle of Optimality). Linear programming (not DP) is much more suited for this problem.

So what about optimization problems that can be solved by reasonably small DP algorithms - can we prove lower bounds also for them? Very interesting in this respect is an old result of Kerr (Theorem 6.1 in his phd). It implies that the classical Floyd-Warshall DP algorithm for the All-Pairs Shortest Paths problem (APSP) is optimal: $\Omega(n^3)$ subproblems are necessary. Even more interesting is that Kerr's argument is very simple (much simpler than that Jerrum and Snir used): it just uses the distributivity axiom
$a+\min(b,c)=\min(a,b)+\min(a,c)$, and the possibility to "kill" min-gates by setting one of its arguments to $0$.This way he proves that $n^3$ plus-gates are necessary to multiply two $n\times n$ matrices over the semiring $(+,\min)$. In Sect. 5.9 of the book by Aho, Hopcroft and Ullman it is shown that this problem is equivalent to APSP problem.

A next question could be: what about the Single-Source Shortest Paths (SSSP) problem? Bellman-Ford DP algorithm for this (seemingly "simpler") problem also uses $O(n^3)$ gates. Is this optimal? So far, no separation between these two versions of the shortest path problem are known; see an interesting paper of Virginia and Ryan Williams along these lines. So, an $\Omega(n^3)$ lower bound in $(+,\min)$-circuits for SSSP would be a great result. Next question could be: what about lower bounds for Knapsack?  In this draft lower bounds for Knapsack are proved in weaker model of $(+,\max)$ circuits where the usage of $+$-gates is restricted; in Appendix Kerr's proof is reproduced.


Teaching high school TCS - existing programs I was offered to teach a novel TCS high school program, which requires constructing a curriculum. I would very much like to hear opinions and suggestions regarding this.

First, does anyone know of high schools where a TCS program has been taught successfully (or unsuccessfully)?

The idea is for a 3-year program (10th-12th grades, ages 16-18), about 8 weekly hours, for selected outstanding students, meaning that it can and should be demanding. Unlike the standard "computers" program, this program should not focus on programming, but rather on selected topics in CS, mostly in TCS. The topics we have in mind so far are, broadly:

Asymptotic analysis
Basic data structures and algorithms (lists, arrays)
Graph algorithms, also as a demonstration of greedy algorithms v.s. dynamic programming.
Other algorithms (e.g. probabilistic)
Computability - the concept of a TM, reduction, decidability.
Complexity - NP, P, perhaps PSPACE and NL. Completeness.
Automata theory

Basically, this covers the TCS part of the first two years of a B.Sc in CS. However, we must keep in mind that these students lack the mathematical foundation needed for most of this material. In particular, things like set theory, combinatorics, probability, and modular artihmetic are not taught in high school (unfortunately).

To sum up, and to give precise questions:

Does anyone know of a similar program anywhere?
Are there suggestions for concrete/general topics which you think can and should be taught in addition/instead of the topics above, while keeping the program interesting as well as important and directly relevant (e.g. group theory is important and interesting, but not relevant enough to justify the time it will take)
I would have been happy to introduce machine-learning in some form, as it is a really hot topic nowadays. Any ideas as to how machine learning can be presented without tools like measure-concentration theorems are welcome.

Many countries organize summer schools for their IOI teams
(consisting of high school students aged roughly 16 IIRC).
The one we have in Iran used to have the following courses:

programming,
data structure and algorithms,
combinatorics, and
graph theory.

I think ACM's Computer Science Teachers Association has
a K12 curriculum on its Curriculum Resources page
though it is probably way too light for talented teenagers.

I think programming must definitely be part of the curriculum.
Python should be a good first language to learn.

You might want to also cover some accessible topics with applications
(the joy of building something cool can have a big effect on their interest).
I think Andrew Ng's ML course on Coursera
should be accessible for talented students
(specially for those in countries like yours where
there is a more serious K12 math curriculum ).

A nonstandard topic that you might want to consider is combinational game theory,
it might be not very interesting with 16 years old (I don't have experience for it) but
it works quite well for a bit younger students in my experience.

I personally think the central and connecting theme should be around algorithms,
I think it would work better than automata theory as the central theme and
arguably the algorithmic perspective (not Turing machines, automata, etc.)
is the essence of computer science.


Longest path in a DAG that's not too long The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is maximized, subject to the constraint that the sum of the weights is less than or equal to some upper bound W. Hence the title of this post, that the longest path not be "too long".

I am aware that the general longest-path problem is NP-Hard, and that the standard longest-path problem on DAGs is easily solved in O(|V|+|E|) time using topological sort and edge-relaxation (i.e. DP) (or we can solve this as shortest path by negating edge-weights).

I've frustratingly searched for a while on the web and came up with nothing on this problem; one would think that so simple a variant would at least be mentioned somewhere (if even in the general case, not limited to DAGs; or perhaps phrased as a shortest path problem where the path shouldn't be "too short").

I thought perhaps simply modifying the edge-relaxation condition to include the upper-bound constraint would do the trick, but I realized this is flawed: a "heavier" path may look attractive at the moment, but may end up violating the constraint (and so we should've stuck with the previous, albeit "lighter" estimate). I've not been able to find some alternative way of modifying the DP method to make this go through.

Efficient solutions are appreciated, or, conversely, a proof that this problem is hard. Relevant sources or references would also be appreciated.

This is NP-hard by reduction from subset sum.    There is a vertex for each element of the

set and one more vertex.    The extra vertex has an outgoing edge to each other vertex

but no incoming edges, and otherwise there is an edge from x to y if and only if  x < y .

The weight of each edge is equal to that edge's terminal vertex.

However, one can topologically sort the vertices and then use dynamic programming

in a way that's similar to the dynamic programming algorithm for subset sum.


Does this bin packing problem have a name? My problem is related to the standard bin packing problem (where you have bins of capacity $1$, items of capacity $(0,1]$, and want to pack the items into as few bins as possible), but there are a couple of twists. First, you have a fixed number of bins, and want to fit as many items as possible into them. As far as I can see, this is not obviously equivalent (except for the decision versions of the problems). Or perhaps I’m missing something obvious?

Second, some items are not permitted in some bins. That is, for each item, there is a list of forbidden bins.

Does this problem have a name? Even a name for the version without the forbidden bins would be useful. (I’m sure the “as many items as possible” part must be a totally standard packing problem?)

What I’m ultimately looking for is a way of attacking the problem (an exponential, exact DP algorithm; an approximation algorithm; a good heuristic/B&B solution…), or some starting-point that could be adapted.

Your problem is the multiple knapsack problem.

Although I am not familiar with this problem, I believe you'll find some papers on your problem, since there are many papers on this problem (see for example a SODA 2009 paper)


Commutativity of addition in polymorphic lambda calculus In the article "Extensional models of polymorphism" by Breazu-Tannen and Coquand, natural numbers are presented using a Church-like encoding:

$polyint = \forall t . (t \to t) \to t \to t$

Addition for this encoding is introduced as:

$\mathsf{Add} = \lambda u,v : polyint . \Lambda t . \lambda f : t \to t . \lambda x : t . u t f (v t f x)$

Then they say that commutativity of addition cannot be proved, and they say that $\mathsf{Add} u v = \mathsf{Add} v u$ does not follow from polymorphic lambda calculus theory by a simple Church-Rosser argument. What's this Church-Rosser argument? Is it related to the Church-rosser property? How can I prove it?

EDIT: the exact statement is:

"However, the pure $\lambda^{\forall}$ is not sufficient for that, as it cannot even prove, for example, that the operation of addition is commutative:

$\mathsf{Add}\ u\  v = \mathsf{Add}\ v\ u$

with arbitrary $u, v : polyint$ is not provable in $\lambda^{\forall}$ (by a simple Church-Rosser argument)".

The fact that $\mathsf{Add}\ u\ v = \mathsf{Add}\ v\ u$ is not provable for arbitrary $u$ and $v$ does indeed follow from the Church-Rosser property.

Write $u =_\beta v$ if $u \mathrel{({}_\beta\!\!\leftarrow\cup\rightarrow_\beta)^\ast} v$, where $\rightarrow_\beta$ is $\beta$-reduction in System F and $(\cdot)^\ast$ is the reflexive-transitive closure operator (this is a possible definition of $\beta$-equality, which Breazu-Tannen and Coquand denote simply by $=$. Here I will use the $\beta$ subscript and keep the $=$ symbol for strict equality, i.e., $\alpha$-equivalence if you like).  It follows immediately from the definition that if two terms have a common reduct, i.e., $u\rightarrow_\beta^\ast w$ and $v\rightarrow_\beta^\ast w$, then $u=_\beta v$. The Church-Rosser theorem states that the converse also holds:
$$u=_\beta v \quad \textrm{implies}\quad \exists w.\ u\rightarrow^\ast w\textrm{ and }v\rightarrow^\ast w.$$
It follows that $\beta$-equivalent normal forms are necessarily identical:
$$u,v\textrm{ normal and }u=_\beta v\textrm{ implies }u=v.$$

Read contrapositively, the above says that different normal forms can never be $\beta$-equivalent. Now, suppose $\mathsf{Add}\ u\ v=_\beta\mathsf{Add}\ v\ u$ for arbitrary $u$, $v$. In particular, this holds when $u=x$ and $v=y$ are distinct variables of type $polyint$. But it is easy to show (just apply a couple of steps of $\rightarrow_\beta$) that $\mathsf{Add}\ x\ y=_\beta u'$ and $\mathsf{Add}\ y\ x=_\beta v'$ with $u'$ and $v'$ distinct normal forms. Contradiction.


3SUM Complexity—A special(?) Case In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of the integer 3-SUM conjecture is stated.
Conjecture 1 (3-SUM Conjecture) In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets
$A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$
integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$
Not being an expert I have the following question.
How is this restriction to the set of integers with absolute value $\leq n^3$ justified? Is this in some sense hardest and other cases can be solved if this case is solved?
Remark: I suppose a ground set of size $O(n^3)$ is dense in the sense that a lot of triple candidates cannot be ruled out, but I imagine there are more spread out sets which may have similar properties.
Edit 2: Changed the focus of the question.

The smaller this upper bound is, the easier the problem becomes. In particular, if the range is $m$, then the problem can be solved in $O(m \log m)$ time using FFT. It is impressive/interesting that the authors were able to show that the problem is still quadratically nasty for numbers that are "slightly" larger than quadratic.


Does a multilayer perceptron taught by simple backprop learn the shape of a character or the exact image of a character? (Feel free to suggest a better title) (same with tags, none of relevant tags exist yet, and I only have 101)

Let's say I have a perceptron with an optimal number of layers and optimal number of neurons, which I have taught to recognize an alphabet which was printed in a certain font, with the same settings and resolution. Now if I feed it a symbol from that set, but say, printed in another (but similar) font, or with the same font, but rotated 5 degrees, or shifted 2 pixels to the left, or scaled a 5 percent, and so on, will this system recognize this modified symbol, or at least have an easier time learning to recognize this symbol? (than a system without any prior learning)

Basically, what is the point of back-propagating neural networks? Is it
1) a way to recognize shapes, and effectively filter noise in images of those shapes, in form of different rotations, scales and other disortions
or
2) just a relatively simple and fast way to recognize a limited number of bitmaps of those shapes, and not being able to recognize the shape in another bitmap if that particular bitmap was never taught to the network.

I would be very surprised if a backpropagation-trained multilayer FFN spontaneously learned concepts of shape. It's not that the notion of "shape" isn't representable by a FFN (given enough layers, anything is). It may even be the case that the globally optimal configuration does capture something about shape. But there must be a strong local minimum about the exact-image replicator, meaning that typical backpropagation (i.e., gradient descent) algorithms will get stuch in such local minima. Unless you've specifically primed your FFN to learn shape, I would be very surprised if it did.


Why an infinite type hierarchy? Coq, Agda, and Idris have an infinite type hierarchy (Type 1 : Type 2 : Type 3 : ...). But why not do it instead like λC, the system in the lambda cube that's closest to the calculus of constructions, which has only two sorts, $*$ and $◽$, and these rules?

$$\frac {} {∅ ⊢ * : ◽}$$

$$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ t : T _ 2} {Γ ⊢ (λ \: x : T _ 1, \: t) : (Π \: x : T _ 1, \: T _ 2)}$$

$$\frac {Γ ⊢ T _ 1 : s _ 1 \qquad Γ, \: x : T _ 1 ⊢ T _ 2 : s _ 2} {Γ ⊢ (Π \: x : T _ 1, \: T _ 2) : s _ 2}$$

This seems simpler. Does this system have important limitations?

Actually, the approach of the CoC is more expressive -- it permits arbitrary impredicative quantification. For example, the type $\forall a.\; a \to a$ can be instantiated with itself to get $(\forall a.\; a \to a) \to (\forall a.\; a \to a)$, which is not possible with a universe hierarchy.

The reason it is not widely used is because impredicative quantification is incompatible with classical logic. If you have it, you cannot give a model of type theory where types are interpreted as sets in the naive way --- see John Reynolds's famous paper Polymorphism is Not Set-theoretic.

Since many people want to use type theory as a way to machine-check ordinary mathematical proofs, they are generally unenthusiastic about type-theoretic features which are incompatible with the usual foundations. In fact, Coq  originally supported impredicativity, but they have steadily abandoned it.


What is the proof that visibility graphs can be used to compute the shortest path? I am trying to understand what the proof is that constructing a visibility graph and searching on can give you the shortest path between two points, avoiding a set of convex polygons. I am trying justify that using the visibility graph algorithm on spherical polygons transformed with the Gnomonic Projection to a linear plane will result in the shortest path, using great circle distance, between two points on the sphere's circle. To do so, I need to understand what assumptions the visibility graph needs to be valid, so I can see if those are still true for this mapping.

On page 612 of Discrete and Computation Geometry, Mitchell states:

  It is easy to show that an locally optimal s-t path must on the
  visibility graph VG(P)

Referring to the fact that a shortest path between two points, navigating around polygonal obstacles, can be found by creating a visibility graph and then searching that visibility graph using an algorithm like A*.

He however, does not explicitly state how we know that this path is in the visibility graph.

The paper most people cite for the original Visibility Graph algorithm is "An Algorithm for Planning Collision-Free Paths
Among Polyhedral Obstacle" from 1979, stating:

  The shortest collision-free path from S to G on the plane is the
  shortest path in the VGRAPH from the node corresponding to S to that
  corresponding to G when the euclidean metric is used on the links. We
  will call this method for finding collision-free paths for a point by
  finding the shortest path in a visibility graph the VGRAPH algorithm.
  This method was used for navigating SHAKEY [8], an early robot
  vehicle, and is also described in some detail in Ignat'yev [5].

They however, again fail to say how they know this is true. The SHAKEY paper also does not mention any proof.

Now in Chapter 15 of Computational Geometry: Algorithms and Applications, titled "Visibility Graphs Finding the Shortest Route", they give this proof for why they shortest path should consist entirely of endpoints of the obstacles, implying that it will be in the visibility graph:

  Lemma 15.1 Any shortest path between pstart and pgoal among a set S of
  disjoint polygonal obstacles is a polygonal path whose inner vertices
  are vertices of S.

  Proof. Suppose for a contradiction that a shortest
  path τ is not polygonal. Since the obstacles are polygonal, this means
  there is a point p on τ that lies in the interior of the free space
  with the property that no line segment containing p is contained in τ.
  Since p is in the interior of the free space, there is a disc of
  positive radius centered at p that is completely contained in the free
  space. But then the part of τ inside the disc, which is not a straight
  line segment, can be shortened by replacing it with the segment
  connecting the point where it enters the disc to the point where it
  leaves the disc. This contradicts the optimality of τ, since any
  shortest path must be locally shortest, that is, any subpath
  connecting points q and r on the path must be the shortest path from q
  to r. Now consider a vertex v of τ. It cannot lie in the interior of
  the free space: then there would be a disc centered at p that is
  completely in the free space, and we could replace the subpath of τ
  inside the disc— which turns at v—by a straight line segment which is
  shorter. Similarly, v cannot lie in the relative interior of an
  obstacle edge: then there would be a disc centered at v such that half
  of the disc is contained in the free space, which again implies that
  we can replace the subpath inside the disc with a straight line
  segment. The only possibility left is that v is an obstacle vertex.

They however, don't give a citation for this proof. Is there a previous version of this proof, or is this the original?

Are there other ways to writing this proof?

I think the first proof was given in Der-Tsai's 1978 thesis on pages 111-113.

  With the above result it is immediate to realize that the shortest
  path problem with line segments as obstacles can be solved by first
  constructing the graph G=(V,E), called visibility graph, where V
  consists of the two distinguished points and the set of 2N endpoints
  of the given N line segments, E is the set of edges each of which
  connects two vertices i and j of V without intersecting any obstacle
  except possibly at the endpoints (i and j are visible according to Definition 4.2); and the weight
  associated with each edge (i,j) of E is the Euclidean distance between
  points i and j; and then applying a well known shortest path algorithm
  to G.

However this is only for with line segments as obstacles, not polygons as obstacles.


NP-Complete Hard-on-Average Problems This question considers a special class of problems in (NP,P-samplable). The question is:

Do there exists a problem $(L,\mu) \in \mbox{(NP,P-samplable)}$ such that:

$L$ is $\rm{NP}$-complete, and
$L$ is hard on instances sampled by $\mu$; That is, for any $\rm{BPP}$ algorithm $A$, any polynomial $p(\cdot)$, and any all sufficiently large $n$:
$\Pr_{x \leftarrow \mu(1^n)}[A(1^n,x) = \chi_L(x)] < 1/p(n)$. (Here, $\chi_L(\cdot)$ denotes the characteristic function of $L$.)

Your answer can be based on any reasonable assumption, like:

$\rm{P} \ne \rm{NP}$;
one-way functions (or permutations) exist;
factoring is hard;
etc.

Another question is based on the following quote from On Basing One-Way Functions on NP-Hardness:
More than two decades ago, Brassard ("Relativized Cryptography") observed that the inverting task associated with a one-way permutation cannot be NP-hard, unless NP = coNP.

Is my understanding correct: It is saying that, there does not exist polynomial-time-computable permutations whose inverting is worst-case NP-hard and hard-on-average (unless NP = coNP)?

If there exist some NP language L that's hard on the average on some distribution $\mu$, then by applying the standard reduction $f$ from L to 3SAT you get that 3SAT is hard on $f(\mu)$.

Your understanding is wrong. By saying that the inverting task  for a function f is NP hard, one means that there is a polynomial-time algorithm A such that A can solve 3SAT on every input given black-box access to an inverter I that inverts f on a non-negligible fraction of the inputs.


Subexponentially solvable hard graph problems In light of the recent result of Arora, Barak, and Steurer, Subexponential Algorithms for Unique Games and Related Problems, I'm interested in graph problems that have subexponential time algorithms but believed not to be polynomially solvable. A famous example is graph isomorphism which has subexponential algorithm of $2^{O(n^{1/2} \log n)}$ run-time. Another example is log-Clique problem which is solvable in quasi-polynomial time ($n^{O(\log n)}$).

  I'm looking for interesting examples and preferably a reference to surveys of subexponential hard graph problems (not necessarily $NP$-complete). Also, Are there any $NP$-complete graph problems with subexponential time algorithms?

Impagliazzo, Paturi and Zane showed that the Exponential Time Hypothesis implies that Clique, k-Colorability, and Vertex Cover need $2^{\Omega(n)}$ time.

Since every planar graph on $n$ vertices has treewidth $O(\sqrt{n})$, all problems which are solvable in $O^*(2^{O(k)})$ time for graphs of treewidth at most~$k$ (there are a LOT of such problems) have subexponential-time algorithms on planar graphs by computing a constant-factor approximation to the treewidth in polynomial-time (for example by computing the branchwidth with the ratcatcher algorithm) and then running the treewidth algorithm, resulting in runtimes of the form $O^*(2^{O(\sqrt{n})})$ for graphs on $n$ vertices. Examples are Planar Independent Set and Planar Dominating Set, which are NP-complete of course.


Lower bounds and class separation Consider the language $A=\{0^{k}1^{k}|k\geq0\}$ . On Sipser's book "Introduction to the Theory of Computation" an algorithm with running time $O(n\log n)$ is given, on single-tape TM. We also know that the set of languages that run in time $o(n\log n)$ is exactly the set of regular languages. Since $A$ is not a regular language, we can be sure that this is a strict lower bound, on a single-tape TM.

Therefore, if $f(x) = n\log n$ and $g(x) = o(f(x))$ , the existence of this language allows us to say that
$DTIME(g(x)) \subset DTIME(f(x))$ . Therefore:

By using the padding argument, couldn't we argue that for any time function $h(x) = \Omega(n\log n) $ the same result applies, i.e. that if $g(x) = o(h(x))$ then $DTIME(g(x)) \subset DTIME(h(x))$

I will try to answer the question more generally so does not depend on the specific problem. Let $L$ be a language in $DTime(O(t(n))-DTime(o(t(n))$. Can we use padding to get a language in  $DTime(O(s(n))-DTime(o(s(n))$ where $s(n) \in \Omega(t(n))$ is an arbitrary (time constructible) function?

The answer is no:

  the complexity class separations using padding translate downwards but not upwards, see Why do equalities between complexity classes translate upwards and not downwards?.


Is there a sense in which we can say error returned from a function is the reverse of context? This came up in a discussion about golang, but I think it applies more generally.

Context in which a function is executed (specially in when we have RPCs) and error returned from a function seem to be kind of special input and return values. Is that really the case? Are there any sense that they are related or say reverse or dual of each other?

A duality between exceptions and states was observed and worked out by Jean-Guillaume Dumas, Dominique Duval, Laurent Fousse, and Jean-Claude Reynaud.

TL;DR: Reader and exception monads are obviously dual.

In your setup, I think it works as follows. Let $S$ be the type of environments in which a program might run (you call them contexts, but I'd rather save that word for typing contexts), and let $E$ be a type of errors that a program may raise. The environments here are read-only.

A program which runs in environment of type $S$, takes input of type $A$, and outputs a result of type $B$ has type
$$S \times A \to B.$$
A program which may raise an error of type $E$, takes input of type $A$, and outputs a result of type $B$ has type
$$A \to E + B.$$
We clearly have a duality here. If we imagine that this is all hapenning in some category $\mathcal{C}$, then $X \times A \to B$ in $\mathcal{C}$ is the same thing as $B \to X + A$ in the dual category $\mathcal{C}^\mathrm{op}$.


What is empirical mutual information? The topic says it all - I've been seeing this referenced a few times in information theory literature (Feedback in the non-asymptotic regime, Y. Polyanskiy et. al. among others), oftentimes making mentions to an article by a guy called Goppa. I've not seen it defined in any of the referencing articles and the article is nowhere to be found online.

So, can anyone tell me what it is? A reasonable guess would be that it relates to information density, i.e. $i(x;y) = \log \frac{p(x,y)}{p(x)p(y)}$, but it's hard to say.

EDIT: There seems to be consensus as to what it SHOULD mean at least, i.e. basically the average information density, i.e. $\sum \log \frac{p(x_i,y_i)}{p(x_i)p(y_i)}$ where we're summing over observations. Not going to accept however as I am looking for a definite statement.

I agree with @usul. I've also never seen the term empirical mutual information mentioned, but I've seen the term empirical entropy quite a lot, especially in the compression community. The definition of empirical information is $-\Sigma p_i \log p_i$, where $p_i$ are the empirical probabilities, i.e. the fraction of the time that each value appears in your samples.

To compute empirical mutual information given samples $(x_1,y_1),\ldots,(x_n,y_n)$, I'd just compute the empirical entropy of the $x$'s separately, and of the $y$'s separately, and of the pairs together, and then I'd use the standard equation $I(X:Y)=H(X)+H(Y)-H(XY)$, where all quantities on the right hand side are replaced by their empirical analogue.

I don't know if this is equivalent to the equation that @usul gave, and I don't know if this is the quantity referenced in the articles you're reading, but this seems like the natural interpretation to me.


Is #PE (#P Easy) closed under decrement? Given a function $f : \Sigma^* \to \mathbb{N}$, define function $f_{-1}$ as: $f_{-1}(x) = f(x) - 1$ if $f(x) > 0$, and $f_{-1}(x) = 0$ otherwise. Moreover, say that a class ${\cal C}$ of functions is closed under decrement if for every $f \in {\cal C}$, it holds that $f_{-1} \in {\cal C}$.

Define $\#\text{PE}$ [2,3] as the class of functions in $\#\text{P}$ with easy decision versions, that is, the class of functions $f \in \#\text{P}$ for which there exists a polynomial-time deterministic TM $M$ such that $L(M) = \{ x \in \Sigma^* \mid f(x) > 0 \}$. It was shown in [1] that if $\#\text{P}$ is closed under decrement, then $\text{NP} \subseteq \text{SPP}$. But the ideas in the proof of this result cannot be used to provide evidence that  $\#\text{PE}$ is not closed under decrement. So I was wondering what is known about this problem. Is $\#\text{PE}$ closed under decrement? Can at least one prove that if $f \in \#\text{PE}$, then $f_{-1} \in \#\text{P}$? Any help with this would be greatly appreciate it.

[1] Mitsunori Ogiwara, Lane A. Hemachandra: A Complexity Theory for Feasible Closure Properties. J. Comput. Syst. Sci. 46(3): 295-325 (1993)

[2] Aris Pagourtzis. On the complexity of Hard Counting Problems with Easy Decision Version. In Proceedings of the 3rd Panhellenic Logic Symposium,  2001.

[3] Aris Pagourtzis, Stathis Zachos: The Complexity of Counting Functions with Easy Decision Version. MFCS 2006: 741-752

If $\text{#PE}$ is closed under decrement then $\text P=\text{NP}$: consider $\text{#SAT}+1$. Conversely if $\text P=\text{NP}$ then $\text{#PE}=\text{#P}$ is closed under decrement because we can always find an accepting path if one exists then ignore it.

I don't know whether $f\in\text{#PE}$ always implies $f_{-1}\in\text{#P}$. Your $M$ might not provide an accepting path for us to ignore.


The Optimum Strategy to Find the Best Parking Slot Along a Busy Road Imagine that you are going to a shop. In front of the shop there are $N$ number of parking slots. That shop is located at the $k^{th}$ slot.

As you drive along the parking slots, you notice that for $n$ parking slots, $n_{fill}$ of the slots are filled, whereas $n_{empty}$ slots are empty ( naturally, $n=n_{fill}+n_{empty}$ and $n<k$ ).

Base on this information, and the assumption that all slots are equal ( that is, one won't prefer this slot over that slot, or this block of slots over that block of slots), what is the optimum strategy to find the parking space that is the nearest to the shop?

Like some of the commenters, I'm not sure the problem as written is fully specified, especially with respect to inferring the probability of future spaces being empty.  However, even if you assume that all spaces are empty with known probability $p$, the problem is still interesting.  Much of the reasoning below still applies to the case where the probability is inferred, and the solution should become exact as the number of pre-parking observations goes to infinity.

Question. Assume that parking spaces $-k, -k+1, … -1, 0, 1, 2, 3, ...$ are filled independently with probability $1-p$.  You pass each space in turn and note whether it is filled or empty.  If a parking space is empty, you may choose to park there; but once you pass a space, you may not go back.  You want to park as close to space $0$ as possible.  What strategy minimizes the expected value of $|X|$, where $X$ is the space in which you park?

Answer. You should park in the first available space $x$ such that $x \ge \lceil\log(2) / \log(1-p)\rceil$.

Proof.
Let $Q(x)\equiv E\left[ |X| \big| X>x\right]$ be the expected penalty given that you have passed space $x$.  Clearly you will accept any parking space $x$ such that $x \ge 0$, since at that point each candidate is better than all future possible candidates.  So we can calculate $Q(x)$ for $x \ge -1$ as follows:

$$
\begin{eqnarray}
Q(x \ge -1) &\equiv& E\left[ |X| \big| X > x \ge -1 \right] \\
&=& E[\text{position of first empty space after } x] \\
&=& x + 1/p
\end{eqnarray}
$$

For spaces $x$ with $x < 0$, you will park (if possible) whenever $-x$ (the current penalty) is no greater than $Q(x)$ (the expected penalty if you keep driving); i.e., you will park when the function $D(x) \equiv Q(x)+x \ge 0$.  For $x<-1$, we have:

$$
\begin{eqnarray}
D(x) &\equiv& Q(x)+x \\
&=& p\min\left\{-(x+1), Q(x+1)\right\} + (1-p)Q(x+1) + x \\
&=& Q(x+1) - p \max\left\{0, Q(x+1) + x + 1\right\} + x \\
&=& -1 + Q(x+1) + x + 1 - p\max\left\{0, Q(x+1)+x+1\right\} \\
&=& -1 + D(x+1) - p\max\left\{0, D(x+1)\right\}.
\end{eqnarray}
$$

As long as $D(x+1) \ge 0$, we have $D(x) = -1 + (1-p)D(x+1)$.  This recurrence relation has the closed-form solution

$$
\begin{eqnarray}
D(-n) &=& -1 - (1-p) - (1-p)^2 - ... -(1-p)^{n-1} + (1-p)^n D(0) \\
      &=& (1-p)^n /p - \left(1 + (1-p) + ... + (1-p)^{n-1}\right) \\
      &=& (1-p)^n /p - \left(1 - (1-p)^n\right) / p \\
      &=& \left(2(1-p)^n - 1\right) / p,
\end{eqnarray}
$$
valid until $D(-n)$ becomes negative, after which $D(-n) = -1 + D(-(n-1))$, and so $D$ continues to become increasingly negative as you move to the left.  Moving to the right, then, the first parking space for which $D(x) \ge 0$ is at $x = \lceil\log(2) / \log(1-p)\rceil$.


Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length? Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$.
For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic exptime oracle machine $M_2$ with access $M_2^{L_2}$ such that (a) $M_2$ may only make poly(n) length queries to $L_2$ (b) $M_2^{L_2}$ accepts iff $M_1^{L_1}$ accepts? (Note $M_1$ is capable of making exp(n) length queries to $L_1$ as it is an exponential time TM).
If the above is not true for a particular $L_2$, is it possible to find an $M_2$ and an $L_2\in$NEXP such that the above is true?
Obviously, there is always a polytime reduction from $L_1$ to $L_2$ as $L_2$ is NEXP-hard and $NP\subseteq NEXP$. However if the queries to $L_1$ have $exp(n)$ length, then under the polytime reduction the corresponding $L_2$ instances will now also have $exp(n)$ length. Hence, if $M_2$ is restricted to only $poly(n)$ length queries it's not clear $M_2^{L_2}$ can always make the necessary queries.
It does not seem unreasonable that given an $(M_1, L_1)$ pair, that $M_2^{L_2}$ can simulate $M_1^{L_1}$ and return the same output. If we have an NP language with $exp(n)$ input, a non-deterministic TM of runtime $O(exp(n))$ is capable of solving it. A NEXP machine also has an $exp(n)$ runtime but on an input of length $poly(n)$ and so might be capable of solving the exponential length NP instance.
Edit: I suppose this boils down to the question, if $EXP_{poly}^A$ is an exponential time oracle machine which is only allowed to make polynomial length queries to $A$, does the following hold: $EXP_{poly}^{NEXP} = EXP^{NP}$? The containment $EXP_{poly}^{NEXP} \subseteq EXP^{NP}$ seems to be straightforward to prove.

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict subclass of $\mathrm{EXP^{NP}}$ (which is the exponential analogue of $\Delta^P_2$).
$\Theta^{\exp}_2$ can be variously defined as
$$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=EXP^{NP[poly]}=PSPACE^{NEXP}=P^{NEXP}=\exists\cdot DEXP},$$
where $\|$ denotes parallel (nonadaptive) access to the oracle, $\mathrm{[poly]}$ restricts the number of oracle queries to polynomial, the oracle tape is included in the space requirements of the $\mathrm{PSPACE}$ machine, and $\mathrm{DEXP}=\{L_0\smallsetminus L_1:L_0,L_1\in\mathrm{NEXP}\}$ is the exponential analogue of $\mathrm{DP}$.
For the $\mathrm{EXP_{poly}^{NEXP}}\subseteq\Theta^{\exp}_2$ inclusion, note that there are only exponentially many strings of polynomial length, hence the exponential-time machine may first ask all possible queries of that length in parallel, and then proceed with the computation, showing $\mathrm{EXP_{poly}^{NEXP}\subseteq EXP^{\|NP}}$.
For the $\Theta^{\exp}_2\subseteq\mathrm{EXP_{poly}^{NEXP}}$ inclusion, it is obvious that $\mathrm{P^{NEXP}\subseteq EXP_{poly}^{NEXP}}$.


Edge-partitioning cubic graphs into claws and paths Again an edge-partitioning problem whose complexity I'm curious about, motivated by a previous question of mine.

Input: a cubic graph $G=(V,E)$

Question: is there a partition of $E$ into $E_1, E_2, \ldots, E_s$, such that the subgraph induced by each $E_i$ is either a claw (i.e. $K_{1,3}$, often called a star) or a $3$-path (i.e. $P_4$)?

I think I saw a paper one day where this problem was proven to be NP-complete, but I cannot find it anymore, and I don't remember whether that result applied to cubic graphs. On a related matter, I'm aware that edge-partitioning a bipartite graph into claws is NP-complete (see Dyer and Frieze). Does anyone have a reference for the problem I describe, or something related (i.e. the same problem on another graph class, that I could then try to reduce to cubic graphs)?

This isn't an answer to the complexity of the problem, but it at least shows that the complexity has a chance at being nontrivial: it's an example of a cubic graph that cannot be partitioned into paths and claws.

(source: uci.edu)

Within each of its three lobes, any partition into paths and claws can only use six of the seven edges. The remaining six central edges take the form of a claw with each edge subdivided, which cannot be partitioned into paths and claws.

ETA: The graph shown above is more famous as an example of a cubic graph without a perfect matching. But every cubic graph with a perfect matching has a decomposition into paths (not even using any claws). By König's theorem this includes all cubic bipartite graphs and by Petersen's theorem this includes all bridgeless cubic graphs, answering a question of Joseph Malkevitch in the comments.

The proof is very simple: if M is a perfect matching in a cubic graph, the removal of M leaves a 2-regular graph, that is, a disjoint union of cycles. Orient each cycle arbitrarily, and attach each edge uv of M to the cycle edges that follow u and v in the orientations of their cycles.

In the other direction, if there exists a decomposition into paths, then there exists a perfect matching: the middle edges of each path must be a matching since no two middle edges can share a degree-three vertex.

(Disclaimer: this idea may have already been present in Carsten Thomassen's invited talk at GD 2010, which was about this sort of graph decomposition problem.)

(addition to disclaimer (by Anthony Labarre): the "orientation idea" for going from a perfect matching to a partition into paths appears in this paper by Jünger, Reinelt and Pulleyblank, who attribute it to W. H. Cunningham.)


Does a chordal graph where the size of minimal separators is constrained have name? An undirected graph $G$ is chordal if it has no induced cycles of length 4 or more. A set $S \subseteq V(G)$ disconnects a vertex $a$ from vertex $b$ if every path of $G$ between $a$ and $b$ contains a vertex from $S$. A non-empty set $S \subseteq V(G)$ is a minimal separator of $G$ if there exists $a$ and $b$ such that (i) $S$ disconnects $a$ from $b$ in $G$, and (ii) no proper subset of $S$ disconnects $a$ from $b$ in $G$.

A $k$-tree is a chordal graph where all maximal cliques are of size $k+1$ and all minimal separators of size $k$. A block graph is a chordal graph, where maximal cliques can be of any size, but the minimal separators are of size one. What about chordal graphs where the maximal cliques can be of any size, but there's a constraint on the size of the minimal separators? This feels like a rather natural variant, but I was unable to find a reference that captures this.

  Let $k$ be a positive integer. Consider a chordal graph such that the size of every minimal separator $|S| = k$. (Alternatively, replace $=$ with $\leq$). Have such graphs been studied before somewhere?

For $k=1$, such a graph is known as a block graph. What about $k \geq 2$?

In this paper graphs in which the size of every minimal separator $|S| \le k$ are called graphs of separability at most $k$.

Theorem 1 of that paper implies that chordal graphs of separability at most $2$ are obtained from complete graphs by "gluing" along a vertex or an edge.


Hardness of LWE on not-uniform vector samples The "usual decisional LWE":
The challenger and the adversary get a common random matrix $A \in F_{q}^{m \times n}$. The challenger chooses a secret $s \in F_{q}^{n}$ and generates random (small) secret noise vector $\chi \in F_{q}^{m}$, and the claim is that the adversary can't distinguish efficiently between $(A, As + \chi)$ and $(A, U_{m})$ (where $U$ is the uniform distribution over $F_{q}$).

My question:
Assume that the challenger and adversary do not get $A$ at random, but rather create $A$ via some deterministic reduction from some common input $x$. All the rest is the same, i.e., the challenger chooses the secret  $s \in F_{q}^{n}$ and generates random (small) noise vector $\chi \in F_{q}^{m}$ and then sends to the adversary either $As + \chi$, or a true random vector. What conditions does $A$ have to fulfill to ensure that the challenger can't distinguish between  $(A, As + \chi)$ and   $(A, U_{m})$?

I'm currently more interested in the case of $q=2$, i.e., the LPN problem, but even a conclusion on the non-binary scenario may be useful.

I realize this question might be tricky and without an answer, so my hope is to at least get references to articles that either tried to tackle this issue directly or at the very least articles that will be a good entry point for me in the case I'll have to try and solve it myself.

Since you are specifically interested in $q=2$, I will focus on this case in my answer. A note on your choice of tags: you tagged your question with "lattice" and "lattice-theory"; however, your question seems much more closely related to questions in coding theory. I elaborate below.

A good starting point is to observe that LPN with matrix $A$ reduces to the hardness of decoding a linear code generated by the parity-check matrix $B$ of $A$ - or rather, in the decisional case, to distinguishing a codeword from random.

proof: for any secret vector $s$, $B\cdot\chi = B\cdot(As + \chi) \approx_{\mathsf{LPN}} B\cdot U_m = U_{m-n}.$

Hence, one can reword your question as follows: for which choice of code matrix is the corresponding decoding problem hard? Coding theory gives essentially the following informal answer: it is hard for most choices of codes. Specifically, there are only few linear codes for which we do know of an efficient decoding algorithms - hardness of decoding seems to be the rule rather than the exception.

Some examples of bad choices of $A$: if $A$ is an LDPC code, then its parity-check matrix $B$ is sparse, and distinguishing $B\cdot\chi$ from random is easy (given that $\chi$ is a distribution over sparse vectors). Reed-Solomon codes can also be decoded efficiently when the noisy codeword has sufficiently low noise rate, hence should be used with care (but if there is enough noise, they should still work).

In general, we do not have any generic reduction stating "if $A$ has the following structure, then the LPN problem with respect to the matrix $A$ is as hard as the standard LPN problem." However, we do have good conjectures regarding what properties of $A$ make the corresponding LPN problem hard. Two of the main such properties is for the code to have a good minimal distance - ideally, meeting the Gilbert-Varshamov bound (which is achieved with good probability by a linear code generated by a uniformly random matrix, corresponding to the standard LPN assumption), and to satisfy the uniform output property (see the next two references). This was investigated in this paper, where new candidate efficient linear codes (with linear-time encoding) were suggested as plausible candidates for giving an intractable variant of LPN (see also the master thesis of the first author, specifically the chapter 5).

While LPN with a random parity-check matrix $B$ is the most well-studied form of the assumption, a bunch of specific alternative choices of code matrix have been used in the cryptography literature. These includes LDPC codes, which are at the core of the famous cryptosystem of Alekhnovich (note that if the code matrix $A$ is an LDPC code, the LPN variant is insecure; however, when its parity-check matrix $B$ is an LDPC code, meaning that $A$ is a sparse matrix, then it leads to a plausible assumption), MDPC codes, used to construct variants of the McEliece cryptosystem, quasi-cyclic codes, codes generated by Toeplitz matrices, and others. An overview of candidates which have been used in the literature is given, with pointers, in one of my recent papers.


Complexity of graph isomorphism with properly colored edges (ref. request) An edge-colored graph $G$ is a graph whose edges are labeled with a color (generally represented by an integer). Such a coloring is proper if all adjacent edges in $G$ have different colors. I recently realized that isomorphism between two such graphs can be tested in polynomial time. The arguments are pretty simple and the question natural, so this fact should already be mentioned somewhere. However, I could not find it so far.

The arguments: Fix an arbitrary vertex $v_1$ in $G_1$. We will try to send it to every vertex $v_2$ of $G_2$ successively, until either a valid bijection is found (accept) or all the vertices of $G_2$ have been tried (reject). The key point is that once the selection of $v_2$ is made, no other choice remains to be done, because local constraints imposed by the colors recursively determine the remaining of the bijection. For instance, if $v_1$ shares an edge colored $c$ with vertex $u_1$, then this vertex must be sent to a vertex that shares an edge colored $c$ with $v_2$. This vertex (if any qualifies) must be unique due to the fact that the coloring is proper.

Has anyone seen such an observation somewhere or has an idea where to find it?

In general, if the number of adjacent edges, which have the same color, is bounded by a constant, say d. Then, the isomorphism problem for n-vertex graphs can be solved in n^(cd) for some constant c. In your case, d=1. See for example, Proposition 4.5 in CANONICAL LABELING OF GRAPHS by Babai and Luks. Actually, they considered vertex coloring, but the same arguments works for edge colors as well. For example, you could subdivide each edge and instert a new vertex that encodes the edge color.


Typical hardness of tree decomposition? Tree decomposition is hard in the worst case but greedy method seems to be near-optimal on small real-life networks.

Is anything known about hardness of tree decomposition of a "typical" instance of some class of graphs?
Is there example of a family of graphs where greedy methods for tree decomposition do badly?

I just came across a relevant paper -- Kloks/Boedlander's "Only few graphs have bounded tree width". They show that almost all graphs with $n$ vertices and $\delta n$ edges have treewidth on the order of $n^\epsilon$, $\epsilon=\frac{\delta-1}{\delta+1}$. For instance $\delta=3$ means typical tree-width grows as $\sqrt{n}$

So even if greedy method found the best decomposition for all graphs, the resulting algorithm would still be intractably slow for typical graphs


Universe polymorphism: the inference of universes and their constraints When making a universe polymorphic definition in Coq, universes and their constraints are automatically inferred. Are they somewhat the most general ones (in a sense similar to the principal type property in ML)? Or are they just the result of arbitrary heuristics? Or something in between?

It's complicated because universe constraints are simplified during inference (in order to avoid an explosion of constraints). Have a look at:

Matthieu Sozeau and Nicolas Tabareau: Universe Polymorphism in Coq, Interactive Theorem Proving - 5th International Conference, ITP 2014
Beta Ziliani & Matthieu Sozeau: A Unification Algorithm for Coq featuring Universe Polymorphism and Overloading, ACM SIGPLAN International Conference on Functional Programming 2015.


Explaining monad transformers in categorical terms Most resource regarding categorical notions in programming describe monads, but I've never seen a categorical description of monad transformers.

How could monad transformers be described in the terms of category theory?

In particular, I'd be interested in:

the relationship between monad transformers and their corresponding base monads;
the relationship between them and the monads they're transforming into new monads;
monad transformer stacks.

According to Oleksandr Manzuk, they are "translation of a monad along an adjunction", see "Calculating Monad Transformers with Category Theory". By the way, that's the third hit on Google for "monad transformer categorically". The first is a Stackoverflow question about this and the second is your question.


Languages recognized by polynomial-size DFAs For a fixed finite alphabet $\Sigma$, a formal language $L$ over $\Sigma$ is regular if there exists a deterministic finite automaton (DFA) over $\Sigma$ which accepts exactly $L$.

I am interested in languages that are "almost" regular in the sense that they can be recognized by automata families of size that grows only polynomially with the word length.

Formally, let me say that a formal language $L$ is recognized by a DFA family $(A_n)$ if for every word $w \in \Sigma^*$, letting $n = |w|$, $w$ is in $L$ iff $A_n$ accepts $w$ (no matter if the other $A_i$ accept it or not), and let me define p-regular languages as languages recognized by a PTIME-computable DFA family $(A_n)$ of polynomial size, namely, there is a polynomial $P$ such that $|A_n| \leq P(n)$ for all $n$. (This name, "p-regular", is something I made up, my question is to know if another name already exists for this. Note that this is not the same as p-regular languages in the sense of permutation automata.)

This class of p-regular languages includes of course regular languages (just take $A_n = A$ for all $n$, where $A$ is some DFA recognizing the regular language); but it is a strict superset of it: for instance, it is well-known that $\{a^n b^n \mid n \in \mathbb{N}\}$ is context-free but not regular, but it is p-regular ($A_n$ just has to count $n$ occurrences of $a$ and $n$ occurrences of $b$). However, because I require the automata to be polynomial-sized DFAs, some formal languages (actually some context-free languages) are not p-regular: for instance, the language of palindromes is not p-regular, because, intuitively, when you have read the first half of a word, you need to have as many different states as there are possible words, because you will need to match exactly this first half with the second.

So the class of p-regular languages is a strict superset of regular languages that is incomparable with context-free languages. In fact, it seems that you can even get a hierarchy of languages by distinguishing p-regular languages based on the smallest degree of the polynomial $P$ for which they are $P$-regular. It is not too hard to construct examples to show that this hierarchy is strict; though I do not understand well yet the interaction between this, and an alternative definition of the hierarchy which would also restrict the complexity of computing the $A_n$.

My question is: has this class that I call p-regular, and the associated hierarchy, been studied before? If yes, where and under which name?

(A possible link is with the field or streaming, or online algorithms. In the terminology of Streaming algorithms for language recognition problems, I am interested in the class (or hierarchy) of languages that can have a deterministic, one-pass recognition algorithms, using a polynomial number of states (so a logarithmic memory size), but I found no definition of this class in this paper or related papers. Note, however, that in my phrasing of the problem the length of the word is known in advance, which is less natural in a streaming context: in streaming you could see this as an infinite automaton, a special "end-of-word" symbol, and a constraint that the number of reachable states after reading $n$ characters is polynomial in $n$. I think that this distinction makes a difference, possible example: language of binary words whose value is divisible by their length, which is easy for a fixed length but (I conjecture) cannot be represented by an infinite automaton in the previous sense because no identifications can be made if the length is not known in advance.)

(The motivation for this p-regular class is that some problems, such as the probability of language membership for probabilistic words, seem to be PTIME not only when the language is regular, but also when it is p-regular, and I am trying to characterize exactly in which circumstances those problems are tractable.)

the question does not seem to have been studied much (one possibility is attempting to find a relationship with a "nearby" complexity class say P/poly etc); although here is at least one ref that touches on it:

Language operations with regular expressions of polynomial size Gruber/Holzer

  This work deals with questions regarding to what extent regularity-preserving language operations affect the descriptional complexity of regular expressions. Some language operations are identified which are feasible for regular expressions in the sense that the result of the operation can be represented as a regular expression of size polynomial in that of the operands. We prove that taking language quotients, in particular the prefix and suffix closures, of a regular set can incur at most a quadratic blow-up on the required expression size. The circular shift operation can cause only a cubic increase in size and at least a quadratic bloat can be necessary in the worst case.

as AS suggests there may be other more natural ways to study something like the question posed. here is another somewhat similar way to study growth of a regular language based on number of words of size $n$ which does have some loose relation to the question eg

Finding the growth rate of a regular or context-free language in polynomial time
(Gawrychowski, Krieger, Rampersad, Shallit)

  Given a context-free language L, we can test whether it is of polynomial or exponential growth in polynomial time. Moreover, if it is of polynomial growth we can also find the exact order of this polynomial in polynomial time.