Is Bayes optimal RL of a finite set of DFAs feasible? Let $Q$ be a finite set of states, $\Sigma$ a finite alphabet, $q_0\in Q$ the start state and $F\subseteq Q$ the set of accepting sets. Let $\{\delta_k:Q\times\Sigma\rightarrow Q\}_{k=1}^n$ be a set of $n$ possible transition functions and $m$ a fixed natural number. Consider the following problem: find a word $w\in\Sigma^m$ s.t. the DFA accepts $w$ with maximal probability, assuming that the transition function is chosen randomly from a uniform distribution over the $\delta_k$, and that you are allowed to observe the state transitions resulting from $w_1\ldots w_k$ before choosing $w_{k+1}$ (but you don't know which transition function was chosen). In other words, we are doing one-shot reinforcement learning for a deterministic MDP where $\Sigma$ is the set of actions, and the reward is $1$ if we end up in $F$ after $m$ actions and $0$ otherwise.

Given a policy $\pi: (\Sigma \times Q)^{< m} \rightarrow \Sigma$ (that decides which action to take after observing a given history), and some choice of $\delta_k$, we get a particular history $h_{\pi,k}\in(\Sigma\times Q)^{m}$. In fact, the collection of the $h_{\pi,k}$ for $k$ from $1$ to $n$ gives us a compact description of $\pi$: in order to implement $\pi$, we just need to look at the current history $h\in(\Sigma \times Q)^{< m}$ and find $k$ s.t. $h$ is a prefix of $h_{\pi,k}$ to know what action to take next. This description is of size $O(nm|\Sigma||Q|)$, as opposed to a lookup table for $\pi$ which would be of size exponential in $m$. In particular, an optimal policy (i.e. a policy which maximizes the probability of the DFA accepting) also has such a compact description.

Is it possible to find a compact description (as above) of an optimal policy in time polynomial in the size of the problem and $m$?

Here I'm assuming that the $\delta_k$ are given explicitly as lookup tables, and $F$ as a list of states (where states and actions are represented by numbers). For a negative answer, you can assume any standard complexity-theory conjecture.

Even determining whether there is a policy which always succeeds is NP-complete, by a reduction from constructing optimal decision trees (Hyafil and Rivest, Constructing Optimal Binary Decision Trees is NP-complete). We interpret the word $w$ as a sequence of $m-1$ yes/no questions about $k$, drawn from a list of allowed questions, followed by a guess for the value of $k$. It's easy to construct state machines $\delta_k$ which keep a counter of how many questions have been asked so far together with the answer to the most recent question asked as their state, and then accept or reject based on whether the guess at the end is correct.


Abstract algebra for Theoretical Computer Scientists I have a reasonable undergrad math education but have never been 100% comfortable with abstract algebra (the mathematics of groups, rings, fields etc. ).  I think this was partly as I needed to see applications and any that I could find were in physics, not CS.  As my interest is really CS, are there any materials available now (online drafts, lecture notes, videos, books) that cover abstract algebra from the point of view of applications in CS and in particularly algorithms/theory?  I am happy for these applications to be entirely theoretical but they shouldn't assume any pre-existing abstract algebra knowledge.

I am pretty sure that were these resources to exist, they would be appreciated by  a large number of CS researchers.

You could try the notes from Madhu Sudan's course: Algebra and Computation


Is any computational problem a search problem? I was looking for a formal and general definition of a computational problem (and major subclasses thereof e.g. decision, function and search problems). But, given the definitions I have found thus far, I fail to see how the definition of a 'search problem' is any less general than that of a general 'computational problem', as both seem to correspond to an arbitrary binary relationship.

Concretely,

I have found the following definitions of a computational problem:

[source: http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf]

  In a computational problem, we are given an input and we want to
  return as output a solution satisfying some property: A computational
  problem is then described by the property that the output has to
  satisfy given the input.

[source: https://en.wikipedia.org/wiki/Computational_problem]

  A computational problem can be viewed as an infinite collection of
  instances together with a solution for every instance.

I interpret both to imply that a computational problem corresponds to a relation $R \subseteq X \times Y$ between (representations of) problem instances $X$ and (representations of) solutions $Y$.

Under this definition, the subclasses of decision (Y={yes,no}) and function problems (R is a function) make sense.

However, the definitions of a search problem (in the same articles) confuse me, as they seem to be equivalent:

[source: cs.stanford.edu]

  Thus, a search problem is specified by a relation $R \subseteq\{0,1\}^∗\times\{0,1\}^∗$.

[source: wikipedia.org]

  a search problem is a type of computational problem represented by a
  binary relation

[EDIT]

After some reflection, one candidate for being more general than search problems would be optimization problems that do not have to be solved optimally (otherwise they would reduce to 'finding an optimal solution', i.e. a search problem), as they, besides capturing the 'desirability' of a solution, also capture the'desirability' thereof (some preference relation on Y), a concept not corresponding to any $R \in X \times Y$.

In general, I would answer my own question as follows:
As long as you think of problems in terms of 'acceptable' outputs given inputs, we're dealing with search problems by definition.
Once we need to a more subtle ('fuzzy')/general notion than 'acceptability', such as 'desirability' (e.g. non-exact optimization problem above) a binary relation does no longer suffice.

Is this reasoning sound?

Also, do you know of any sources I can cite (beyond wikipedia, PlanetMath and handouts...) for definitions of 'computational problem' and 'search problem'?

The linked PDF, "Handout 2
 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems":

Decision problems
Search problems
Optimization problems
Counting problems

As the document notes at the beginning, it focuses on the first two: decision and search problems.

  In this course we will deal with four types of computational problems: decision problems, search problems, optimization problems, and counting problems. For the moment, we will discuss decision and search problem.

However, the document seems to talk about decision problems and search problems as though they were conceptually distinct from each other.  It also fails to mention the mapping between them, which is simple and commonly known (PlanetMath):

  A relation $R$ can be viewed as a search problem, and a Turing machine which calculates $R$ is also said to solve it. Every search problem has a corresponding decision problem, namely $L(R)=\{x\mid\exists yR(x,y)\}$.

In short, you're correct to realize that decision and search problems are two sides of the same coin.  You're also correct that it's weird that the document doesn't appear to mention this obvious fact.

Personally, I'd tend to see these terms differing in connotation.  This is, while they can often be mapped to each other, referring to a particular problem as one type rather than another suggests a perspective on how to see that problem, rather than asserts that that problem can't be cast to another type.


Simulation of deterministic turing machines What are the best known upper and lower bounds for simulating t steps of certain models of deterministic turing machines (1 tape, 1 tape with read only input tape, 2 tape, multi tape, with/without random access to memory)?

Edit: I am mainly interested in efficient simulations with the same or with weaker models. Simulations with stronger models are quite efficient in most of the cases.

For what regards (apparently) "weaker" models, one of the recent new results that I saw is that a deterministic Turing machine can be efficiently simulated by a 2-tag system:
Damien Woods and Turlough Neary, On the time complexity of 2-tag systems and
small universal Turing machines (FOCS 2006)

...

Theorem 1: Given a single tape deterministic Turing machine $M$ that computes in time $t$ then there is a 2-tag system TM that simulates the computation
of $M$ and computes in polynomial time $O(t^4(\log t)^2)$.

...

Corollary 1: The small UTMs of Minsky, Rogozhin and others are polynomial time, $O(t^8(\log  t)^4)$, simulators of Turing machines.


Topological sort with alternative choices of predecessors I have a family of directed graphs over the same set of nodes $V$ defined as follows.

Each node $v \in V$ has $k_v$ alternative choices for its set of predecessors. In other words, I am given a relation $\rho\colon V \to 2^{V}$ such that $|\rho(v)| = k_v$ (where $\rho(v) = \{S \subset V \mid (v, S) \in \rho\}$, I'm abusing the relation notation a little bit). This relation induces a family of graphs: if we pick one predecessor set $S_v \in \rho(v)$ for each $v$, we obtain a fixed set of edges $E = \{ (u, v) \mid u \in S_v \}$ for the entire graph.

There are $\prod\limits_{v \in V} k_v$ such possible graphs, some of them are acyclic, some are not. I want to find at least one acyclic graph among these possibilities, and sort it topologically. Can it be done in polynomial time (i.e., faster than enumerating all possible combinations of choices explicitly)?

(As an illustrative application, imagine a package manager where some packages depend on either one of these other packages, because they all provide similar capabilities.)

Yes, a valid ordering and a graph that goes with it can be found in polynomial time. I think it's easier to understand this if you look for the topological ordering first, and the graph second.

What you are trying to find is an ordering of the vertices with the property that, for each vertex $v$, at least one of its predecessor sets appears in its entirety before $v$. This can easily be found by a greedy algorithm if it exists:

Initialize an empty ordering and then, while the ordering does not include all of the vertices:

Find a vertex $v$ such that one of the predecessor sets of $v$ has already been included in the ordering
Add $v$ to the end of the ordering

If this succeeds, you have found your topological ordering, and you can choose the graph to be the one that connects each $v$ to its previously-appearing predecessor set. If it fails, then you have found a subset $S$ of vertices (the ones not yet added) so that every predecessor set of a vertex in $S$ contains another vertex in $S$, blocking any solution from existing.

Incidentally, the class of valid orderings for a problem of this type form an antimatroid, and all antimatroids can be represented in this way. This idea that you might have more than one way of satisfying the prerequisites for an object but that, once satisfied, a vertex can never become un-satisfied, is the defining principle of an antimatroid.


Efficient algorithm for updating a parse tree Let's say I have a big block of code which I already have lexed and parsed.
Suppose that just one character changes; I would want to update my parsing, but since the modification is very small compared to the whole thing, I would like to know if it's possible not to parse the whole thing again, but if there are algorithms to determine the range to re-parse, and to properly deal with moving token boundaries.

Thanks in advance!

As per @Agos request, I turned the comment into an answer.

First, I must admit that I'm not really knowledgeable in this field. Yet I suggest you read the papers Building friendly parsers and Efficient and Flexible Incremental Parsing to have a view of what algorithms were used for incremental parsing before 2000.

For updated treatments, you may take a look at these papers:

Lazy functional incremental parsing (2009)
Practical, incremental, noncanonical parsing: Celentano's method and the Generalized Piecewise LR parsing algorithm (2006)
Incremental validation of XML documents (2004)
Incremental parsing in language-based editors: user needs and how to meet them (2001)
Incremental Parsing and the C Preprocessor (Couldn't find the PDF anywhere. It is from Google cache.)

More info: There are (at least) two approaches to parsing/compilation:

The batch approach, in which the whole block of code is parsed/compiled.
The incremental approach, in which the document is first parsed/compiled in the batch mode, and then changes are detected and the minimal re-parsing/re-compilation is applied. This approach not only increases the parse/compilation speed, but also helps in IDE nifty features such as background compilation, which is related to lazy compilation. (You can also search about commercial features such as the  IntelliSense).


Stronger version(2) of Isolation Lemma for linear forms Klivans and Spielman give isolation lemma for linear forms in their paper Randomness Efficient Identity Testing of Multivariate Polynomials. Lemma 4 in this paper says.

  "Let $C$ be any collection of distinct linear forms in variables $z_1\ldots z_l$
  with coefficients in range {$0,\ldots, K$}.
  If $z_1,\ldots,z_l$ are independently chosen uniformly at random from set $S = \{0\ldots Kl/\epsilon\}$,
  then with probability greater than 1-$\epsilon$,
  there is a unique form of minimal value at $z_1,\ldots,z_l$".

Is there a stronger version of this lemma? Namely, can we choose set $S$ to be of size sublinear in $K$? Assume that $l$ is small compared to $K$.

Let me introduce a different notion of "stronger". Suresh Chari, Pankaj Rohatgi and  Aravind Srinivasan give Generalized isolating lemma in their paper Randomness-Optimal Unique Element Isolation, With Applications to Perfect Matching and Related Problems. Lemma 2[Generalized isolating lemma] in this paper says

  Let ($S$, $\mathcal{F}$) be any set system  and let $Z$ be a give upper bound on the size of unknown family $\mathcal{F}$. There is a simple scheme which uses $O(\log Z + \log N)$ random weights to assign integer weights to the $x_i$'s in the range $[0,N^7)$ such that with probability atleast $\frac{1}{4}$, there is a unique minimum weight set in $\mathcal{F}$.
  Here $S=\{x_1,x_2,\ldots x_N\}$ and $\mathcal{F}\subset2^S$.

Do we have something similar for isolating linear forms? Namely, if we know that number of linear forms is bounded by $Z$, can we reduce random bits as compared to $O(N\log(KN))$ random bits used in Randomness Efficient Identity Testing of Multivariate Polynomials. We also want that weights should not be too large, again weights sublinear in $K$ should be interesting.

For your first question, if $l=1$, then $\frac{K^\frac 23}\epsilon$ is sufficient. This follows the fact that the lower envelope of some lines has the same complexity as the upper convex hull of its dual point system and if you have a convex polygon with integer vertices in $[0,K]^2$, then it can have at most $O(K^\frac 23)$ sides. I know I did not explain the details, but this is anyhow only a partial answer to your question...


On the properties of a family of submatrices Let $n$ and $k \le n/2$ be positive integers, and consider a family $\mathcal{F}$ of $k\times k$ sub-matrices of an $n\times n$ matrix such that every two elements of $\mathcal{F}$ intersect. What non-trivial (I know I'm already annoying people by this term) properties of $\mathcal{F}$ one could claim? (in particular related to its cardinality).

As @Steven Stadnicki points out in his comment, acording to your question, the contents of the matrices are not important here, but the number $k$ and $n$. Therefore, you can look at $\mathcal{F}$ as a family of intersecting $k$-subsets of $\{1,\dots,n\}$.

You can derive properties from something called a Sunflower.

Definition: A sunflower with $m$ petals and a core $Y$ is a collection of sets $S_1,\dots,S_m$ such that $S_i\cap S_j=Y$ for all $i\neq j$. Moreover, the sets $S_i\setminus Y\neq \emptyset$.

Sunflower Lemma: Let $\mathcal{F}$ be a family of sets each of cardinality $k$. If $|\mathcal{F}|>k!(k-1)^k$ then $\mathcal{F}$ contains a sunflower with $k$ petals.

You can make relaxations to the sunflower, like the petals not being intersected by a set of size smaller than $c$. In this case we have the following lemma.

Lemma: Let $\mathcal{F}$ be a family of sets each of cardinality $k$. If $|\mathcal{F}| > (c-1)^k$ then $\mathcal{F}$ contains a flower with $k$ petals.

There are more properties that you can look for in the book:

Extremal Combinatorics with Applications to Computer Science by Stasys Jukna.

The definitions and lemmas above are from chapter 7. Take a look at the excercises, and maybe also chapter 8 on Intersecting Families.


Low space computation and branching program One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log  T(n)]$.
I want to consider the small branching program family simulating low space  computation.

Question1: What is the best simulation bound $S_{1}(n)$ which is known at this moment such that $DSPACE [S(n)]\subseteq BP-SIZE[S_{1}(n)]$
Question2:What is the best time complexity bound as far as we know, for the function that $1^{n}\rightarrow $a branching program in the Question 1.

Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$,
the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$.
This matches the known inclusions $\text{DSPACE}(\log n) = \text{L} \subseteq \text{L}/poly = \text{BP}(poly)$; if a better bound were known then I would expect it to have been noted by Razborov in his FCT 1991 survey (preprint), or in Jukna's 2012 BFC textbook.


Deciding whether an NC${}^0_3$ circuit computes a permutation or not I would like to ask about a special case of the question “Deciding if a given NC0 circuit computes a permutation” by QiCheng that has been left unanswered.

A Boolean circuit is called an NC0k circuit if each output gate syntactically depends on at most k input gates.  (We say that an output gate g syntactically depends on an input gate g′ when there is a directed path from g′ to g in the circuit as viewed as a directed acyclic graph.)

In the aforementioned question, QiCheng asked about the complexity of the following problem, where k is a constant:

Instance: An NC0k circuit with n-bit input and n-bit output.
Question: Does the given circuit compute a permutation on {0, 1}n? In other words, is the function computed by the circuit a bijection from {0, 1}n to {0, 1}n?

As Kaveh commented on that question, it is easy to see that the problem is in coNP.  In an answer, I showed that the problem is coNP-complete for k=5 and that it is in P for k=2.

  Question.  What is the complexity for k=3?

Clarification on May 29, 2013: “A permutation on {0, 1}n” means a bijective mapping from {0, 1}n to itself.  In other words, the problem asks whether every n-bit string is the output of the given circuit for some n-bit input string.

This problem with $k=3$ is coNP-hard (and therefore coNP-complete).

To prove this, I will reduce from 3-SAT to the complement of this problem (for a given $NC_3^0$ circuit, does the circuit enact a non-bijective function).

First a preliminary definition that will be helpful:

We define a labeled graph to be a directed graph, some of whose edges are labeled with literals, with the property that every vertex has either one unlabeled incoming edge, one labeled incoming edge, or two unlabeled incoming edges.

The reduction

Suppose we have a 3-SAT formula $\phi$ consisting of $m$ clauses, each containing three literals. The first step is to construct a labeled graph $G$ from $\phi$. This labeled graph contains one copy of the following gadget (sorry for the terrible diagram) for each clause in $\phi$. The three edges labeled L1, L2, and L3 are instead labeled with the literals in the clause.

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

The gadgets (one for each clause) are all arrange in one big cycle with the bottom of one gadget linking to the top of the next.

Note that this arrangement of gadgets does in fact form a labeled graph (every vertex has indegree 1 or 2 with only edges leading to vertices of indegree 1 being labeled).

From the formula $\phi$ and the labeled graph $G$ (which was constructed from $\phi$) we next construct an $NC_3^0$ circuit (this will conclude the reduction). The number of inputs and outputs for this circuit is $n+v$ where $n$ is the number of variables in $\phi$ and $v$ is the number of vertices in $G$. One input and one output is assigned to each variable in $\phi$ and to each vertex in $G$. If $x$ is some variable in $\phi$ then we will refer to the input and output bits associated with $x$ as $x_{in}$ and $x_{out}$. Furthermore, if $l$ is a literal with $l = x$ then we define $l_{in} = x_{in}$ and if $l$ is a literal with $l = \neg x$ then we define $l_{in} = \neg x_{in}$. Finally, if $v$ is some vertex in $G$ then we will refer to the input and output bits associated with $v$ as $v_{in}$ and $v_{out}$.

There are four types of output bits:

1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Note that this output depends on only one input bit.

2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Note that this output depends on only two input bits.

3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l_{in})$. Note that this output depends on only three input bits since $l_{in}$ depends only on $x_{in}$ for whatever variable $x$ is used in the literal $l$.

4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. Note that this output depends on only three input bits.

Since in all cases the output depends on only three inputs, the circuit we build is in $NC_3^0$ as desired.

Correctness proof case 1: $\phi$ is satisfiable

Suppose there exists a satisfying assignment for $\phi$. Then construct the following two sets of values for the inputs.

1) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. All of the inputs associated with vertices of $G$ are given the value 0.

2) The inputs associated with the variables of $\phi$ are given the values of the satisfying assignment. Consider the vertices in one clause gadget in $G$. If the value of a label is 0 (under the satisfying assignment), the input associated with the vertex at the target endpoint of the edge labeled with that label is given a value of 0. If both L1 and L2 have value 0 then the second-top vertex in the gadget (as shown above) is also given a value of 0. All other vertices are given a value of 1.

We wish to show that these two sets of inputs yield identical outputs and therefore that the $NC_3^0$ circuit does not encode a permutation.

Consider the four types of output bits:

1) For every variable $x$ in $\phi$, $x_{out} = x_{in}$. Since $x_{in}$ is the same for both sets of inputs, outputs of this form will always be the same across the two sets of inputs.

2) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is unlabeled, $v_{out} = v_{in} \oplus u_{in}$. Examining the gadget whose copies make up $G$, we see that all such edges consist only of pairs of vertices whose input values are always 1s under the second set of inputs. Thus $v_{out} = v_{in} \oplus u_{in} = 0 \oplus 0 = 0$ under the first set of inputs and $v_{out} = v_{in} \oplus u_{in} = 1 \oplus 1 = 0$ under the second set of inputs. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

3) For every vertex $v$ in the labeled graph with exactly one incoming edge $(u, v)$ such that the edge is labeled $l$, $v_{out} = v_{in} \oplus (u_{in} \land l)$. If $l$ is false under the assignment then $v_{in}$ is 0 under both sets of inputs; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 0) = v_{in} = 0$ under both sets of inputs. If $l$ is true under the assignment, $v_{in}$ is 0 under the first set of inputs and 1 under the second; also note that in the gadget, the only labeled edges $(u, v)$ have vertices $u$ which always have $u_{in} = 1$ under the second set of inputs. As a result we see that under both sets of inputs, $u_{in} = v_{in}$ whenever $l$ is true; then $v_{out} = v_{in} \oplus (u_{in} \land l) = v_{in} \oplus (u_{in} \land 1) = v_{in} \oplus u_{in} = v_{in} \oplus v_{in} = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

4) For every vertex $v$ in the labeled graph with exactly two incoming edges $(u, v)$ and $(w, v)$, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in})$. There are two such vertices in each gadget. The top vertex and the second-from top vertex. We consider those two cases separately.

4a) When $v$ is the second-top vertex in a gadget, $u$ and $w$ are the two target endpoints of the edges labeled L1 and L2. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff L1 has value 0 under the satisfying assignment (aka $u_{in} = L1$); similarly, $w_{in}$ is 0 iff L2 has value 0 under the satisfying assignment (aka $w_{in} = L2$); and finally, $v_{in}$ is defined to be 0 iff both L1 and L2 have value 0  (aka $v_{in} = L1 \lor L2$). Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = (L1 \lor L2) \oplus (L1 \lor L2) = 0$. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

4b) When $v$ is the top vertex in a gadget, $u$ is the second-top vertex and $w$ is the target endpoint of the edge labeled L3. Under the first set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 0 \oplus (0 \lor 0) = 0$. Under the second set of inputs, $u_{in}$ is 0 iff both L1 and L2 have value 0 (aka $u_{in} = L1 \lor L2$); $w_{in}$ is 0 iff L3 has value 0 (aka $w_{in} = L3$); and finally $v_{in} = 1$. Thus under the second set of inputs, $v_{out} = v_{in} \oplus (u_{in} \lor w_{in}) = 1 \oplus ((L1 \lor L2) \lor L3) = 1 \oplus (L1 \lor L2 \lor L3) = 1 \oplus 1 = 0$ where the equality $(L1 \lor L2 \lor L3) = 1$ holds by definition in a satisfying assignment for every clause. Thus outputs of this form will always be the same (and in fact zero) across the two sets of inputs.

Clearly, we see that the outputs are the same for two different sets of inputs and therefore that the $NC_3^0$ circuit enacts a non-bijective function.

Correctness proof case 2: $\phi$ is unsatisfiable

Suppose now that there exists no satisfying assignment for $\phi$. Then assume for the sake of contradiction that some two different sets of inputs lead to the $NC_3^0$ circuit having the same output.

Clearly, the two inputs must have the same values for $x_{in}$ for every variable $x$ in $\phi$. Thus we may now unambiguously refer to the value of $x$.

Define $S$ to be the set of vertices $v$ in $G$ such that $v_{in}$ is different in the two sets of input values.

We will prove the following lemmas below:

Lemma 1: If in some gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertices above those three in the gadget are in $S$.

Lemma 2: If in some gadget the top vertex is not in $S$ then in the next gadget up no vertex is in $S$.

Since the gadgets form a loop, this implies that if in any gadget all three vertices at the target endpoints of the labeled edges are not in $S$ then no vertex in $G$ is in $S$ (in other words $S$ is empty).

However, consider a gadget associated with a clause $(L1 \lor L2 \lor L3)$ that is not satisfied. In this gadget all three labels have value 0. We know that edge $(u, v)$ labeled $L$ must satisfy $v_{out} = v_{in} \oplus (u_{in} \land L)$, but $L = 0$, so $v_{out} = v_{in} \oplus (u_{in} \land L) = v_{in} \oplus (u_{in} \land 0) = v_{in} \oplus 0 = v_{in}$. Thus since the output is the same for both inputs, the values of $v_{in}$ must also be the same across the two sets of inputs. In other words, we have shown that $v$ is not in $S$. Thus we see that in this particular gadget, the three vertices at the target endpoints of the labeled edges are not in $S$.

As a result, we conclude that $S$ is empty. This however, implies that between the two sets of inputs, there were no differences, which contradicts the assumption that these input sets are different. As a result, we see that the function enacted by the $NC_3^0$ circuit is injective and therefore a bijection.

All that's left is to prove the lemmas.

To do this, we note that for every type of vertex in $G$ (indegree 1 with label, indegree 1 without label, and indegree 2), if all incoming edges come from vertices not in $S$ then the vertex in question is also not in $S$. This is because in all three cases $v_{out} = v_{in} \oplus X$ where $X$ is some function of the inputs associated with variables and/or vertices with edges to $v$. Since all such vertices are not in $S$ by assumption, the value of $X$ must be the same under both sets of inputs. Therefore $v_{in} = v_{out} \oplus X$ is also the same under both sets of inputs. In other words $v$ is not in $S$.

Now that we have the rule that a vertex is not in $S$ whenever all of its predecessors are not in $S$, the lemmas follow simply by applying the rule repeatedly to the gadget diagram above.


Algorithm for finding a 3-cycle cover Given: An undirected, unweighted graph

Looking for: A disjoint vertex cycle cover where every cycle has at least 3 edges

Is there any algorithm that solves this problem, possibly with some heuristics? Can the bipartite representation of the graph used for finding perfect matching be leveraged here?

The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph.
If all the cycles in the cover must consist of at least $k$ edges/arcs, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs).

The complexity of the directed version is fully understood:

Markus Bläser and Bodo Siebert ("Computing Cycle Covers without Short Cycles", in Proceedings of ESA 2001, LNCS 2161, pp 368--379) have proved that $k$-DCC is NP-complete for any fixed $k\ge3$.

The complexity landscape of the undirected version is more diverse, and there are some open questions:

$3$-UCC is polynomially solvable. This is a folklore result that follows from a reduction of Tutte ("A short proof of the factor theorem for finite graphs", Canadian Journal of Mathematics 6, pp 347–352, 1954) to the classical unrestricted matching problem.
David Hartvigsen (in his PhD thesis "An Extension of Matching Theory", Carnegie-Mellon University, 1984) has shown that $4$-UCC is polynomially solvable.
The complexity status of $5$-UCC is open. David Hartvigsen has some positive results on special cases of this problem ("The square-free 2-factor problem in bipartite graphs", in Proceedings of IPCO 1999, LNCS 1610, pp 234–241).
Papadimitriou has proved that $k$-UCC is NP-complete for any fixed $k\ge6$. His proof is sketched in the 1980 paper "A matching problem with side conditions" by Gerard Cornuejols and Bill Pulleyblank (Discrete Mathematics 29, pp 135--159).


What is the VC Dimension of the $k-$Junta class A boolean function $f(x_1,x_2,\dots,x_n)$ is $k$-Junta if it depends on at most $k$ variables. Consider the class $\mathcal{J}_{\leq k}$ of all $k$-Juntas over $n$ variables, what is the VC dimension of this class?

Or at least is there any known method to construct the largest shattered set for small values of $k$ say when $k=1$.

For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$.

The upper bound follows essentially from Sasho's argument: there are $2+2n$ 1-juntas on $n$ variables, and if there were more than $\log_2$ of that many inputs, we could find a function that avoids all 1-juntas.

To see the lower bound, consider the matrix whose columns contain the $2^{\lfloor \log_2(n+1) \rfloor} - 1 \le n$ not-all-zero bitstrings of length $\lfloor \log_2(n+1) \rfloor + 1$ that start with a zero. The inputs to shatter are the rows of this matrix (padded up to length $n$). Every function of these inputs is either constant, or else it or its negation appears as a column, so it's computed by a 1-junta.

Here's an example for the case $n=7$ which illustrates the general idea. The claim is that the VC dimension of $1$-juntas on $7$ bits is $4$. Consider the matrix

$$\begin{array}{ccccccc}
  0&0&0&0&0&0&0\\
  1&0&0&0&1&1&1\\
  0&1&0&1&0&1&1\\
  0&0&1&1&1&0&1
\end{array}$$

formed by setting the columns to be all the length-$4$, not-all-zero bit strings that start with a zero. The claim is that the rows of this matrix are shattered by 1-juntas.

To see this, let $f$ be any boolean function of the rows. We can regard $f$ as a column. Now observe that either $f$ is constant, or else $f$ or its negation appears as some column in the matrix, simply by virtue of how we defined the matrix. In the first case, $f$ is obviously a 1-junta. In the latter case, suppose $f$ appears as column $i$, and observe that we can therefore compute $f$ as just the $i$-th dictator function. It follows that $f$ is again a 1-junta. A similar argument works when the negation of $f$ appears as a column--we represent $f$ by the negation of the $i$-th dictator. Thus in every case $f$ is a 1-junta. Since $f$ was arbitrary, it follows that the set formed by the rows of the above matrix is shattered by 1-juntas.

This idea can in theory be extended to larger $k$, where you encode every function as some $k$ columns in the matrix. I don't see how best to argue this at the moment, though.


Is $P^{\#P}=(P^{\#P})^{\#P}$ ? Intuitively, this equation holds because given the second #P oracle can be omitted since we can always use the first one.

More generally, say O is an oracle, is $P^{O}= (P^{O})^{O}$?

You should probably take a look at Is $(NP^{NP})^{NP} = NP^{(NP^{NP})}$? and Are Oracles Associative?. I don't know any canonical definition of $(A^B)^C$ hence I've got the same problem as Tsuyoshi Ito.

If only the $P$ machine has access to oracle $O$, then yes, ${(P^O)}^O=P^O$ by definition.

If both the $P$ machine and the oracle $O$ can both query the oracle $O$, then just take $O=EXP$ as a counterexample: $(P^{EXP})^{EXP} = TIME(2^{2^{n^{O(1)}}})$ whereas $P^{EXP}=TIME(2^{n^{O(1)}})$.


What is a substantial contribution to software design, with respect to authorship? Background

I am a biologist. I wrote and am about to submit a manuscript that describes a statistical analysis of computer model; it is a statistical methods and modeling paper.

After my manuscript was written, a collaborator with a background in CS started to develop the code for their own project. In the process, they substantially improved the code, making it more logical, more readable, more adaptable. However, it still reproduces my original analysis unchanged and the manuscript itself has not changed.

The collaborator has not asked for, and I have not offered, authorship, but another co-author asked me to consider it.

I am uncertain about whether his contributions merit authorship, and my primary concern is that authorship reflects intellectual contribution.  On the one hand, the manuscript itself has not changed. On the other, the software that was described by and will be released with the paper has changed.

I would like to collaborate with this and other computer scientists more in the future, but I would like to better appreciate what constitutes an intellectual contribution.

Question

Both with respect to this case, and more generally, how can I determine when a collaborator's contribution meet both of the two following criteria of authorship (from the Committee on publication ethics):

substantial contribution to conception and design, or acquisition of data, or analysis and interpretation of data;
drafting the article or revising it critically for important intellectual content;

?

update: it is clear from further consideration and the answers in below that the contribution justifies authorship, so I will offer it.

My view on this particular case is that the CS colleague's name should not go on the paper for the simple reason that the research had been done and written up before his/her contribution was made. The CS colleague's work made no contribution to your results.

As you said, the CS colleague is going to use the code for his/her own research, so he/she already has something for free. One question you could be asking is whether you should be on his/her subsequent papers based on this software.

In general, people who do the development work do deserve some credit even if their work helps facilitate scientific output, rather than directly contributes to it. For example, if someone wrote a program based on some design that I made, which would then form the basis of my further work, I would definitely give them credit for it, at least on the first instance.

Of course a lot of factors will influence this decision. Whether the developer is a PhD student, post-doc, professor or a "just a" programmer. Whether the person depends crucially on the publication. Whether the project's evaluation depends on joint publications (to show, for example, interdisciplinary collaboration). Political reasons: will the joint publication create goodwill for future collaborations?

It's not a black/white issue and very hard to decide. In general, it's probably best to avoid any possible badwill, because that can really spoil a (possible) collaboration.


What is the best place to get BibTeX entries for ICLR and other machine learning papers? dblp seems the best i found so far (as also mentioned in the comments and in What is the best place to get BibTeX entries for computer science articles ?) but even there some papers from NIPS workshops and ICLR in general are not listed as such and are listed simply as CoRR papers.

For example "Neural Machine Translation by Jointly Learning to Align and Translate"
https://dblp.uni-trier.de/rec/bibtex/journals/corr/BahdanauCB14
although after writing the question i'm finding that most papers are referencing the NMT paper also as CoRR/arXiv. I also didn't find proceedings of ICLR so maybe it's a general issue only with ICLR papers and some conference workshops.

For NeurIPS (previously NIPS), the NeurIPS website itself is a good source: look for a paper, go to its page, and click on the "BibTex" link. Here is a random sample (!):

ICML, COLT, and JMLR appear to have similar BibTex-ready websites: see http://proceedings.mlr.press/. For instance, going to the abstract of a randomly chosen paper from ICML'15:

ICLR does not seem to have this in place; for instance, even checking on Google Scholar, the paper you point out is cited a lot (~4k times), but always as the arXiv version. For conferences or workshops using OpenReview, such as ICLR'18 (I believe it was the first time for this conference), you can get some BibTex entry by clicking on a specific paper, and selecting "Show BibTex":

However, it is unclear to me the resulting citation is better that the ArXiv one.


Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now? In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational hierarchy) of the nonrational phenomena... using rational relations as a tool for comparison. Rational sets are at the bottom of this hierarchy. Moving upward one encounters 'algebraic phenomena,'" which lead to "to the context-free grammars and context-free languages of Chomsky, and to several related topics."

But Eilenberg never published volume C. He did leave preliminary handwritten notes for the first few chapters (http://www-igm.univ-mlv.fr/~berstel/EilenbergVolumeC.html) complete with scratchouts, question marks, side notes and gaps. But they do not reveal much beyond the beginnings of the well-known power series approach to grammars.

So, my actual question -- does anyone know of work along the same lines to possibly reconstruct what Eilenberg had in mind? If not, what material is likely closest to his ideas?

The site http://x-machines.net/ is about x-machines, one of Eilenberg's key innovations, but it deals mainly with applications of x-machines rather than further developing the theory as Eilenberg seemed to promise.

Also, anyone know why Eilenberg stopped before making much progress on Volume C? This was the late 70's, and he lived until 1998, though he did not appear to have published any math after Volume B. Yet he seemed to have the math for Volumes C and D largely done, at least in his mind.

(Same question asked on math.stackexchange -- https://math.stackexchange.com/questions/105091/eilenbergs-rational-hiererchy-of-nonrational-automata-languages -- apologies if this is considered cross-posting.)

An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange.


Data structure for updates on intervals and querying number of zeros I am looking for a data structure that would maintain an integer table $t$ of size $n$, and allowing the following operations in time $O(\log n)$.

$\text{increase}(a,b)$, which increases $t[a],t[a+1],\ldots,t[b]$.
$\text{decrease}(a,b)$, which decreases $t[a],t[a+1],\ldots,t[b]$.
$\text{support}()$, which returns the number of indices $i$ such that $t[i]\neq 0$.

You have the promise that every call to decrease can be matched to a previous call to increase with the same parameters $a,b$. The application I have in mind is a sweepline algorithm to compute in time $O(n\log n)$ the area of the union of n given rectilinear rectangles.

A quad-tree would have size $\Theta(n^2)$, so it is not a solution. Fenwick or Interval trees have the right flavor, but I don't see how to extend them to support the operations above.

Use a segment tree — a recursive partition of the range $[1,n]$ into smaller ranges. Each interval $[a,b]$ of your update operations can be partitioned into $O(\log n)$ of the ranges in this recursive partition. For each range $[x,y]$ store:

The number $c(x,y)$ of intervals $[a,b]$ that have been increased and not decreased such that $[x,y]$ is one of the ranges into which $[a,b]$ is partitioned
The number $u(x,y)$ of cells that are not covered by partitioned subsets of intervals that are at $[x,y]$ or lower in the recursion

Then if $[x,y]$ is recursively split into $[x,z]$ and $[z+1,w]$ we have
$$u(x,y)=\begin{cases}
0&\text{if }c(x,y)>0\\
u(x,z)+u(z+1,y)&\text{otherwise}
\end{cases}$$
so we can update each $u(x,y)$ value in constant time when the other data for a range changes. Each support query can be answered by looking at $u(1,n)$.

To perform an increase$(a,b)$ operation, partition $[a,b]$ into $O(\log n)$ ranges, increment $c(x,y)$ for each of these ranges, and use the formula above to recalculate $u(x,y)$ for each of these ranges and each of their ancestors. The decrease operation is the same with a decrement instead of an increment.


Pairing algorithm for simple speed dating problem I am asking myself whether there is an polynomial algorithm for the following problem:

Given:

- m persons (think of them as "men")
- w persons (think of them as "women")

- t-talking sessions
- a function
     f: (w, m) -> {-1,0,1,2}, which is preference of a specific woman to talk with a specific man: -1 means, that the woman does not want to talk to this man, if possible.
     g: (m, w) -> {-1,0,1,2}, which is preference of a specific man to talk with a specific woman: -1 means, that the man does not want to talk to this woman, if possible.

Target: Accomplish the "best" dating plan, meaning a pairing function for each talking session, which maximizes by summing over all dates using this function: m, w -> max(f(m,w),g(w,m)). During the talking sessions noone should date a person he has met before.

Is there a greedy algorithm for this problem, e.g. by matching the most loved-person with the most preferred person having the least number of talks?

This is simply the Stable Marriage Problem, where rankings go from -1 to 2 instead of 1 to n. Thus it's almost a subset of the problem solved by the Gale–Shapley algorithm. Quoting from Wikipedia:

  The Gale–Shapley algorithm involves a number of "rounds" (or
  "iterations").

  In the first round, first a) each unengaged man proposes to the woman
  he prefers most, and then b) each woman replies "maybe" to her suitor
  she most prefers and "no" to all other suitors. She is then
  provisionally "engaged" to the suitor she most prefers so far, and
  that suitor is likewise provisionally engaged to her.

  In each subsequent round, first a) each unengaged man proposes to the
  most-preferred woman to whom he has not yet proposed (regardless of
  whether the woman is already engaged), and then b) each woman replies
  "maybe" to her suitor she most prefers (whether her existing
  provisional partner or someone else) and rejects the rest (again,
  perhaps including her current provisional partner).

  The provisional nature of engagements preserves the right of an
  already-engaged woman to "trade up" (and, in the process, to "jilt"
  her until-then partner).

  This algorithm guarantees that:

  Everyone gets married.

  Once a woman becomes engaged, she is always engaged to someone. So, at
  the end, there cannot be a man and a woman both unengaged, as he must
  have proposed to her at some point (since a man will eventually
  propose to everyone, if necessary) and, being unengaged, she would
  have had to have said yes.

  The marriages are stable.

  Let Alice be a woman and Bob be a man who are both engaged, but not to
  each other. Upon completion of the algorithm, it is not possible for
  both Alice and Bob to prefer each other over their current partners.
  If Bob prefers Alice to his current partner, he must have proposed to
  Alice before he proposed to his current partner. If Alice accepted his
  proposal, yet is not married to him at the end, she must have dumped
  him for someone she likes more, and therefore doesn't like Bob more
  than her current partner. If Alice rejected his proposal, she was
  already with someone she liked more than Bob.

It's not greedy, so I'm not totally answering the question, but it works. It's probably easier if you convert the problem to the marriage problem by changing the -1...2 to 1-n (by picking randomly higher preferences in the case of ties) before processing, I think.

Edit: Nevermind, this doesn't have the least number of talks either I think, but I figured it was still worth bringing up. Really it depends on whether those talking preferences are known beforehand (and we are optimizing the pairings, in which case this algorithm works), or whether those talking preferences aren't known until a talking session begins - in which case this algorithm isn't applicable at all. I mean you could just set everyone up with everyone else, compute these values, then run the algorithm above, but it's certainly not optimal.


Edge and vertex fault tolerance in graphs Suppose we are given two graphs $G$ and $H$, where $H$ is a subgraph of $G$. What is the maximum number $k$ such that if any $k$ edges are removed from $G$, $H$ still remains a subgraph of $G$? What about the same question when edges are replaced by vertices? A generalization is to consider weights on edges/vertices and ask for maximum weight edges/vertices. I want both a bound as well as an algorithm. This problem is NP-hard as subgraph isomorphism is a special case of it.

Any papers on this problem will be helpful.

The question is very general and so the following is only a partial solution.  My main motivation was to draw the connection between this and k-hitting sets.

As Arindam has pointed out, this problem (or the decision version thereof) could be used to solve the subgraph isomorphism problem: "Is $H$ a subgraph of $G$ if any $0$ edges of $G$ are removed?".  But as is often the case, we still want to know "is it possible to do better than the naive solution?"

The naive solution:

for i in 0 ... (|E(G)|-|E(H)|+1)
    for every i-subset of edges, S, in E(G)
        if H is not a subgraph of (G - S)
            return k=i-1 as the greatest number of edges that can be removed

Ignoring the obvious edge cases (returning $-1$ when $H$ is not a subgraph of $G$) then the cost is basically $\sum_{i=0}^k \binom{|E(G)|}{i}$ computations of he subgraph isomorphism problem on inputs (basically) $G$ and $H$.  And so, we are basically up against a possibly exponential number of subgraph isomorphism problems.

The problem can be restated as a hitting set problem (also known as a vertex cover of a hypergraph problem).  Let $S$ be the set of all sets, $T$, where $T$ is a set of $|E(H)|$ edges of $G$, and $H$ is isomorphic to $G - (E(G) - T)$.

Note, $S$ is not every mapping of $H$ onto $G$, but is every edge set that can be mapped to.

Let $h$ be the size of the minimum hitting set of $S$.  Then $k=h-1$.

This is neat, but it is not immediately useful.  Calculating a minimum hitting set is NP-hard, and the input into the problem is possibly exponential in the size of the input of our original problem.  Double-wam-o.

However, it does provide us with a case for a fast approximation.  If $|E(H)|$ is small (and by that I mean bounded by some constant $e_H$), then we have $|S| = O(\binom{|E(G)|}{e_H})$.  Also, an $e_H$-approximation can be computed in polynomial time.  Thus the real work is in finding $S$, which can be done with $\binom{E(G)}{e_H}$ cases of the graph isomorphism problem.  The naive solution does not compute in polynomial time when $E(H)$ is bound because $k$ is not bound.


Complexity of the directed Steiner tree problem on special graph classes I am interested in the complexity of the directed Steiner tree problem: Given a weighted digraph $D=(V,E)$, a root $r\in V$ of $D$, and a set of terminals $T\subseteq V$. The objective is to find a minimum cost arborescence of $D$ rooted at $r$, in which there is a path from $r$ to each node in $T$.

Is a polynomial time algorithm known if the input is restricted to digraphs whose underlying undirected graph is a series-parallel graph (or equivalently is a $K_4$-free graph or is a partial $2$-tree or has treewidth at most $2$)?

This manuscript seems to prove exactly that. (It doesn't; the complexity parameter is $|T|$, not the treewidth.)

In general, most NP-hard optimisation problems have polynomial-time algorithms when the input is restricted to bounded-treewidth graphs. These algorithms use the rather well-known tree-decomposition machinery, which is also used in the linked paper.

EDIT: The undirected Steiner tree is, on the other hand, known to be fixed-parameter tractable with regards to parameter $w$ the treewidth of the underlying graph. My suggestion would be to try and adapt this algorithm to the directed case, which would in particular give a polynomial time algorithm for series-parallel graphs.


Relation between interval temporal logic and linear temporal logic I am trying to understand the relation between interval temporal logic and linear temporal logic. Do the two form of expressing temporal constraints have the same expressive power, or is one of the two more expressive?

I found a proof of the ability of translating Allen Interval temporal logic formulas into linear temporal logic formulas (http://fsl.cs.uiuc.edu/index.php/Allen_Linear_(Interval)_Temporal_Logic_-Translation_to_LTL_and_Monitor_Synthesis-), but I couldn't find much info for the other direction.

The question you ask is more complex than it seems. ITLs have been defined in different ways and fashions, and the answer depends on the particular definition and the particular semantics. To get an intuition, you have to decide first if points are to be considered special intervals or excluded by the semantics; the second choice is more common, and it makes more difficult the comparison. I suggest to check, first, the webpages

1.http://perseo.dif.um.es/~guido/publications.html

2.https://itl.dimi.uniud.it/

to get an idea of the last 10 years of research on this topic. Second, you can contact me to discuss more in particular your question (my address is on the link number 1).

cheers


Choosing one number from each set so that the difference between maximum and minimum is minimized Suppose I have four sets A={0, 4, 9}, B={2, 6, 11}, C={3, 8, 13}, and D={7, 12}.

I need to choose exactly one number from each of these sets, so that the difference between the largest and smallest chosen numbers is as small as possible.

What type of problem is this?  Is there a graph algorithm that could be used to solve this problem?

It's not really a graph problem, I think. Problems in which you try to choose some objects to minimize the difference between the min and max chosen object are called "minimum range" problems — e.g. look up "minimum range cut", which is a graph problem — but this one looks like you're trying to find the minimum range basis of a partition matroid with one partition set for each of your groups.

In general minimum range matroid basis problems can be solved in $O(n\log n)$ time, plus $O(n)$ steps of a subroutine that finds a basis of a set with corank one: sort the elements from smallest to largest and then process the elements one by one. While you process the elements maintain an independent set $I$; when you process an element $e$, add $e$ to $I$ and, if that addition causes $I$ to become dependent, kick out the minimum weight element in the unique circuit of $I$. The minimum range basis is one of the sets $I$ that you found in this process: the one that has full rank and has as small a range between min and max as possible.

For your partition matroid special case it's easy to find the circuit in $I$ when it becomes dependent: a circuit happens when $e$ belongs to the same group as an element $f$ that you previously added, and $f$ is the element you should kick out of $I$. So the whole algorithm takes $O(n\log n)$ time, or possibly faster depending on how much time it takes to do the sorting step.


Difference between time-bounded and memory-bounded Kolmogorov complexity Let $x$ be a finite string of length $n$.

Denote by $C^t(x)$ the Kolmogorov complexity of $x$ bounded by time $t$ (i.e. the length of a minimal program that outputs $x$ and running at most $t$ steps).

Denote by $C_m(x)$ the Kolmogorov complexity of $x$ bounded by memory $m$.

Can $C^{\mathsf{poly}(n)}(x)$ be much greater than $C_{\mathsf{poly}(n)}(x)$?
It seems that the answer is "yes" but how to prove it under natural assumptions?

More accurately: let $(x_i)$ be a sequence of finite strings. Is it true that for every polynomial $p$ there exist a polynomial $q$ and a constant $c$ such that for every $x_i$ of length $n$ the following inequality holds: $$C^{q(n)}(x_i) <  C_{p(n)}(x_i) + c\log n ?$$
Does it contradict to some natural assumptions of Computational complexity theory?

Assume that there exists a sparse set $L \in \mathbf{NP} -\mathbf{P}$, this is equivalent to $\mathbf{EXP}\not= \mathbf{NEXP}$.

Then we can construct such a sequence. Indeed, consider $L_n = \{l_1,\ldots, l_k\} = L \cap \{0,1\}^n$.

Denote by $s_i$ the lexicographically first certificate for $l_i$.

Define $x_n$ as the list of pairs: $ x_n:= \{ (l_1, s_1), \ldots, (l_k,s_k)\}$.

Certainly, $C_{\mathsf{poly}(n)}(x_n) = O(\log n)$. Let us show that $C^{\mathsf{poly}(n)}(x_n) > c\log n$ for every $c$.

Indeed, otherwise there exists a polynomial-time algorithm calculating   all strings of complexity  at most $c\log n$ (including $x_n$). Hence we can verify that a string belongs to $L$ in polynomial time.


Relativization with Respect to Non-Recursive Oracles In the paper Relativizations of the P = ? NP Question, Baker et al. showed that there are relativized worlds in which either P = NP or P ≠ NP holds. All oracles in their settings were recursive sets.

In another paper Relative to a Random Oracle $A$, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability $1$, Bennett and Gill put forward the notion of random oracles, which are almost surely non-recursive sets. (See the comments below.)

I wasn't aware of any other non-recursive relativizations, unless I came up with one (see this question and Joshua's answer to it.)

  What are the implications of non-recursive relativizations? How are they useful in structural complexity theory?

I can't resist putting in a plug for some recent results, indicating that it can be interesting to consider computation relative to the (non-computable) set of Kolmogorov-random strings.

Let $R$ be the set of Kolmogorov-random strings; that is, the set of strings $x$ such that $K(x)$ is greater than or equal to $|x|$.  (Actually, each "optimal" prefix Turing machine $U$ gives a different version $R_U$ of this set; usually it doesn't make much difference which $U$ we use to define $K$; it affects $K(x)$ only by $O(1)$.)

Buhrman et al. showed (at CCC 2010) that $BPP$ is poly-time truth-table reducible to $R$, and earlier work showed that $PSPACE$ is in $P^R$, and NEXP is in $NP^R$.

These might seem like fairly worthless results, since they give a non-computable upper bound on complexity classes!  However a recent paper (see http://www.eccc.uni-trier.de/report/2010/138/ ) shows $PSPACE$ is an upper bound on the class of decidable sets that are poly-time truth-table reducible to $R_U$ for every $U$.  That is, $PSPACE$ is sandwiched between the class of decidable problems that are Turing and truth-table reducible to $R$.

The same paper also shows that Exponential Space is an upper bound on the class of decidable problems that are in $NP^{R_U}$ for every $U$.  I would guess that it might be possible to characterize $NEXP$ in this way.


Are there Belief Revision techniques for quantified data? Are there Belief Revision techniques that aren't based solely in formal logic propositions?

For example, if one agent believes the temperature for an area is 85 degrees and another believes the temperature is 79 degrees, is there a technique in the literature that has been proposed to to harmonize their beliefs?

Fuzzy Belief Revision and Probabilistic Belief Revision are two flavours of Belief Revision that do not fall within the formal logic propositions characterisation of the field.


Are there poly time algorithms to determine if a graph is almost bipartite? Given an undirected graph G, we can say that G is almost bipartite if deleting k edges (or vertices) would make it bipartite.

Are there poly time algorithms to determine if a graph is exactly or approximately almost bipartite?

The vertex version is called "odd cycle transversal"; it's NP-complete but fixed-parameter tractable. See:

Yannakakis, Mihalis (1978), "Node-and edge-deletion NP-complete problems", Proceedings of the 10th ACM Symposium on Theory of Computing (STOC '78), pp. 253–264, doi:10.1145/800133.804355.

Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters, 32 (4): 299–301, doi:10.1016/j.orl.2003.10.009.

Hüffner, Falk (2005), "Algorithm engineering for optimal graph bipartization", Experimental and Efficient Algorithms: 240–252, doi:10.1007/11427186_22.

The edge version has been called "edge bipartization"; it's also NP-complete but fixed-parameter tractable. See:

Guo, Jiong; Gramm, Jens; Hüffner, Falk; Niedermeier, Rolf; Wernicke, Sebastian (2006), "Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization", JCSS 72 (8): 1386–1396, doi:10.1016/j.jcss.2006.02.001.

(added following daniello's comment):

Odd cycle transversal has an $O(\sqrt{\log n})$ approximation algorithm, but (assuming the Unique Games Conjecture) no constant-factor approximation; see (references copied from "On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal" by Jansen and Kratsch):

Agarwal, Amit, Charikar, Moses, Makarychev, Konstantin, Makarychev, Yury, $O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems, STOC'05, pp. 573–581.

Khot, S., On the power of unique 2-prover 1-round games, STOC '02, pp. 767–775.

Wernicke, S., On the algorithmic tractability of single nucleotide polymorphism (SNP) analysis and related problems. Master’s thesis, Wilhelm-Schickard-Institut für Informatik, U. Tübingen (2003)


Complexity of n-queens-completion? The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions:

$1\le Q[i] \le n$ for all $i$
$Q[i] \ne Q[j]$ for all $i\ne j$
$Q[i]-i \ne Q[j]-j$ for all $i\ne j$
$Q[i]+i \ne Q[j]+j$ for all $i\ne j$

Each integer $Q[i]$ represents the position of a queen on the $i$th row of an $n\times n$ chessboard; the constraints encode the requirement that no queen attacks any other queen. It is easy to prove that there are no solutions when $n=2$ or $n=3$, and closed-form solutions are known for all other values of $n$.  Thus, as a decision problem, the $n$-queens problem is completely trivial.

The standard backtracking algorithm for constructing an $n$-queens solution speculatively places queens on a prefix of the rows and then recursively determines whether there is a legal placement of queens on the remaining rows.  The recursive subproblem can be formalized as follows:

Given an integer $n$ and an array $P[1..k]$ of integers, is $P$ a prefix of an array $Q[1..n]$ that describes a solution to the $n$-queens problem?

Is this more general decision problem NP-hard?

Several nearby questions are known to be NP-hard, including Latin square completion [Colbourn 1984], Sudoku completion [Yato and Seta 2002], and a different generalization of $n$-queens [Martin 2007], but this specific question seems to have escaped any serious attention.

Related cstheory.se questions:

Is the N Queens problem NP-hard?

Is the half-filled magic square problem NP-complete?

It's taken years but this post inspired us to write a paper which has come out today.

The answer is that n Queens Completion is NP-Complete.  However for full disclosure should mention we solve a slight variant of the problem.  In our case the set of queens doesn't have to be a prefix of the full set.  So technically we haven't resolved the exact problem asked here.  However it would be extremely surprising if the version of n Queens Completion from this query wasn't also NP-Complete.

I want to repeat the thanks we put in the paper to Jeffε for raising this question here.

The complexity of n Queens Completion
Journal of AI Research
Gent, Jefferson, Nightingale
doi:10.1613/jair.5512
http://www.jair.org/papers/paper5512.html


What is the computational complexity of "solving" chess? The basic idea of backwards induction is to start with all the possible final positions of a game in which player X wins. So for chess, look at all the ways White can checkmate Black. Now work backwards to all the possible moves/positions that would allow White to move in to one of those positions. If White ever found herself in such a position she could win by moving to the relevant checkmating move. Now we work backwards another step and so on. Eventually we get back to all the possible first moves White could make. The point is, once we've done this, we know that we have White's best response to any move Black makes.

Recently (last five years or so) Checkers was "solved" in this way. Obviously Noughts and Crosses (what the colonials might call "Tic-Tac-Toe") has been solved for ages. At the very least since this xkcd but presumably long before.

So the question is: what factors does this sort of procedure depend on? The number of possible legal positions, presumably. But also perhaps the number of legal moves at any given node... And given this, how complex is this sort of problem?

Bonus question: how long before a $2000 PC can solve checkers in a day? Chess? Go? (Of course for this you also have to take into account increasing speed of home computers...)

I've added the graph-algorithms tag because you can represent these games as trees, but if I'm abusing the tag please add something more appropriate

As @Joe points out, chess is trivial to solve in $O(1)$ time using a lookup table.  (An actual implementation of this algorithm would require a universe significantly larger than the one we live in, but this is a site for theoretical computer science.  The size of the constant is irrelevant.)

There is obviously no canonical $n\times n$ generalization of chess, but several variants have been considered; their complexity depends on how the rules about moves without captures and repeating positions are generalized.

If a draw is declared after a polynomial number of capture-free moves, or after any position repeats a polynomial number of times, then any $n\times n$ chess game ends after a polynomial number of moves, so the problem is clearly in PSPACE.  Storer proved that this variant is PSPACE-hard.

For the variant with no limits on repeated positions or capture-free moves, the number of legal $n\times n$ chess positions is exponential in $n$, so the problem is clearly in EXPTIME.  Fraenkel and Lichtenstein proved that this variant is EXPTIME-hard.


Hierarchy theorems for circuit depth What kind of hierarchy theorems are there for circuit depth?

Statements like

  if $g(n) \in o(f(n))$ and $f(n) \in n^{O(1)}$ then
  $\mathsf{SizeDepth}(n^{O(1)}, g(n)) \subsetneq \mathsf{SizeDepth}(n^{O(1)}, f(n))$.

A paper of Klawe, Paul, Pippenger, and Yannakakis gives an hierarchy theorem for constant depth monotone formulas:
http://dl.acm.org/citation.cfm?id=808717

Specifically, for every $k$ it gives a function that can be computed by a formula of depth $k$ and size $n$ but requires formulas of depth $k-1$ of size $\exp(n^{1/k})$.


Which complexity class does this problem belong to? Consider the following problem $\mathcal{P}$.

Instance: A Boolean formula $F$ of $n$ Boolean variables ($x_1,...,x_n$) and $m$ Boolean parameters ($b_1,...,b_m$) where $0 \leq m \leq n$.

Problem: Find an assignment $b_1^*,...,b_m^*$ to the parameters $b_1,...,b_m$ such that the number of satisfying assignments to the variables $x_1,...,x_n$ of $F(b_1/b_1^*,...,b_m/b_m^*)$ is minimum.

For example, $F = \{((x_2 \lor x_3) \leftrightarrow x_1) \lor (x_1 \leftrightarrow b_1 \land (x_2 \lor x_3) \leftrightarrow \neg b_1)\} \land \{((x_1 \land \neg x_2) \leftrightarrow x_2) \lor (x_2 \leftrightarrow b_2 \land (x_1 \land \neg x_2) \leftrightarrow \neg b_2)\} \land \{x_1 \leftrightarrow x_3\}$ where $n = 3$ and $m = 2$.

If $(b_1^*,b_2^*) = (0,0)$, then the number of satisfying assignments of $F(b_1/b_1^*,b_2/b_2^*)$ is 2.

If $(b_1^*,b_2^*) = (0,1)$, then the number of satisfying assignments of $F(b_1/b_1^*,b_1/b_2^*)$ is 3.

Here, I consider the constructive version $\mathcal{P}_C$ of $\mathcal{P}$ (i.e., the output of $\mathcal{P}_C$ includes the optimal assignment to $b_1, ..., b_m$ and the minimum number of assignments to $x_1, ..., x_n$). When $m = 0$, $\mathcal{P}_C$ is equivalent to #SAT, which is known as #P-complete. Thus, $\mathcal{P}_C$ is #P-hard. However, it is insufficient to conclude that $\mathcal{P}_C$ is #P-complete.

Which complexity class does this problem belong to (#P or other one)? If it does not belong to #P, please give me a proof.

We'll argue that the following formulation of OP's problem is complete for OPT#P under poly-time reductions:

input: A Boolean formula $\phi\big(b=(b_1,b_2,\ldots,b_n), x=(x_1, x_2,\ldots, x_m)\big)$

output: The maximum, over all assignments to $b$, of the number of assignments to $x$ such that $\phi(b, x)$ is satisfied (evaluates to true).

The problem differs from OP's problem in two minor ways.  First, the output does not include an assignment to $b$.  Second, it chooses $b$ to maximize, rather than  minimize, the number of satisfying assignments.  However, OP's problem for a given $\phi$ is essentially equivalent to this problem for the complement of $\phi$.

Lemma 1. The problem above is OPT#P-complete under polynomial-time reductions.

Proof sketch. The proof is a simple variant of the standard proof that SAT is NP-complete.

First, as I understand it, OPT#P is the class of functions of the form
$$g(w) = \max_b \#M(w, b)$$
for some non-deterministic poly-time TM $M$, where $\#M(w, b)$ is the number of accepting computation paths for $M$ on input $(w, b)$.  In the $\max$, $b$ ranges over all binary strings of length equal to some fixed polynomial $p(|w|)$.

So fix any such TM $M$ and corresponding $g$.  Given any $w$, the reduction will produce (in time poly$(|w|)$) an equivalent instance of the problem in question: a Boolean formula $f_w(B, X)$ with Boolean variables $(B, X)$ such that

$$g(w) = \max_{b} \#f_w(b),$$

where $\# f_w(b)$ is the number of assignments $X=x$ such that $f_w(b, x)$ is true.

Recall that the classical Cook-Levin reduction for $M$ on a given input $(w, b)$ first produces a formula $F(W,B,X)$ with boolean inputs $W$, $B$, and $X$, where $|W|=|w|$, $|B|=|b|$, and $|X|$ is some fixed polynomial in $|w|+|y|$.  But then it adds constraints to force $W=w$ and $B=b$ (or makes these substitutions and simplifies the resulting formula), resulting in a formula $F_{wb}(X)$ such that there is exactly one assignment to $X$ that satisfies $f_{wb}(X)$ for each accepting computation of $M$ on input $(w, b)$.  (The variables in $X$ encode the non-deterministic guesses of $M(w, b)$, and also auxiliary values that encode the rest of the computation.  But the auxiliary values are determined by the non-deterministic guesses and $w$ and $b$.) In this way, $f_{wb}(X)$ is satisfiable if and only if $M(w, b)$ has an accepting computation.

Instead, given $w$, the reduction outputs the formula $f_w(B,X)$ obtained from $F(W,B,X)$ by adding only the constraints that force $W=w$. Then, for any given second argument $b$, the number of accepting computations of $M(w, b)$ is the number of assignments $X=x$ such that $f_w(b, x)$ is true.  That is, in our previous notation, for all $b$,
$$\#M(w, b) = \# f_w(b).$$
It follows that $g(w) = \max_b \# f_w(b)$ as desired.$~~~~~\Box$


Does a pair of disjoint homotopic cycles in the dual separate the graph? Let $G$ be a graph embedded on an orientable compact surface of genus $g$ so that the embedding is cellular. Consider the dual of the graph $G^*$. Let $C_1$ and $C_2$ be disjoint cycles in $G^*$ that are homotopic to each other and let $E_1$ and $E_2$ be their corresponding edge sets in $G$ respectively. Is $G \setminus (E_1 \cup E_2)$ a disconnected graph?

Yes.  Let me write $\Sigma$ for the surface on which $G$ and $G^*$ are embedded.

Because the cycles $C_1$ and $C_2$ are homotopic, they are also in the same $\mathbb{Z}_2$-homology class.  So by definition, the symmetric difference $C_1\oplus C_2$ is the boundary of the union of some subset of faces of $G^*$; call this union of faces $U$.  (In fact, either $U$ or its complement $\Sigma\setminus U$ must be an annulus, but this isn't important.)

Because $C_1$ and $C_2$ are disjoint, the symmetric difference $C_1\oplus C_2$ is equal to the union $C_1\cup C_2$.  In particular, we have $C_1\oplus C_2\ne \varnothing$, which implies that both $U$ and its complement $\Sigma\setminus U$ are non-empty.  In other words, the subsurface $\Sigma \setminus (C_1\cup C_2)$ is disconnected.

Any path in $G$ can be viewed as a path in $\Sigma$ that avoids the vertices of $G^*$, and vice versa (up to homotopy).  Thus, the (graph) components of $G\setminus (E_1\cup E_2)$ correspond bijectively to the (surface) components of $\Sigma \setminus (C_1\cup C_2)$.  We conclude that $G\setminus (E_1\cup E_2)$ is disconnected.

The assumption that $\Sigma$ is orientable is never used.


What is the best upper bound on the running time of the graph minor algorithm? A cornerstone of the graph minor theory is an algorithm that, given undirected graphs $G, H$, runs in time $f(|H|)poly(|G|)$, and determines whether $H$ is a minor of $G$ or not. It has been obtained from the famous result of Roberson and Seymour.

This result, as well as other algorithms for minor testing, is always cited with $f$ being some implicit computable function. I wonder what are the best known upper bounds on $f$, e.g., is it elementary?

In this discussion, user @Saeed mentions that $f$ is at most quadruple-exponential but provides no reference for this claim.

My answer was based on the explanation in paper of Adler et al for disjoint paths problem. That running time is not exactly what is in the Robertson and Seymour paper but it is the improved one by Kawarabayashi and Wollan. It’s been a long time ago and I am not sure if this is restricted to specific graph class. You may have a look at the corresponding reference.

https://arxiv.org/pdf/1310.2378.pdf


"Send Once"-One way Multiparty Communication Complexity There are plenty results on multiparty communication complexity, and one way protocol which anyone playing communicatin games is able to send one person, is a basic setting.

I want to consider more restricted protocol that is "send once" protocol.

For example, Alice, Bob, and Cate are players and their communication must follow the following way:

Alice is only able to send Bob.
Bob   is only able to send Cate .

Each plyer sent bits just one time.

Are there lower bounds results and methods that k-party NIH or NOF communication complexity for set-disjointness and other functions ?

There are several flavors of communication complexity.  It sounds like your "send once" model is uses one-way communication and private messages.  For concreteness, I give short synopses of some different communication complexity variants below.

Say there are k players who wish to jointly compute a function f(x_1,...,x_k) on k different inputs.  Some different variants:

(1) One-way complexity vs interactive communication:  In this setting, player 1 sends a single message, then player 2, etc.  Player k computes the output of the protocol.  With interactive communication, players may speak back and forth.

(2) Broadcast vs. private-messages models:  In the broadcast model of communication, each message is received by all players.  In the private-messages model, messages are sent point-to-point i.e., a message can come from player i to player j.  In this model, if player i wants to communicate with all players, he must send individual messages to each other player.  Broadcast messages is a stronger model, so lower bounds in the broadcast model will give you lower bounds in the private-messages model, and upper bounds for private-messages will give you upper bounds in the broadcast model.

(3) NIH vs. NOF complexity:  In the Number-in-Hand (NIH) communication model, player i sees only x_i.  In the Number-on-the-Forehead (NOF) communication model, player i sees all inputs except x_i.  NOF lower bounds are harder to show, because players share inputs.  Intuitively, this should allow players to compute a function using less communication, thus making lower bounds harder to prove.

As I said, I sense that you're looking for one-way communication with private messages (and perhaps importantly you're assuming the private messages only go from player i to player i+1).
This setting is not very well-studied, but the NIH version of this setting is extremely well-motivated:  The standard reduction from communication complexity to one-pass streaming algorithms naturally gives you a one-way protocol where player i sends a single (private) message to player i+1.  Thus, lower bounds in this setting yield streaming algorithm lower bounds.

There are a couple of reasons why the one-way private-message model is not-as-studied, despite having such strong motivation.  First, there's a longer history and more established toolbox for proving lower bounds in the broadcast model.  Second, the lower bounds achieved from the broadcast model are typically very close to the upper bounds you get from the streaming algorithms, so it's not always necessary to use private-messages for your lower bounds.

One example where the communication bound crucially uses private-messages and not broadcast messages is the following bound for estimating the length of the longest increasing subsequence in a stream:

Gal, Gopalan SIAM Journal of Computing 2010. Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence

Note that their communication bound is for deterministic protocols.  Determining the space complexity of randomized streaming algs for estimating LIS is a big open problem.

For the private messages NIH communication model, there is a recent paper by Woodruff and Zhang that gives several strong communication lower bounds, as well as good applications towards distributed functional monitoring.   They mostly cover interactive (rather than one-way) communication complexity, but it's worth reading.

Woodruff, Zhang STOC12. Tight Bounds for Distributed Functional Monitoring


How to define list zipping categorically/inductively? Lists and fixpoints

The type of $A$-lists is defined as $\mu F_A$, where $F_A(X) = 1 + A \times X$ is the "cons-or-nil"-functor and $\mu$ is the least fixpoint operator. In Haskell syntax, this would correspond to:

data List a
   = Nil
   | Cons a (List a)

Here, Nil is the sole inhabitant of $1$, and Cons a as corresponds to A \times X. The fact that lists are fixpoints is reflected in the recursive definition of List a.

Initial algebras

It is well known that least fixpoints have semantics in initial algebras.
See e.g. Brian Howard's thesis. For our purposes, the type of $A$-lists is the initial algebra of the functor $F_A$.

Algebra map

Being an algebra, lists come with the algebra map $\phi\colon F_A (\mu F_A) \to \mu F_A$. It an isomorphism, so if we unpack we have $1 + A \times \mu F_A \cong \mu F_A$. In words, a list is either empty or consists of an $A$ and another list.

Universal property

Since $\mu F_A$ is initial, there is a unique algebra map from $A$-lists to any $F_A$ algebra. That is, if there is a morphism $\beta\colon F_A B \to B$, there is a unique algebra map $\mathrm{it}(\beta)\colon \mu F_A \to B$.

Warm up: Unzip

unzip takes a list of pairs $\mu F_{A \times B}$ and produces a pair of lists $\mu F_A \times \mu F_B$. It is thus a function from a list into something else, and could thus be defined via the universal property. All we need to do is to give $\mu F_A \times \mu F_B$ the right $F_{A \times B}$-structure:

$$F_{A \times B} (\mu F_A \times \mu F_B) = 1 + A \times B \times  \mu F_A \times \mu F_B$$
$$\hookrightarrow 1 + A \times \mu F_A + B \times \mu F_B + A \times B \times \mu F_A \times \mu F_B$$
$$\cong (1 + A \times \mu F_A) \times (1 + B \times \mu F_B) = \mu F_A \times \mu F_B$$

One can see that we inject into either the case "both lists stop" or "both lists continue". Apply the universal property, and you have unzip.

Puzzle: Zip

Now we would like to do the reverse. Given two lists, create a list of pairs. The Haskell version is simple:

zip (Cons a as) (Cons b bs) = Cons (a, b) $ zip as bs
zip _ _ = Nil

But now we need to write a function into a list. This suggests using the algebra morphism, but I can't figure out how. Alternatively, one might want to create an algebra structure for $\mu F_{A \times B}$ for some other functor, but I don't know which, and I don't know how to map from two fixpoints into a single one.

This complication is the same as in the definition of the Church predecessor function. We need to take the tail of a list, but we only have a folding operation given by (weak) initiality, which does not directly provide access to that, so we need to rebuild the tail from the right end.

It is the easiest to write the solution in a lambda calculus with products, exponentials and foldr for lists, witnessing weak initiality. In Haskell:

-- foldr :: (a -> b -> b) -> b -> [a] -> b

-- matching on whether a list is empty or non-empty
split :: [a] -> b -> (a -> [a] -> b) -> b
split as b f = fst (foldr (\a (b, as) -> (f a as, a:as)) (b, []) as)

zip :: [a] -> [b] -> [(a, b)]
zip = foldr (\a hyp ys -> split ys [] (\b ys -> (a, b): hyp ys))
            (\_ -> [])

With split we can branch on whether a list is empty or non-empty, and we rebuild the tail of the list from the end. zip can be translated back to cartesian closed categories with list objects, but of course a precise definition in that setting would be much less readable, because of the mandatory point-free definitions.


Problems in BQP but conjectured to be outside P Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain roots of unity.

Are there any other such problems?

To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on  this (see QAZ for precise definitions and references. This is another way to say I don’t even pretend to understand many of the problems of this list!)
Algebraic and Number Theoretic Problems
If I’m not mistaken, all problems listed before the Abelian hidden subgroup problem are special cases of it.

Factorization
Discrete logarithm
Pell’s Equation. Factoring reduces to Pell’s equation.
Principal Ideal Ideal problem. Pell’s equation reduces to this problem, which therefore at least as hard as factoring.
Unit Group problem
Class Group problem
Gauß Sums estimation
Matrix Elements of Group Representations
Group Order and Membership
The Abelian hidden subgroup problem
Some (but not all) non-Abelian hidden subgroup problems
Some (but not all) problems phrased as special cases of the hidden shift problem
Some (but not all) Hidden Nonlinear Structures problems
Exploring some graphs (Welded trees)
Group Isomorphism, for Abelian and some non-Abelian groups
Find some properties of Finite Rings and Ideals

Approximation and Simulation

Quantum simulation. Obviously $BQP$-complete
Computing some knot-invariants, including HOMFLY polynomial, of which the Jones polynomial is a special case. Some of them are $BQP$-complete
Computing some Three-manifold Invariants. Some of them are $BQP$-complete.
Estimating the thermodynamic partition function of some classical systems
Computing Zeta Functions over finite fields
A string rewriting problem is  $\mathit{PromiseBQP}$-complete
approximating matrix elements of powers of exponentially large sparse matrices.

Algorithm I don’t really  get.
These are mainly algorithms where QAZ claims a superpolynomial increase, but I don’t get why the original problem is supposed to be out of $P$. That said, I’ll bet lots of my money on QAZ being right and myself being wrong on that.

Pattern matching for large enough ($>\log(n)$) patterns
Some linear system problems, in $P$ but having a $\mathrm{polylog}$ quantum algorithm if the linear system is given as an oracle.
Computing the Electrical Resistance of a graph,has a $\mathrm{polylog}$ quantum algorithm if the electric circuit is given as an oracle
Weight Enumerators problem. Something related to code and partition functions, but I don’t understand what it is about.

$P$ problems 1st proved to be in $BQP$ and then in $P$
Here are some problems where an efficient quantum algorithm has been published before a classical one. In other words, they were once conjectured to be in $BQP$ but not in $P$, but this conjecture is now invalidated.

Satisfying more than $(\tfrac12-\tfrac{\text{constant}}{D})N$ (but less than $\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$) constraints of the  Max E3LIN2 problem. As pointed by Juan Berego Vega in the comments : there is now a classical algorithm for $(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$, which was motivated by the quantum result. (Blog post on this result, paper 1, paper2)
Recommendation systems (see Scott Aaronson’s blog post  for a more detailed explanation). Recommendation system — à la Netflix/Amazon/etc.— can be seen as completing a sparse $m×n$ matrix of low rank $k$ with very incomplete data. Known classical algorithm where polynomial in $m$, $n$ ad $k$. If the matrix is given as an oracle, Iordanis Kerenidis an Anupam Prakash found a $\mathrm{poly}(k)\mathrm{polylog}(mn)$ quantum algorithm finding samples of the unknown elements of the matrix in 2016 (paper). In 2018, while trying to prove this scaling is impossible to reach with a classical machine, Ewin Tang actually found a classical algorithm achieving the same performance under the same conditions (paper available here and here).


Modifying Edmonds' Blossom Algorithm Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by helicopter)?

Or in terms of Graphs:
Given an un-directed, connected, weighted Graph, what is the optimal start vertex and shortest path that visits every edge at least once (return to the start vertex not required)?

This question is an altered version of the Route Inspection Problem or Chinese postman problem.

The solution I have working is O(n^5) and I'm trying to improve this.

A Slow-ish Solution

First we need to change the graph so that an Eulerian Path exists. We can do this by finding the Minimum Weight, Perfect Matching between all odd vertices (removing two odd vertices since we want a Path and not a Cycle!)
We can use Edmonds' Blossom Algorithm to make the Matching computation efficient. My implementation is currently O(n^3)
Adding the computed edges into the Graph ensures an Eulerian Path exists (using the two skipped Vertices as start and end point)
We then compute the Eulerian Path and have an optimal solution for the chosen start and end vertex

Question:

The big questions is which two odd vertices to use as the start and end point for the Eulerian Path. So far I am computing all possible Matchings using the Blossom algorithm and taking the one with the minimum weight.

Is there a way that we can do this better? Potentially already integrating it into the Blossom algorithm? Are there any assumptions we can make about the vertices that are optimal? I.e. in a lot of cases two odd vertices with largest distance in the original graph are the best choice, however this is not always true (see Example 3).

  How can we adjust e.g. this implementation to consider only Matchings of maximum size - 1?

Example 1

Here is the optimal solution for a maze (the coloring indicates the chosen path). The computation for a given start-end vertex pair is relatively fast (around 100ms). However since this needs to happen for every odd-vertex pair, the overall computation time is over an hour.

There are 278 odd vertices in the maze. Hence we have to compute a Matching (278 * (278 - 1)) / 2 = 38503 times.

Example 2

In this example it is obvious that the optimal start and end points are very far apart.

Example 3

The maximal distance between two odd Vertices (the one at the top and the one at the bottom) is 50. However for the optimal path the distance is only 11.

PS: Had all the terms nicely linked in the question, but can only include two links due to not having reputation. Oh well...

You just have to solve the following problem: Find a matching of size exactly $k$ with minimum weight.

It can be solved by reducing to min weight perfect matching. See the paper by Ján Plesnı́k. There is a constant blow up in the number of vertices. So your original problem can be solved in $O(n^3)$ time.


What is the etiquette of naming concepts after people? There is a concept introduced by other researchers that I use in my work, and IMO it is appropriate to rename it to honor the inventors. Is it considered normal to just go ahead and name it like that in my own paper? Should I ask the inventors for their permission? Are there any other considerations I should be aware of?

It is best to spend some time researching to ensure that you associate the correct person with the idea and mention related ideas by others. You wouldn't want a misnomer to be called a Squark - like Squark says: "Be LessWrong". :)
By simply explaining the concept and mentioning that you believe it was first developed by a particular person you permit others to write to you, the author, and correct you with earlier references, this comes across as better than expounding falsehoods and detracting from the creditability of your work.
When the person whom you propose to associate with the idea is available (alive, and replies to email) it is useful and respectful to contact them; they may be planning a retraction or know of another whom is actually the developer, they mearly refined (or copied) the idea.
The Wikipedia section on concepts has this to say:

Concepts
Buildings, such as the Trump Tower, and companies, like the Ford Motor Company, are often named for their founders or owners. Biologic species and celestial bodies are frequently named for their discoverers. Alternatively, their discoverers may name them in honor of others. Occasionally, material goods, such as toys or garments, may be named for persons closely associated with them in the public mind. The teddy bear, for example, was named for President Theodore "Teddy" Roosevelt, because of a popular story in which the then-President objected to cruel treatment of a bear by hunters.
The fedora hat may be considered the "namesake" of a fictional character, Princess Fédora Romanoff, from an 1887 play, Fédora, by Victorien Sardou. In her famous portrayal of that character, Sarah Bernhardt wore a soft felt hat with a center crease, which became known popularly as a "fedora".


The flaw in Bellare-Rogaway (1995) model on authenticated key exchange Background:
In their 1995 paper, Bellare and Rogaway describe a formal model for authenticated key exchange in a tripartite setting. In this setting, each client has a shared key with a central server, which is willing to help in key distribution between any two mutually distrustful clients. This model is reminiscent of the security settings for Needham-Schroeder protocol, Kerberos and Active Directory.
For brevity, let's denote the Bellare-Rogaway-1995 model by "BR95."
The adversary in the BR95 model is a probabilistic polynomial-time algorithm, which has total control over the communication between each pair of parties. Moreover, the adversary
can mount a number of attacks on any single party. The attacks include revealing the session key, corrupting a party, and a special "TEST" attack, which is described next.
When the adversary has finished with experimenting different attacks on the parties, it makes a final TEST attack. The attack is restricted in several ways; for instance, the adversary cannot mount the TEST attack on a corrupted party, or on a party whose session key is already revealed. (Nor can the adversary mount the test attack on the partner of such party.)
On issuing the TEST attack, the adversary is given either of the following, each with probability 1/2:

The session key of the party on which the TEST attack is mounted; or
A random string of the same length as the session key.

The idea is that the adversary must be unable to distinguish the above two cases with advantage more than negligibly over 1/2.

The Flaw
In another paper, Bellare, Pointcheval, and Rogaway write:

Soon after the appearance of [BR95], Rackoff came up with an example showing how the definition given in that paper was not strong enough to
guarantee security for certain applications using the distributed session key. The
authors of [BR95] traced the problem to a simple issue: they had wrongly made the
restriction that the TEST query be the adversary's last. Removal of this restriction
solved the problem. This minor but important change in the definition of [BR95],
made in 1995, has since been folklore in the community of researchers in this
area, and is explicitly incorporated into our current work.

Along the same lines, Shoup explains:

We have taken the opportunity here to correct a serious flaw that appears in [BR95,...] that was pointed out to the authors of [BR95] by Charles Rackoff. In the formulation in [BR95, ...], the TEST operation is only allowed to be performed at the very end of the adversary's execution, whereas we have allowed it to occur at any time.

Shoup then tries to pinpoint the flaw on a contrived version of a protocol called "DHKE-1" (designed by himself). However, the contrived version is too "non-standard" for me to understand. Specifically, it includes the operation (or attack) core dump, which is not compatible with the attacks listed in the BR95 model.

Question
Could you please illustrate the flaw in the BR95 via an example, where disallowing the TEST attack in the middle of execution can result in a false proof of security?

The "protocol interference" attack:

From Fig 2 of http://seclab.cs.ucdavis.edu/papers/Rogaway/3pkd.pdf --

In Flow3A (resp. 3B), before the intended message is delivered, the adversary manages to obtain an encryption under $K_A$ (resp. $K_B$) of a different session key $\sigma'$ (through interacting with $S$ in a higher-level protocol) and sends this "forged" message to $A$ and $B$. This is a successful man-in-the-middle style attack.

Why the security definition should include TEST in the middle of execution:

If the interaction doesn't terminate immediately after TEST, then the forged session breaks security in a very obvious way. Namely, with probability 1/2, the TEST operation hands a key to the adversary; it becomes the "higher-level protocol" we're worried about with constant probability. If the adversary is not forced to immediately halt, then it can use this key to perform the man-in-the-middle attack above (at least in the BR95 scheme).

The security definition given in BR95 is, therefore, too weak as this is a plausible attack (Why would an adversary arbitrarily halt, especially after they've just extracted useful information?). That is, a protocol vulnerable to this attack is (wrongly) proven secure under the given definition.