Complexity of a switch network problem A switch network (the name is invented) is made with three types of nodes:

one Start node
one End node
one or more Switch nodes

The switch node has 3 exits: Left, Up, Right; has two states L and R and
a target state TL or TR. Each switch can be traversed with the following rules:

always from Left to Up; the state of the switch changes to L
always from Right to Up; the state fo the switch changes to R
from Up to Left only if the switch is in state L; the state doesn't change
from Up to Right if the switch is in state R; the state doesn't change
never from Left to Right or Right to Left

Figure 1. Switch node in state L with target state TR
These properties also hold:

0, 1 or 2 of the exits of a switch can be isolated (not connected to another switch);
a path can just "touch" a switch to change its state: enter from Left and exit from Left or enter from Right and exit from Right;
there are no restrictions on the number of times a switch can be traversed / touched.

The decision problem is: "Does a path from the Start node to the End node
exist such that all the final states of the switches match the corresponding target state?"
Obviously, all the switches that are not initially in their target state must be traversed (or touched) at least once;
This is a quick draw of a trivial network (made with Excel ... I'll make a better one):

A trivial solutions is:
S -> 1 -> 2 -> 3 -> 2 -> E -> 1 -> E

EDIT 2:

Is this problem known? ---> you gave me the good reference to the Hearn's thesis (constraint graphs);

The problem is in $NPSPACE = PSPACE$; before posting a sketch of my proof that it is in NP, I found an error; so the open questions are again:

2 . Is it $\mathsf{NP}$?
3 . Has the problem any chance to be $\mathsf{NP\text{-}complete}$?

The problem is at least NP-hard, by a reduction from 3-SAT.

First consider the problem of finding a path from the Start to the Exit of the following directed graph with the restriction that no path may visit all three (square) nodes of a clause:

For this graph, such a path only exists if the formula $(X1 \lor X2 \lor X3)\land(X1\lor\neg X2\lor X4)$ can be satisfied. We can build such graphs for arbitrary formulas in 3-CNF, and finding such a path is NP-complete.

We transform these graphs to a switch network. For this we use three gadgets:

Every circle node and bidirectional edge becomes a Wire, forming the connections between switches.
Every directed edge becomes a One-way gadget consisting of a single switch (see below).
Every square node represents one of the three switches that are part of a Clause gadget (see below).

In the following illustrations, switches are drawn as two incoming arrows, one of which is dashed (disabled). The target direction is drawn with a black circle (such that the solid arrow must eventually be on the side of the circle).

Remark: We will use boldface to distinguish the Exit of the graph from exits of gadgets.

For the One-way gadget, entrance $A$ cannot be reached from exit $B$ until $B$ has been reached from $A$.
For the Clause gadget, entrances $X1$, $X2$ and $X3$ lead to exits $X1'$, $X2'$ and $X3'$, respectively.

Recall that for the original graph, finding a path that led to the Exit and did not visit all three square nodes of any clause was NP-complete.
Now consider the problem of reaching the Exit of the transformed graph without worrying about the target positions of the switches.

Observe that any path that is a solution for the original graph problem is also a solution for the transformed graph.
So assume a path for the transformed graph is not a solution for the original graph.
This may happen in two cases:

A One-way gadget is traversed in the unintended direction ($B$ to $A$).
A path traverses all three paths of some Clause gadget.

In the first case, the One-way gadget must have first been traversed in the intended direction, in which case the path might as well have avoided traversing it in the first place.

So consider the second case where the path traverses all three switches of some Clause gadget.
Then that gadget will have all its three switches flipped (see below). This is where we make use of the target positions.
Notice that the gray backbone of the Clause gadget can no longer be reached, meaning that the switches can no longer be directed to their target positions.
In this case, we say that this Clause gadget is unrecoverable.

It remains to show that for any solution of the original graph problem, the switches of the transformed graph can be placed in their target position.
For this, we make use of the fact that the Exit wire can only be reached when there is a solution, or some Clause gadget becomes unrecoverable.

To place switches in their target position, we can now add additional One-way gadgets from the Exit wire to the entrance of every existing One-way gadget, as well as to the three exit wires of all Clause gadgets.
Then, once the token reaches the Exit, all the additional One-way gadgets can be traversed (and thereby put in their target position), and also put the remaining switches in their target positions (unless there is an unrecoverable clause).
Finally, the token can return to the Exit and the puzzle is solved.

We should remark that Clause gadgets can only be recovered when entered from an untraversed exit; and due to the One-way gadgets that are placed between Clause gadgets and the next variable, this cannot happen until the Exit wire is reached.

Hence, the switch network problem is NP-hard.

It is still unclear if the problem is in NP or PSPACE-hard.
An NP-hardness reduction constructing a planar switch network will have great implications for restricted variants of Sokoban, namely because all switches are equivalent to the Sokoban gadget below.


Decidability of diophantine equations over {=, +, gcd} It is well-known that polynomial diophantine equations are undecidable (Hilbert's 10th problem): that is, given a quantifier-free formula over the language $\{=, +, \cdot, 1\}$ (of equality, addition, multiplication, and the constant $1$), with free variables taking values in the integers, deciding whether the formula is satisfiable is undecidable.
If multiplication $\cdot$ is replaced by the binary greatest-common-divisor (gcd) function, defined appropriately for 0 and negative numbers, does the satisfiability problem remain undecidable?

For example, the input might be a formula like
$$
a + b = c \land \gcd(a, b) = 2 \land \gcd(a, c) = 1
$$
or
$$
\gcd(a, \gcd(b, c) + b) = a + c \land \lnot (\gcd(a, b) = a).
$$
I suspect this to be a basic result in the study of decidability results for integer theories, but this came up in another context and I am not entirely familiar. From a brief literature search (see On Decidability Within the Arithmetic of Addition and Divisibility, Marius Bozga and Radu Iosif) I know of the following classical results:

The theory of $\{=, +, |\}$ (where $|$ is divisibility) allowing quantifiers is undecidable (Julia Robinson 1949).

The satisfiability of quantifier-free formulas over $\{=, +, |\}$ (i.e. existential fragment of the above) is decidable. (The diophantine problem for addition and divisibility, Leonard Lipshitz 1976.)

Divisibility can be defined in terms of gcd ($a \mid b \iff \gcd(a, b) = a$), but vice versa requires existential quantification ($\gcd(a, b) = c \iff (c \mid a) \land (c \mid b) \land \exists x \exists y.\; c = ax + by$), which won't work in quantifier-free formulas in a negated context, so at least at first glance I am not sure that gcd is equivalent to divisibility for the purposes of decidability.

($=$ is a logical symbol, hence I will not write it as part of the signature.) The satisfiability problem is decidable, as $\gcd$ has both a universal and an existential definition in terms of $|$, $+$, and $\le$:
$$\begin{align*}
\gcd(a,b)=c&\iff c\ge0\land c\mid a\land c\mid b\land\forall d\:(d\mid a\land d\mid b\to d\mid c)\\
&\iff c\ge0\land c\mid a\land c\mid b\land\exists u,v\:(a\mid u\land b\mid v\land c=u+v).
\end{align*}$$
Thus, any existential sentence over the structure $\langle\mathbb Z,+,\gcd\rangle$ (or even $\langle\mathbb Z,{\le},+,\gcd\rangle$) can be (in polynomial time) converted to an equivalent existential sentence over the structure $\langle\mathbb Z,{\le},+,|\rangle$, which can in turn be converted to an equivalent existential sentence over the structure $\langle\mathbb N,+,|\rangle$ in the obvious way. The last problem is decidable by the result of Lipshitz [1] quoted in the question.
Reference:
[1] Leonard Lipshitz: The Diophantine problem for addition and divisibility, Transactions of the American Mathematical Society 235 (1978), pp. 271–283, doi: 10.1090/S0002-9947-1978-0469886-1.


Shortest paths disallowing each edge I'd appreciate any pointers or terms that could get me started in the right direction.

We have a directed graph $G=(V,E)$ and lengths $l_{ij}$ for each edge $ij$ that can be assumed positive.  There is a special start node $s$ and end node $t$.

For each edge $ij$, we'd like to compute the length of the shortest path from $s$ to $t$ that does not use edge $ij$.

A simple brute force algorithm is to run a shortest path algorithm for each edge, each time removing a different edge from the original graph.  Is there a more efficient algorithm that takes advantage of the fact that there is a lot of repeated computation happening in this brute force algorithm?

Thanks in advance.

The problem you mention is called "replacement paths".
Here are a few references:

Gotthilf and Lewenstein, Improved algorithms
for the k simple shortest paths and the
replacement paths problems. Inf. Proc. Letters,
109(7):352–355, 2009. This paper gives the fastest to date exact algorithm for the replacement paths problem, running in time $O(mn+n^2\log\log n)$ time in graphs with $n$ nodes and $m$ edges.
A. Bernstein. A nearly optimal algorithm for approximating
replacement paths and k shortest simple
paths in general graphs. In Proc. SODA, pages
742–755, 2010. This paper amazingly gives a quasilinear time approximation scheme for the problem.
J. Hershberger, S. Suri, and A. Bhosle. On the
difficulty of some shortest path problems. In Proc.
STACS, pages 343–354, 2003. This paper shows that any path-comparison algorithm solving the replacement paths problem exactly must take at least $\Omega(m\sqrt{n})$ time.
V.Vassilevska W., R. Williams. Subcubic Equivalences between Path, Matrix and Triangle Problems. In Proc. FOCS, pages 645-654, 2010. We show that if you obtain an $O(n^{3-\varepsilon})$ time exact algorithm for replacement paths for any constant $\varepsilon>0$, then this can be converted to an $O(n^{3-\varepsilon'})$ time algorithm for all pairs shortest paths for constant $\varepsilon'>0$. Such a truly subcubic algorithm for all pairs shortest paths is a longstanding open problem.
O. Weimann, R. Yuster. Replacement Paths via Fast Matrix Multiplication. In Proc. FOCS, pages 655-662, 2010. and V. Vassilevska W. Faster Replacement Paths. In Proc. SODA, pages 1337-1346, 2011. These papers show how to use fast matrix multiplication to find replacement paths in graphs with integer edge weights in the interval $\{-M,\ldots, M\}$. The latter paper gives the best known runtime so far, $\tilde{O}(Mn^\omega)$.


Reference request: An algebraic characterisation of LTL[XF]-definable word languages I'm looking for a reference to the fact that LTL[XF]-definable languages (LTL where only the (strict) finally/future modality is allowed) correspond to the variety $\mathbf{R}$ (see: 1).
A similar characterisation is available for LTL[XF,XP], namely the variety $\mathbf{DA}$, see: Theorem 11 from 2.
1 Brzowoski, Fich: Languages of R-Trivial Monoids LINK
2 Tesson, P., Thérien, D.: Diamonds are forever: the variety DA LINK
PS: I have an idea how to prove it (by employing the correspondence that R = partially-ordered DFA), but before writing the result it would make sense to check whether this is already known in the literature (although I do not claim any breakthrough).

An algebraic characterisation of the restricted temporal logic (fragment using only next and eventually, but not until) is given in [1].
The expressive power of this fragment is the set of regular languages whose syntactic monoid are locally $\cal L$-trivial.
I am not sure of the result you are looking for, but this article probably contains enough material to help you.
[1] J. Cohen, D. Perrin and J.-É. Pin, On the expressive power of temporal logic for finite words, J. Comput. System Sci. 46 (1993), 271-294.


Can we distinguish strictly syntactic and semantic methods in programming language? While discussion strong normalization proofs, this comment contrasts the "normal forms model" with "purely syntactic methods".

This brings me back to a more basic question: can we still distinguish syntactic and semantic constructions strictly, in the face of syntax-based models? What about term models for algebras, Henkin models for first-order logics? What about structural operational semantics? Since term models can be isomorphic to syntax, it seems hard to make a firm distinction.

Until I studied the difference between proof theory and model theory in logic, I was even baffled by the idea that "static type systems are a syntactic method". After all, a type system reasons about types, which are an abstraction of program behavior (and with dependent types, an arbitrarily precise one).

No, you cannot strictly distinguish syntactic from semantic methods, but the distinction still ends up making sense.

Structural operational semantics is not denotational, because it is not a compositional method of giving semantics to a programming language.

However, you can build denotational models out of a structural operational semantics by using a realizability or logical relations method. As an example, see Robert Harper's Constructing Type Systems over Operational Semantics.

Term models are denotational, but generally semanticists are not satisfied with them. What they usually want is a category of models in which the term model is initial, which can be used to prove soundness and completeness results.  (The soundness and completeness of the typed lambda calculus for cartesian closed categories is the paradigmatic example; see Alex Simpson's Categorical Completeness Results for the Simply-Typed $\lambda$-calculus for some details.)

In the other direction, if you have a denotational semantics, you might want to figure out what the syntax for it is. Then you want to go and find a syntax and abstract machine whose term model can serve as an intitial object in a suitable category of models.
For instance, game semantics began its life as a purely semantic construction, and eventually led to work on operational game semantics --- a recent example of which is Alexis Goyet's The lambda lambda-bar calculus: A dual calculus for unconstrained strategies.

Overall, you can think of structural operational semantics as a way of specifying abstract machines, which we hope are easy to implement. A denotational semantics gives a compositional model of a language, which we hope is easy to reason about. If we have both, then we can both implement and reason about the language.

Normalization theorems are an interesting ambiguous case. Usually, to prove normalization, you need a semantic model (typically a logical relation). However, once you know that normalization holds, many properties can now be proved by induction on normal forms, which is a purely syntactic argument.
For weak logics (anything up to first-order logic without induction, roughly), you can prove normalization syntactically, using the technique of hereditary substitution. In these logics, the subformula property holds, and so you can prove normalization by induction on types. See Frank Pfenning's paper Structural Cut Elimination for an explanation of how this works.


Monotone-2SAT and Vertex Cover The following decision problem is called k-True-Monotone-2SAT:

  Given a 2-CNF boolean formula $F$ that does not contain any negated variables
  and given a positive integer $k$, can $F$ be satisfied by setting $k$ or fewer
  variables to true?

It is NP-complete: it's easy to see a straightforward reduction from Vertex Cover to it (i.e. can we cover all the edges with $k$ or fewer nodes?).

The following decision problem is called Monotone-2SAT:

  Given a 2-CNF boolean formula $F$ that does not contain any negated variables, is it satisfiable?

As a decision problem, Monotone-2SAT is trivial. The answer is always YES: just set every variable to true.

But consider its counting version, called #Monotone-2SAT:

  Given a 2-CNF boolean formula $F$ that does not contain any negated variables, how many satisfying assignments $F$ has?

Surprisingly, #Monotone-2SAT is #P-complete.

Now here is the question. Suppose we have an oracle for #Monotone-2SAT, which returns the exact solution count of a Monotone-2SAT formula: how such solution count can be used to solve k-True-Monotone-2SAT?

I'm asking this because I do not immediately see how the solution count may give information on how many solutions have k or less literals set to true and how many don't.

The name “#Monotone-2SAT” usually refers to the problem of counting the satisfying assignments of a given monotone 2CNF formula, without a restriction on the number of variables set to true.  The stated “Monotone 2SAT” problem, or the Vertex Cover problem as is usually called, is not the decision version of #Monotone-2SAT because of the additional restriction on the number of variables set to true.  (This is certainly unfortunate.)  Therefore, Vertex Cover (or “Monotone 2SAT”) is not reducible to #Monotone-2SAT in the same way as 3SAT is reducible to #3SAT.

Note that Vertex Cover is clearly in NP and that #Monotone-2SAT is known to be #P-complete (see my answer to your previous question for the reference) and hence NP-hard.  Therefore, Vertex Cover is reducible to #Monotone-2SAT.  (Note that this does not require the fact that Vertex Cover is NP-complete.)  To construct an actual reduction, you can simply composing several reductions as always.  There may be a simpler reduction than this, but I do not expect that seeking for a simpler reduction gives much insight into either problem.


VC generalization bound extended to other types of target functions In Y. S. Abu-Mostafa's book "Learning from Data", he mentions on page 55 after deriving the VC generalization bound for a binary target function that "it can be extended to other types of target functions". I have looked online for quite a bit but it's really not clear to me how that should work. I'm particularly interested in continuous target functions, where hypothesis $h \in \mathcal{H}$ maps input space $\mathcal{X}$ to $\mathbb{R}^N$, rather than classifications. But I don't see how shattering could be adapted for these target functions.

Pseudo dimension and fat shattering dimension are (some of the) analogue of VC dimension in the regression setting. See https://ttic.uchicago.edu/~tewari/lectures/lecture15.pdf (section 3)


Investigation of Symbol Minimal Context-Free Grammars for the Language $a^n$ Question

Given the language $L_n = \{ a^n \}$ for a natural number $n \geq 2$. Is there a symbol minimal context-free grammar $G$ that generates $L_n$ and contains a rule of the form $A \rightarrow aB$ where $A$ and $B$ are non-terminals?

Remark

Symbol minimal means that there is no other context-free grammar that generates $L_n$ with fewer characters (symbols) for all rules. For instance, the number of symbols of the rules in $\{ S \rightarrow a, S \rightarrow aS \}$ is 7 (these rules are also minimal for $\{ a \}^+$).

Known Results

Facts about G (a symbol minimal context-free language for $L_n$) that I have already proved:

The right hand side of the rules of $G$ consist of at least 2 characters (non-terminals and/or terminals) (otherwise it’s easy to find a grammar that has fewer symbols).
For each non-terminal of $G$ there exists exactly one rule (can be shown by contradiction).
There are no loops in the derivations of $G$ (because $L_n$ is finite).
There is an upper bound for the number of symbols: we can trivially generate $L_n$ with the rules $\{ S \rightarrow a^n \}$. We count the number of symbols and get $n + 2$ – that’s an upper bound.

I wrote a program that finds symbol minimal grammars for a specific $n$ by creating all possible grammars generating $L_n$ (there are only a finite number because we have an upper bound). Here are the results for some small $n$:

$n = 2$: $\{ S \rightarrow aa \}$, $4$ symbols
$n = 3$: $\{ S \rightarrow aaa \}$, $5$ symbols
…
$n = 7$: $\{ S \rightarrow aaaaaaa \}$, $9$ symbols
$n = 8$: $\{ S \rightarrow a^8\}$, $\{ S \rightarrow AA, A \rightarrow a^4 \}$, $\{ S \rightarrow AAAA, A \rightarrow aa \}$, $10$ symbols
$n = 9$: $\{ S \rightarrow AAA, A \rightarrow a^3 \}$, $10$ symbols
$n = 10$: $\{ S \rightarrow AA, A \rightarrow a^5 \}$, $\{ S \rightarrow A^5, A \rightarrow aa \}$, $\{ S \rightarrow aA^3, A \rightarrow a^3 \}$, $11$ symbols
$n = 11$: $\{ S \rightarrow aAA, A \rightarrow a^5 \}$, $\{ S \rightarrow aA^5, A \rightarrow aa \}$, $\{ S \rightarrow aaA^3, A \rightarrow a^3 \}$, $12$ symbols
$n = 12$: $\{ S \rightarrow AAA, A \rightarrow a^4 \}$, $\{ S \rightarrow A^4, A \rightarrow aaa \}$, $11$ symbols
$n = 13$: …,  $12$ symbols
$n = 14$: …,  $13$ symbols
$n = 15$: …,  $12$ symbols
$n = 16$: …,  $12$ symbols

There are nice „ups and downs“ in the number of symbols, right? I have seen grammars that contain rules like $A \rightarrow aB$ but they were not symbol minimal …

First, let me add some more to the known results section, specific to your question.

$B$ must occur in another RHS than $A\rightarrow aB$, or we could just copy the rule that has $B$ on the LHS instead of $B$ to the above rule to get a smaller system.
In any other RHS that has $B$, there can be no terminal symbol because instead of $aB$ we could write $A$.
$A$ must occur at least $4$ times on the RHS, otherwise, we could just write $aB$ instead of it.

This already shows that $n$ will be quite large that satisfies these. However, I think such an $n$ might exist. Below I give a set of rules for $n=93$ with $28$ symbols and I challenge all to make a smaller system! (If the challenge is too easy, generalize it in the obvious way...)

$S\rightarrow AAAACCC$

$A\rightarrow aB$

$B\rightarrow aaa$

$C\rightarrow DDD$

$D\rightarrow BBB$

Update

Well, this is not optimal for any $n$ as shown by Peter in the comment...


Finding $x_1,x_2,...,x_k$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is minimal Here is a problem I'm trying to solve:

Given an integer $n$ return a list $[x_1,x_2,...,x_k]$ such that $n=x_1!+x_2!+...+x_k!$ and $k$ is as low as it can be.

I'm thinking of creating a list of n ones, then pairing them as long as I can (so for example $[1,1,1,1,1]$ becomes $[2,2,1]$) then I want to exchange all triples of $[2,2,2]$ to one $3$ (because $2!+2!+2!=3!$) and so on...

Intuitively this should be correct, and also quite fast - the input on which I'm executing my "concatenations" shrinks as fast as factorial function grows...

But is my method correct? And also if I were to find complexity of my algorithm in terms of $n$, how should I do that? One more thing, maybe there is simpler way to solve this algorithmic problem - any ideas?

Your algorithm is correct and its running time is in $\Theta(n)$ which is exponential to the input size. But we can use simple greedy algorithm to achive $O(\log n)$. Find largest number $i$ such that $i! \le n$. To do so just simply iterate through numbers in $1,\cdots, \log n +1$. And do the same for $n -i!$.


Places where the order of points along a simple polygon passing through them is useful We know that finding the convex hull of $n$ points on a plane has a lower bound of $\Omega(n\log n)$ on its running time. However, if the points are given in the order in which they occur along some simple polygon that has those points as its vertices, then their convex hull can be found in linear time.

I find this intriguing because there are probably too many simple polygons that have the given points as their vertices and therefore, intuitively, the order along one of them sounds like a very useless piece of information. And yet, it helps.

So my question is, are there other places where the same information helps in bringing down the running time of an algorithm?

As a side, I also want to know bounds on the number of permutations of a given set of points on a plane for which there is a simple polygon with those points as its vertices so that the order in which the points occur along the polygon is the same as the order in the permutation. What's known about this?

Your comment that "there are probably too many simple polygons" is the key, because actually there aren't that many.  $n$ points have $n!$ paths (permutations) and $(n-1)!/2$ polygons if we allow self intersections -- that is, $2^{\Theta(n \log n)}$.

The numbers of paths or polygons without self intersections are $2^{\Theta(n)}$, easiest observed from the fact such paths and polygons can be completed to triangulations, the number of triangulations of a given point set in the plane is $<30^n$ [Sharir-Sheffer'09, latest in a long history], and the number of proper subsets of edges of each triangulation is $<2^{3n-6}$.

The convex hull of simple polygons has been one of my favorite things since using it to find and/or formulae for polygons in SIGGRAPH'88 http://dx.doi.org/10.1145/54852.378472


What is the complexity of counting parse trees? A Counting Problem

Given a CFG $G$ and a string $s$, how many distinct parse trees are there for the string $s$?

An Example Instance

Let's consider an example instance consisting of a CFG $G$ with grammar rules:

$S \rightarrow aS$

$S \rightarrow aSb$

$S \rightarrow \epsilon$

And, a string $s = aaab$.  Then, there are three parse trees for $s$:

(1) $S \rightarrow aS \rightarrow aaS \rightarrow aaaSb \rightarrow aaab$

(2) $S \rightarrow aS \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$

(3) $S \rightarrow aSb \rightarrow aaSb \rightarrow aaaSb \rightarrow aaab$

  Question

  What is the complexity of this counting problem?  Is it hard for any
  notable counting complexity classes?

Edit: Based on @MRC's comments, it seems that this problem is equivalent to calculating the weight of $s$ relative to the weighted CFG obtained by attaching the semiring $(\mathbb{N}, +, \times)$ to $G$ and assigning the weight of 1 to each of $G$'s rules.

Because you are asking the question in general, the answer will be: uncertain number of trees.

Consider a degenerate case, when you have such a CFG:

$S\rightarrow aA$

$A\rightarrow B$

$B\rightarrow A$

$A\rightarrow aS$

$S\rightarrow a$

This is a valid grammar, right? Though not normalized.
Obviously you can "run" between $A$ and $B$ for any number of times for any given string $s$ generated by this grammar. Each transition between $A$ and $B$ gives you new node in a parse tree, thus we have uncertain number of them.

So, I would rather ask about normalised CFG. For a normalised CFG I guess it should be only one parse tree per the given string $s$.


"a" or "an" with big O notation? A simple (though somewhat pedantic) question: when using big O notation in a sentence, should it be preceded with "a" or "an"?  Example:

  The extra loop results in a/an $\mathcal{O}(N)$ increase in cost.

The ubiquitous Cormen textbook notes on page 47:

  For a given function $g(n)$, we denote by $\mathcal{O}(g(n))$ (pronounced “big-oh of g of n” or sometimes just “oh of g of n”)

which would seem to indicate "a" should precede something pronounced "big-oh".  Later on the same page, however, the textbook uses the phrase "an $\mathcal{O}(n^2)$ upper bound."   Which is used more in the literature?  It seems like a triviality, but as someone working on the edge of theoretical computer science from a primary focus on another field, I'd like not to sound like an outsider.

Evidence for "an":

Ajtai, Miklós, János Komlós, and Endre Szemerédi. "An O(n log n) sorting network." Proceedings of the fifteenth annual ACM symposium on Theory of computing. ACM, 1983.
Asadpour, Arash, et al. "An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem." SODA. Vol. 10. 2010.
Bracha, Gabriel. "An O(log n) expected rounds randomized Byzantine generals protocol." Journal of the ACM (JACM) 34.4 (1987): 910-920.
Hwang, F. K. "An O(n log n) algorithm for suboptimal rectilinear Steiner trees." Circuits and Systems, IEEE Transactions on 26.1 (1979): 75-77.
Tarjan, Robert E., and Christopher J. Van Wyk. "An O(n log log n)-time algorithm for triangulating a simple polygon." SIAM Journal on Computing 17.1 (1988): 143-178.
Yao, Andrew Chi-Chih. "An O (|E| log log|V|) algorithm for finding minimum spanning trees." Information Processing Letters 4.1 (1975): 21-23.

Of course, these examples alone merely suggest that "an" is acceptable. This list does not show that "an" is necessarily standard or preferred nor does it show that "a" is unacceptable.


Faster pseudo-polynomial time algorithms for PARTITION I want to partition N given numbers (may or may not be equal) into 2 subsets such that the 2 subsets have sum as close as possible and also the cardinality of the sets are equal (if n is even) or differ only by 1 (if n is odd).

I think we can do this in pseudo polynomial time $O(n^2 A)$, where $A$ is the sum of numbers in the set.

Can I do better than this? Namely, is there a pseudo polynomial time algorithm that runs in time $O(n^c A)$ with $c < 2$?

Thanks in advance!

One can solve the decision problem in $\tilde{O}(nA)$ time.

Let the sequence of numbers be $S$. Define $F_S$ to be a set such that $(i,j)\in F_S$ iff there exist a subsequence of $S$ of length $j$ that sums to $i$. If we have computed $F_S$, then we just need $O(nA)$ additional time to go thorough $F_S$ to solve your problem.

If $S_1$ and $S_2$ are two subsequences that partitions $S$, then

$$F_S = F_{S_1} + F_{S_2}$$

where $A+B=\{a+b  | a\in A, b\in B\}$ is the minkowski sum, and addition between tuples are defined coordinate-wise.

Claim: Computing $F_S$ from $F_{S_1}$ and $F_{S_2}$ takes $\tilde{O}(|S|A)$ time.

Proof: Apply 2D convolution on two tables of size $A\times |S|$.

The algorithm partition the sequence to two equal sized sequences, apply recursion to each, and take the minkowski sum of the result. Let $T_A(n)$ be the worst case running time when the input to the algorithm has $n$ elements and $A$ is an upper bound of the sum.
We have
$$
T_A(n) = 2 T_A(n/2) + A \tilde{O}(n)
$$
Which shows $T_A(n) = \tilde{O}(n A)$.

The hidden $\log$ factor is $\log n \log nA$.


Separation of limited nondeterminism classes? It is interesting to find the best lower bound on the  number of nondeterministic bits needed to solve satisfiability problem. Let $\beta_k P$ be the class of problems solvable by a  nondeterministic Turing machine in polynomial time and using $O(\log^k n)$ nondeterministic bits.

$P=\beta_1P$. Notice that $O(\log n)$-clique
 is in $\beta_2P$.
It is an open problem whether $\beta_1 P = \beta_2 P$. It is known that
$\beta_1P \neq \beta_2P$ implies $P \neq NP$

  What is the most serious attempt at separating  $\beta_1P$ from $\beta_2P$?

Does $\beta_kP=NP(\log^k n)$ form an infinite hierarchy?

This reference contains a survey of limited nondeterminism:

A SURVEY OF LIMITED NONDETERMINISM
IN COMPUTATIONAL COMPLEXITY THEORY

For attempts to separate the bounded nondeterminism hierarchy, I think monotone dualization of prime formulas is the most salient topic.

Consider the decision problem

  MONOTONE DUAL
  Input: two monotone CNF formulas, from which no literals can be removed
  Question: is the one formula the dual of the other?

MONOTONE DUAL can be decided with $O((\log\ n)^2/\log\ \log\ n)$ nondeterministic steps.  There is also a quasi-polynomial $n^{o(\log\ n)}$ time upper bound for this problem which has stood since 1996.

So MONOTONE DUAL is in co-$\beta_2$P and also doesn't seem to require the full power of this class.  On the other hand, MONOTONE DUAL may be a good candidate for a problem that is outside P = co-$\beta_1$P.

This is surveyed in:

Thomas Eiter, Kazuhisa Makino, and Georg Gottlob, Computational aspects of monotone dualization: A brief survey, DAM 156 2035– 2049, 2008.  doi: 10.1016/j.dam.2007.04.017 (preprint)

I am not sure there is more work along these lines.  As with many other areas with the potential to separate P from NP, after some promising early progress new ideas now appear to be necessary.


Brute force search algorithm for semidefinite programming (representation of spectrahedron) I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for any objective, we can get a good approximation by searching over these finite points?

In a linear program, the answer is positive; we can search over all the vertices of the constraint, which is a convex polytope.

This question is closely related to the representation of a spectrahedron, which is the intersection of the PSD cone with planes or half-spaces. Specifically, if the spectrahedron is finite representable, then we can search the values of the objective over the basis of the representations.

The question is not very well defined.  E.g., if the SDP has an optimal solution, then "searching" that one optimal solution is (trivially) enough to find a good approximate (in fact optimal) solution.  Similarly, any algorithm that solves the SDP in finite time will find a "good approximate solution" while considering only finitely many points of the SDP.

But if you mean to ask whether the feasible region of every SDP is the convex closure of finitely many extreme points, or whether, for any SDP, there is a finite set $S$ of points in the feasible region such that, for any linear objective, some point in $S$ is approximately optimal, the answer is surely no.

For example, fix $\epsilon>0$ and consider the SDP
$$\min \{\epsilon X_{11} + X_{22} :
X\in\mathbb{R}^{2\times 2},~X \text{ p.s.d.}, X_{12} = X_{21} = 1\}.$$
The feasible region consists of 2d p.s.d. matrices of the form $\left(\begin{array}{cc}x&1\\1&y\end{array}\right)$. The matrix is p.s.d. iff $x,y> 0$ and $xy\ge 1$.  So there are infinitely many matrices $X$ (those with $y=1/x$) in the feasible region that are not convex combinations of other matrices in the region.

Further, the unique optimal point has $(x,y)=(1/\sqrt{\epsilon}, \sqrt{\epsilon})$ and has value $2\sqrt{\epsilon}$.  The feasible region is independent of $\epsilon$, and, for any finite subset $S$ of that feasible region (where $S$ is independent of $\epsilon$), letting $x' = \min\{ X_{22} : X\in S\} > 0$, no point in $S$ has value less than $x'$.  So, for sufficiently small $\epsilon$ (where $\sqrt\epsilon \ll x'$), no point in $S$ approximates the optimum well.


The origin of the notion of treewidth My question today is (as usual) a bit silly; but I would request you to kindly consider it.

I wanted to know about the genesis and/or motivation behind the treewidth concept. I sure understand that it is used in FPT algorithms, but I do not think that that was the reason why this notion was defined.

I have written up the scribe notes on this topic in the class of Prof Robin Thomas. I think I understand some of the applications of this concept (as in it transfers separation properties of the tree to the graph decomposed), but for some reason I am not really convinced that the reason this concept was developed was to measure closeness of a graph to a tree.

I will try to make myself more clear (I am not sure if I can, please let me know if the question is not clear). I would like to know if similar notions existed elsewhere in some other branch of mathematics from where this notion was supposedly "borrowed". My guess will be topology -- but owing to my lack of background, I cannot say anything.

The primary reason as to why I am curious about this would be -- the first time I read its definition, I was not sure why and how would anyone conceive of it and to what end. If the question is not still clear I would finally try stating it this way - Let us pretend the notion of treewidth did not exist. What natural questions (or extensions of some mathematical theorems/concepts) to discrete settings will lead one to conceive of a definition (let me use the word involved) as treewidth's.

Here's how you could come up with tree-width concept yourself.

Suppose you want to count the number of independent sets in the following graph.

Independent sets can be partitioned into ones where top node is occupied, and ones where it is unoccupied

Now, notice that knowing whether top node is occupied, you can count number of independent sets in each subproblem separately, and multiply them. Repeating this process recursively gives you an algorithm to count independent sets based on graph separators.

Now, suppose you no longer have a tree. This means separators are bigger, but you can use the same idea. Consider counting independent sets in the following graph.

Use the same idea of breaking the problem into subproblems on the separator you get the following

Like in the previous example, each term in the sum decomposes into two smaller counting tasks across the separator.

Note that we have more terms in the sum than in the previous example because we have to enumerate over all configurations on our separator, which can potentially grow exponentially with size of the separator (size 2 in this case).

Tree decomposition is a data-structure to compactly store these recursive partitioning steps. Consider the following graph and its tree decomposition

To count using this decomposition you'd first fix values in nodes 3,6 which breaks it into 2 subproblems. In the first subproblem you'd additionally fix node 5, which breaks its part into two smaller subparts.

Size of the largest separator in an optimal recursive decomposition is precisely the tree width. For larger counting problems, size of the largest separator dominates the runtime, which is why this quantity is so important.

As to the notion of tree-width measuring how close graph is to a tree, one way to make it intuitive is to look at the alternative derivation of tree decomposition -- from correspondence with chordal graphs. First triangulate the graph by traversing vertices in order and interconnecting all "higher ordered" neighbors of each vertex.

Then construct tree decomposition by taking maximal cliques and connecting them iff their intersection is a maximal separator.

Recursive separator and triangulation based approaches of constructing tree decomposition are equivalent. Tree width+1 is the size of the largest clique in optimal triangulation of the graph, or if the graph is already triangulated, just size of the largest clique.

So in a sense, chordal graphs of treewidth tw can be thought of as trees where instead of single nodes we have overlapping cliques of size at most tw+1. Non-chordal graphs are such "clique trees" with some clique edges missing

Here are some chordal graphs and their tree-width.


Approximating the value of k in $k$-mean clustering problem Consider a set of $n$ points in $R^d$ which are covered by some finitely many (say $k$) unit balls. Can we approximate the value of $k$ by querying only sublinear many points. More precisely, by sampling $poly(\frac{1}{\epsilon},\mathcal{o(n)})$ points from the set, algorithm outputs some good enough approximation of $k$ i.e., $\lceil{k(1+\epsilon)\rceil}$.

This problem is known as Geometric Set Cover (which deals with covering with different shapes, so unit balls are a special case). I'm unaware of any relation to $k$-means which is a clustering algorithm whose clusters are not limited in radius.

The problem is known to be NP-complete for $k\geq 2$.

For unit balls, this problem has a PTAS ( ($1+\epsilon$)-approximation) ) for the 2D case and is known to be APX-hard for $d=3$.


Papers to credit for spectral partitioning of graphs If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity

$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$

Where $Edges(A,B)$ is the number of edges with one endpoint in $A$ and one endpoint in $B$. Then the Edge Expansion problem is to find a set $S$ with $|S|\leq |V|/2$ that minimizes $\phi(S)$. Call $\phi(G)$ the expansion of an optimal set.

The Spectral Partitioning Algorithm for the Edge Expansion problem works by finding an eigenvector $x$ of the second largest eigenvalue of $A$, the adjacency matrix of $G$, and then considering all the ``threshold sets'' $S$ of the form $\{ v : x(v) \leq t \}$ over all thresholds $t$. If we let $\lambda_2$ be the second largest eigenvalue of the  matrix $\frac 1d \cdot A$, then the analysis of the Spectral Partitioning Algorithm shows that the best threshold set $S_{SP}$ found by the algorithm satisfies

$\phi(S_{SP}) \leq 2\sqrt {\phi(G)}$

Which follows from the Cheeger's Inequalities

$\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$

and

$1-\lambda_2 \leq 2 \phi(G)$

What is the first paper to make such a claim? What papers are to credit for the ideas? Here is what I have got:

N. Alon and V.D. Milman. $\lambda_1$, isoperimetric inequalities for graphs, and superconcentrators, Journal of Combinatorial Theory, Series B, 1985, 38(1):73-88

Prove a result in the spirit of the "simple" Cheeger inequality $1-\lambda_2 \leq 2\phi(G)$, but for vertex expansion instead of edge expansion. Recognize that the relation between edge expansion and eigenvalues is the discrete version of a problem studied by Cheeger in

J. Cheeger. A lower bound for the smallest eigenvalue of the Laplacian. Problems in Analysis, 1970.

N. Alon. Eigenvalues and expanders. Combinatorica. 6(2):83-96, 1986.

Proves a result in the spirit of the difficult Cheeger inequality $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda_2)}$ but for vertex expansion instead of edge expansion.

A. Sinclair, M. Jerrum. Approximate counting, uniform generation, and rapidly mixing Markov chains. Information and Computation 82:93-133, 1989 (Conference version 1987)

Prove the Cheeger inequalities as stated above. (Their paper studies _conductance_ of time-reversible Markov chains, which happens to equal _edge expansion_ in regular graphs.) They credit the work of Alon and Milman and of Alon for the techniques. They also credit Aldous for a related bound between mixing time and edge expansion in regular graphs.

M Mihail. Conductance and convergence of Markov chains-a combinatorial treatment of expanders. FOCS 1989, pages 526-531

While the main point of the paper is that its techniques apply to non-time-reversible Markov chains, when it is applied to regular undirected graphs it has an advantage over previous work: it shows that if one runs the spectral partitionig algorithm with an arbitrary vector, one still obtains the inequality $\phi(S_{SP}) \leq \sqrt{2\cdot (1-\lambda')}$ where $\lambda'$ is the Rayleigh quotient of the vector. The arguments of Alon, Milman, Sinclair and Jerrum require an actual eigenvector. This is relevant to fast spectral partitioning algorithms that use approximate eigenvectors.

Are there other papers that should be credited in terms of proof techniques?

When is the algorithmic significance of the above results, as graph partitioning algorithms, first recognized? The above papers have no such discussion.

It seems that the first paper introducing this set of ideas (using the algebraic invariant $\lambda_2$, the second smallest eigenvalue of the graph Laplacian, to bound various properties of the graph) to graph theory was Fiedler's "Algebraic Connectivity of Graphs" in Czechoslovak Mathematical Journal. It appeared in 1973,  roughly at the same time as the Cheeger's paper (1970), which dealt with manifolds. I am not sure who was the first to observe the parallel between graphs and manifolds in that respect. $\lambda_2$ is sometimes called the Fiedler number.

Interestingly, there is a remark at the end of the Fiedler's paper, pointing out an independent technical report by Anderson and Morley titled Eigenvalues of the Laplacian on a Graph from 1971, which apparently had similar ideas. However, it the paper by Anderson and Morley with the same title appeared in Linear and Multilinear Algebra only in 1985.


Looking for algorithm (or at least name) for this optimization problem Suppose that we have $n \geq 2$ distinct triplets $t_0, t_1, ..., t_{n-1}$ of real numbers, $t_i = (x_i, l_i, r_i)$.

Define $$\Delta(s) = \max_{i, j} \left[ s (x_j - x_i) + (r_j - l_i) \right]$$

The problem is, given some arbitrary target $\Delta_0$, to find $s^*$ such that $\Delta(s^*) = \Delta_0$.  (NB: There may be no such $s^*$.  For example, $n = 2$, and $t_0 = (0, -1, 0), t_1 = (0, 0, 1)$, then $\Delta(s)$ has constant value $2$, so the problem has a solution, infinitely many in fact, only if $\Delta_0 = 2$.)

  I'm looking for an algorithm to solve this problem, or at least some search terms (keywords, author names, etc) that I may try when searching online for such an algorithm.

FWIW, for the special case I'm working with, the following additional conditions/considerations apply:

$x_0 < x_1$;
$l_0 = r_0 = l_1 = r_1 = 0$;
$l_i < r_i, \forall \, i > 1$;
only positive solutions $s^*$ are of interest;
$\Delta_0 \geq \max_{i,j} (r_j - l_i)$.

If I understand your problem correctly, we can formulate it like so: given pairs $(\alpha_k,\beta_k)$ and $\Delta_0$, find $s > 0$ such that $\max_k (s\alpha_k + \beta_k) = \Delta_0$. Here is one way to solve this (this algorithm can be made more efficient). Go over all possible $k$. For each $k$, find the value of $s$ such that $s\alpha_k + \beta_k = \Delta_0$ (namely $s = (\Delta_0 - \beta_k)/\alpha_k$), check that it's positive, and check that for all $l \leq k$, $s\alpha_l + \beta_l \leq \Delta_0$. This runs in $O(m^2)$, where $m$ is the number of pairs (in your case, $m = n(n-1)$); you can probably get the running time down to quasilinear. Your case is more structured, so you may be able to get an even faster algorithm.


Structured set of binary words Definitions:

Let $n\in \mathbb N$ be an integer, and consider the field $\mathbb K=GF(2^n)$.

For $c\in \mathbb N$, let $S_c$ be a set of $n$ elements from $\mathbb K$ such that:

Every element $e$ from $S$ is balanced: its weight $|e|=n/2$ (there are as many $1$s as $0$s).
Every pair of distinct elements $e,e'\in S, e\neq e'$ are at distance a multiple of $c$. That is:
$$\forall (e,e')\in S^2, e\neq e', \exists k \in \mathbb N, |e\oplus e'|=k\cdot c$$

Observations:

If the set $S_c$ could contain 0, 1, or 2 elements, its construction is trivial.
For some values of $c$, there are no solutions.

Questions:

Does this set structure has a name?
Are there algorithms to construct $S_c$?
For fixed $(n,c)$, how many sets $S_c$ exist?
This question seems related to binary coding theory where the minimal distance is replaced by codewords evenly located in the space. Is there a way to express the problem into a code problem?

If there exists a solution for $(n,c)$, there exists a solution for $(4n,2c)$ (assuming $n \ge 4$): e.g., take $T = \{x||x||y||y : x,y \in S\}$, where $S$ is the solution for $(n,c)$.  This works since $n^2 \ge 4n$ for $n \ge 4$.

This implies that $c = \Omega(n^{1/2})$ should be a sufficient condition to imply existence of such a set (and this is constructive; i.e., there is an algorithm to construct such sets that achieves this bound).

More generally, if there is a solution for $(n,c)$ and $n$ is even, there is a solution for $(n^2,cn/2)$.  Here we let $T = \{x||\cdots ||x||y||\cdots || y : x,y \in S\}$, where we repeat $x$ $n/2$ times and repeat $y$ $n/2$ times.

This implies that, asymptotically, $c = \Omega(n/\lg n)$ is sufficient to ensure the existence of such a set (and again this is constructive).

I don't know whether $c = \Omega(n)$ is sufficient to ensure the existence of such a set.


Proof of causal multicast algorithm? I'm reading Causal Memory:
Denitions, Implementation and
Programming and trying to get through the proof of liveliness of the algorithm around the middle of page 9, and I'm not really following it. There's almost certainly a typo/misprint when they refer to the $(s(q) \mathbin\bot 1)$st write. I assume they meant $(s(q) - 1)$st, but even then I'm not really following the reasoning of the proof.

Does anyone have a reference to this proof in the context of a causal multicast that I could look through instead? (or in any other context?)

Alternatively, can someone try to explain the proof. In particular I don't get:

"Let $\hat{w}$ be the $(s(q)\mathbin\bot1)$st write." Even assuming $s(q) - 1$, what if $s(q)$ is $0$ or $1$?
Why does lemma 1 say that $t(\hat{w}) \preceq t(w)$?
Even if we assume $t[j] \ge s[j] - 1$ (equivalently $s[j] \le t[j] + 1$), why is this sufficient? Don't we need to show $s[j] \mathbf{=} t[j] + 1$?

Sorry if this question isn't appropriate/is tagged incorrectly.

Basically you have been mislead by the errors in the proof in the edition of the paper you are referring to. Please refer to the published edition on "Distributed Computing'1995".

  There's almost certainly a typo/misprint when they refer to the $(s[q] \bot 1)$st write.

Yes, it is a typo. It should be "the $(s[i] - 1)$st write" (not $(s[j] - 1)$st either)

  "Let $\hat{w}$ be the $(s[j] - 1)$st write." Even assuming $s[j]−1$, what if $s[j]$ is 0 or 1?

It should be "Let $\hat{w}$ be the $(s[i] - 1)$st write."
By definition, $s$ is the timestamp of the write operation $w$ of process $i$. According to the rule of Write operation in Fig.3, we have $s[i] \ge 1$. The problem is what if $s[i] = 1$. Well, it seems that the authors have missed the edge case. Fortunately, it is obviously true that $t[i] = 0 = s[i] - 1$.

  Why does lemma 1 say that $ts(\hat{w}) \le ts(w)$?

$\hat{w}$ and $w$ are two consecutive write operations in process $i$ and $\hat{w}$ is the former one. According to the rule of Write operation in Fig.3, we have $ts(\hat{w}) \le ts(w)$. (Actually, we have $ts(\hat{w}) < ts(w)$.)

  Even if we assume $t[i] \ge s[i]−1$, why is this sufficient? Don't we need to show $s[i]=t[i]+1$?

Yes, you are right. That is exactly what are proved in the DC edition.


Importance of single author papers? I'm a fourth year PhD student in theoretical computer science. I'd like to stay in academia, so I'm thinking about how best to advance my career. Obviously the best way to do that is write lots of good papers, but another question is whether I should be trying to have more of those papers be single author.

So far I only have one single author paper (out of six). It's neither my best work, nor very recent. Is that a red flag when applying for postdoc or faculty positions? Should I try to have more single author papers?

This comes down to my approach to research. I like talking to people. I like telling people what I'm working on and, if they are interested, I'm keen to work with them. In other words, I'm very open to collaboration even when it isn't strictly necessary. Should I change that? That is, should I try to keep projects to myself more so that I end up with some single author papers?

Apologies if this question is off topic. I want to ask this question to people in my area, rather than on a general forum like academia.se. In particular, on all my papers, authors are ordered alphabetically. This makes single author papers a more important signal in TCS than in other areas, where author ordering conveys this information.

In some fields (like e.g. Economics and Mathematics) single authored papers -are- a good thing to have when you go on the job market. In theoretical computer science, collaboration is much more common, and it is not unusual for even relatively senior researchers to have very few single authored papers. It is not at all suspicious if a student on the market has only papers with co-authors. This is partly because we publish more frequently, so it is ok that each individual paper has less signal about your specific contribution. This is not to say that single authored papers are not impressive, but credit is super-additive across authors, and all things being equal, you should prefer to have a better paper with more coauthors than a worse paper with fewer. This should push you towards collaboration, since collaborators make your research both more fun and generally stronger.

Of course in hiring decisions, committees will attempt to figure out whether you were a significant contributor to the papers you worked on or not -- but this will be done largely through the letters you obtain. If you have several good papers with the same senior co-author, that coauthor should write a letter for you, since they can explain in detail your contribution. It also helps if you have a clear research agenda of your own. Many papers on -your- topic with a rotating cast of coauthors conveys that you are leading the research direction, in contrast to a series of papers on disparate topics, each in the research agenda of your various coauthors.


What's the difference between term rewriting and pattern matching? As there was no response at Lambda the Ultimate I try it here again: term rewriting systems are used for instance in automated theorem proving a symbolic calculation, and of course to define formal grammars. There are some programming languages based in term rewriting, but as far as I understand the concept is more known as pattern matching. Pattern matching is used a lot in
functional languages. Barry Jay has created a whole theory called pattern calculus, but he only mentions term rewriting in brief. I have the feeling that they all refer to the same basic idea, so can you use term rewriting and pattern matching synonymously?

One way of looking at these two concepts is to say that pattern matching is a feature of programming languages for combining discrimination on constructors and destructing terms (while at the same time selecting and locally naming term fragments) safely, compactly and efficiently. Research on pattern matching typically focusses on implementation efficiency, e.g. on how to minimise the number of comparisons the matching mechanism has to do.

In contrast, term rewriting is a general model of computation that investigates a wide range of (potentially non-deterministic) methods of replacing subterms of syntactic expressions (more precisely an element of a term-algebra over some set of variables) with other terms. Research on term rewriting systems is usually about abstract properties of rewriting systems such as confluence, determinism and termination, and more specifically about how such properties are or are not preserved by algebraic operations on rewrite systems, i.e. to what extent these properties are compositional.

Clearly there are conceptual overlaps between both, and the distinction is to a degree traditional, rather than technical. A technical difference is that term rewriting happens under arbitrary contexts (i.e. a rule $(l, r)$ induces rewrites $C[l\sigma] \rightarrow C[r\sigma]$ for arbitrary contexts $C[.]$ and substitutions $\sigma$), while pattern matching in modern languages like Haskell, OCaml or Scala provides only for rewriting 'at the top' of a term. This restriction is also, I think, imposed in Jay's pattern calculus.
Let me explain what I mean by this restriction. With pattern matching in the OCaml, Haskell, Scala sense, you cannot say something like

match M with
   | C[ x :: _ ]  -> printf "%i ...\n" x
   | C[ [] ] -> printf "[]"

What is C[.] here? It's supposed to be a
variable that ranges over one-holed contexts.  But languages like
OCaml, Haskell or Scala don't give programmers variables that
range over arbitrary (one-holed) contexts, only variables that range
over values.  In other words, in such languages you cannot pattern
match at an arbitrary position in a term. You always have to specify
the path from the root of the pattern to the parts that you are
interested in.  I guess the key reason for imposing this restriction
is that otherwise pattern matching would be non-deterministic, because
a term might match a pattern in more than one way. For example the
term (true, [9,7,4], "hello", 7) matches the
pattern C[7] in two ways, assuming C[.]
ranged over such contexts.


What do you do when you cannot make progress on the problem you have been working on? I am a 2nd year graduate student in theory.
I have been working on a problem for the last year (in graph theory/algorithms).
Until yesterday I thought I am doing well (I was extending a theorem from a paper).
Today I realized that I have made a simple mistake.
I realized that it will be much harder than I thought to do what I intended to do.
I feel disappointed so much I am thinking about leaving grad school.

Is this a common situation that a researchers notices that her idea is not going to work after considerable amount of work?

What do you do when you realized that an approach you had in mind is not going to work and
the problem seems too difficult to solve?

What advice would you give to a student in my situation?

Is this a common situation that a researchers notices that her idea is
  not going to work after considerable amount of work?

Yes. But as you get more experienced, you're able to "fail fast" - learn how to test the idea quickly to see if it passes a 'smell test'.

  What do you do when you realized that an approach you had in mind is
  not going to work and the problem seems too difficult to solve?

It depends. Sometimes the best thing to do is put the problem away for a while and work on something else. Sometimes the failure suggests a different question.

  What advice would you give to a student in my situation?


Is $\mathsf{DTIME}(n^{O(\log n)})$ an interesting complexity class? Do languages decidable in deterministic $n^{O(\log n)}$ time form an interesting complexity class? If yes, is there a name for this class and are there some interesting properties about it that we know about? If not, why not (can we derive it properties easily from some other known complexity class)?

Thank you!

Quoting the complexity zoo:

QP: Quasipolynomial-Time
Equals DTIME(2polylog(n)).

QPLIN: Linear Quasipolynomial-Time
Equals DTIME(nO(log n)).
Has the same relationship to QP that E does to EXP.

Both these classes exist. I know that Quasipolynomial-time algorithms arise frequently in many areas. A google search will reveal several known quasipolynomial-time algorithms. Some of these may actually be QPLIN algorithms.
One of the advantages of QP over QPLIN is that it's more robust. For example, it is closed under composition, so if you have a quasipolynomial-time subroutine that takes an input of size $n$ to an input of size $n^{\log n}$ and now run a quasipolynomial-time algorithm on this new input, you will have an algorithm that runs in $O(n^{\textrm{polylog}(n)})$ time.


Subset Sum Problem and hard looking instances that are not really hard I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" instances are easier to solve than the really hard ones.. (and maybe this applies to other problems as well)

I was wondering if this has been described (and analyzed) elsewhere, any reference will be greatly appreciated.

The values in the input instance must have $GCD = 1$, if greater, the instance (let's name it $A$) will look harder than it really is, due an artificial input length
The real hardness, will only be known once all input values, and the target, have been divided by their GCD, creating a B instance from A, with $|B| < |A| $.
The reason is, when this input instances are presented to the algorithm, both instances will take the same number of steps to compute while having a supposedly different hardness (density). This characteristic can be used to present a $n\ge p$ instance, when in reality is $n<p$, just the values, and the target, have been multiplied by an integer long enough to produce the desired artificial length.

This was found when experimenting with edge cases, trying to better understand the input length impact in the algorithm, if a instance $n=100$ / $p=16$ takes $x$ total steps, and we create an artificial instance by multiplying the values and the target by the same integer, causing all the values including the target to have $\approx 100$ bits, the resultant instance, having $\approx 10000$ bits will take exactly the same number of steps like the original one having $\approx 1600$ bits, that is, $x$ steps.

In my opinion, this is an utter triviality, so unimportant that no one would remark on it.   Furthermore, the chance that $t$ numbers chosen at random would have gcd > 1 is vanishingly small once $t$ is large.  (There is an explicit formula, which says that t integers chosen at random from the interval [1..n] will have gcd 1 with probability tending to $1/\zeta(t)$ as $n$ gets large.)


Stream fusion in total functional language As I understand, stream fusion consists in converting operations on lists to operations on streams (colists), optimize redundant codata to data and back conversions, fuse operations on streams, and finally convert the resulting stream to a list again.

Data to codata conversion is a total operation, but the opposite is not. Is stream fusion optimization impossible in total functional programming languages?

If all you have are are plain inductive and coinductive types, fusion is impossible, for the reason you point out.

However, it is possible if your type system supports sized types. These types let you track how big the elements of a type are. So you can use a coinductive representation, but instrument the type with size information, to guarantee that you can convert back to an inductive representation.
A reasonably gentle introduction to these ideas is in Hughes, Pareto and Sabry's paper Proving the Correctness of Reactive Systems Using Sized Types, and they have also recently been  implemented in Agda.


Deterministic error reduction, state-of-the-art? Assume one has a randomized (BPP) algorithm $A$ using $r$ bits of randomness. Natural ways to amplify its probability of success to $1-\delta$, for any chosen $\delta>0$, are

Independent runs + majority vote: run $A$ independently $T=\Theta(\log(1/\delta)$ times, and take the majority vote of the outputs. This requires $rT =\Theta(r\log(1/\delta))$ bits of randomness, and blows up the running time by a $T=\Theta(\log(1/\delta))$ factor.
Pairwise independent runs + Chebyshev: run $A$ "pairwise-independently" $T=\Theta(1/\delta)$ times, and compare to a threshold This requires $rT =\Theta(r/\delta)$ bits of randomness, and blows up the running time by a $T=\Theta(1/\delta)$ factor.

Karp, Pippenger, and Sipser [1] (apparently; I couldn't get my hands on the paper itself, it's a second-hand account) provided alternative approaches based on strong regular expanders: essentially, see the $2^r$ nodes of the expander as the random seeds. Pick a random node of the expander using the $r$ random bits, and then

do a short random walk of length $T=\Theta(\log(1/\delta))$ from there, and run $A$ on the $T$ seeds corresponding to nodes on the path, before taking a majority vote. This requires $r+T = r+\Theta(\log(1/\delta))$ bits of randomness, and blows up the running time by a $T=\Theta(\log(1/\delta))$ factor.
run $A$ on all neighbors of the current node (or, more generally, all nodes within a distance $c$ of the current node) before taking a majority vote. This requires $r$ bits of randomness, and blows up the running time by a $T=d$ factor, where $d$ is the degree (or $d^c$ for distance-$c$ neighborhood. Setting up the parameters well, this ends up costing $T=\operatorname{poly}(1/\delta)$ here.

  I am interested in the last bullet, which corresponds to deterministic error reduction. Has there been any improvement following [1], reducing the dependence of $T$ on $\delta$? What is the current best achievable -- $1/\delta^\gamma$ for which $\gamma > 1$? $\gamma > 0$? (For $\textsf{BPP}$? For $\textsf{RP}$?)

Note: I'm also (very) interested in $\textsf{RP}$ instead of $\textsf{BPP}$. As introduced in [2], the relevant construction then is no longer expanders, but dispersers (see e.g., these lecture notes by Ta-Shma, esp. Table 3). I couldn't find the corresponding bounds for deterministic (not a single more random bit than the allowed $r$) amplification, however, nor (more importantly) what the state-of-the-art explicit disperser constructions for the relevant range of parameters are.

[1] Karp, R., Pippenger, N. and Sipser, M., 1985. A time-randomness tradeoff. In AMS Conference on Probabilistic Computational Complexity (Vol. 111).

[2] Cohen, A. and Wigderson, A., 1989, October. Dispersers, deterministic amplification, and weak random sources. In 30th Annual Symposium on Foundations of Computer Science (pp. 14-19). IEEE.

Doesn't van Melkebeek's lecture notes already give a $O(1/\delta)$ bound? The bound there is $\lambda$ at most $O(\sqrt{\delta})$ and we can get $\lambda = O(1/\sqrt{d})$ using existing constructions.

In Dwork's lecture notes as well, the condition required is that the expansion be $C/\delta$ for some constant $C$ (looking at a points in distance c is essentially using powering to improve expansion). Which again can be obtained with degree $O(1/\delta)$.

Perhaps there is a lower bound of $\Omega(1/\delta)$ on number of runs required.


How to compute the disagreement between hypotheses Given a class of hypothesis $\mathcal{H}$ representing the set of all consistent hypotheses with the examples seen so far, how to compute the region of uncertainty? The region of uncertainty is defined as all points where there are two or more hypotheses disagree on its labelling.

I am representing $\mathcal{H}$ as two hypotheses: most specific (MS) and most general (MG) (as described here ). $\mathcal{H}$ consists of these two and anything in between. Clearly, enumerating all possible hypotheses is infeasible due to the size of $\mathcal{H}$. To put it in one word, how to compute disagreements in practice?

EDIT:

sorry for not being specific. I am trying to learn a graphical model similar to bayesian networks but instead of probabilities I have order relation.

I have a set of variables $V=\{v_1,v_2,...,v_n\}$ where each variable has a set of possible values (its domain). $V$ defines an outcome space $\mathcal{O}$ (the set of all possible assignments over $V$ from their domain values). For example, if $A=\{1,2\}$ and $B=\{3,4\}$ we have $\mathcal{O}=\{(1,3),(1,4),(2,3),(2,4)\}$. The input space $X$ is the set of all pairs of outcomes from $\mathcal{O}$. Each example $x$ consist of pairs of outcomes $a$,$b\in \mathcal{O}$ (denoted as $x[a]$,$x[b]$ respectively). The target function is a strict order relation $\succ$ over $\mathcal{O}$. I am adopting the active learning paradigm. I first choose $\mathcal{U}$ unlabelled examples, then ask the oracle to label an example $x\in \mathcal{U}$. $h(x)=+$ if $x[a]$ is better than $x[b]$ otherwise $-$. The hypothesis class $\mathcal{H}$ is the set of all possible strict (partial/total) orders consistent with the examples seen so far.  My main concern is how to select representative hypotheses from $\mathcal{H}$

One major task of computational learning theory is to try to handle questions like this for specific classes.  In general, if you assume no structure on the hypothesis space, you basically have no choice but to look at each hypotheses individually.  On the other hand, if there is a lot of structure, eg. if you assume the hypotheses are linear separators, say in $\mathcal{R}^2$, you can see that it's possible to be quite efficient even though there are infinitely many linear separators!

The same thing happens for trying to find the ERM (empirical risk minimizing) hypothesis in a class.  This is important for PAC learning. Sometimes it's easy, sometimes it's not.


What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal? In this article Chang et al. provide a counterexample by giving an oracle $A$ such that $\mathsf{IP}^A \neq \mathsf{PSPACE}^A$.

I wanted to know if there are more examples like this.

$\mathsf{MA_{EXP}} \not\subseteq \mathsf{P/poly}$ but there is an oracle relative to which this is false; both were proved in

  H. Buhrman, L. Fortnow, T. Thierauf. Nonrelativizing separations. CCC '98. (freely available author's version)


Gradient descent-like optimization on a convex landscape with noisy sampling We have a strictly convex function $f(x,y)$ with a global minimum at $p_{min}$.
The goal is to approximate the minimum.
E.g.
$$f: [0,\pi]^2 \to \mathbb{R}$$
$$f(\theta,\phi) = t_1 \sin \theta + t_2 \sin \phi$$
where $t_1,t_2$ are constants in $\mathbb{R}^+$.

We want to find the best possible approximation for the minimum $p_{min}$,
but we only have noisy black-box access to the function $f$.

We can think of the setting as a game with two players Alice and Bob as follows:

Alice provides Bob a point $s$ such that $|s-p_{min}|<r$.
Bob provides Alice a point $p$.
Alice provides Bob information about the value of the function on $p$.
However, the information is noisy: Bob gets $v \sim f(p) + N(\mu,\sigma)$.

If Bob can pick $k$ points adoptively,
what would be an optimal strategy for choosing the points s.t.
the last one is as close as possible to the minimum?

On average, how well can Bob do?

What would be the dependency of the error on $k$?

If it simplifies things, we can use uniform distribution $U[a,b]$ in place of Gaussian distribution for noise.

The copy of the question on MathOverflow.

The problem you describe is called "stochastic convex optimization in the bandit setting". This is the problem considered and solved here: http://arxiv.org/pdf/1107.1744v2.pdf

They show that after $k$ queries, you can get within $O(1/\sqrt{k})$ of the minimum value of the function (ignoring a poly$(d)$ dependence on the dimension $d$ of the domain of the function $f$).


Is combinatory strong reduction equivalent to lambda beta-eta reduction? I'm familiar with the correspondence between combinatory logic and $\lambda$-calculus at equality level, ie $=_{\beta\eta}$ corresponds to $=_s$ (the equivalence relation generated by strong reduction) and that there is also a combinatory equality $=_{C\beta}$ corresponding to $=_\beta$ in $\lambda$.

However, I'm having trouble understanding what happens at reduction level. In particular, is it true that Curry's strong reduction corresponds to $\rightarrow_{\beta\eta}$? For instance, could we use strong reduction to "evaluate" (up to $\beta\eta$) $\lambda$-terms? Also, if I understand correctly, is it even harder to come up with a combinatory reduction equivalent to $\rightarrow_\beta$?

The answer to the second question is yes, beta-reduction is harder to imitate than beta-eta-reduction.  There is an article by J P Seldin in "Theoretical Computer Science" (2011) I think that discusses the problems to which beta-reduction gives rise.

As to the question, "could we use strong reduction to evaluation lambda terms?", the correspondence is not as neat as you might wish.  There is a mapping called the H-transformation that takes lambda terms to combinatory terms and which preserves the relation "reduces to", but it is not one-to-one and therefore not invertible.  So if you start with a lambda term M and find its image H(M) under the H-transformation and you can reduce H(M) to a normal form, you will know that M also has a normal form, but it may not be entirely easy to find it.  In the other direction, there is a mapping called the lambda-transformation that takes combinatory terms to lambda terms but it is not onto and is not the inverse of the H-transformation.  It also does not preserve the reduction relation, unlike the H-transformation.

All the above information is found in sections 6E and 6F of "Combinatory Logic Volume I" by Curry and Feys and in chapter 9 of "Lambda Calculus and Combinators" by Hindley and Seldin.  Hindley also wrote an article published in MLQ in 1977 that discusses these things in more detail.


Is every busy beaver strictly monotonic asymptotically? To be specific, let me first define the busy beaver function BB(n)= maximum number of 1's that can be printed on the tape (i.e., the maximum score) by a standard n-state, 2-symbol (0 and 1) Turing machine before halt, starting with an all-zero tape.

My first question maybe trivial: is it true that BB(n+1)>BB(n) for all n?

The claim is true if we define the busy beaver by BB'(n)= maximum number of shifts made by the machine before halt. (This is because we can always keep everything else the same, and change the last shift made by BB'(n), say $\{ 0{q}_{i}1RH\}$, to $\{ 0{q}_{i}1R{q}_{n+1}\}$ and $\{1{q}_{n+1}1RH\}$ to arrive at an (n+1)-state turing machine which has exactly one more shift than BB'(n) before halt.)

Can we show that the strict inequality holds too if we measure by scores?

What about the general case? Is every busy beaver strictly monotonic, for large enough n?

Take an $n$-state Turing machine $M$ which outputs $k$ one symbols. Define the new Turing machine $M'$ with $n+1$ states as follows. Every transition in $M$ to the ACCEPT state instead goes into a new state $q'$. The state $q'$ has the following behavior. If the head currently contains a ZERO, we overwrite with a ONE and ACCEPT. If the head currently contains a ONE, we shift to the right and remain in state $q'$.

As machine $M$ halts, so does machine $M'$. Furthermore, machine $M'$ always puts one $k+1$ ONES onto the tape.

So $BB(n+1) \geq k+1 > k = BB(n)$


Maximum Positive Negative Set Cover Problem I am considering the following problem.

Input: Given two disjoint subsets $A$ and $B$ and a collection $C$ of $k$ sets $S_1,S_2,\ldots,S_k$ where $S_i \subseteq A \cup B$ for all $i=1\ldots k$.

Solution form: A collection $C' \subseteq C$.

Objective: Maximize $\left|\left(\bigcup\limits_{c \in C'} c\right) \cap A\right| + \left|B \setminus\left(\bigcup\limits_{c \in C'} c\right)\right|$.

That is, maximize the nodes in A covered plus the nodes in B not covered.

I am wondering the hardness of approximation.

Related work:

If we consider minimizing the objective, it becomes the problem studied in the following paper.

Miettinen, Pauli. "On the positive–negative partial set cover problem." Information Processing Letters 108.4 (2008): 219-221

This problem has a few simple constant-factor approximation algorithms, such as the trivial algorithm that picks the $C' \in \{\emptyset, C\}$ with a higher objective score.

Here's a loose constant-factor hardness result. No significant effort was put into optimizing the constant. I'm sure others can find something tighter.

Let $G = (V,E)$ be an instance of Max-Cut. We construct $A$, $B$, and $C$ as follows:

$A$ contains two vertices, $a_{u,v}$ and $a_{v,u}$, for each $(u,v) \in E$.
$B$ contains two vertices, $b_{u,v}$ and $b_{v,u}$, for each $(u,v) \in E$.
$C$ contains one set $c_v$ for each $v \in V$.
$c_v := \bigcup_{u \in \mathcal{N}(v)} \{a_{u,v}, a_{v,u}, b_{u,v}\}$, where $\mathcal{N}(v)$ denotes the neighborhood of $v$ in $E$.

Every subset of $C$ naturally corresponds to a collection of vertices from $V$ (i.e. via the subscripts). Call the set of vertices in this solution $V_C$.

Now for every edge $(u,v) \in E$, we count how many vertices from $\{a_{u,v}, a_{v,u}, b_{u,v}, b_{v,u}\}$ belong to $S = \left(A\cap \left(\bigcup_{c \in C} c\right)\right) \cup \left(B \setminus \left(\bigcup_{c \in C} c\right)\right)$.

If $u \in V_C$ and $v \in V_C$, then only $a_{u,v}$ and $a_{v,u}$ are in $S$.
If $u \in V_C$ and $v \not\in V_C$, then $a_{u,v}$, $a_{v,u}$, and $b_{u,v}$ are in $S$.
If $u \not\in V_C$ and $v \in V_C$, then $a_{u,v}$, $a_{v,u}$, and $b_{v,u}$ are in $S$.
If $u \not\in V_C$ and $v\not\in V_C$, then only $b_{v,u}$ and $b_{u,v}$ are in $S$.

Therefore, the total number of vertices in $S$ is equal to $2|E| + |\textrm{Cut}_E(V_C, V \setminus V_C)|$. Thus, the optimal solution involves a Max-Cut computation.

If it is hard to distinguish Max-Cut instances with optimal value $\geq \alpha |E|$ from those with value $\leq \beta |E|$, then for your problem it's hard to distinguish instances with optimal value $\geq (2+\alpha)|E|$ from those with value $\leq (2+\beta)|E|$, for a hardness of $\frac{2 + \beta}{2 + \alpha} = 1 - \frac{\alpha - \beta}{2 + \alpha} < 1 - (\alpha - \beta)/3$.

At this point we can plug in our favorite result on the hardness of max cut. E.g. UGC implies that we can choose $\alpha - \beta > .1$,$^*$ so this gives us a UGC gap of something less than $1-(1/10)/3 = 29/30$. Similar results can be had for NP-hardness, albeit with a slightly bigger constant.

$^*$ Note: this is not quite $1-\alpha_{GW}$, since $\alpha_{GW}$ measures the gap ratio rather than the gap difference.


Is it possible to MAC a quantum state with a classical key under reasonable assumption? Assume that classical one-way functions secure against quantum adversaries exist.  Is it possible, given a quantum state $Q$ and classical secret key $k$, produce a quantum state $AuthQ$ such that:

One who knows $k$ can recover $Q$, provided that $AuthQ$ has not been altered.
If $AuthQ$ has been altered, this can be detected with high probability.

It may or may not be possible to recover the original state without the secret key.  What matters is that, given the secret key, one can be confident that:

The creator of the quantum state had the secret key
The message has not been tampered with since.

Howard Barnum, Claude Crepeau, Daniel Gottesman, Adam Smith, Alain Tapp. "Authentication of Quantum Messages", FOCS 2002.

http://www.cse.psu.edu/~ads22/pubs/PS-CSAIL/BCGST02-focs-final.pdf

As with encryption, there is a protocol that requires no computational assumptions. It uses a key of length about 2n+2k to authenticate n qubits with security level 2^{-k}.


Bin allocation problem Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway.

We have a script as part of an application at work which is responsible for sorting items into bins.  (Sounds simple, right?)

There are X items and Y bins.  Each Item has a Primary, Secondary and Tertiary preferential bin.  It also has an overall rating which corresponds to the item's overall quality, as well as the bin preference (rating is adjusted by -0.5, -1 for decreasing bin preference).

All item's ratings are probably different, and this affects the rating of each bin, and also an overall rating of all bins.

The ordering of items and their preferences into according bins is also important, i.e. Bin A containing Item1 and Item2, may have a different rating overall to Bin B containing Item1 and Item2.

Rules:

Each bin can contain between 1 and 3 items.
Any one item can only appear once in each bin, and can only appear in one bin.

Initially, we thought it was a knapsack problem, or possibly a multiple knapsack problem, but after researching each, we're not sure that any of the common algorithms for that problem fits our task.

We currently brute force it, but given that the Item pool contains 50 items, and the number of Bins is about 10, the runtime for a single bruteforce run is in the order of tens of seconds.  We'd like to get this down to 0.5s

So basically, has anyone come across this problem before, and does it have a name (that we can search academic papers with)?

As far as I can see, the value of each item depends on which bin it is added to. Its full quality if it is added to its primary preference, and a reduced quality (reduced by -0.5 and -1, respectively) for its secondary and tertiary preferences. Do I understand you correctly?

In this case, this problem can be formulated as a min-cost flow problem, which resembles min-cost bipartite matching (but with the added twist of bin capacity). I.e., it is not an NP-hard bin packing problem at all (unless P=NP).

Construct a flow network with a source, a sink, and two "layers" of nodes, corresponding to the items (first layer) and bins (second layer). Add edges from the source to the items (zero cost, capacity 1) and from the bins to the sink (zero cost, capacity equal to the bin capacity, i.e., from 1 to 3). From each item, you add an edge to each of its primary, secondary and tertiary bins, with capacity 1 and a cost of its adjusted quality multiplied by -1 (to go from a positive value to a negative cost).

Now just run a standard min-cost-flow (or min-cost max-flow) algorithm to get your answer.

Of course, not all items will be matched if the total capacity is less than the number of items, but the match will produce the matching that gives the greatest total (adjusted) quality.

If you don't want to muck about with min-cost flow, you could split each bin node into multiple nodes (the number of nodes corresponding to the bin capacity), and duplicate the edges from the items. So if an item has an edge with a given cost to a bin node with a capacity of 3, you'd now have 3 bin nodes, and that item would have an edge to each of them with the given cost. You could then just use an algorithm for min-cost bipartite matching, such as the Hungarian algorithm. (You will now no longer have a source or a sink, of course.)

This latter version is probably more practical to implement, and libraries for the Kuhn-Munkres algorithm are available in multiple languages.


Database query languages for efficient queries It seems that in popular query languages for relational databases, it is possible to create queries that will require a lot of resources to answer. In practice, database admins manage this by limiting the amount of memory per query, and checking for any long-running queries if there is a slowdown in the database. This seems rather ad-hoc, is there a TCS solution to this?

  Are there query languages that can
  only implement efficient queries?

If there are no such languages, is there a theoretical reason for this?

Some reasons why I might expect these sort of things to exist or atleast make sense:

we have programming languages that are specifically designed to only implement efficient computations (usually by having some restrictive logic in their type system)
popular query languages (such as SQL) are already inspired by logic, so it does not seem as a stretch for database users to consider more restrictive logics.
a non-malicious database user already tries to prepare queries that execute quickly, so we should expect these more restrictive query languages to only hamper malicious users.

This question is inspired by the intersection of two previous questions:

Programming languages for efficient computation

Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

One way of looking at database query languages is through the lens of deductive databases, where queries are represented as logic programs. In this setting, the most relevant work related to your question is McAllester's On the complexity analysis of static analyses, which observed that you can reason about the running time of a query by reasoning about the number of "prefix firings" in the rules of your program. What a "prefix firing" is isn't terribly complicated, but I'll refer you to the paper for that.

In the functional programming world, this sort of thing is called a cost semantics: it doesn't mean you can only implement efficient queries (programs), but it means that you can reason about the asymptotic complexity of your declarative program in a reasonable way.

Some later work on implementations of McAllester's ideas include From datalog rules to efficient programs with time and space guarantees (Liu and Stoller) and Dedalus: Datalog in Time and Space (Alvaro, Marczak, Conway, Hellerstein, Maier, and Sears). I admit I haven't yet read the latter of those two papers, however.


What is simplest polynomial algorithm for PLANARITY? There are several algorithms that decide in polynomial time whether a graph can be drawn in the plane or not, even many with a linear running time. However, I could not find a very simple algorithm that one could easily and fast explain in class and would show that PLANARITY is in P. Do you know any?
If necessary, you can use Kuratowski's or Fary's theorem but no deep stuff, like the graph minor theorem.
Also note that I do not care about the running time, I just want something polynomial.
Below are the so far 3 best algorithms, showing a simplicity/no-deep-theory-needed trade-off.

Algorithm 1: Using that we can check whether a graph contains a $K_5$ or a $K_{3,3}$ as a minor in polynomial time, we get a very simple algorithm using deep theory. (Note that this theory already uses graph embeddings, as pointed by Saeed, so this is not a real algorithmic approach, just something simple to tell students who already knew/accepted the graph minor theorem.)
Algorithm 2 [based on someone's answer]: It is easy to see that it is enough to deal with 3-connected graphs. For these, find a face and then apply Tutte's spring theorem.
Algorithm 3 [recommended by Juho]: Demoucron, Malgrange and Pertuiset (DMP) algorithm. Draw a cycle, components of remaining graph are called fragments, we embed them in a suitable way (meanwhile creating new fragments). This approach uses no other theorems.

I am going to describe an algorithm. I am not sure it qualifies as "easy" and some of the proofs are not so easy.

First we break the graph into 3-connected components, as mentioned by Chandra Chekuri.

Break the graph into connected components.
Break each connected component into 2-connected components. This can be done in polynomial time checking for each vertex $v$ of each 2-connected component $G_i$ whether $G_i-v$ is connected.
Break each 2-connected component into 3-connected components. This can be done in polynomial time checking for two distinct vertices $v,u$ of each 2-connected component $G_i$ whether $G_i-\{ v,u \}$ is connected.

We have reduced the problem to checking whether a 3-connected component of the graph is planar. Let $G$ denote a 3-connected component.

Take any cycle $C$ of $G$.
Pin the vertices of $C$ as vertices of a convex polygon. Put each of the other vertices in the barycenter of its neighbors. This leads to a system of linear equations telling the coordinates of each vertex. Let $D$ be the resulting drawing; it may have crossings.
If $D$ has no crossings, we are finished.
Take the vertices $U$ in any connected component of $G-V(C)$. The restriction of $D$ to the induced subgraph $G[U\cup V(C)]$ should be planar. Otherwise, $G$ is not planar. Take any face $F$ in the drawing $D$ restricted to the induced subgraph $G[U\cup V(C)]$, and let $C'$ be the cycle defining $F$. If $G$ is to be planar, then $C'$ must be a facial cycle. (When $C$ is a Hamiltonian cycle, then $C'$ should be constructed using an edge.)
Repeat step 2 with C' instead of C. If the resulting drawing is planar, then $G$ is planar. Else $G$ is not planar.

Remarks:

Arguing that Tutte's spring embedding gives a planar embedding is not straightforward. I liked the presentation in the book of Edelsbrunner and Harer, Computational Topology, but it is only for triangulations. Colin de Verdiere discusses the spring embedding in http://www.di.ens.fr/~colin/cours/algo-graphs-surfaces.pdf , section 1.4. A general reference is Linial, Lovász, Wigderson: Rubber bands, convex embeddings and graph connectivity. Combinatorica 8(1): 91-102 (1988).
Solving a linear system of equations in a polyomial number of arithmetic operations is easy via Gaussian elimination. Solving it using a polyonomial number of bits is not that easy.


Another algorithm for stable matching? The only algorithm I have seen to compute a stable matching is the one by Gale an Shapley. Is there any other algorithm to compute a stable matching?

There is a totally different algorithm due to Subramanian which uses a fixed point approach. The first idea is to represent the knowledge that we have at any given point in time using intervals, which represent which women each man is considering, and vice versa. Using ideas similar to Gale-Shapley, we keep shrinking the intervals. In contrast to Gale-Shapley, this algorithm is symmetric with respect to gender. Eventually a fixed point is reached, and we can read the man-optimal and woman-optimal matchings. Subramanian found a neat way to implement this using three-valued logic and comparator networks. Check out for example this paper.
Subramanian's approach was later elaborated by Feder.


Can choice or sequential execution be expressed with other basic operators of the pi calculus? There are several definitions of what basic operators constitute the pi calculus  (see papers from R. Milner, B.Pierce, J.Wing).

The common basic operators ($C$) are:

the parallel composition
reading from a named channel
writing to a named channel
restriction to get a new named channel
replication to get an infinite number of parallel copies of a process
the inert process that does nothing.

Sometimes, there is additionally one of the following two operator mentioned as basic operator:

the sequential operator for sequential execution;
the summation operator to choose between processes.

Is $C$ together with the sequential operator equivalent to $C$ with the summation operator? Are they even equivalent to $C$ without any further operator? Why (not)?

This is a really interesting question and only partially understood.
The $
\newcommand{\OUT}[2]{\overline{#1} #2 }
$ precise answer to such questions depends in subtle ways on exactly what the ambient $\pi$-calculus is and exactly what feature you are encoding.

For sums  you need to realise that there are different kinds of sums for example input guarded sums like $x(v).P + x(v).Q$ or $x(v).P + y(v).Q$, or
mixed sums like $x(v).P + \OUT{y}{v}.Q$ or even $x(v).P + \OUT{y}{v}.Q + \tau.R$. What you can and cannot encode really depends on what sums you have. The groundbreaking study (1) gives hard limits to 'good' encodings. Simplifying greatly, what (1) shows is that adding mixed sums to a calculus strictly increases expressivity. This it cannot be encoded (in a nice way). The reason is that mixed sums allow a certain form of symmetry breaking that is not achievable in conventional $\pi$-calculi without mixed choice.

With sequential composition $P; Q$ the situation is less complicated, but you need to be clear exactly what sequential means for parallel processes and replication/recursion:

Should $R$ begin to execute when one or both of $P$ and $Q$ terminate in $(P|Q); R$?
What is the meaning of $(!x(v).P); R$?

If $(P|Q); R$ means that both $P$ and $Q$ must terminate before $R$ goes to work, and if we disallow sequential composition like $(!x(v).P); R$ with replication, then $P; Q$ is easily encodable, and by (1) it cannot simulate general forms of sums that include mixed sums.

The curse of Turing completeness. There is a further complication. Process calculi typically are  Turing-complete, hence any feature can be 'somehow' be encoded. So you need to be very precise about what you mean when you ask if some calculus is "equivalent" to some other. The usual approach to making this precise is to constrain admissible encodings, e.g. to require them to be compositional, or preserve termination, or be closed under renaming, or any number of other interesting structural properties. For different concepts of admissible encoding you tend to get different answers.
None of this is germane to process calculi, Turing's curse affects all programming languages, but process calculi are especially subtle, since they can do so much more than mere sequential computation.

For an overview of the state-of-the art in process calculus expressivity, see (2, 3).

(1) C. Palamidessi, Comparing the Expressive Power of the Synchronous and the Asynchronous π-Calculi.

(2) D. Gorla, Comparing Communication Primitives via their Relative Expressive Power.

(3) D. Gorla, A Taxonomy of Process Calculi for Distribution and Mobility.


How do I figure out how to combine simpler quantum gates to create the gate I want? I want to create other quantum gates from the basic building blocks of a universal quantum gate set. I've been playing with IBM's quantum computing interface for that.

I wanted to create a Toffoli gate, which I managed to in the end, but part of it was by trial and error. I want to create some other gates now, and I want to avoid the long arduous process of trial and error.

Is there a better way?

Is there also a way to how to construct the gate from the minimum number of gates necessary?

I'm going to add my work on the Toffoli here for anyone to see / critique.

% Matlab / Octave code
q=[1 0];
X=[0 1;1 0];
Y=[0 -1i; 1i 0];
Z=[1 0;0 -1];
H=[1 1;1 -1]/sqrt(2);
S = [1 0;0 1i];
St = [1 0;0 -1i];
C = [1 0 0 0;0 1 0 0; 0 0 0 1; 0 0 1 0];
Cgap = [1 0 0 0 0 0 0 0; 0 1 0 0 0 0 0 0; 0 0 1 0 0 0 0 0; 0 0 0 1 0 0 0 0; 0 0 0 0 0 1 0 0; 0 0 0 0 1 0 0 0; 0 0 0 0 0 0 0 1; 0 0 0 0 0 0 1 0];
T = [1 0; 0 exp(pi*1i/4)];
Tt = [1 0; 0 exp(-pi*1i/4)];
I = eye(2);
I2 = eye(4);
I3 = eye(8);

CS = kron(T,Tt)*C*kron(Tt,Tt)*C*kron(T,S);
CSt = kron(Tt,St)*C*kron(T,T)*C*kron(Tt,T);
CgapS = kron(T,kron(I,Tt))*Cgap*kron(Tt,kron(I,Tt))*Cgap*kron(T,kron(I,S));

Toffoli = kron(I2,H)*kron(I,CS)*kron(C,I)*kron(I,CSt)*kron(C,I)*CgapS*kron(I2, H)

Toffoli gate program using IBM's Quantum Experience (the two X gates on the very left are used to set the values of the qubits to 1; they can be removed to run the gate with 0 values):

The way I figured it out was I found some lecture notes with the gate expressed as seven building blocks, but I didn't have some of the blocks, so I constructed those by trial and error. Here's the pdf:
https://inst.eecs.berkeley.edu/~cs191/fa07/lectures/lecture9_fa07.pdf

There are standard ways to approximate any unitary operation with just CNOTs, Hs, and Ts. In the specific case of the Toffoli gate you don't need something so general.

Start with the Toffoli gate:

Use a construction that relies on operations having a square root to cut the worst-case number of controls from 2 to 1:

Use a construction that moves controls off of arbitrary single-qubit operations and onto CNOTs:

Oh hey that looks kinda familiar ;)

Now simplify by sliding gates around so that some of them cancel. Zs can move over controls, but not over NOTs (but can hop over the space between two NOTs that undo each other). It's also useful to know how to move a CNOT over another CNOT's control by introducing a third CNOT. Hadamards cancel when paired, and turn Zs into Xs (and vice versa) when hopping since $HX = ZH$. Anyways, after some fiddling...:

(Note: $T = Z^{1/4}$ and $T^\dagger = Z^{-1/4}$)

You can confirm the circuit works by toying with it in Quirk.

These constructions are explained in more detail in textbooks such as Nielsen and Chuang. The 'moving controls' one is particularly tricky, because you have to find $A$, $B$, $C$ such that $ABC=I$ but $AXBXCe^{i\theta}=U$. Or you can read a few blog posts about making a controlled-by-every-other-wire NOT using $O(n)$ basic gates that also uses these constructions but explains them in more detail.


Are there problems for which divide-and-conquer / recursion is provably useless? When we try to construct an algorithm for a new problem, divide-and-conquer (using recursion) is one of the first approaches that we try. But in some cases, this approach seems fruitless as the problem becomes much more complicated as its input grows.

My question is: are there problems for which we can prove that a divide-and-conquer approach cannot help to solve? In the following lines I try to make this more formal.

Let $P(n)$ be a certain problem whose input has size $n$ (e.g. a problem that accepts an input an array of $n$ numbers). Suppose we have a recursive algorithm for solving $P(n)$.    The recursive runtime of that algorithm is calculated assuming an oracle which can solve $P(k)$ for every $k<n$ in constant time. For example:

The recursive runtime of binary search is $O(1)$, since it uses only a comparison and two recursive calls.
The maximum element in an array can be found in recursive time $O(1)$.
The recursive runtime of merge sort is $O(n)$, because of the merging step.

The recursive time is usually smaller than the actual runtime, which reflects the fact that the recursive algorithm is simpler than a straightforward non-recursive solution to the same problem.

Now my question is:

Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime asymptotically less than $f(n)$?

Some specific variants of this question are:

Is there a problem in $P$ which has no algorithm with recursive runtime $O(1)$? (Maybe sorting?)
Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

EDIT: contrary to my guess, sorting has an algorithm with recursive runtime $O(1)$. So it is still open, whether there a problem in $P$ which has no algorithm with recursive runtime $O(1)$.

Is there a problem with an exponential algorithm which has no algorithm with polynomial recursive runtime?

Yes.  Note that if a tally language has “recursive algorithm” with polynomial “recursive runtime,” then it is in P.  There is a tally language in E∖P by a standard diagonalization argument.

  Is there a problem which can be solved in time $f(n)$, but provably has no recursive algorithm with recursive runtime $o(f(n))$?

It may depend on the computational model, but I doubt this is known, given that the time hierarchy theorem for two-tape Turing machines is not powerful enough to distinguish, say, O(n2) time and o(n2) time even without giving the latter the constant-time access to the answers on smaller instances.

Random comments on your questions in this post:

I do not think that these questions are related to the usefulness of recursive programs, despite what the title of the post and your choice of terminology suggest.  As BVMR wrote in an answer, recursions and iterations are equivalent in a certain sense.  Instead, I think that the questions have a connection to the usefulness of the divide-and-conquer approach.
In complexity theory, a related notion to your notion of “recursive algorithms” with their “recursive runtime” is called “length-decreasing self-reductions” with their time complexity.
Some part of your questions (definitely the part referring to sublinear-time algorithms) depend on the choice of computational model.