Show that minimal CFG is undecidable via mapping reduction Actually the problem below is an exercise in Sipser's textbook (Problem 5.36). However, from my perspective, it is not so trivial so that I post this question on this site instead of CS.SE.
The question itself was asked on Math.SE:

Say that a CFG (context-free grammar) is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{\textsf{CFG}}$ = $\{\, \langle G \rangle \ | \ G$ is a minimal CFG$\}$.
a) Show that $MIN_{\textsf{CFG}}$ is Turing-recognizable.
b) Show that $MIN_{\textsf{CFG}}$ is undecidable.

The OP figured out a), the relatively simple part, by himself. And I answered b) few days ago, by reducing to $ALL_{\textsf{minCFG}}$:

It suffices to focus on the case $\Sigma = \{0,1\}$. We argue that $ALL_{\textsf{minCFG}} \leq_T MIN_{\textsf{CFG}}$. That is, we can determine whether a minimal CFG can generate all possible strings, by using the oracle for $MIN_{\textsf{CFG}}$.
Let $G$ denote the minimal CFG we are interested. Since $G$ is minimal, there exists a length $p$ such that, for each rule $R$ in $G$ there exists a string $w_R$ with $|w_R|<p$ that can be generated by $G$, but not with $R$ deleted.
Note here that $p$ is computable in a brute force manner.
Construct $G^+_{a_1a_2\cdots a_p}$ where $a_i \in \Sigma$, by adding following rules in $G$:
$$
S \to a_1 a_2 \cdots a_pT \\
T \to T0 \ | \ T1 \ | \ \epsilon
$$
First, consider what will happen if $G^+_{a_1a_2\cdots a_p}$ is not minimal, thus, there exists a rule $R$ in $G^+$ being dispensable. By our construction it is clear that each rule $R$ in $G$ is indispensable.

If $S \to a_1 a_2 \cdots a_pT$ or $T \to \epsilon$ is dispensable, then we have $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$.
If $T \to T0$ is dispensable, then we have $(a_1 a_2 \cdots a_p \Sigma^* - a_1 a_2 \cdots a_p 1^*) \subseteq L(G)$. Because whether $a_1 a_2 \cdots a_p1^* \subseteq L(G)$ is easy to determine by some classical algorithm, we can also determine whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$.
It is similar for $T \to T1$.

Therefore, if $G^+_{a_1a_2\cdots a_p}$ is not minimal, we can determine whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$. What if it is minimal? In this case we will immediately know $L(G) \neq \Sigma^*$. So we can suppose that all possible $G^+_{a_1a_2\cdots a_p}$ is not minimal. Then by checking whether $a_1 a_2 \cdots a_p \Sigma^* \subseteq L(G)$ one by one and checking those strings of less-than-$p$ length, we can still decide whether $L(G) = \Sigma^*$.
Update. (Oct 12, 2020) After a short discussion with @xdavidliu I realized that the argument above can directly prove what we want, without a justification of uncomputability of $ALL_{\textsf{minCFG}}$. Recall that the reduction we have established achieves the following: Given a minimal CFG $G$, determine whether $L(G) = \Sigma^*$. Now if we want to decide whether $L(G_0) = \Sigma^*$ for an arbitrary CFG $G_0$, just simply feed into the (reduction) algorithm all minimal sub-CFG (test each sub-CFG by the $MIN_{\mathsf{CFG}}$ oracle to determine whether it is minimal) of $G_0$ and see if there is one that generates all strings.

However, there are still two questions:

Can we find a simple proof for undecidability of $ALL_{\textsf{minCFG}}$?

Since this problem appears in Chapter 5, in which Turing reduction has not introduced. I personally believe that there is an elegant proof using only mapping reduction. Can we do it?

Update. (Nov 5th, 2017) We found that, roughly speaking, we could prove $A_{\textsf{TM}} \leq_T ALL_{\textsf{minCFG}}$ by the same way as one for $A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$, just adding some stuff to show that the grammar we used in proving $A_{\textsf{TM}} \leq_T ALL_{\textsf{CFG}}$ is already minimal. However, I could not assert that this way is quite simple.
Comment. @Sylvain gives an elegant proof below, by showing
$$ PCP \leq_T FullPCP \leq_m MIN_{\textsf{CFG}}$$
in which I personally thought the key is that context-free language is closed under $h^{-1}$ he defined.

Here is a solution based on a reduction from Post Correspondence Problem.  The general idea is similar to the ones used in reductions from PCP to the emptiness of intersection and ambiguity in context-free grammars.  I am afraid I am using a Turing reduction for a preliminary claim---which I would consider fair game considering the number of variants of PCP `out there'.

Preliminaries.
A PCP instance is a finite set of pairs $\Pi=(u_i,v_i)_{i<n}$ of finite words over a finite alphabet $\Sigma$.  A solution is a sequence of indices $j_0,\dots,j_m$ with $u_{j_0}\cdots u_{j_m}=v_{j_0}\cdots v_{j_m}$.  The set of indices $I(\Pi)$ of a PCP instance $\Pi$ is the set of indices $i<n$ that appear in some solution; formally $$I(\Pi)=\{ i < n\mid \exists i_0,\dots,i_m <n\mathbin.u_{j_0}\cdots u_{j_m}=v_{j_0}\cdots v_{j_m}\text{ and }\exists 0\leq k\leq m\mathbin.i=j_k\}\;.$$
Then the PCP instance has a solution iff $I(\Pi)\neq\emptyset$.

Claim.  The following decision problem called full PCP is also undecidable:

instance $\Pi$
question $I(\Pi)=\{0,\dots,n-1\}$?

Proof.  By a Turing reduction from PCP.  Assume full PCP is decidable, and consider a PCP instance $\Pi$.  For a subset $J\subseteq\{0,\dots,n-1\}$, let $\Pi_J=(u_i,v_i)_{i\in J}$.  Then $\Pi$ has a solution iff $I(\Pi)\neq\emptyset$ iff there exists $J\subseteq\{0,\dots,n-1\}$ such that $\Pi_J$ is a positive instance of the full PCP.  Thus it suffices to check all the subsets $J$ with the algorithm for the full PCP; if at least one succeeds, the original PCP instance was positive, otherwise it was negative. $\Box$

The first grammar $G_1$ is constructed from a full PCP instance $\Pi$ in order to recognise
$$\begin{aligned}L_1&=\{ \$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\mid j_0,\dots,j_m < n\}\;,\\L'_1&=L_1\cup\{\#\}\end{aligned}$$
where $\cdot^R$ denotes the reversal operation, and $\$,\#$ are fresh symbols not in $\Sigma$.  Indeed, we can define $G_1=(\{S_1\},\Sigma\uplus\{\$,\#\},P_1,S_1)$ with $$P_1=\{S_1\to \$u_j S_1 v_j^R\$\mid j<n\}\cup\{S_1\to\#\}.$$ Then $L'_1=L(G_1)$.
Without loss of generality, we can assume $(u_i,v_i)\neq(u_j,v_j)$ for all $i\neq j<n$, and the grammar $G_1$ is minimal: the $\$$ symbols are indeed here to ensure minimality (as otherwise there might exist two different sequences of indices yielding the same words).

The second grammar generates `centered non-palindromes'
$$L_2=\{w\#{w'}^R\mid w\neq w'\in\Sigma^*\}.$$  Note that a word $w\#{w'}^R$ in $L_2$ is such that $w$ and $w'$ share a longest common prefix $u$: $w=uv$ and $w'=uv'$ for some $v,v'\in\Sigma^*$ with

either $v=ax$ and $v'=bx'$ for some $a\neq b\in\Sigma$ and $x,x'\in\Sigma^\ast$,
or $v=ax$ and $v'=\varepsilon$ for some $a\in\Sigma$ and $x\in\Sigma^\ast$,
or $v=\varepsilon$ and $v'=ax'$ for some $a\in\Sigma$ and $x'\in\Sigma^\ast$.

Thus $L_2$ is generated by $G_2=(\{S_2,E,A\},\Sigma\uplus\{\#\},P_2,S_2)$ with $$\begin{aligned}P_2&=\{S_2\to aS_2a\mid a\in\Sigma\}\cup\{S_2\to E\}\\&\cup\{E\to aA\#Ab\mid a\neq b\in\Sigma\}\cup\{aA\#\mid a\in\Sigma\}\cup\{\#Aa\mid a\in\Sigma\}\\&\cup\{A\to aA\mid a\in\Sigma\}\cup\{A\to\varepsilon\}\end{aligned}$$
The idea is that $S_2$ generates $u E u^R$ for $u$ the longest common prefix of $w$ and $w'$, after which $E$ applies one of the three cases above.  Thus $L(G_2)=L_2$, and the grammar is minimal.

Relating the two grammars.  Let $h$ be the homomorphism from $(\Sigma\uplus\{\$,\#\})^*$ to $(\Sigma\uplus\{\#\})^*$ defined by $h(a)=a$ for all $a\in\Sigma$, $h(\#)=\#$, and $h(\$)=\varepsilon$; $h$ simply erases $\$$ symbols.  Then $\Pi$ has a solution iff $h(L_1)\not\subseteq L_2$.  We define $L'_2=h^{-1}(L_2)$ and construct the corresponding grammar $G'_2=(N'_2,\Sigma\cup\{\$,\#\},P'_2,S'_2)$ in the obvious way (add a nonterminal $D$ with productions $D\to \$D$ and $D\to\varepsilon$ and introduce $D$ symbols everywhere in the right hand sides of the productions in $P_2$); it is still minimal and $\Pi$ has a solution iff $L_1\not\subseteq L'_2$.

We are however interested in the full PCP on $\Pi$.  Construct $$G=(N_1\uplus N'_2\uplus\{S\},\Sigma\uplus\{\$,\#\},P_1\cup P'_2\cup\{S\to S_1,S\to S'_2\},S) .$$

If $\Pi$ is a positive instance of the full PCP, then it has solutions, which describe words $\$u_{j_0}\cdots \$u_{j_m}\#(\$v_{j_0}\cdots \$v_{j_m})^R\not\in L'_2$ and moreover require every production of $G_1$.  Regarding $G'_2$, it suffices to consider words from $L_2\subseteq L'_2$ with no occurrence of $\$$, which do not belong to $L_1$ and therefore all the productions of $G'_2$ are needed.  Therefore, $G$ is minimal.
Otherwise, there exists $i<n$ such that $i\not\in I(\Pi)$, and the production $S_1\to \$u_i S_1 v_i^R\$$ can be removed, since it cannot be part of a solution of $\Pi$, and therefore any generated word that uses this production is in $L(G'_2)$; thus $G$ is not minimal.  In particular, if $\Pi$ has no solution ($I(\Pi)=\emptyset$), then all the productions in $P_1$ except $S_1\to\#$ can be removed. $\Box$


Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)? It seems to be known that to find an answer to a query $Q$ over a relational database $D$, one needs time $|D|^{|Q|}$, and one cannot get rid of the exponent $|Q|$.
As $D$ can be very large, we wonder why databases work at all in practice.
Is it just a matter of the usual queries not being large at all in the real-world applications? (Then it is interesting to know what the usual size of the queries posed to relational database systems is, and what the "maximal" size of the queries that are expected to be effectively answerable by a DB system in practice is.)
Notes on the exponent $|Q|$ not `removable'
To show that the exponent $|Q|$ is not removable, one can use a query asking whether there exists a clique of size $n$ in the graph given by the database. To check whether a graph has an $n$-clique is an NP-complete problem. Moreover, it is not fixed-parameter tractable, with parameter $n$. Details can be found in, e.g.,
Libkin, L.: Elements Of Finite Model Theory. Springer (2004)
or
Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. J.
Comput. Syst. Sci. 58(3), 407–427 (1999)

There are large classes of queries which are "easy", even in the worst case.  In particular, if the class of queries contains conjunctive queries only and each query has bounded width (for instance treewidth, treewidth of its incidence graph, fractional hypertree width, or submodular width) then the query can be answered by using something like a join tree, together with brute force enumeration for the local parts of the query that deviate from the tree.  This requires polynomial time, with the degree of the polynomial determined by the width parameter.

It seems that many queries encountered in practice are both conjunctive and have small width.  So the polynomial runtime has low degree in this case.

Dániel Marx presented a paper at STOC 2010 on submodular width recently, the full version of which includes a nice summary of the various notions of width and how the CSP formulation relates to the database formalism (the conference version lacks this).

Dániel Marx, Tractable hypergraph properties for constraint satisfaction and conjunctive queries, 2010. arxiv:0911.0801

This is not a complete answer, since it does not deal with the "typical" complexity of database queries, but even with worst-case analysis there are easy queries.


In what sense are Scala's Try[T] and Future[T] dual? In a recent course based on Scala I found a hint that the Scala types Try[T] and Future[T] are dual. This was explained only informally and the reader was referred to duality in category theory for a more precise definition.

I have some basic knowledge of category theory but I cannot see how these two types can correspond to categories that are dual to each other.

So, what categories correspond to the Scala types Try[T] and Future[T], and why are these categories dual?

The short answer is: they are not dual.

The Try[T] type is basically the sum type $T + E$, where $E$ is the type of exceptions.

A typical way of rendering a future Future[T] is via temporal logic. Here, a future can be understood as a "weak eventually" operator, $\Diamond T$, saying that at some point in the future you may receive a $T$. This can be decomposed as the coinductive type $\nu \alpha.\;T + \bullet\alpha$, where $\bullet$ is the "next-step" modality.


Does it help for clique if the vertices are partitioned into 3 cliques? A graph is $(p,q)$-colorable if its vertices can be partitioned
into $p$ cliques and $q$ independent sets.
For $(2,0)$-colorable graphs clique is polynomial.
I am interested how easier (if any) is clique in $(3,0)$-colorable,
when the partitions are given.
Given graph $G$ and 3 partitions of its vertices
$A,B,C : A \cup B \cup C=V(G)$ such
that $A,B,C$ induce cliques in G.

Q1 Is clique faster in this case?
Q2 If it is faster what is the complexity?
Q3 How good can we approximate clique in this case?

We have a clique $\frac{V(G)}{3}$ for free.

Computing a maximum clique in a graph whose vertex set can be partitioned into 3 cliques, is equivalent to computing a maximum independent set in the complement graph, which can be partitioned into 3 independent sets and is therefore 3-colorable. The latter problem is still NP-complete, which can be seen as follows: Start from an arbitrary instance $(G,k)$ of independent set and subdivide each edge twice, i.e., replace each edge ${u,v}$ by a path ${u,e_1, e_2, v}$ on two new vertices. It is not difficult to prove that the resulting graph $G'$ has an independent set of size $k + |E(G)|$ if and only if $G$ has a size-$k$ independent set: for every independent set in $G$, you can add exactly one of the two subdivider vertices on every edge without violating independence.

Hence the Clique problem is still NP-complete for such inputs.


Small kernel (i.e. proof-verifier) for Agda? Proof-assistants usually include a lot of machinery that assists in the creation of proofs. The creation process may be unsound without risking the soundness of the proof-assistant if the alleged proof that was created is later verified by a sound proof-verifier. The smaller this verifier is, the less likely it is to be unsound due to coding or reasoning errors. The term small kernel was coined to refer to such a verifier in Barendregt and Geuvers (the idea apparently goes back to De Bruijn).

I have found literature mentioning this concept in relation to Coq and HOL Light (among others), but not to Agda, hence the question:

  How close is Agda to having a small kernel? How does it compare to other proof-assistants such as Coq and HOL Light?

Geuvers, H., Proof assistants: history, ideas and future, Sādhanā 34, No. 1, 3-25 (2009). ZBL1192.68629.

Barendregt, Henk; Geuvers, Herman, Proof-assistants using dependent type systems, Robinson, Alan (ed.) et al., Handbook of automated reasoning. In 2 vols. Amsterdam: North-Holland/ Elsevier; 0-444-50812-0 (vol. 2); 0-444-50813-9 (set)). 1149-1238 (2001). ZBL1005.03011.

Adams, Mark, Proof auditing formalised mathematics,  ZBL07106502.

It is true that Agda currently has a much shakier foundation than say Coq or Lean. It does have an internal term syntax that could be seen as a core language (https://github.com/agda/agda/blob/master/src/full/Agda/Syntax/Internal.hs). It even has an independent typechecker for internal syntax (https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/CheckInternal.hs).

However, this story is far from complete because it takes the signature of defined types and functions for granted. In particular, functions by dependent pattern matching are represented as case trees that need to pass coverage checking and termination checking, which means those checks are also part of Agda's 'trusted core'. In our ICFP paper last year (https://dl.acm.org/citation.cfm?doid=3243631.3236770) Andreas and I describe a potential core language for case trees, but so far there is no independent typechecker for case trees as we have for internal syntax (one day...).

Another important part of Agda's trusted core is the conversion checker, which in Agda shares most code with the constraint solver (https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/Conversion.hs), while in Coq it's two separate algorithms. Recently I added the possibility to run the conversion checker in 'pure' mode which is guarateed to be free of side-effects (https://github.com/agda/agda/blob/master/src/full/Agda/TypeChecking/Conversion/Pure.hs).

As you can see, there is bits and pieces that could be part of a core language of Agda, but no real coherent story yet. In general, any attempt to build a core language will also be an exercise in selecting which features of Agda should be included and which ones should not (e.g. irrelevance, sized types, prop, rewrite rules, cubical, ...). Yet this selection of various features would've been much harder to implement if Agda already had a core language from the beginning, so not having a core language has advantages as well as disadvantages.


Length bounded minimum cardinality cut in DAGs Suppose I have a DAG with non-negative edge lengths. The problem is to compute the minimum number of edges which disconnects all paths of length L or less. We call this L-length bounded minimum cardinality cut problem on DAGs. It can naturally be extended to all directed graphs.

There can be a further generalization where removing an edge has some associated cost. The L-length bounded min cut problem is finding the set of edges with minimum total weight that gives a L-length bounded min-cut.

The L-length bounded min-cut problem is known to be NP hard. In fact for a given budget it is NP hard to decide if there exists a length bounded cut which does not exceed the budget for series parallel graphs [1]. So it holds for DAGs.

In this paper [1] it is showed that for directed graphs L-length bounded minimum cardinality cut itself is NP hard to have an 1.1377 approximation.

1) Does there exist NP hardness result for L-length bounded minimum cardinality cut on DAGs?

Or,

2) Is there any polynomial time, w.r.t. the number of edges and vertices, algorithm to construct the L-length bounded minimum cardinality cut on DAGs?

References:

1: Baier, Georg, et al. "Length-bounded cuts and flows." Automata, languages and programming. Springer Berlin Heidelberg, 2006. 679-690.

The paper mentioned in the question uses a reduction from Vertex Cover problem to show that the length bounded cut problem is NP Hard. The instance they construct given an instance of vertex cover, is nothing but a DAG. In this case all the edge has unit weight which corresponds to the minimum cardinality case. Therefore, the problem of L-length bounded minimum cardinality cut on DAGs is NP hard.


How long does it take to find a short cycle in a random graph? Let $G \sim G(n, n^{-1/2})$ be a random graph on $\approx n^{3/2}$ edges.  With very high probability, $G$ has many $4$-cycles.  Our goal is to output any one of these $4$-cycles as quickly as possible.

Supposing we have access to $G$ in adjacency list form, we can succeed with constant probability in $O(\sqrt{n})$ time as follows: pick any node $v$ and start generating random $2$-paths starting from $v$; once we find two distinct $2$-paths that share an endpoint, we are done.  There are $n$ possible endpoints, and by the birthday paradox we will succeed with constant probability after discovering about $\sqrt{n}$ of them.

Can we do better?  In particular, is a constant-time algorithm that succeeds with constant probability possible?

No, you can't beat $\Theta(\sqrt{n})$ queries.  I will explain how to formalize exfret's proof sketch of this, in a way that works for adaptive algorithms.  This is all anticipated in exfret's answer; I am just filling in some of the details.

Consider any (possibly adaptive) algorithm that issues a sequence of queries, where each query is either "fetch the $i$th edge of vertex $v$'s adjacency list" or "test whether vertices $v,w$ are connected by an edge".  We can assume that no query is repeated, as any algorithm that repeats a query can be transformed to one that never repeats any query.  Similarly, we can assume that the algorithm never does a connectivity query on any pair of vertices that are already known to be connected by an edge (namely, testing $v,w$ when $w$ was previously returned by a fetch query on $v$, or $v$ was previously returned by a fetch query on $w$, or we previously tested connectivity of $w,v$).

Let $E_k$ denote the event that, during the first $k$ queries, no vertex $w$ is returned by more than one fetch-query, and no fetch-query returns a vertex that was previously queried, and that no connectivity-test-query returns "connected".  We'll prove that $\Pr[E_q] = 1-o(1)$ if $q=o(\sqrt{n})$.  It follows that no algorithm that makes $o(\sqrt{n})$ queries can have a constant probability of finding a 4-cycle.

How do we prove this?  Let's compute $\Pr[E_k|E_{k-1}]$.  There are two cases: either the $k$th query is a fetch query, or it is an connectivity-test query:

If the $k$th query is a fetch query on vertex $v$, there are $2(k-1)$ vertices mentioned among the first $k-1$ queries, and if the $k$th query returns one of those then we will have $\neg E_k$, otherwise we will have $E_k$.  Now the response to the $k$th query is uniformly distributed on a set $S$ of vertices, where $S$ contains all vertices that haven't been returned by prior fetch queries on $v$, so the response to the $k$th query is uniformly distributed on a set of size at least $n-k+1$.  The probability of hitting at least one of these is $\le 2(k-1)/(n-k+1)$, so in this case, $\Pr[E_k|E_{k-1}] \ge 1 - 2(k-1)/(n-k+1)$.
If the $k$th query is a connectivity-test query, then $\Pr[E_k|E_{k-1}] \ge 1 - 1/\sqrt{n}$.

In either case, if $q=o(\sqrt{n})$ we have

$$\Pr[E_k|E_{k-1}] \ge 1 - {2(k-1) \over (n-k+1)}.$$

Now,

$$\Pr[E_q] = \prod_{k=1}^q \Pr[E_k|E_{q-1}].$$

If $k \le q \le \sqrt{n}$, then

$$\Pr[E_k|E_{k-1}] \ge 1 - {2q \over n - q},$$

so

$$\Pr[E_q] \ge (1 - {2 q  \over n - q})^q.$$

The right-hand side is approximately $\exp \{ - 2q^2/(n-q)\}$.  When $q = o(\sqrt{n})$, this is $1 -o(1)$.

In conclusion: $\Pr[E_q] = 1-o(1)$ when $q=o(\sqrt{n})$.  It follows that you need $\Omega(\sqrt{n})$ to have constant probability of finding any cycle (let alone a 4-cycle).


Simply typed lambda calculus and higher order logic What is the relation between simply typed lambda calculus and higher order logic?

Under Curry-Howard it seems that simply typed lambda calculus corresponds to propositional logic. How is it related to higher order logic? According to this tutorial by Geuvers: http://typessummerschool07.cs.unibo.it/courses/geuvers-1.pdf the language of HOL seems to be STT. Shouldn't it be PROP? What does that mean?

Did Church have in mind HOL when defined STT?

The distinction is this: if STLC is taken as a primitive language at the type-level adding constructors and a small number of axioms is sufficient to give you the full expressive power of HOL.

Taking $\iota$ as the base type of numbers ans $\omicron$ as the base type of propositions, you can add the constants
$$ \forall_\tau:(\tau\rightarrow \omicron)\rightarrow \omicron\quad \supset:\omicron\rightarrow\omicron\rightarrow \omicron$$

where $\tau$ is an arbitrary type (so one $\forall$ constant for each type). One possible set of axioms:

$$ \frac{\phi(x)}{\forall_\tau(\lambda x.\phi(x))}\mbox{$x:\tau$ not free in the hypotheses}$$

$$ \frac{\Large{\substack{[\psi]\\ \\ .\\ .\\ .\\ \\ \phi}}}{\psi\supset \phi}$$

where $[\psi]$ means that the hypothesis $\psi$ is discharged. Interesting fact: the other connectives $\exists_\tau, \vee$... can be derived from just those 2.

The subtlety is distinguishing between $\lambda$-terms as a way to represent proofs, as predicated by the Curry-Howard-de Bruijn (Martin-Löf) correspondence, or as a way to represent the terms you reason upon. The two views are not incompatible, of course.

In particular there is a typed $\lambda$-calculus that faithfully represents HOL (minus various axioms of course). This happens to be a sub-system of the Calculus of Constructions, and is described in detail by Geuvers in The Calculus of Constructions and Higher Order Logic. He also details the differences between the two (the CoC is not a conservative extension of HOL).


Convergence theorem for Genetic Programming? Genetic Programming (GP) is stochastic algorithm, there has been early attempts to explain its convergence with the Schmea Theorem (Holland 1975) for Genetic Algorithm adapted for GP such as (Koza 1992) (O'Reilly 1994) (Altenberg 1994) (Rosca 1997), but I was wondering if someone could point me to the generally agreed theorem that proves GP's covergence? Does it exist?

References:

[Altenberg 1994]: Altenberg, Lee. "Emergent phenomena in genetic programming." Evolutionary Programming—
Proceedings of the Third Annual Conference. World Scientific Publishing, 1994.
[Goldberg 1989]: Goldberg, David. “Genetic Algorithms in Search, Optimization and Machine Learning.” Addison-
Wesley Professional, Reading, MA 1989.
[Koza 1992]: Koza, John R. Genetic programming: on the programming of computers by means of natural selection.
[O'reilly 1994]: O'Reilly, Una-May, and Franz Oppacher. Using Building Block Functions to Investigate a Building Block Hypothesis for Genetic. No. 94-04-020. 1994.
Vol. 1. MIT press, 1992.
[Rosca 1997]: Rosca, Justinian P. "Analysis of complexity drift in genetic programming." Genetic Programming
(1997): 286-294.

I am not sure that there is one Theorem to point to. Anyhow, you will probably be interested in the following reference, which summarizes many more recent results than those you mention in the question, e.g., for the (1+1)-EA with linear functions, quadratic functions, and monotone polynomials as objective functions (I know these are probably much simpler functions than you care about). Anyway the citations within should give you good pointers, via Google Scholar, to even newer results.

Stefan Droste, Thomas Jansen, Günter Rudolph, Hans-Paul Schwefel, Karsten Tinnefeld, and Ingo Wegener (2002): Theory of evolutionary algorithms and genetic programming.  In H.-P. Schwefel, I. Wegener, and K. Weinert (Eds.): Advances in Computational Intelligence Theory and Practice. Springer, Berlin, Germany, pages 107-144.


Cooperative Pathfinding to minimize global costs There are some algorithms and methods around, that allow cooperative pathfinding. Unfortunately they all seem to aim at avoiding collisions or conflicts between entities.

I'm looking for an algorithm that allows agents to explicitly join their paths to go some part of the way together if that minimizes the overall costs, regardless of individual costs (e.g. using the wind shadow of another car)

Is there any research going on in this area that I'm not aware of, or are there even algorithms around that solve such problems?

This may be related to network formation games - games in which players try to find a path in a network, and collaborating along a path reduces the cost for both players (i.e. the cost is shared)
This paper may be of help.


Has the compactness theorem for FOL been formalized in Coq/Isabelle/etc? I've been searching for a formalization of the compactness theorem for FOL, but haven't found any. Is anyone aware of such a development or related work?

The compactness theorem for classical first-order logic is a direct consequence of the completeness theorem, and, actually, one can prove directly Compactness by the Henkin-style argument used for Completeness without ever mentioning derivation.

The Completeness theorem for classical FOL with respect to standard Tarski models has been formalized in Mizar. See the series of articles under http://fm.mizar.org/2005-13/fm13-1.html

The same completeness theorem, but with a constructive proof, has been almost formalized in the Coq proof assistant by myself, see the zip file under https://sites.google.com/site/dankoilik/publications/phd-thesis

I say "almost" because there is one technical point, proving a correctness of a sorting algorithm, that I have not yet had time to finish, however the main ingredient (constructive ultra-filter theorem for countable languages) is formalized.

One can also consider Completeness, and hence Compactness, for a non-standard notion of validity, and get a complete and formalized constructive proof.


Sum of Independent Exponential Random Variables Can we prove a sharp concentration result on the sum of independent exponential random variables, i.e. Let $X_1, \ldots X_r$ be independent random variables such that $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$. Let $Z = \sum X_i$. Can we prove bounds of the form $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$. This follows directly if we use the variance form of chernoff bounds and hence I believe is true , but the bounds that I read require bounded-ness or have some dependence on bounded-ness of the variables. Could someone point to me to a proof of the above ?

For concreteness, say that the pdf of the r.v. $X_i$ is

$$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$$

This is the Laplace distribution, or the double exponential distribution. Its variance is $\frac{2}{\lambda_i^2}$. The cdf is

$$
\Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x}
$$
for $x \geq 0$.

The moment generating function of $X_i$ is

$$
\mathbf{E}\ e^{uX_i} = \frac{1}{1 - u^2/\lambda_i^2},
$$
for $|u| < \lambda_i$. Using this fact and the exponential moment method which is standard in the proof of Chernoff bounds, you get that for $X = \sum_i X_i$ and $\sigma^2 = 2\sum_i \lambda_i^{-2}$, the following inequality holds

$$
\Pr[X > t\sigma] < e^{-t^2/4},
$$
as long as $t \leq 2\sigma \min_{i}{\lambda_i}$. You can find a detailed derivation in the proof of Lemma 2.8 of this paper.


Quick-select contiguous subarray Motivated by the question from this blog post,
the following data structure question seems interesting and fun to me.

Preprocess: A list of numbers $A = a_1,...,a_n$
Query(s,t,k): Return the $k$-th rank element of the sublist $A[s:t]$ where $A[s:t] = a_s,...,a_t$.

There are two trivial solutions:

Space = $n^3$, Time = $1$. Construct a look-up table
Space = $n$, Time = $O(n)$. Do nothing for preprocessing. Quick-select the $k$-th element in $A[s:t]$.

Is there some non-trivial solution?

$O(n)$ space with $O(\log k/\log \log n+\log \log n)$ query time is possible. See this paper.


Combinatorial Expansion implies Algebraic Expansion Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves:

  Algebraic Expansion implies Combinatorial Expansion

  If G is a $(n, d, x)$ expander graph, then it is an $(n, d, (1-x)/2)$
  edge expander.

(good, I understand this part)

They they go on to state:

  Combinatorial Expansion implies Algebraic Expansion

  If G is a (n, d, p) edge expander, then i's second largest eigen
  value (without taking the absolute values) is at most $1 - p^2/2$.
  Furthermore, if G has all self loops, then it is an $(n, d, 1-\epsilon)$
  expander where $\epsilon = min(2/d, p^2/2$).

Now, this is the part I am unhappy with. Here is what I understand:

If G is bipartite, it has an eigen value of -1, and thus we can't say much about the 2nd largest absolute value of the eigen values.

If G has all self loops, it's clearly not bipartite.

However, the above theorem does not make any guarantees about graphs G, which are:

(1) non-bipartite
(2) do not contain all self loops.

For graphs in this class, do we have a proof of "combinatorial expansion" implies "algebraic expansion"? [If the answer is yes, can you please provide a reference?]

Thanks!

If we have combinatorial expansion, then the second eigenvalue (without taking absolute value) is not too large (or, equivalently, second eigenvalue of the Laplacian is not too small) no matter what (that is, regardless of bipartiteness or having self-loops or even all vertices having the same degree, if notions are defined properly). See the proof of Cheeger's inequality, for example here:

Spielman's lecture notes on Cheeger's inequality.


In System F à la Church, can we automatize type inference for the for-all elimination? The question is the following. Generally when one have a term like $\Lambda X.t$, we can eliminate the forall by applying this term to a type, as instance $(\Lambda X.t)[T]\to t[X:=T]$.

Now, suppose this is an arrow and we want to give it an argument, then we would need to apply this term to the proper type such that it can receive such an argument. That is what I am asking if I can automatize: Is it possible to construct a function $f$ taking two terms and returning a type such that
$f<{\Lambda X.t}><{r}>$ give us the type needed to be replaced by $X$ in $t$ such that $t$ can accept the argument $r$?

Some examples:

$f<{\Lambda X.\lambda x^{X\to X}.t}><{\lambda x^T.x}>=T$.
$f<{\Lambda X.\lambda x^X.r}><{(\lambda x^{R}.t^T)~s}>=T$

I'm not really sure I've understood the question.
First, I try to reduce your problem to the following unification problem:

Given a system F type τ(X) with a free (type) variable X, and a type σ.
Is it possible to find a type γ such that τ(γ) = σ ?

Here is a pseudo-code (with an exception raised when not unifiable) for
solving this problem.

unify (X, σ) = σ
unify (Y, Y) = Y
unify (τ₁ → τ₂, σ₁ → σ₂) = unify(τ₁,σ₁) → unify(τ₂,σ₂)
unify (∀Y.τ(Y), ∀Y.σ(Y)) = ∀Y.unify(τ(Y),σ(Y)) (with Y a fresh variable)
unify (_,_) = raise Not_unifiable

You can prove (by induction) that γ = τ(unify(τ(X),σ) works if and
only an exception is not raised.

Now for your problem you can take

f (ΛX.t) (r) = match type of t with "τ₁ → τ₂" => unify (τ₁, type of r) | _ => fail end

(of course your function f should take as argument a context if your terms are open).


What is the complexity of this covering problem? Edit: I first misformulated my constraint (2), it is now corrected. I also added more information and examples.

With some colleagues, studying some other algorithmic question, we were able to reduce our problem down to the following interesting problem, but we were not able to solve the question of its complexity. The problem is as follows.

  Instance: An integer $n$, an integer $k<n$, and a set $S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$ of $n$ pairs from the set $\{1,\ldots,n\}$.

  Question: Is there a set $S'\subseteq S$ of size $k$ such that for each element $i$ of $\{1,\ldots,n\}$:
  (1) if $i<n$, the interval $[i,i+1]$ is included in some interval $[s_i,t_i]$ defined by a pair in $S'$, and
  (2) at least one of $i$, $i+1$ belongs to some pair of $S'$?
  (2) $i$ belongs to some pair of $S'$.

Example
The set $\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$ is a feasible solution (assuming $n$ is even): the pair $\{1,n\}$ ensures condition (1), whereas all other pairs ensure condition (2).

Remarks
(I) Since each pair contains exactly two elements, in order to fulfill condition (2), we need at least $\frac{n}{2}$ pairs. BTW this implies a trivial 2-approximation by returning the whole $S$, since we assume $|S|\leq n$.

(II) Another way of looking at the problem is to consider a ladder with $n$ steps (such as the one below), together with a set $S$ of $n$ cycles of the ladder. Each step of the ladder corresponds to some element, and each side edge is an interval $[i,i+1]$. A cycle including steps $s,t$ corresponds exactly to a pair $\{s,t\}$: it covers all consecutive intervals between $s$ and $t$, and it stops at both $s$ and $t$.The question is then whether there is a set $S'\subseteq S$ of $k$ cycles whose union covers all the edges of the ladder (including step edges and side edges).

(III) If one was asking only for condition (1), the problem would correspond to the dominating set problem in some interval graph defined from the intervals $[s_i,t_i]$ given by the pairs of $S$ together with additional tiny intervals $[i+\epsilon,i+1-\epsilon]$ for each $i$ in $\{1,\ldots, n-1\}$. This problem is classically solvable in linear time (see e.g. here).Similarly, if one was just asking for condition (2), this could be reduced to the edge cover problem (vertices are the elements, edges are the pairs), which is also polynomial-time solvable by a maximum matching approach.

So my question is in the title:

  Is this problem in P? Is it NP-complete?

Any reference to a similar problem is welcome.

Although this does not resolve the question you raise, some of the previous comments consider approximation algorithms.  FWIW, I think a PTAS (poly-time approximation scheme) is possible using dynamic programming.  Here's the idea.

Given any instance and $\epsilon > 0$, build a solution as follows.  Mark every $(1/\epsilon)$'th vertex.  For each marked vertex $i$, from all of the edges $(j,k)$ that "span" $i$ (i.e., that satisfy the constraint (1) for $i$), choose one edge that minimizes $j$ and one that minimizes maximizes $k$.  Add these $2 \epsilon n$ edges to the solution.

These edges satisfy the constraints of type (1) for many of the vertices.  Meanwhile they contribute $2n\epsilon$ edges to the solution, which is only $O(\epsilon \mbox{OPT})$.  To finish, we will find an optimal solution to the remaining problem of finding a set of edges that meets all remaining type (1) and type (2) constraints.

Define a "block" of vertices to be a set of consecutive vertices whose type (1) constraints are met by the edges added so far.  Between any two consecutive blocks, there is a sequence of vertices whose type (1) constraints are not met.  (Any such sequence has length at most $1/\epsilon$, because the marked vertices have their type (1) constraints met by the edges already added.)  Call any such sequence a "neighborhood" of the two adjacent blocks (so each block has a neighborhood to its left and a neighborhood to its right).

Within each neighborhood, for each vertex in the neighborhood, each edge leaving the vertex spans a distance of at most $1/\epsilon$ (because the edge doesn't span any marked vertex).  Thus, the vertex has degree at most $1/\epsilon$.  Thus, each neighborhood has at most $1/\epsilon$ vertices and touches at most $1/\epsilon^2$ edges.  Call any subset of those edges a "configuration" of the neighborhood.  If a configuration meets all of the type (1) and type (2) constraints for the vertices in the neighborhood, call the configuration "valid".

For each block $i$, for each pair $(C_i, C_{i+1})$ of valid configurations of the block's two neighborhoods, compute (in polynomial time, using maximum matching etc), the minimum size $F_i(C_i,C_{i+1})$ of any set $S$ of edges (if any exists) such that the edges in $C_i\cup S \cup C_{i+1}$ meet the type (2) constraints for the vertices in the block.  Since there are at most $2^{1/\epsilon^2} = O(1)$ configurations, this can be done in polynomial time (for fixed eps).

Now you can solve the original instance by finding a sequence $D_1, D_2, .., D_k$ of valid configurations, one for each neighborhood, that minimizes $\sum_i |D_i| + F_i(D_i, D_{i+1})$, where $F_i$ is as defined in the previous paragraph.  This can be done by finding a shortest path in the graph formed by all valid configurations, with an edge of cost $|D_i| + F_i(D_i, D_{i+1})$ from each configuration $D_i$ for neighborhood $i$ to each configuration $D_{i+1}$ for neighborhood $i+1$.  (This graph has size $O(2^{1/\epsilon^2} n)$, which is $O(n)$ for fixed $\epsilon$.)


Is a reference on T a subtype of T? If I take the book Practical Foundations for Programming Languages by Robert Harper, the following definition is given for subtyping:

  A subtype relation is a pre-order on types that validates the subsumption principle: if $\tau'$ is a subtype of $\tau$, then a value of type $\tau'$ may be provided when a value of type $\tau$ is required.

I was wondering whether we can say that a reference on $T$, denoted by $\text{Ref }T$ is a subtype of $T$. If not, why?

No, Ref T is not a subtype of T. In typical sub-typing rules, a term of type Ref T is not substitutable for a term of type T. A Ref T has the value of a pointer to a location in memory of an T, whereas T has the value of an T. More concretely, in ML-based languages, in order to pass the value from a Ref T to a function that takes the enclosed type T, you need to dereference the argument first. Typically that will involve using a unary operator like !.

So, while it is possible that a coercion could make the Ref T appear to be a subtype, I think it's better to think of Ref as a container type, rather than a more specific kind of T.

An example from OCaml:

# let t = ref 2 ;;
val t : int ref = {contents = 2}
# let q : int = t ;;
Error: This expression has type int ref
       but an expression was expected of type int
# let r : int = !t ;;
val r : int = 2

A possible workaround for this would be to look into some form of implicit coercions, which are available in certain languages. See more on coercion here.


How can relational parametricity be motivated? Is there some natural way to understand the essence of relational semantics for parametric polymorphism?

I have just started reading about the notion of relational parametricity, a la John Reynolds' "Types, Abstraction and Parametric Polymorphism", and I am having trouble understanding how the relational semantics is motivated.  Set semantics makes perfect sense to me, and I realise that set semantics is insufficient to describe parametric polymorphism, but the leap to relational semantics seems to be magic, coming completely out of nowhere.

Is there some way of explaining it along the lines "Assume relations on the base types and terms, and then the interpretation of the derived terms is just the natural relationship between ...such and such a natural thing... in your programming language"?  Or some other natural explanation?

Well, relational parametricity is one of the most important ideas introduces by John Reynolds, so it shouldn't be too much of a surprise that it looks like magic. Here is a fairy tale about how he might have invented it.

Suppose you're trying to formalize the idea that certain functions (identity, map, fold, reversal of lists) act "the same way on many types", i.e., you have some intuitive ideas about parametric polymorphism, and you have formulated some rules for creating such maps, i.e., the polymorphic $\lambda$-calculus or some early variant of it. You notice that naive set-theoretic semantics is not working.

For instance, we stare at the type $$\forall X : \mathsf{Type} . X \to X,$$
which should contain only the identity map, but naive set-theoretic semantics allows unwanted functions such as
$$\lambda X : \mathsf{Type} . \lambda a : X . \mathsf{if}\ (X = \lbrace 0, 1 \rbrace) \ \mathsf{then} \ 0 \ \mathsf{else}\ a.$$
To eliminate this sort of thing, we need to impose some further conditions on functions. For instance, we could try some domain theory: equip each set $X$ with a partial order $\leq_X$ and require that all functions be monotone. But that doesn't quite cut it because the above unwanted function is either constant or identity, depending on $X$, and those are monotone maps.

A partial order $\leq$ is relfexive, transitive and antisymmetric. We can try to alter the structure, for instance we could try to use a strict partial order, or a linear order, or an equivalence relation, or just a symmetric relation. However, in each case some unwanted examples creep in. For instance, symmetric relations eliminate our unwanted function but allow other uwanted functions (exercise).

And then you notice two things:

The wanted examples are never eliminated, whatever relations you use in place of partial orders $\leq$.
For each particular unwanted example you look at, you can find a relation that eliminates it, but there is no single relation that eliminates all of them.

So, you have the brilliant thought that the wanted functions are those that preserve all relations, and the relational model is born.


Is it known whether hypergraph minimal covers are P-enumerable? Is it known or unknown whether hypergraph minimal covers are P-enumerable? I would be most happy with lower bounds. I'd also like to hear about conditional results, which assume some conjecture is true. Of course, I'd also want to know about closely related problems (such as independent sets and cliques).

Motivation. I have a problem to which enumeration of minimal covers in hypergraphs can be reduced, and an algorithm that is exponential in the worst case and works OKish in practice.  I wonder whether doing much better is possible; or are there good reasons I haven't found something better? (The problem arises in the context of static analysis of programs.)

Background. A hypergraph is a pair $(V, E)$ of vertices $V$ and edges $E:(V\to2)\to2$, the latter being subsets of vertices. A cover $U$ is a subset of vertices that intersects all edges: $\forall e:E\;\exists u:U\;(u:e)$. A cover is minimal when no strict subset of it is a cover.

Judging from the results of googling ‘P-enumerable’, the term is not too popular. I'm referring to the definition given by Valiant [1]:

  A relation $R$ is P-enumerable iff there is a polynomial $p$ such
  that for all $x$ the set $\{y:R(x,y)\}$ can be enumerated in time
  $|\{y:R(x,y)\}|\times p(|x|)$.

Related. According to Johnson et al. [2], in 1988 it was unknown whether minimal covers of hypergraphs are P-enumerable.  The equivalent problem for graphs, when $\forall e:E\;(|e|=2)$, is known to be P-enumerable, since 1977 [3]. But, [2] explains why the method of [3] cannot be generalized to hypergraphs. The related decision problem of finding one minimal cover is clearly in P. The related counting problem is #P-complete for graphs [1].

I also found some sources [4, 5] which I find hard to read: one uses many concepts I'm not familiar with, and the other is long.  For example, Theorem 1.1 in [4] seems to imply that there exists a quasi-polynomial algorithm; but, [5] has an extra condition (1.2, submodularity) that wouldn't hold for the covers problem. Moreover, [5] mentions an obstruction (Proposition 5.2) similar to the one alluded to by [2] (‘exercise for the reader’) for the methods of [3]. So, it seems to me that it was still unknown in 2002 whether hypergraph minimal covers are P-enumerable, although I'm not completely sure I interpret [4 and 5] correctly.

[1] Valiant, The Complexity of Enumeration and Reliability Problems, 1979.

[2] Johnson, Yannakakis, Papadimitriou, On Generating All Maximal Independent Sets, 1988.

[3] Tsukiyama, Ide, Ariyoshi, Shirakawa, A New Algorithm for Generating All Maximal Independent Sets, 1977

[4] Boros, Elbassioni, Gurvich, Khachiyan, Makino, Dual-Bounded Generating Problems: All Minimal Integer Solutions for a Monotone System of Linear Inequalities, 2002

[5] Elbassioni, Incremental Algorithms for Enumerating Extremal Solutions of Monotone Systems of Submodular Inequalities and Their Applications, 2002

You are looking for an output-polynomial algorithm for enumerating minimal transversals of hypergraphs (or hitting sets for set systems). According to Golovach et al. (ICALP 2013),

  The question whether the minimal transversals
  of a hypergraph can be enumerated in output polynomial time is a fundamental and
  challenging question; it has been open for several decades and has triggered extensive
  research. [...]

  Whether or not all minimal transversals of a
  hypergraph can be listed in output polynomial time has been identied as a fundamental
  challenge in a long list of seminal papers, e.g., [10, 11, 12, 13, 14, 19, 30], and it remains
  unresolved despite continuous attempts since the 1980's.


Random walk returning probability Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ with $p_1$, goes to $(0,1)$ with $p_2$ etc.

I am interested in the probability $x$ of going back to (0,0), starting from (0,0). In general, this probability is not 1 (I guess that $x$ is not rational in general). The question is, given a probability threshold $r$, is it decidable that $x\geq r$?

this ref covers it.

  In sections 5 & 6 we use the elliptic integral to express the probability, less than one, that certain biased random walks return to the origin. The probability of a return to the origin for these walks can then be computed accurately and easily using Gauss' arithmetic-geometric mean (AGM) method to evaluate the elliptic integral.

[1] Recurrence of Simple Random Walk in the Plane
Terence R. Shore and Douglas B. Tyler
The American Mathematical Monthly
Vol. 100, No. 2 (Feb., 1993), pp. 144-149


Complexity of $r$-sum as a function of integer sizes Given $n$ distinct integers whose absolute value is of size $c_{n,k}=\lceil n^{1/k}\rceil$ bits ($c_{n,k}$th bit position is always $1$ for absolute value) we know that using dynamic programming we can find if there is a subset that sums to $0$ in $2^{O(n^{1/k})}$ time.

Given $r\in\Bbb N$ what is best known algorithm for complexity of $r$-sum on such situations for case (1) fixed $k>1$ and for case (2) $k=\theta((\log n)^\alpha)$ for some fixed $\alpha\in(0,1)$?

What happens at limit $\alpha\rightarrow1-$?

There is a straightforward dynamic programming algorithm with complexity $n \times 2^{O(r \cdot n^{1/k})}$.  This is pretty slow.

For $r=2$, you can use algorithms for the birthday paradox to find a solution in time $O(n)$, if a solution exists.  A solution will exist with high probability.  In fact, for $r=2$, with high probability a solution will exist within the first $n^{1/2k}$ numbers, and we can find a solution in expected running time $O(n^{1/(2k)})$.

There is an algorithm with complexity $O(r \cdot n^{1/(k(1+\lg r))})$.  You start by finding pairs (2-sums) whose sum has many of their high bits equal to zero (by combining pairs of elements, using algorithms for the birthday paradox); then look for 4-sums whose sum has a (slightly smaller) number of high bits equal to zero (by combining pairs of 2-sums); then look for 8-sums (by combining pairs of 4-sums); and so on.  The running time comes from optimizing the exact number of high bits that you ask to be zero at each stage.

For instance, for the case $r=4$, there is an algorithm with complexity $O(n^{1/(3k)})$ for finding at least one such solution.

As far as I know, it is an open problem whether one can do better than this.

See also the following research papers:

A. Blum, A. Kalai, H. Wasserman. "Noise-tolerant learning, the parity problem, and the statistical query model".  JACM, 50(4):506-519, 2003.
P. Camion, J. Patarin.  "The Knapsack hash function proposed at Crypto'89 can be broken".  EUROCRYPT '91, pp.39-53.
R. Schroeppel, A. Shamir.  "A T = O(2^n/2), S = O(2^n/4) algorithm for certain NP-Complete problems".  SIAM J. Computing,  10(3):456--464.
P. Chose, A. Joux, M. Mitton.  "Fast Correlation Attacks: an algorithmic point of view".  EUROCRYPT 2002.


Decomposition of edges of eulerian graph into maximum number of cycles I'm interested in the following problem.

Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j = \varnothing$), such that each $C_i$ forms a simple cycle in $G$ and $k$ is maximum possible.

In other words, we are to cover every edge of an eulerian graph with a maximum number of edge-disjoint simple cycles.

Is this problem well-known? Is there a known approach to solve it?

This paper may be helpful with regard to the question you raised:
https://pdfs.semanticscholar.org/32a0/821e384e726819155065f7bc26e2d57329e5.pdf


Can relativization results be used to prove sentences formally independent? Is it possible to demonstrate that a sentence must be formally independent based on the fact that it is non-relativizing?  In other words, are there examples of sentences in computability/complexity theory where it can be demonstrated both a)  that all proofs that resolve the question of whether or not two classes are equal must relativize, and b)  that there are no relativizing proofs that can be used in such a resolution?

I think that results satisfying part b would be easier to come by.  Another way to ask this question is:  Has there ever been a sentence in computability or complexity theory where it can be demonstrated that the equality or inequality must be established through the use of (and only through the use of) relativizing techniques?  An example of this would be interesting to me.

Thanks; an answer to either version of this question would be very interesting to me.

-Philip

There are no "natural" complexity-theory questions that have been proved independent of really powerful formal systems, such as ZF set theory or Peano Arithmetic.  (One could certainly construct such a question artificially, by playing games with Gödel sentences.)

On the other hand, yes, you can interpret the statement that a sentence S relativizes as meaning that S can be proved from a certain restricted set of axioms (basically, the "Cobham axioms" that characterize closure under polynomial-time reductions).  Conversely, the existence of oracles making S either true or false is equivalent to S being independent of those particular axioms.  Here's the paper to read about this, by Arora, Impagliazzo, and Vazirani.

This is a very pretty connection mathematically---but it's worth stressing that we do have techniques (such as arithmetization) that go outside the relativizing axioms.  And I don't know of any results of the form "if natural open problem P can be solved at all, then it can also be solved in a relativizing way."


When is the duality gap of semidefinite programming (SDP) zero? I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold?

For example, when one goes back and forth between the Lasserre and the SOS SDP, in principle one has a duality gap. However, somehow there seems to be some "trivial" reason why this gap isn't there.

Slater's condition seems to be sufficient but not necessary and it applies to all convex programs. I am hoping that for SDPs in particular something stronger might be true. I would be equally happy to see any explicit example of using Slater's condition to prove the vanishing of the duality gap.

There is a more complicated theory of duality for SDPs that is exact: there is no 'extra condition' like Slater's condition.  This is due to Ramana.  (For another take on this involving SOS, see [KS12].)  To be honest, I've never tried to understand these papers and would be happy if someone dumbed them down for me.

One notable consequence of this work is that the problem of testing whether a given SDP is feasible is in NP if and only if it is in coNP.  (However, I think the experts expect the problem is in neither.  The best upper bound known is PSPACE.)


What is a practical non-von Neumann architecture? Are there any practical applications for non-von Neumann programming models? What are the most widely adopted non-von Neumann programming languages?

When I say "von Neumann architecture", I mean some hardware that is limited by the "von Neumann bottleneck" -- i.e., it has all data is funneled through some narrow data bus.

The non-von Neumann programming languages I bump into most often are VHDL and Verilog.
In VHDL and Verilog, by default, everything happens at the same time.
The programmer has to go to extra effort to make a series of events occur in sequential order.
That is very different from most other programming languages that imply a "instruction pointer" that, by default, executes at most one line of code at any one instant, and the programmer has to go to extra effort to get multiple things happening at the same time.

Some people would say that's a more natural default.
Lots of beginning programming students expect a "while( x > 0 ){...}" loop to exit the instant that x becomes equal to zero, and they are surprised to learn that the computer doesn't continously evaluate that condition.

Most people writing VHDL and Verilog code compile their programs onto FPGAs,
creating little blocks of activity that all run at full speed all the time.
Often such people set up a "pipeline" that reads data from the input pins, processes it through a series of blocks, the output pins of one block directly wired to the input pins of the next block, and the final block sends the result out the output pins.
It's reminiscent of the Unix pipeline, except that a new piece of data goes in and a new piece of data comes out on every clock cycle.

The input pins, the intermediate stages, and the output pins are all independent of each other -- you don't have to re-use a single data bus multiplexed between the various pieces of data.

You might also be interested in: Are there other computer architectures apart fom the von neumann /turing architectures?


Outstanding conjectures and open problems in (algorithmic) game theory? What sort of conjectures and major open problems are the most important in algorithmic game theory (or game theory in general as it relates to CS)? For example, the resolution of NASH as being PPAD-complete would, I think, have been the biggest one up until it was resolved.

(Added: resolving PPAD's relation to P and NP is one good open problem, but others not so deeply entrenched in computational complexity would be nice too.)

Here are several open problems:

1-Major open problem is the problem of computing approximate Nash equilibria.

2- Existence of efficient algorithm for computing pure Nash equilibria in congestion
games?

3-finding equilibria with minimum inefficiency?

4-Tim Roughgarden, in Communications of the ACM , posed the following open problem:

  to what extent is “incentive-compatible” efficient computation fundamentally less powerful
  than “classical” efficient computation?

Algorithmic game theory,
Communications of the ACM, Volume 53 , Issue 7,  (July 2010)

Also, these references contains some open problems:
Nisan, Roughgarden, Tardos, and Vazirani, editors. Algorithmic Game Theory. Cambridge
University Press, 2007.

T. Roughgarden. Algorithmic game theory: Some greatest hits and future directions. In TCS ’08, p. 21–42.


Can programming help one understand constructive mathematics? I have read about the principles of constructive mathematics, for example, the principle of excluded middle is not allowed, and now I want to do some exercises to increase my understanding of the subject. As a student in computer science, I have a background in programming, and I was wondering if programming in a language like Haskell would help in this endeavor? If not Haskell, then which programming language is best suited for learning constructive math?

Agda is a dependently typed programming language and/or proof assistant for Martin-Löf type theory. Programming in Agda feels very much like programming in Haskell. For example, inductive proofs are written as recursive functions with multiple equations that pattern match on the function arguments. So programming and/or proving in Agda is a good way to learn about constructive mathematics coming from a (functional) programming background.


Meaning of P=NP? depends on space-time geometry ? This question is about Page 125 of the book "Cellular automata in hyperbolic spaces: Volume 2" By Maurice Margenstern, Publisher Archives contemporaines, 2008.

http://books.google.com/books?id=eEgvfic3A4kC&pg=PA125

In the author's opinion, the question P=NP is ill-posed because in the hyperbolic setting P=NP or in the notation used later in the book Ph=NPh.

I don't know enough about complexity to know what to make of this, but it sounds interesting.

So the question is basically, what do you make of it?

Do his claims make sense ?

P=NP is a well-defined mathematical question which does not depend on space-time geometry. The question "which problems can be solved by computations that are tractable in this universe?" may depend on physics, and the answer does indeed appear to change in hyperbolic space or with quantum mechanics (e.g. quantum computing). However, this doesn't affect the P=NP question.

In fact, one of the first reactions of a theoretical computer scientist would have to your reference is: "What complexity class can be computed by a cellular automaton in hyperbolic space?" If you redefine complexity classes when you change to hyperbolic space, it becomes much harder to talk about this question.

And if you look later in the book, the author defines P$_h$ as problems solvable in polynomial time on a hyperbolic cellular automaton, and proves P$_h$=PSPACE (and NP$_h$=P$_h$=PSPACE), so even the author isn't really taking complexity classes to change in hyperbolic space.


How to efficiently read the theoretical computer science research papers? I am a computer science graduate student works in theory. The general advice is to go through the paper and then in the second or third round try to understand the detail. Read the abstract, introduction and then main results(just the results). I go through research paper multiple times, each time keep record of confused things. Many time I have to spend more than a week to understand even the bigger picture. Once I have bigger picture, then it is easy for me to understand the paper quickly.

Reading is taking quite long time. I am even about to graduate but it takes me couple of weeks to read a single paper. I have to many times present research papers in front of senior researchers. So I prepare, but as I mentioned that reading is taking too much time.

Is there any better way to speedup the reading? Efficiently means getting the overall idea with less number of passes.

Question :  How to efficiently read  the theoretical computer science research papers ?

How long it takes one to read a paper typically depends on what one wants to get out of it. I'll outline three levels of granularity.

Coarsest level: Relevant or not? When building up a list of potentially relevant literature, we often start with a handful of important papers, and then play the game -- who cites them? Whom do they cite? Iterating this game naively would cause an exponential explosion, so we prune the search tree. Briefly scan each candidate and classify it as relevant to my topic or not. This shouldn't take more than a few minutes.
User level: I've decided the paper is relevant, but does it contain a particular result that I need? Say, some variant of Chernoff bounds for non-iid random variables? Unbounded ones? This can take a bit longer, since not all results are stated in the form I'm looking for -- but shouldn't take more than an hour.
Expert level: The paper is relevant and has useful results; now I want to get an in-depth understanding and mastery of the technique. After all, this is the are I want to innovate in! This can take arbitrarily long, since it may require going down various rabbit holes of carefully reading previous results the present one relies on, and so on. No time limit here -- decide how badly you need this and settle in for the long haul.

Update, by popular demand. OK, the paper in question falls into category (3) and you're willing to devote serious time and effort into it. My first suggestion is to read the paper at the User Level, as specified in (2) above. Try first to understand what the main results are claiming, not how to prove them. Once you understand the claims, try to flesh out the proof outline. What basic strategy is being used? Is it a construction, an existence proof, etc -- try to "decompose" it into the various techniques you know. If it's an important paper, you might discover that it invents novel techniques -- make good note of these!

Sometimes short and seemingly elementary proofs are notoriously difficult to understand in an intuitive sense -- one such paper, I believe, is Haussler's "Sphere packing numbers for subsets of the Boolean n-cube with bounded Vapnik-Chervonenkis dimension". It's easy enough to follow the proofs step by step, but most beginner readers will still not be able to say much about the "big picture", even after the 2nd or 3rd reading. In such a case, it might be useful to seek out an expert (perhaps the author himself) to try to understand how he came up with the proof.


Animate a graphviz graph I'm exploring some graph algorithms, and would like to animate the graph change over time (e.g. when adding a heap node or balancing a tree).

Is there a nice way to animate a sequence of graphviz graphs?

I'm not sure this question is on-topic here, and would suggest StackOverflow instead. For what it's worth, I never heard that what you are asking for is possible, but you might obtain better-looking results with Ubigraph (check out the demos, they are amazing).


Complexity of transforming a balanced bipartite graph into regular graph? I'm studying certain graph editing problems and I'd like to determine the complexity of this problem:

Input: Balanced bipartite graph $G(A \bigcup B, E)$, $|A|=|B|=n$, integer $k$

Problem: Is there $r$ edit operations that transform the input graph into balanced bipartite $n/2$-regular graph ($r \leq k$).

An edit operation can be an addition of one edge or a removal of one edge (between sets $A$ and $B$).

  Has anyone seen this problem in the literature? Is there a polynomial time algorithm or is it $NP$-complete?

My main interest is in the case where $k \leq cn$ for some constant $c \gt 0$.

EDIT: One way to look at the problem is to find the minimum number of edit operations that transform an input of balanced bipartite graph $G(A \bigcup B, E)$ into balanced bipartite $n/2$-regular graph $G(A \bigcup B, E^{'})$. Notice that $n$ must be even integer.

Transform G into a weighted flow network N: connect the source s to all nodes in A by arcs of capacity n/2 and cost 0, connect all nodes in B to the sink t by arcs of capacity n/2 and cost 0, and connect each A-node u to each B-node v by an arc of capacity 1, with cost -1 if (u,v) is in G and 1 otherwise.

The maximum flow in N is n^2/2. Its cost can be written as -|E|+d, for some d >= 0. This d is the minimum edit cost of transforming G into a balanced n/2-regular bipartite graph with partition A,B.


Is there a theory of computation that takes failure and decay of the computation substrate into account? There are obvious differences between a Turing machine and a real computer. Not only is the latter finite in size, it is also prone to failures and it is made from decaying matter. The kind of framework I have in mind is this (but please excuse the handwavy vagueness): In some sense, (quasi)particles that constitute matter can be thought to perform computation: They have state that persists at least for some time (properties such as position, spin, charge, momentum) and they can change their state in feedback loops by interacting with other particles. The more elementary particles locally affect each other, the more complex the state and feedback loops can be. What kinds of computation we can perform on such a substrate depends on the configurations and rules that govern the particles, in particular, how many feedback loops they allow to simultaneously affect a local arrangement of particles. In this sense I'm looking for a framework that is analogous to the Chomsky hierarchy, i.e. in which the complexity of the system is successively extended to eventually build up to a notion of general computation. Is there something similar to this in the literature?

I'm not 100% sure what the question is about, but the title seems to ask about computation that allows failure. There is a lot of work on noisy (erroneous) computation in the sense that I think you are asking about. I don't have time to give a complete overview, but here are some pointers that may be of interest.

Distributed systems. This is probably by far the most developed field because the very definition of a distributed system is based on the possibility of (partial) faults. There are elaborate theories of DS depending on the chosen fault model, e.g. fail/stop or byzantine failure. See also the work on failure detectors.
Cryptography. This may seem a bit bizarre, but I think much of the field of cryptography can be seen as a form of extreme failure, with the adversary trying to undermine (in a general sense) the working of the system. You can think of the usual polynomially bound attacker as an case of failure model. This lead to things like secure multi-party computation as an algorithmic tool in the face of extreme adversity.
π-calculus: see (1) for a generalisation of Shannon-style information theory to interacting processes. I think the error model in (1) is unrealistic, because it does not cater for the situation where an error converts a free into a bound name or vice versa.
Turing machines: see (2, 3, 4).
Cellular automata: various researchers have added failure models, sorry no references at the moment, maybe look at work by  P. Gacs.
λ-calculus: see (6).
Assembly language: see (5, 7).
Quantum computation: is all about error correction, I'm not qualified to say more on this.
An increasingly important subfield of computation is the use of probabilistic process calculi to model chemical reactions. Have a look at Luca Cardelli's recent work.

Note also that this line of thinking is very old: J. von Neumann wrote about this in 1956 [8]. Maybe even more impressive C.-A. Petri invented Petri-nets in August 1939 at the age of 13 for the purpose of describing chemical processes.

M. Ying, Pi-Calculus With Noisy Channels.
I. Capuni, P. Gacs, A Turing Machine Resisting Isolated Bursts Of Faults.
I. Capuni, Fault-tolerant Turing Machine.
E. Asarin, P. Collins, Noisy Turing Machines.
J. Chang, G. A. Reis, D. I. August, Automatic Instruction-Level Software-Only Recovery.
D. Walker, L. Mackey, J. Ligatti, G. A. Reis, D. I. August, Static Typing for a Faulty Lambda Calculus.
F. Perry, L. Mackey, G. Reis, J. Ligatti, D. I. August, D. Walker, Fault-tolerant Typed Assembly Language.
J. von Neumann, Lectures on Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components.


Scoring set of points based on clustering I have a sparse set of points with unpredictable locations. I need a way of "scoring" each set of points such that clustering is rewarded. My working case is actually one dimensional, but a two dimensional use case may come up later.

Here's an example:
Data A contains points at -2, 1, 5, 7. Data B has points at -10, 0, 20, 6. A and B are independent of each other and have not had clustering applied. Ideally, after clustering, A would have clusters (-2, 1) and (5, 7). There is more clustering in A so I would like it scored higher. Bonus points if the algorithm allows the points to have variable values so that in some cases, if points are 100 units apart but each of the points has a high value, that set of points will rate higher than a set of points 10 units apart with much lower values.

EDIT: My current idea is to use a clustering algorithm to figure out the center of each cluster and it figure out which points occupy the cluster. I would then score each cluster finding the mean of the distances squared (EDIT: Apparently this is called "variance.").

For the one dimensional case, you can use the variance.

For the higher dimensions, you can generalize the variance by first computing a mean point and then computing the sum of the square of the distance between each point and the mean squared followed by a division the sum by the number of points. This division by the number of points (which also happens in the variance) is the difference between the solution you have suggested and what I am recommending.  This division allows for a fair comparison of clustering between sets of points of different sizes.

For $n$ points with mean point $m$, the computation is $\frac{1}{n} \sum_{i=1}^n \operatorname{dist}(m, p_i)^2$.


Do buyers bidding for sellers and sellers bidding for buyers produce equivalent outcomes? Google adwords is a well known application of algorithmic game theory. It has a system wherein  buyers of ad placements bid to put their ads up on various sellers websites, then pay the second bid below them.

If this system were turned on its head, and sellers of ad placements (websites, in other words) bid to be the cheapest space (relative to their quality) for buyers of ads and were paid the second cheapest price instead, would this result in the same prices being paid for ad placements?

If these two scenarios are not equivalent, where is the breakdown?

In general, is there any duality between these problems?

Generally speaking, auctions can go both ways in a dual manner: you can sell something via an auction among buyers or you can buy something via a procurement auction among possible providers (sellers).  The asymmetry usually comes from where the competition lies: the auctioneer holds a "monopoly" while the bidders compete with each other.

In the example of ad auctions we usually view the advertisers as having unlimited demand for "impressions" and thus there is no effective competition between websites which each can be viewed as having a monopoly over the impressions it delivers.  More realistic models may take into account some limits on the demand of advertisers for impressions (e.g max impressions or budget limits) in which case taking competing websites into account too would take us out of the usual auction model and into a two-sided market scenario.

Generally speaking there is no reason for the prices of a buyer-led auction to be equal to those from a seller-led one.  Consider even the case of one buyer and one seller: certainly the side running the "auction" (which in this case is just setting a transaction price for the other to take or leave) can set it at the others' value in order to optimize for himself.  A related example would be the stable-marriage problem where a "men-propose algorithm" produces a man-optimal matching, while a "women-propose algorithm" produce a women-optimal one.


Existence of graphs of every order related to Barnette’s conjecture Consider the class C3CBP of $3$-connected cubic bipartite planar graphs. They form the class on which the (in)famous Barnette’s  conjecture is based. My interest in C3CBP graphs is somewhat orthogonal to this:

My questions are:

Does there exist a C3CBP graph on $n$ vertices for every even $n > n_0$ where $n_0$ is some small constant?
Does there exist a C3CBP graph without any non trivial automorphisms on $n$ vertices for every even $n > n_1$ where $n_1$ is some small constant?

Notice that $3$-connected planar graphs have only at most linear sized automorphism groups so the second question is natural.

I need the existence and explicit construction of such graphs in an algorithmic problem apparently unrelated to Barnette’s conjecture.

I have a partial solution, with constructions for the first question and for the second question when $n = 2\ (\text{mod}\ 4)$.

Here are constructions for $n = 8$ and $n = 14$. These generalise to constructions for $n = 0\ (\text{mod}\ 4)$ and $n = 2\ (\text{mod}\ 4)$, by taking any square, for example 1,2,3,6 in the second construction, and replacing it with a ladder like shown in the third image.

For the second question, the $2\ (\text{mod}\ 4)$ construction has no nontrivial automorphisms when $n \geq 18$, as we can recover the labeling. First find the added ladder and the pairs 1-2 and 3-6. To discern between them, note that the nodes 1 and 2 are not in any four-node cycle except in the ladder, while 1 and 6 are. Similarly 2 and 3 are not in a four-node cycle except in the ladder, while 1 and 6 are. Then you can uniquely discern 4 (only non-ladder node connected to 1), 5 (same for 6), 8 (only node connected to 3 and 5) and so on.


What are good set size estimation algorithms for small sets (around 10-50 elements)? I'm trying to implement an online distinct counting algorithm, and I have thousands of small sets of 32 bit IP addresses whose sizes I want to estimate with high accuracy (1-5%).

I came across quite a few algorithms such as linear counting$^1$, PCSA$^2$, HyperLogLog$^3$ etc. According to their papers, their space needed varies with relative error as $1/\epsilon^2$. For my purpose, this seems really wasteful e.g., PCSA needs > 10,000 bits when the set size is 50 and $\epsilon$ is 1%.

Is there any reason why in practice, we may not need that many bits? Is there any algorithm that uses little space to estimate the size of small sets with high accuracy?

Thanks!

References:

[1] Linear Counting: Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor. 1990. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst. 15, 2 (June 1990), 208-229. DOI=10.1145/78922.78925 http://doi.acm.org/10.1145/78922.78925

[2] PCSA: Philippe Flajolet and G. Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31, 2 (September 1985), 182-209. DOI=10.1016/0022-0000(85)90041-8 http://dx.doi.org/10.1016/0022-0000(85)90041-8

[3] HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm, by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Proceedings of the AofA07 Conference (Analysis of Algorithms-2007), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AH, pp. 127--146 (2007).

2^32 is only 4 billion; and doubtful you will saturate even a small fraction of that if you are watching IPs. Just store it all. A radix tree will compact as it saturates since you can flag entire subdomains as saturated.


What are the relationships between Functional Reactive Programming, Automatic Differentiation, Self-Adjusting Computation and Partial Evaluation? Self-adjusting computation seems to be related to all of the other topics, but I would like to get a clearer sense of how they all relate. For example, do any of them subsume or obsolete any of the others?

One might also throw Incremental Computing into the mix, of which Self-adjusting computation is presumably a special case.

I essentially agree with Dave's comment: these are lots of different things (and I only feel remotely competent to talk about three of them).

However, from the perspective of a consumer of functional programming research, the three things I know something about probably feel related, because they all are ways of making functional programs deal with inputs that change over time. For instance:

Functional reactive programming - consider this when you want to write a program as if you're taking, as input, list of all the user events that's ever happened, but you still want the program to behave reasonably as you feed it inputs over time. An underlying assumption is therefore that the data about past events won't change, and that the only changes to the input will be the addition of new events that happened after all the old events.
Partial evaluation - consider this when your program neatly cleaves into two parts, and you want to recompute, over and over, part 2 based on the outcome of part 1. This assumes your code has the property that the difference between "part 1" and "part 2" are known when you write the code, so an underlying assumption is that the data that stays the same (the data part 1 computes with) and the data that changes (the data part 2 computes with) are known in advance.
Self-adjusting computation - consider this when your program's execution flow is not neatly divided into parts, but involves a lot of decisions based on data. Self-adjusting computation is designed to react to small changes in inputs by only redoing computation that was based on modified data. Therefore, an underlying assumption is that the particular changes can't be anticipated in advance.

[Update] In practice, the challenges associated with each of these three things are different: it doesn't necessarily make sense to talk about any of them as special cases of the others. However, as Jake points out below, there are (slightly restricted) libraries of functional reactive programming that are implemented on top of self-adjusting computation primitives. Similarly, it might be possible to effectively implement something like partial evaluation on top of self-adjusting computation, since SAC makes the very few a priori assumptions about its input data.


Are there non trivial 2-basis of a 2-connected planar graph? Based on MacLane's planarity criterion, planar graphs are exactly those that admit a 2-basis. Such basis can be easily obtained considering $|E| - |V| + 1$ of its faces. Denoting those basis as trivial bases, my question is: are there examples of non-trivial 2-basis of a 2-connected planar graph?
A non-trivial basis should contain at least one cycle surrounding at least two faces. I could neither find an example nor prove their inexistence.
Any help would be highly appreciated.

The cycles of a 2-basis (and the one leftover cycle formed from the symmetric difference of all these cycles) necessarily form the faces of a planar embedding of the graph. First, all edges of the graph belong to some cycle by 2-connectivity. Second, the edges appearing only once in the basis cycles must form a single cycle, else their subgraph would have multiple cycles not all of which could be represented by the basis. So adding the leftover cycle produces a set of cycles that cover every edge exactly twice. Third, one can form an embedding of the graph onto a topological surface by making a polygon for each cycle and gluing these polygons together. One can use 2-connectivity again to show that the surface is actually a manifold: if multiple patches of surface touched each other locally at a single vertex, one could find a cycle passing from one patch to another through that vertex which could not be represented by the basis, because any basis representation would produce evenly many edges into that vertex within each patch of surface. And fourth, every cycle in the graph must be a boundary of a subset of the surface (it is the boundary the union of the basis cycle polygons whose symmetric difference is the given surface cycle). But this can be true only of a topological sphere, so the embedding is planar.
However, a planar graph that is 2-connected but not 3-connected can have multiple embeddings and when it does, the cycles of any given 2-basis may not be faces of a different embedding. As an example, $K_{2,4}$ has three combinatorially-distinct embeddings, for the three ways of choosing which pairs of degree-two vertices are non-co-facial, and for any particular embedding it is possible to find a cycle basis using one or both of the two non-facial cycles. (The degree-two vertices of this example can be replaced by two triangles connected edge-to-edge to make an example where all degrees are greater than two.)


Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization? First of all, I want to make clear that my question is about algorithms. I'd like to know if there are any algorithms with provable guarantees in the context of manifold learning (or manifold regularization).

I do not necessarily require that guarantees are with respect to generalization. However, those are always nice though but I just want to emphasize that the main focus of the question is about algorithms (with guarantees), not necessarily about generalization.

What I do want is that given a finite sample of data (maybe mixed with labeled and unlabeled data) if we can provably learn. For example, are there algorithms that guarantee that we learn the manifold or its structure? Or maybe, are there algorithms that theoretically guarantee better prediction with the manifold assumption? Any algorithm with provable guarantees is good.

To be clear of what I mean with provable guarantees I will give a couple of examples of scenarios/problems (and algorithms) where there are provable guarantees for (learning) algorithms.

Consider the non-negative matrix factorization problem where we have:

$$M =  AW$$

s.t. A and W are $m \times k$ and $k \times n$ and are required to be entry-wise nonnegative. In fact, lets suppose that the columns of M each sum to one. One can interpret this problem as follows. Each column is a document from our model. Its generated as a convex combination from topics (i.e. the columns of A). The combination is specified by the columns of W. Can we recover the best non-negative factorization of the model? It turns out that Vavasis proved its NP-hard 1. However, under the separability condition on the topics, one can show that there exists a polynomial time algorithm to compute such a non-negative factorization (of minimum inner-dimension). So this scenario has two things that are interesting:

We can learn the true model (the negative factorization) from the (samples) documents (with some probability conditions)
There a polynomial time algorithm for it.

The algorithm for this is based on finding the "Anchor words" (i.e. the highly technical words for each document) and then taking advantage of that to find the factorization. The some of the details for this can be found on this monograph on algorithmic aspects of machine learning.

This is exactly the type of thing I am interested in, on learning algorithms with some provable guarantees under some conditions. For more example, the following monograph has many that are appropriate examples. To name the monograph explains tensor methods, ICA, alternating minimization, mixtures of gaussians, matrix completion, phylogenetic trees, noisy parity and more!

References:

1 S. Vavasis. On the complexity of nonnegative matrix factorization. SIAM
Journal on Optimization, pages 1364-1377, 2009.

It depends what you mean by "learn[ing] the manifold", but here are a few papers that present some algorithms and a theoretical analysis:

Isomap (see tech report by Bernstein, de Silva, Langford and Tenenbaum)
Random linear projections (see paper by Ken Clarkson)
Nash-type embedding (see paper by Nakul Verma)
Maximum variance unfolding (see arXiv:1209.0016)

In terms of using/exploiting manifold structure to help learning or estimation, there are many such results. For example, many of the papers by Misha Belkin and Samory Kpotufe explore this direction.


Proof that the graph optimization problem is NP-hard I'm trying to prove that the following optimization problem is NP-hard:

Given a graph $G=(V,E)$, non-negative vertex weight functions $w(v)$ and $s(v)$, and a non-negative edge weight function $t(u,v)$, find a subset of vertices $S \in V$ that minimizes the function $C$:

$$C = \sum_{v \notin S}{w(v)} + \sum_{v \in S}{s(v)} + \sum_{(u,v) \in E:u \in S, v \notin S}{t(u,v)} $$

$$w(v) \geq 0, s(v) \geq 0, t(u, v) \geq 0$$

In other words, I'm trying to bipartition the graph and minimize the sum of vertex weights and edge weights across the cut, but the vertex weights are different depending on which "side" of the partition they are.

I've tried to reduce the max-cut problem to this by somehow minimizing the complement graph, also tried the sparsest cut, but the second weight function always seems to be problematic. Obviously, assuming that $s(v) = 0$ or $s(v) = w(v)$ makes the problem trivial, so there must be some solution that I'm missing. Or maybe the problem isn't NP-hard at all?

Any help is appreciated :)

Edit: restrict to non-negative weights

This problem is in P, it can be reduced to the Minimum cut problem.

The graph construction is as follows - Add a source and a sink vertex. For each vertex $i$, add an edge with cost $w(i)$ from source to $i$ and another edge of cost $s(i)$ from $i$ to sink. Also add edges from $i$ to $j$ of cost $t(i,j)$ for every pair of vertices $i$ and $j$.

The cost of the cut from source to sink in this graph with set of vertices $S$ along with source in one side of the cut exactly corresponds to your function $C$


Can we do joins in NC? Suppose we want to join two relations on a predicate. Is this in NC?

I realize that a proof of it not being in NC would amount to a proof that $P\not=NC$, so I'd accept evidence of it being an open problem as an answer.

I'm interested in the general case as well as specific cases (e.g. perhaps with some specific data structure it can be parallelized).

Some specifics:

We could consider an equijoin $A.x = B.y$. On a single processor, a hash-based algorithm runs in $O(|A|+|B|)$ and this is the best we can do since we have to read each relation
If the predicate is a "black box" where we have to check each pair, there are $|A|\cdot|B|$ pairs, and each one could be in or not, so $2^{ab}$ possibilities. Checking each pair divides the possibilities in half, so the best we can do is $O(ab)$.

Could either of these (or some third type of join) be improved to $\log^k n$ on multiple processors?

(Reposted from here as per site policy.)

$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.


Are there any heuristics that works solely on graphs? I'm exploring heuristics in A* and apparently all heuristics require coordinates of all the locations to calculate a h-cost. This is fine if you are working on grids, but what if you need to work solely on graphs where "traveling in a straight line" doesn't make sense at all?

Are there any heuristics that works solely on graphs (i.e. without requiring coordinates of the locations)?

There are known pre-processing methods that rely solely on the graph representation itself (and not on any kind of geometric embedding) to establish good heuristics for A*. Perhaps the most well-known example in recent research is called ALT (A* + Landmarks + Triangle-Inequality). Here is one of the original papers on this topic: https://www.microsoft.com/en-us/research/publication/computing-the-shortest-path-a-search-meets-graph-theory/

There has since been much further research on expanding and improving upon the heuristics used by the ALT technique. A simple search on this topic should turn up plenty of more-recent and relevant results (I tried posting links to some of them here, but the system has unfortunately limited the number of links I can provide in my response).

Aside from ALT, there has also been subsequent research on alternative techniques for constructing other similar heuristics purely from the graph representation (which is directly compared to ALT as well): http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/view/5372/5180


Is it possible to create a machine learning classifier to generate Mock interfaces for systems testing? I'm investigating whether it is feasible to be able to learn a system interface by watching network traffic (assuming the usual problems are solved e.g. encryption etc)

I haven't been able to find any literature on this - but there might be a cross-discipline piece of work which could assist.

The main purpose here would be to allow complex enterprise systems to be refactored independently. A simple replay of data doesn't always work because we want to learn the request-response interface - though e.g. something like a market trade having multiple fills is an example of very complex orchestration that might make the whole thing unpractical.

A classical result from automaton theory shows that even the problem of finding minimum-size DFA consistent with given positive and negative samples is NP-hard. This was shown by Gold in 1978. Your problem is much harder, as in practice you would have to learn data relationships in addition to any finite-state control of the system interface.


Upper bounds on the length of longest simple path in non-Hamiltonian graph? Hamiltonian cycle problem is $NP$-complete on cubic planar bipartite graphs. I'm interested in upper bounds on the length of the longest simple path in non-Hamiltonian cubic planar bipartite graphs.

  What is the best known upper bound on the length of longest simple path in non-Hamiltonian cubic planar bipartite graphs?

Edit: Also, I am interested in non-trivial lower bounds on the length of the longest simple path in this class of graphs.

There exist cubic bipartite planar graphs in which the longest path has length only $O(\log^2 n)$:


Useful equivalence relations on $X^{\ast}$ (like the Nerode and syntactic equivalence relations) I want to have an overview of all the meaningful equivalence relations defined on $X^{\ast}$, in particular when the languages in question are regular. They typically arise in connection with the minimization of automata. Further I want to know all the relations among them. Below I write what I know, I encourage everyone to add useful facts to this list, give other equivalence relations and how they relate to the given ones!?

Common equivalence relations on $X^{\ast}$ are
\begin{align*}
 u \equiv_L v & :\Leftrightarrow
  \forall w \in X^{\ast} : uw \in L \leftrightarrow vw \in L \\
 u \equiv_R v & :\Leftrightarrow
  \forall w \in X^{\ast} : wu \in L \leftrightarrow wv \in L \\
 u \equiv_S v & :\Leftrightarrow
  \forall w_1, w_2 \in X^{\ast} : w_1uw_2 \in L \leftrightarrow w_1vw_2 \in L
\end{align*}
If we have some deterministic and complete automaton $\mathcal A = (X,Q,\delta,q_0,F)$ with $L = L(\mathcal A)$, then every $u \in X^{\ast}$
corresponds to a function $\varphi_u : Q \to Q$. Then we can define
$$
 u \equiv_A v :\Leftrightarrow \delta(q_0, u) = \delta(q_0,v) \Leftrightarrow \varphi_u(q_0) = \varphi_v(q_0).
$$
Also for states $q, q' \in Q$ we could define
$$
 q \equiv q' :\Leftrightarrow \forall u \in X^{\ast} : \delta(q, u) = \delta(q',u) \Leftrightarrow \varphi_u(q) = \varphi_v(q')
$$
and by incorporating the final states (and thereby fitting it more to the conrete language $L$) we could define
$$
 q \equiv^L q' :\Leftrightarrow \forall u \in X^{\ast} : \delta(q, u) \in F \leftrightarrow \delta(q', u) \in F.
$$
And if we have some recognizing monoid $M$ with homomorphism $\varphi : X^{\ast} \to M$ we could define
$$
 u \equiv_h v :\Leftrightarrow h(u) = h(v).
$$
We have (the automaton is arbitrary)
\begin{align*}
 u \equiv_L v & \Leftrightarrow \delta(q_0, u) \equiv^L \delta(q_0,v) \\
 u \equiv_R v & \Leftrightarrow \forall q \in Q : \delta(q, u) \in F \leftrightarrow \delta(q, v) \in F \\
 u \equiv_S v & \Leftrightarrow \forall q \in Q : \delta(q, u) \equiv^L \delta(q,v) \\
 u \equiv_h v & \Rightarrow u \equiv_S v \\
 u \equiv_S v & \Rightarrow u \equiv_L v \land u \equiv_R v \\
 u \equiv_A v & \Rightarrow u \equiv_L v \\
 \varphi_u = \varphi_v & \Rightarrow u \equiv_S v \\
 u \equiv_S v & \Leftrightarrow \forall q \in Q : \varphi_u(q) \in F \leftrightarrow \varphi_v(q) \in F
\end{align*}
And we have that the syntactic monoid is precisely the transformation monoid of the minimal automaton (which could be constructed with $\equiv_L$). Also the above notions could be described in terms of language quotients $u^{-1}L := \{ w : uw \in L \}, Lu^{-1} := \{ w : wu \in L \}$ (and the minimal automaton could also be constructed with the quotients $u^{-1}L$) or the sets $L_q(\mathcal A) := (X,Q,\delta,q,F)$ (i.e. the language accepted if $\mathcal A$ is started at $q$).

The article by Thomas Colcombet on Green's Relations and Their Use in Automata Theory might be interesting for you. These relations are very common in the algebra of semigroups.

See also Section 2.8 in Chapter 10 of the Handbook of Formal Languages.


Complexity of reversible Circuit Value I am wondering what is known about the complexity of the reversible Circuit Value Problem (rCVP) and the corresponding reversible Satisfiability problem (rSAT).

More precisely: a circuit $B^n\rightarrow B^n$ on $n$ boolean values is reversible if it computes an invertible function.

The rCVP problem is: given a reversible circuit on $n$ boolean values and $n$ inputs, what is the value of the output?

The rSAT problem is: given a reversible circuit, what is the input that yields the output $1,\dots,1$? (function problem, see comments)

As subcases of their non-reversible versions (CVP and SAT) these problem are respectively in Ptime and NP.

My question is rather about hardness: is rCVP Ptime-complete? Is rSAT NP-complete? I am no specialist of this and looked for a statement of the result, but found nothing so far. I read that one can encode any usual circuit by a reversible circuit using Toffoli's gates, but the is size of the reversible circuit one obtains doing so polynomial in the size of the initial circuit?

For rCVP, we can reduce the usual CVP problem to rCVP as follows. Given a circuit $C$ on $n$ inputs, produce a circuit $C'$ that on input $x=(x_0,x_1,\dots,x_n)$ outputs $C'(x)=(x_0 \oplus C(x_1,\dots,x_n),x_1,x_2,\dots,x_n)$.

For rEQ, we can similarly reduce the UNSAT problem (modifying the suggestion of Marzio De Biasi). Namely, given a formula $\varphi$ on $n$ variables, let $C_1$ on input $x=(x_0,x_1,\dots,x_n)$ output $(x_0 \oplus \varphi(x_1,\dots,x_n),x_1,\dots,x_n)$ and $C_2$ simply output $x$.


What is the first name of Bainbridge? Bainbridge coauthored the paper `Functorial Polymorphism' with Freyd, Scedrov and Scott (DOI). What is his/her first name?

I knew him as a mentor back in the day.  In person he went by "Stewart Bainbridge".  Which also answers the question asked by @a3nm about what the "S" stands for.  I never heard about the "Edwin" so presumably it was a given name he wasn't fond of.


Why does Dinur's proof of the PCP theorem fail to work for unique games? What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap amplification / alphabet reduction while preserving the fact that the problem is a unique label cover instance?
Obviously, the proof still holding essentially unchanged would contradict the fact that we know there is a subexponential time algorithm for unique games, unless all of NP has subexponential time algorithms. However, I'm trying to explicitly understand the critical step where the argument fails.
Since I'm trying to understand to the heart of the issue, I'd prefer to disregard "minor" technical assumptions like ensuring the graph is d-regular, an expander, etc. unless those are actually the main thing preventing the proof from going through.

The powering step fails. After the powering, each vertex is labeled with a neighborhood of the original graph. each edge checks that its endpoints agree on the intersection of their neighborhoods, and that this labeling satisfies the edges in this intersection. However, the edge cannot check anything about part of the labeling that lies outside the intersection of the neighborhoods, and therefore cannot enforce the uniqueness property.


Major unsolved problems in distributed systems? Inspired by this question, what are the major problems and existing solutions which needs improvement in (theoretical) distributed systems domain.

Something like membership protocols, data consistency?

See, for instance, Eight open problems in distributed computing.