Is eta-equivalence for functions compatiable with Haskell's seq operation? Lemma: Assuming eta-equivalence we have that (\x -> ⊥) = ⊥ :: A -> B.

Proof: ⊥ = (\x -> ⊥ x) by eta-equivalence, and (\x -> ⊥ x) = (\x -> ⊥) by reduction under the lambda.

The Haskell 2010 report, section 6.2 specifies the seq function by two equations:

seq :: a -> b -> b
seq ⊥ b  =  ⊥
seq a b  =  b, if a ≠ ⊥

It then claims "As a consequence, ⊥ is not the same as \x -> ⊥, since seq can be used to distinguish them."

My question is, is that really a consequence of the definition of seq?

The implicit argument seems to be that seq would be uncomputable if seq (\x -> ⊥) b = ⊥.  However I haven't been able to prove that such a seq would be uncomputable.  It seems to me such a seq is both monotone, and continuous, which puts it in the the realm of being computable.

An algorithm that implement such as seq might work by attempting to search for for some x where f x ≠ ⊥ by enumerating the domain of f starting with ⊥. Though such an implementation, even if possible at all, gets pretty hairy once we want to make seq polymorphic.

Is there a proof that there is no computable seq that identifies (\x -> ⊥) with ⊥ :: A -> B?  Alternatively, is there some construction of seq that does identify (\x -> ⊥) with ⊥ :: A -> B?

First, let us be explicit about how seq distinguishes $\bot$ from $\lambda x . \bot$:

bottom :: a
bottom = bottom

eta :: a -> b
eta x = bottom

-- This terminates
fortytwo = seq eta 42

-- This does not terminate
infinity = seq bottom 42

It is therefore an experimental fact that in Haskell $\bot$ and $\lambda x . \bot$ are operationally distinguishable. It is also a fact, and a quite obvious one, that seq is computable because Haskell computes it. So much about Haskell. You are asking about the very particular phrasing of the Haskell documentation. I read it as saying that seq is supposed to satisfy the two given equations, but those two equations are not sufficient for the definition of seq. Here is why: I can give you two models of (simply typed) $\lambda$-calculus in which seq is computable and satisfies the given equations, but in one of the models $\bot$ and $\lambda x . \bot$ agree, while in the other they do not.

In a simple domain-theoretic model where $\lambda$-expressions are interpreted in the domain of continuous functions $[D \to E]$ we have $\bot = \lambda x . \bot$, obviously. Take effective Scott domains or some such to make everything computable. It is easy to define seq in such a model.

We can also have a model of $\lambda$-calculus in which seq distinguishes $\bot$ and $\lambda x . \bot$, and then of course $\eta$-rule cannot hold. For instance, we can do this by interpreting functions in the domain $[D \to E]_\bot$, i.e., the function space domain with an extra bottom attached. Now $\bot$ is, well, the bottom of $[D \to E]_\bot$, while $\lambda x . \bot$ is the element just above it. They cannot be distinguished by application because they both evaluate to $\bot$, no matter what you apply them to (they are extensionally equal). But we do have seq as a map between domains and it alwyas distinguishes bottom from all other elements.


Are Turing machines still useful as model of computation? Often when I hear "Turing machine," my mind's eye pictures a quaint infinite ticker-tape with a small little machine writing and erasing $0$'s and $1$'s.

But when I'm forced to think about a Turing machine as a tuple of states, blank symbols, alphabet symbols, transition functions, etc., my mind often glosses over.

I live in the 21st century; thinking about computation is so second-nature to me now that I struggle with keeping my mind on such a pleasantly old-fashioned infinite ticker tape.  I know pretty well how the computer on which I'm writing this operates, clearly not at the details of the machine code but at a level of abstraction that I feel comfortable with.  I also never liked how the alphabet has, basically, three symbols $(0,1,blank)$.  Why do we even need the $blank$?

Turing's work in the 30's was baller of course, and there are some well-deserved accolades when the new "smallest universal Turing machine" or "largest Busy-Beaver" are announced.  People also have a game of writing esoteric programming languages based on small Turing machines.

  But is there a good reason to use the ticker-tape Turing machine for a model of computation, now, in the 21st century?  Are there reasons for the formalism still being "worth it?"  Or can we just say a Universal Turing Machine as in a smart-phone?

Of course Hamilton's etchings on Broom Bridge marked a turning point in the history of mathematics, but I've read that quaternions per se were oversold by the end of the 19th century.

I think the issue is that, you're misunderstanding the purpose of the Turing Machine model.

Turing Machines are not meant to be programmed in.  If you're writing code, you absolutely should not be thinking of how it would run on a Turing Machine.

However, Turing Machines are excellent for reasoning about. In Theoretical Computer Science, we're interested in proofs. We want to be able to say "there exists an algorithm with this property" or "for all algorithms, this statement holds". And we need an operational definition of what an algorithm is.

This is exactly where Turing Machines come in handy. First, the definition of a Turing Machine is precise: it's an exact mathematical object, whose behaviour is fully specified. Secondly, it's small: it contains finite states, and transitions between states that affect the tape.

If you wanted to rigorously prove something about a smartphone model, you would have to reason about all the different bits in memory, possibly even about hardware and transistor states. But to prove something about a Turing Machine, there's one simple state-space, and a simple memory model. This is how we've been able to build up theories of decidability, computational complexity, etc. They work because they're based on a model that's simple enough to write proofs about, but powerful enough that it reflects the capabilities of actual computers.

For example, say you create a new programming language. You want to show that every problem that can be solved, can be solved in your language. Now, you could show that you can simulate an entire smartphone's circuitry in your language, each gate and transistor and byte. But that's huge. Instead, you can achieve the same thing by showing that you can simulate an arbitrary Turing Machine in your language, which is much simpler to write.

Now, it's worth mentioning that Turing Machine's are not the only model of computation. There are two main competitors. First, any time we're discussing  fine-grained complexity, you will likely use a RAM model instead of a Turing Machine, so that you can model the speed of algorithms without having to traverse the entire tape to access a particular part of memory. Secondly, the Lambda Calculus and its various derivatives are equivalent in power to a Turing Machine. While they don't model hardware, their semantics closely match how we think of programming language as behaving, and there's an entire field (Programming Languages Theory) build around such models. They're not as minimal as Turing Machines, but they're more compositional i.e. it's easier to build programs by combining small building blocks. and their behavior is predicable based on those combinations.


What is the running time of taking a limit? I'm interested in finding the running time(s) for determining mathematical limits.

For instance, $\lim_{x \to 2} \frac{1}{x} = \frac{1}{2}$.

I'd like to know more about algorithms for determining mathematical limits such as this, and I'm primarily concerned with the runtimes of such algorithms.

If it helps, there are only certain types of limits that I'm concerned with.

Specifically, I'm concerned with limits of one variable.  I'm also really only concerned with rational functions of polynomials.  For example, given two polynomials $p(x)$ and $q(x)$, I'm interested in finding the limit $\lim_{x \to 1}\frac{p(x)}{q(x)}$.

There is additional information that should greatly help.  I only really want to find the limit as $x$ approaches 1.  Further, the limit itself is bounded $-O(2^n) \leq \lim_{x \to 1} \leq O(2^n)$.

The function $p/q$ itself is actually a description of a polynomial with powers at most $O(2^n)$, and coefficients $c_i \in {-1, 0, 1}$.

This may not be the best method, but I'm essentially trying to sum the coefficients of a polynomial.

  An Additional Interest

I'm also interested in expanding the problem to include limits of rational functions of multiple polynomials, i.e. polynomials $p_i(x)$ and $q_j(x)$ to find:

$\lim_{x \to 1}\frac{\prod_{i=0}^m{p_i(x)}}{\prod_{j=0}^n{q_j(x)}}$

Note that the polynomials $p_i(x)$ and $q_j(x)$ are very sparse in this representation, consisting of no more than 2 terms.

I don't have time to go into detail now, but here's a quick sketch of how to solve it. Let's assume that all of your polynomials look like $x^k-1$. What you have to do is use the identity $x^k-1 = (x-1)(1+x+x^2+\ldots + x^{k-1})$. You are starting with the function $\frac{\Pi_{i=1}^n (x^{k_i}-1)}{\Pi_{i=1}^m (x^{\ell_i}-1)}$. Now, factor out all the $(x-1)$ terms and take the limit. If $n >m$, you get $0$. If $n \lt m$, you get $\infty$. Otherwise, the $x-1$ terms cancel out, and what you're left with is $\frac{\Pi_{i=1}^nk_i}{\Pi_{i=1}^n\ell_i}$.


Planted Clique in G(n,p), varying p In the planted clique problem, one must recover a $k$-clique planted in an Erdos-Renyi random graph $G(n,p)$. This has mostly been looked at for $p=\frac{1}{2}$, in which case it is known to be polynomial-time solvable if $k > \sqrt{n}$ and conjectured hard for $k< \sqrt{n}$.

My question is: what is known/believed about other values of $p$? Specifically, when $p$ is a constant in $[0,1]$? Is there evidence that, for every such value of $p$, there exists some $k=n^{\alpha}$ for which the problem is computationally hard?

References would be particularly helpful, as I haven't succeeded in finding any literature which looks at the problem for values other than $p=\frac{1}{2}$.

If $p$ is constant, then the size of the maximum clique in the $G(n,p)$ model is almost everywhere a constant multiple of $\log n$, with the constant proportional to $\log (1/p)$.  (See Bollobás, p.283 and Corollary 11.2.)  Changing $p$ should therefore not affect the hardness of planting a clique with $\omega(\log n)$ vertices as long as the clique is too small for an existing algorithmic approach to work.  I therefore expect that with constant $p \ne 1/2$ the hardness of Planted Clique should behave just like the $p=1/2$ case, although it is possible that the case of $p$ very close to 0 or 1 might behave differently.

In particular, for $p\ne 1/2$ the same threshold of $\Omega(n^{\alpha})$ for $\alpha = 1/2$ for the size of the planted clique applies, above which the problem becomes polynomial-time.
The value of $\alpha$ here is $1/2$ (and not some other value) because the Lovász theta function of $G(n,p)$ is almost surely between $0.5\sqrt{(1-p)/p}\sqrt{n}$ and $2\sqrt{(1-p)/p}\sqrt{n}$, by a result of Juhász.
The algorithm of Feige and Krauthgamer uses the Lovász theta function to find and certify a largest clique, so it relies on this threshold size for the planted clique.

Of course, there may be a different algorithm that does not use the Lovász theta function, and that for values of $p$ far from $1/2$ can find a planted clique with say $n^{1/3}$ vertices.  As far as I can tell this is still open.

Feige and Krauthgamer also discuss when $p$ is not constant but depends on $n$, and is either close to 0 or close to 1.  In these cases other approaches exist to find planted cliques, and the threshold size is different.

Béla Bollobás, Random Graphs (2nd edition), Cambridge University Press, 2001.
Ferenc Juhász, The asymptotic behaviour of Lovász' $\vartheta$ function for random graphs, Combinatorica 2(2) 153–155, 1982.  doi:10.1007/BF02579314
Uriel Feige and Robert Krauthgamer, Finding and certifying a large hidden clique in a semirandom graph, Random Structures & Algorithms 16(2) 195–208, 2000.  doi:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A


Is there a known extension of Dirac's / Ghoulia-Houri's theorems for $k$-path existence? In the well studied problem of Hamiltonicity, several papers/theorems gave sufficient "degree conditions" for the existence of Hamiltonian path in a graph.

These include:

Dirac's theorem , 1952, which states that "A simple (undirected) graph with $n$ vertices ($n \geq 3$) is Hamiltonian if every vertex has degree $\frac{n}{2}$ or greater".
Ghouila-Houiri 's theorem, ("Une condition suffisante d’existence d'un circuit hamiltonien",1960), which generalized Dirac's result to directed graphs, showing that if $\delta^+(G),\delta^-(G) \geq \frac{n}{2}$ then G is Hamiltonian, where $\delta^+(G)$ is the minimal out degree in $G$, and by $\delta^-(G)$ the minimal in-degree.
A theorem from Bang-Jensen and Gutin's book gave a stronger result, which imply that if $\forall v\in V: d_{in}(v)+d_{out}(v)\geq n$ then the graph is Hamiltonian.

The $k$-path problem is a simple generalization of Hamiltonicity asking whether a simple path on $k$ nodes exist in a graph.

  What would be the weakest sufficient "degree conditions" from a graph such that it is bound to contain a $k$-path?

I don't know about the weakest possible conditions, but if a graph has a subgraph with minimum degree $k-1$ (that is, if its degeneracy is at least $k-1$) then a greedy algorithm can easily find a path of $k$ nodes starting at any node. The example of $K_{k-1}$, which has no $k$-path and has minimum degree $k-2$, shows that this is tight.


Quantum cellular automata This questions is cross-posted from MathOverflow

A little background: As far as I know there is no standard definition of a quantum cellular automaton in the literature. Different authors use different definitions. Here I propose my own definition (though I probably consider it my own out of ignorance rather than originality). This definition seems very natural but immediately raises several questions which I find difficult to answer. Here I ask the two questions that seem the most fundumental. Here it goes:

Fix $V$ a complex inner product vector space of finite dimension $n$. Consider $A$ the *-algebra End($V$). Take $\Gamma = \mathbb{Z}^d$ a lattice. Define the *-algebra $A_\Gamma$ (quantum cellular automaton observables) in the following manner. Assign to each element $x$ of $\Gamma$ a copy $A_x$ of $A$. To each finite subset $S$ of $\Gamma$ we can correspond the *-algebra $A_S$ defined by

$A_S$ := Tensor product of $A_x$ over $x \in S$

For two finite subsets $S$, $R$ of $\Gamma$ with $S$ contained in $R$ we have the morphism

$i_{S,R}$: $A_S \rightarrow A_R$

obtained by tensoring with $1 \in A_y$ for all $y \in R\backslash S$. We define $A_\Gamma$ to be the direct limit of $A_S$ w.r.t. $S$.

Denote $T_\Gamma$ the group of translations of $\Gamma (Z^d)$. $T_\Gamma$ acts on $A_\Gamma$ in the obvious manner.

A quantum cellular automaton is defined to be a *-endomorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. An invertible quantum cellular automaton is defined to be a *-automorphism of $A_\Gamma$ commuting with the action of $T_\Gamma$. The 1st question is:

  Are all quantum cellular automata invertible?

Any unit vector $v \in V$ defines a state

$\phi_v$: $A_\Gamma \rightarrow C$

in the following manner. Suppose $S$ is a finite subset of $\Gamma$ and for any $x \in S$, $a_x$ is an element of $A_x$. Then we have $a_S$ an element of $A_S$ (and hence of $A_\Gamma$) defined by

$a_S$ := tensor product of $a_x$ over $x \in S$

We then define

$\phi_v(a_S)$ := product of $(v, a_x v)$ over $x \in S$

It is easy to see this extends uniquely to a linear map $\phi_v$: $A_\Gamma \rightarrow C$ and that the map is a state.

Fix $v$ in $V$. We construct the Hilbert space $H_v$ in the following manner. Choose $v_1$ ... $v_n$ an orthonormal basis of $V$ s.t. $v_1 = v$. Consider maps

$\alpha: \Gamma \rightarrow \{1 ... n\}$

s.t. $\alpha(x) = 1$ for all $x$ except a finite set. Define $J$ to be the set of such $\alpha$. To each $\alpha \in J$ we assign the basis vector $\Psi_\alpha$ of $H_v$, thought of as

$\Psi_\alpha$ := tensor product of $v_\alpha(x)$ over $x \in \Gamma$

Thus $H_v$ is defined to be $l^2(J)$. It is easy to see that $H_v$ thus defined depends only on $v$ and not on $v_2$ ... $v_n$ i.e. that for any two choices of $v_2$ ... $v_n$, there is a canonical isomorphism between the corresponding Hilbert spaces.

There is a natural *-homomorphism

$\rho$: $A_\Gamma \rightarrow B(H_v)$

where $B(H_v)$ is the *-algebra of bounded operators on $H_v$. Thus, any unit vector $\Psi \in H_v$ defines a state

$\phi_\Psi$: $A_\Gamma \rightarrow C$

by

$\phi_\Psi(a) = (\Psi, \rho(a) \Psi)$

Now, fix an invertible quantum cellular automaton $f$: $A_\Gamma \rightarrow A_\Gamma$. Suppose $v$ in $V$ is s.t. $\phi_v$ is $f$-invariant. Then $f$ is called $v$-representable if there exists

$U$: $H_v \rightarrow H_v$

a unitary operator s.t. for any $\Psi \in H_v$ we have

$\phi_U \Psi = f^*(\phi_\Psi)$

It is clear that if such $U$ exists it is unique.

The 2nd question is:

  Is any invertible quantum cellular automaton $v$-representable for any $v$ with $\phi_v$ $f$-invariant?

Niel de Beausdrap found this article. The authors (Schumacher and Werner) propose a definition of quantum cellular automata and prove they are always invertible (Corrolary 7 on p. 10). Nominally their definition is different since they use the norm-completion of the algebra $A_\Gamma$ and impose a locality condition. However, it is actually equivalent.

Their locality condition states that the image of $A_x$ has to be contained in $A_S$ for some finite S. However, if we avoid the norm completion it holds automatically since any element of the direct limit is in $A_S$ for some finite S and $A_x$ is finite dimensional.

Moreover, an endomorphism of $A_\Gamma$ is always continuous hence extends to the completion. This is because the matrix norm can be defined algebrically as the maximal |lambda| for which a*a - lambda is non-invertible.

Representability follows from their Theorem 6 on p. 10 which gives a rather explicit (modulo some complicated constraints) description of all nearest-neighbour quantum cellular automata. As discussed on p. 9 this description encodes two finite-dimensional unitary operators. These operators can be easily used to construct the operator $U$ I seek.

As discussed on p. 8 the case of non-nearest-neighbour can be easily reduced to this case


Number of Hamiltonian cycles on random graphs We assume that $G\in G(n,p),p=\frac{\ln n +\ln \ln n +c(n)}{n}$.
Then the following fact is well known:

\begin{eqnarray}
Pr [G\mbox{  has a Hamiltonian cycle}]=
  \begin{cases}
    1 & (c(n)\rightarrow \infty) \\
    0 & (c(n)\rightarrow - \infty) \\
 e^{-e^{-c}} & (c(n)\rightarrow c)
  \end{cases}
\end{eqnarray}

I want to know results about the number of Hamiltonian cycles on random graphs.

Q1. How many is the expected number of Hamiltonian cycles on $G(n,p)$?

Q2. What is the probability $Pr [G \textrm{ has a *unique* Hamiltonian cycle}]$ for the edge probability $p$ on $G(n,p)$?

As Yuval said, Q1 is easy to answer using linearity of expectation (spoiler: $(n-1)!p^n$) . I don't know the exact answer to Q2, but it might be good enough if you know it's very low: for the range of $p$ where there is at least one cycle, it holds that $P[\text{there is more than one cycle} | \text{there is at least one cycle}]>1-1/n^{\log n}$ or so. In other words, once there is one cycle, there are many. The reason is that once there is one cycle, there are around $n^2$ ways to create another cycle from it by exchanging two edges of the cycle by the two "crossing" edges (this is called a "2-flip" or something in some of the relevant literature). For any pair of edges, the chance you can do that is $p^2$. So for all of these to fail, the chance is $(1-p^2)^{n^2}$ which is roughly $e^{-(pn)^2}$, which is pretty tiny.


Are there descriptive complexity representations of quantum complexity classes? The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in.

Descriptive complexity theorists, such as Immerman and Fagin, have characterized many of the most well-known complexity classes using logic.  For example, NP can be characterized with second-order existential queries; P can be characterized with first-order queries with a least-fixed point operator added.

My question is:  Have there been any attempts, especially successful ones, at coming up with such representations for quantum complexity classes, such as BQP or NQP?  If not, why not?

Thank you.

Update(moderator): this question is completely answered by this post on mathoverflow.

Gurevich in formulating the conjecture about a logic that could capture $\mathsf{P}$ requires the logic to be computable in two ways: (1) the set of sentences legally obtainable from the vocabulary $\sigma$ has to be computable, given $\sigma$; and (2) the satisfiability relation needs to be computable from $\sigma$, i.e., ordered pairs consisting of a finite structure $M$ and a sentence $\varphi$ such that all models isomorphic to $M$ satisfy $\varphi$.  Also, significantly for comparison with this randomized logic result, the vocabulary $\sigma$ has to be finite.  (A vocabulary is a set of constant symbols and relation symbols, for example, equals sign, less-than sign, $R_1,R_2,\ldots$)  This is a paraphrase of Definition 1.14 of this paper by Gurevich, which is reference [9] in the quote Kaveh gave.

The paper about BPP and randomized logic presents a significantly different framework.  It starts with a finite vocabulary $\sigma$, and then considers a probability space of all vocabularies that extend $\sigma$ with some disjoint vocabulary $\rho$.  So a formula is satisfiable in the new randomized logic if it is satisfiable in "enough" logics based on extensions of $\sigma$ by different $\rho$.  This is my butchering of Definition 1 in the Eickmeyer-Grohe paper linked to by Robin Kothari.  In particular, the vocabulary is not finite (well, each vocabulary is, but we have to consider infinitely many distinct vocabularies), the set of sentences of this logic is undecidable, and the notion of satisfiability is different from the one put forth by Gurevich.


Enumerating all pairs of disjoint paths Given a directed graph $G = (V,E)$ and two vertices $s,t \in V$. A pair of simple paths $p_1,p_2$ from $s$ to $t$ is edge disjoint if they don't share an edge.

Using max flow, it is easy to decide if there is a pair of edge disjoint paths from $s$ to $t$. Now, is there a polynomial time delay algorithm to enumerate all pairs of edge disjoint path from $s$ to $t$?

I believe Artem Kaznatcheev's answer is correct, but it does not give polynomial space. So here's a different approach that should work a little better in that respect.

Using max flow it is possible to solve a slightly more general problem: find a pair of edge disjoint paths from some two vertices {s1,s2} to some other pair of vertices {t1,t2}, but without controlling which source vertex is connected to which destination vertex.

Suppose we have a graph G and vertices s1,s2,t1,t2 for which we want to list all pairs of paths. Find a single pair of paths P1,P2, and let e = (s1,v) be the first edge on one of those paths. Then we can split the problem space into two subproblems: the pairs of paths that use e are the same as the paths from {v,s2} to {t1,t2} in G-s1, and the pairs of paths that do not use e are the same as the paths from {s1,s2} to {t1,t2} in G-e. Recurse in both of these two subproblems, and (to avoid duplication) only report a path when you're at the bottom of the recursion.


How can a problem be in NP, be NP-hard and not NP-complete? For the longest time I have thought that a problem was NP-complete if it is both (1) NP-hard and (2) is in NP.

However, in the famous paper "The ellipsoid method and its consequences in combinatorial optimization", the authors claim that the fractional chromatic number problem belongs to NP and is NP-hard, yet is not known to be NP-complete. On the third page of the paper, the authors write:

  ... we note that the vertex-packing problem of a graph is in a sense equivalent to the fractional chromatic number problem, and comment on the phenomenon that this latter problem is an example of a problem in $\mathsf{NP}$ which is $\mathsf{NP}$-hard but (as for now) not known to be $\mathsf{NP}$-complete.

How is this possible? Am I missing a subtle detail in the definition of NP-complete?

It seems the issue is the kind of reductions used for each of them, and they are using different ones: they probably mean "$\mathsf{NP}$-hard w.r.t. Cook reductions" and "$\mathsf{NP}$-complete w.r.t. Karp reductions".

Sometimes people use the Cook reduction version of $\mathsf{NP}$-hardness because it is applicable to more general computational problems (not just decision problems). Although the original definition of both $\mathsf{NP}$-hardness and $\mathsf{NP}$-completeness used Cook reductions (polynomial-time Turing reductions) it has become uncommon to use Cook reductions for $\mathsf{NP}$-completeness (unless it is stated explicitly). I don't recall any recent paper that has used $\mathsf{NP}$-complete to mean $\mathsf{NP}$-complete w.r.t. Cook reductions. (As a side note the first problem that to be proven to $\mathsf{NP}$-hard was TAUT not SAT and the completeness for SAT is implicit in that proof.)

Now if you look at section 7 of the paper, bottom of page 195, you will see that they mean $\mathsf{NP}$-hardness w.r.t. Turing reductions.

So what they mean here is that the problem is in $\mathsf{NP}$, is hard for $\mathsf{NP}$ w.r.t. Cook reductions, but it is unknown to be hard for $\mathsf{NP}$ w.r.t. Karp reductions (polynomial-time many-one reductions).


What to do as a Theoretical computer science PhD student in a free time? I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff Erickson's lecture note etc. I am doing this thing from many months and wondering. Is this a right thing for me to do in free time as now I am a Ph.D. student not an undergraduate student. Now why I do this to become more strong in an algorithm, discrete maths etc part. Another thing which seems more valuable to me is to read more and more research paper of my research domain as my goal after my Ph.D. is to publish more quality research papers in the field related to my current field. I am wondering which one is better or suggest anything else which may be more valuable to me keeping my future perspective in mind.

Question: What to do as a Theoretical computer science PhD student in free time? I am wondering what star experienced researchers do in their time ( assuming they have a free time ).

Some of my free time I also spent on watching video lecture of workshops related to my field.

After looking at all the comments and answers, I have to edit my question. I think, I have not been able to convey what I was trying to ask. My question was how to sharp my technical skills in the free time for a better future. It has nothing to do with my personal life or some one's personal space. I was here for the various possibilities and opinions of users, who have experience in theoretical computer science. Let me clarify my question further, I was to trying to ask in the free time what is more significant to do " continue to think about the research problem at hand or do the problems related to maths or algorithms " and so on. Looking at the comments have made me realise that definitely I need to improve my writing skills also.

I strongly agree with other comments that over-optimizing your time is not healthy and your brain needs downtime, preferably social interaction or physical exercise. However, if you feel you have that covered, what I think separates good from great researchers, is having an overarching vision; a generic direction, or specific goal to strive to. To see the forest for the trees, if you will.

One way to achieve this, is to reflect in those moments of spare time; to philosophize very generically on society and identify problems in it. This can range from wicked problems like climate change and inequality, to more practical problems like cybersecurity (e.g. Heartbleed) and software safety (e.g. the Toyota incidents). Don't worry about staying inside your field if things fascinate you. Read widely to find interests. Read popular media, popular science writing, quality newspapers and see what other people worry about. Read the solutions that are being proposed, evaluate their feasibility, and think hard to come up with better ones. Better ideas can make all the difference. For example, the Rust language is tackling the security and software safety issues commonly found in C infrastructure, the Julia language is focused on solving the two language problem in scientific computing and improving the state of the art in data science and machine learning, while Elon Musk's Tesla is aiming to accelerate the advent of sustainable energy in order to counter climate change. Each of these admirable projects started with good research ideas, by people committed to a higher level ideal. Finding your higher level ideal is what you should focus on.

A higher level goal will motivate you to get up in the morning, shape your career in a given direction and give you a sense of purpose and satisfaction. Most likely it is not something you'll settle on in a single afternoon. It is something that requires plenty of reflection, that can shift as your knowledge of the world shifts, changes as your priorities change. If you're ambitious, a good question to ask is "What will have the greatest positive impact on the largest amount of people?". Go crazy, get creative and consider scifi: "Maybe I should solve the inequality problem by writing a Decentralized Autonomous Organisation on Ethereum that unconditionally distributes a Global Basic Income to all." If, however, you are somewhat more realistically inclined, you might just choose to work on Blockchain tech because you believe in its huge potential for leveraging social benefit.

Maybe you are satisfied with something lower profile, that concerns you more directly, which is perfectly fine. What matters is that you find it valuable and worth spending your time on. These are the same principles successful entrepreneurs use to identify possible projects; two considerations are "Am I passionate about this?" and "What's the benefit to society?" The greater the benefit to society, the greater the market for it will be. A great researcher understands this, and chooses to accumulate expertise towards solving a general, overarching problem in his domain. This will have the largest impact both on his career, as well as society. Whatever you do, don't think a paper at a time, but see papers as building blocks towards an end, and take control of where you're going.


Imperfect subgraph isomorphism Consider the following problem: Given a query graph $G = (V, E)$ and a reference graph $G' = (V', E')$, we want to find the injective mapping $f : V \rightarrow V'$ which minimizes the number of edges $(v_1, v_2) \in E$ such that $(f(v_1), f(v_2)) \notin E'$. This is a generalization of the subgraph isomorphism problem where we allow the subgraphs to be isomorphic up to a few missing edges and want to find the way to minimize the number of missing edges.

I would also be interested in the weighted version of this problem, where vertex couples $(v_1, v_2) \in V^2$ carry a weight $w(v_1, v_2)$ (which must be zero if $(v_1, v_2) \notin E)$, and likewise for $G'$, and we wish to minimize $\sum_{v_1, v_2} (\max(0, w(v_1, v_2) - w(f(v_1), f(v_2))))$ (the $\max$ is there to only penalize weights from the query graph being larger than those of the reference graph).

My question are: Has this problem already been studied? Does it have a well-known name? Are there any efficient approximation algorithms known?

The motivation of this problem (apart from the fact that it seems like a natural generalization of the subgraph isomorphism problem) is that it is a nice way to make a table plan for a party: the query graph is the graph of guests with edge weights representing the extent to which two people want to interact, the reference graph has the table seats as vertices and edge weights indicating to what extent communication is possible, the solution of the problem is a mapping from people to table seats which respects the social structure to the fullest possible extent.

Your problem is Maximum Common Edge Subgraph Problem (Max CES) defined as follows:
given two graphs $G$ and $G'$, find a graph $H$ with the maximum number of edges
that is isomorphic to a subgraph of $G$ and to a subgraph of $G'$.

Proof: You are finding a subgraph $H$ of $G$ isomorphic to a subgraph of $G'$,
where $|E_{G}| - |E_{H}|$ is minimized. Since $|E_{G}|$ is an invariant of $G$,
$|E_{G}| - |E_{H}|$ is minimized if and only if $|E_{H}|$ is maximized.
Clearly, $H$ is isomorphic to a subgraph of $G$ and to a subgraph of $G'$. Q.E.D.

Approximability. In the Ph.D thesis of Kann, I found the description
"not known to be approximable within a constant" [3] (p. 115).
In a recent paper by Bahiense et al. [1],
it is mentioned that if $|V_{G}|$ and $|V_{G'}|$ are not required to be equal,
the problem becomes APX-hard.
But the citation for this result is an unpublished private communication [2].

L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, to appear. doi:10.1016/j.dam.2012.01.026
M.M. Halldorsson, Personal communication, unpublished manuscript, 1994.
V. Kann. On the Approximability of NP-complete Optimization Problems. Ph.D. Thesis, NADA report TRITA-NA-9206, 1992. http://www.nada.kth.se/~viggo/papers/phdthesis.pdf


Why go to theoretical computer science/research? I'm currently starting on the university [computer science] and there we have lot of opportunities to begin with researching. Before finding this website, I had no intention to go on this way [I wanted to work with AI, probably game dev.], but now I can [or I need] to make a choice.

Can you convince me to join on this "world"? What "segments" I can follow? Is there anything about what kinds of topics a computer scientist or researcher works on?

I can relate my reasons as an undergraduate applying to TCS graduate programs this upcoming Winter (so little time left!).

There's the beauty. This isn't something I can explain (and have witnessed other mathematicians failing to explain). It's like "yellow." If you haven't seen it, I'm not sure I could communicate to you what it is. But since you've become interested in theory, I suppose maybe you do experience it.
There's universality. Universality beyond the Church-Turing Thesis. TCS at it's core investigates high level and low level phenomena in information - it's the "physics" of information. And since information is qualitatively atomic, information theory does have things to say about physics (my QM professor has specifically told me he loves information theory). All of this being said, it's somewhere between Pure Math and Engineering. It has the capability and flexibility to contribute directly to both, and to be contributed to directly by both. Still, it fights on its own frontier.
There's the scope. This was hinted at in the previous bullet. Informatics finds its way into many different applications - stuff everyone from the DHD to startups are interested in. You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)
There's the challenge. Take a look at a list of open problems in Theoretical Computer Science (and pursue an understanding of them to the end of inquiry). They are very hard - here are some reasons why. We really don't understand TCS - most of our proofs boil down to mounting evidence. There's just so much work left to do!


Random self-avoiding lattice cycle within a given bounding box In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.

One way to do this would be to use a Markov chain whose states are sets of squares whose boundaries are simple cycles and whose transitions consist of choosing a random square to flip and keeping the flip when the modified set of squares still has a simple cycle as its boundary. One can get from any simple cycle to any other one in this way (using standard results about existence of shellings) so this eventually converges to a uniform distribution, but how quickly?

Alternatively, is there a better Markov chain, or a direct method for selecting simple cycles?

ETA: See this blog post for code to calculate the number of cycles I'm looking for, and pointers to OEIS for some of these numbers. As we know, counting is almost the same thing as random generation, and I infer from the lack of any obvious pattern in the factorizations of these numbers and the lack of a formula in the OEIS entry that there unlikely to be a known simple direct method. But that still leaves the questions of how quickly this chain converges and whether there's a better chain wide open.

It seems that because you are only using the counts for number of cycles in a graph to randomly choose a cycle, that if you had a random approximation for this number, then you could still choose a cycle approximately uniformly.

Note that the number of cycles in a graph $G$, which contains edge $(u, v)$, equals the number of cycles in $G - (u, v)$ plus the number of simple paths from $u$ to $v$ in $G - (u, v)$.  Thus, with a polynomial time approximation for the number of $u$-$v$ paths, the a polynomial time approximation can be achieved by incrementally building up to $G$ one edge at a time, approximating as you go.

I actually think that there's a more straightforward method for choosing a cycle.  Let $G$ be the entire graph of edges around the $n \times n$ grid of squares. For each edge $(u, v)$ find the number of cycles containing that edge (which is the number of $u$-$v$ paths in $G$ - $(u, v)$). Then randomly choose an edge weighted by the number of cycles that contain it.  This will be the first edge in your randomly chosen cycle. All other edges will be chosen by extending one edge at a time.

Assume that you have chosen a path which is part of your random cycle.  Let the set of vertices on this path be $C$ and let $v_s$ and $v_e$ be the endvertices of the path.  Also let $N$ be the set of neighbors of $v_e$ which are not in $C$ (note that there are only up to 3 in this particular graph).  For each $u \in N$ count the number of $u$-$v_s$ paths in the induced graph $G[V - (C - \{v_s, v_e \} ) ]$. Then choose a neighbor, $u$, of $v_e$ weighted on the paths just counted. Add the edge $(v_e, u)$ to your chosen path, extending it by one.

In this way, a polynomial number of edges are chosen, each requiring a small number of calculations of a polynomial time approximation algorithm.  Thus, a cycle can be uniformly chosen.

I currently have a stackexchange question requesting references for fast path count approximation algorithms. I've read in a few places that these algorithms exist but haven't yet found them.


Complexity of finding a consistent hyperplane Given $m$ binary labeled points in $\mathbb{R}^d$, it is well-known that in general it's NP-hard to find a hyperplane that minimizes sample error. A brute-force search considers all $O(m^d)$ sample point $d$-tuples which span all candidate hyperplanes, and the dimension $d$ is the hardness parameter (see the paper by Höffgen et al.)
What about the realizable case? Here two natural algorithms come to mind: the Perceptron and Linear Programming. The Perceptron has runtime quadratic in inverse margin. Since we currently don't know of any strongly polynomial LP solvers, all current methods depend, in the worst case, on the configuration of the labeled points -- i.e., the runtime also depends on the margin.
Question: Is there a strongly polynomial algorithm for finding a consistent hyperplane?
Edit (04-Oct-2018). I had accepted an answer but there is a problem with it, so as of now the status of the question is unknown. Is consistent hyperplane as hard as general LP?
Edit 2 (06-Oct-2018). Status: solved!

Second version, hopefully correct.

I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce linear programming to the feasibility problem.

Let us first reduce the strict feasibility problem $\exists? x: Ax < b$ to finding a linear separator. Towards this, notice that you can reduce to the special case $b=0$: just transform the constraints to
$$
Ax + tb < 0, \\
t < 0
$$
If $Ax < b$ is feasible for some $x$, then $(x, -1)$ is feasible for the problem above. Conversely, if $(x, t)$ is feasible for the problem above, then $\tilde{x} = -x/t$ is feasible for $A\tilde{x} < b$.
This reduction just adds a row and a column to $A$, and a new variable $t$.

Assume then that you are given the problem $Ax < 0$.
Create a data set which has one point labeled red for every row of $A$, and is equal to that row. It also contains the origin $0$, labeled blue. Any hyperplane $H$ separating the red-labeled points from the blue-labeled origin gives a solution to $Ax < 0$: just take the normal of $H$ in the direction of the origin to be $x$.

The final step is to reduce the feasibility problem $Ax \le b$ to the strict feasibility problem $Ax < b$. We argue that given an oracle for the strict feasibility problem, we can solve the feasibility problem. Let $S$ be an inclusion-maximal set of constraints such that the system $\forall i \in S: (Ax)_i < b_i$ is feasible: we can find $S$ in at most $m$ calls to the oracle (assuming $A$ is $m\times n$). If $S$ contains all constraints, we are done. Otherwise, it is not hard to see that, if $Ax \le b$ is feasible, then for any $i \not \in S$ the constraint $(Ax)_i \le b_i$ must be satisfied with equality for all feasible $x$. Use one (or more) of these constraints to eliminate one (or more) of the variables, and recurse on the remaining variables.

This equivalence between finding a linear separator and linear programming is surely well-known, but I do not know what the right reference is. For example, I have seen something like the final reduction above attributed to Chvatal.


Computation beyond unitary matrices Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be any computation paradigm beyond unitary matrices?

Circuits made out of general linear operators are $PP$-complete. See the PostBQP paper by Scott Aaronson  or Schuch's paper on the computational power of PEPS and tensor network contraction.


Optimization problems with same optimal value, but different approximation behavior Context: related to this answer.

I would like to see an example to emphasize that approximation behavior depends not only on the optimal value but also the set of solutions. This makes sense logically. If two problems are duals of each other, then they have the same optimal value but can have different behavior with respect to approximation (eg: independent set and vertex cover). But, is the same possible if both are minimization problems, or both are maximization problems?

Are there two minimization problems with same optimal value, but different behavior with respect to approximation?

Existence of such a pair of problems justifies the definition of approximation factor preserving reduction.

What about something like minimum vertex cover vs. minimum fractional vertex cover (i.e., optimal solution of the LP relaxation of the vertex cover problem) in bipartite graphs?

These two problems have the same optimal value.

However, if I give you a black-box algorithm that finds a $(1+\epsilon)$-approximation of the minimum fractional vertex cover, this does not help much if you would like to output a $(1+\epsilon)$-approximation of the minimum vertex cover.

This can be formalized in some sufficiently weak models of computation. For example, if we look at distributed algorithms, one can show that a $(1+\epsilon)$-approximation of the minimum fractional vertex cover is easy to find, while a $(1+\epsilon)$-approximation of the minimum vertex cover is hard to find in bipartite graphs. (Here "easy" is e.g. constant time in the LOCAL model and "hard" is e.g. at least logarithmic time in the same model, assuming a sufficiently small constant $\epsilon > 0$ and some constant upper bound on the maximum degree. So there cannot be e.g. constant-time approximation-preserving LOCAL model reductions between the two problems, even if the optimum is the same.)


What can we prove with infinite graphs that we cannot prove without them? This is a follow-up question to this one about infinite graphs.

Answers and comments to that question list objects and situations which are naturally modeled by infinite graphs. But there are also numerous theorems about infinite graphs (see chapter 8 in Diestel's book) of which, for example, Koenig's infinity lemma is a very famous one.

Now I have the following question: What can we prove with infinite graphs that we cannot prove without them? Or more specifically, what is an example where we model something as an infinite graph, then invoke a theorem about infinite graphs, and in the end have proved something about the original problem -- without knowing how to prove it otherwise?

Here's an example from distributed computing:

1 Background

1.1 Asynchronous Shared Memory Model

Let's consider a collection of distributed nodes that communicate using
shared memory variables. There is an adversary that controls when a node take steps
and when to deliver messages. The computation is asynchronous, i.e., the
adversary can delay the steps of nodes for any (finite) amount of time.
You can think of a step of a node as a state transition of its local
automaton (according to the algorithm) where the next state is determined
by the current state and the observations of the node since the last step.

1.2 Safety and Liveness

When formally reasoning about the properties of an asynchronous algorithm,
we distinguish between safety and liveness properties. Informally, a
safety property can be interpreted as a guarantee that something "bad"
never happens. (E.g., for mutual exclusion, a safety property would be
that no two nodes enter the critical section  simultaneously.) Liveness,
on the other hand, can be interpreted as "something good will eventually
happen", e.g.: every node eventually terminates.

To formalize safety, we consider the infinite set ${M}$ of all possible
executions of all possible algorithms, taking into account all possible
choices of the adversary. An execution is an infinite sequence of steps.  We can define a metric on $M$ by taking the distance between two distinct
runs $\alpha,\beta \in M$ to be $2^{-n}$ where $n$ is the first index where $\alpha$ and $\beta$ differ.

A safety property $S$ corresponds to some nonempty set $P\subseteq M$ that
is closed in the sense that the limit of an infinite
sequence of runs in $P$ cannot be in $M\setminus P$. So once we know that some property is a safety property, it is sufficient to show that this property holds on finite prefixes.

Applying Koenig's Infinity Lemma

It's not always straightforward to see whether a specific property is a
safety property: Consider the implementation of read/write atomic objects
on top of basic shared memory variables. Such an implementation should handle requests and their responses in a way that makes them look as if they happen at some instant in time and don't violate their order of invocation. (Due to the asynchronous operation, the actual duration between request and response might be nonzero.) Atomicity is also known as Linearizability. Section 13.1 of [A] gives a proof that Atomicity is a safety property. The proof uses Koenig's lemma to show that the limit of any infinite sequence of executions (each of which satisfies Atomicity) also satisfies Atomicity.

[A] N. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.


Fault-tolerant programming languages / paradigms? I've been passively thinking for a long time, what could be the foundation for programming systems that can tolerate their own and other systems' bugs (not even speaking of environmental conditions such as hardware errors).

The thing is, I don't believe that it's possible to eradicate programming errors, and the fabric of current programming languages and systems is too brittle - a system can completely stop operating because of an off-by-one-error or a race condition (or a distributed race condition between several systems), which seems stupid if you think about it - we don't see the universe halt because of an explosion somewhere, or a society halt because of a typo in a law.

Therefore, it seems to me that type systems, formal verification are not the way to go - they merely protect the brittle systems instead of making them robust. Neither are fault-tolerant distributed protocols, since they assume that at least the protocol is implemented perfectly correctly, and that participants aren't making the same error.

I wonder, what has the PL community invented so far in this area?

Is there hope for a solution, or is this problem equivalent to building "strong AI" (could be, since living systems recover from transient errors by having goals and employing intelligence)?

A good place to start looking for work coming from the PL community could be the following.

Joe Armstrong's work on Erlang, see e.g. his PhD thesis. This work continues to have a profound influence on programming language design, with Scala's integration of the Akka stack being a recent example.
David Walker and his group's work on fault tolerance.
The numerous investigations into exceptions and exception handling, with a famous early publication being Randell's System Structure for Software Fault Tolerance. The literature on this subject is too large to survey.
Another strand of research is work on recovery oriented programming.


Storage requirements for median selection (two passes algorithms) In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array.  In particular they focus on the following model:

the input is read from left to right for a number P of times.

It is shown that $O(n^{\frac{1}{2P}})$ memory cells are sufficient, but the corresponding lower bound is only known for P=1.  I haven't seen any result for P>1.  Is anyone aware of such lower bounds?

Notice that the main difficulty here is that at the second pass the input is not randomly ordered anymore.

The first paper to prove bounds for more than 1 pass was my paper with Jayram and Amit from SODA'08. Then there is the paper that Warren mentioned, which improves the bounds by a cleaner proof.

In short, we understand the dependence if you allow constants in front of the number of passes. Of course, these constants are in the exponent, so you can ask for a precise understanding. My main complaint is that the model of multipass streaming is not all that well motivated.

The more intriguing question is whether we can prove a branching program lower bound. Can it be that even for a bounded space algorithm that can access memory as it pleases, the best strategy is to just do multipass streaming?

The answer appears to be affirmative, and we have some partial progress towards proving it.


Edit distance with move operations Motivation: A coauthor edits a manuscript and I would like to see a clear summary of the edits. All "diff"-like tools tend to be useless if you are both moving text around (e.g., re-organising the structure) and doing local edits. Is it really so hard to get it right?

Definitions: I would like to find the minimum edit distance, where the permitted operations are:

"cheap" operations: add/change/delete a single character (the usual Levenshtein operations),
"expensive": operations: move a substring to a new location ($abcd \mapsto acbd$ for any strings $a$, $b$, $c$, $d$).

Given two strings $x$ and $y$ and integers $k$ and $K$, I would like to solve the following problem:

can you transform $x$ into $y$ using at most $k$ cheap operations and at most $K$ expensive operations?

Questions:

Does this problem have a name? (It sounds like a very standard question in the context of sequence alignment.)
Is it hard?
If it is hard, is it fixed-parameter tractable with $K$ as the parameter?
Are there efficient approximation algorithms? (E.g., find a solution with at most $2k$ cheap and $2K$ expensive operations if a solution with $k$ cheap and $K$ expensive operations exist.)

I tried to have a look at the string metrics listed in Wikipedia, but none of them looked right.

As commented by Serge Gaspers, for $k=0$ the problem is Sorting by Transpositions, and was introduced by Bafna and Pevzner in 1995. Its NP-hardness has been proved only in 2010; see Laurent Bulteau, Guillaume Fertin, and Irena Rusu, "Sorting by Transpositions is Difficult".


Second eigenvalue and the last eigenvalue Note : All eigenvalues that I would referring to below would of the adjacency matrix of the graph

My question arises from having read about Expander Graphs from a few different sources. The most common definition of Expander Graphs that have seen is in terms of the spectral gap which is $d - \lambda _2$ where $\lambda _2$ is the second highest eigenvalue. However certain sources also like to define expansion in terms of $\lambda$ which is the second highest eigenvalue in absolute value. Now I am slightly confused about what is a better definition and why these two values are so mixed in literature ?

For instance Cheeger's inequalities are defined in terms of $\lambda _2$ and the Expander Mixing Lemma is defined is terms of $\lambda$ (I am not sure if there exist versions of each in terms of the other quantity). Also I have seen versions of the Alon-Bopanna bound in terms of both $\lambda$ and $\lambda _2$.

I guess my question is that is there a fundamental connection between these two quantities and is one more natural than the other to be used to define expansion ?

Also is there something fundamental that $\lambda _n$ (by $\lambda _n$ I mean the smallest eigenvalue) represent ?

I am not sure if I have been able to express my confusion clearly but I am sure I am missing something fundamental in my understanding.

Thanks

Regarding the last eigenvalue:

The last eigenvalue $\lambda_n$ measures (roughly) how close is the graph to be bipartite. For example, $\lambda_n = -d$ if and only if the graph is bipartite (this is a fairly easy exercise). You can read more about it in Luca Trevisan's blog:

http://lucatrevisan.wordpress.com/2008/06/13/max-cut-and-the-smallest-eigenvalue/

http://lucatrevisan.wordpress.com/2008/09/23/max-cut-gain-and-the-smallest-eigenvalue/


A tool for minimal NFA computation It is well known that minimizing an NFA for a fixed regular language is $PSPACE-Complete$.

As far as I know, there are no better than trivial algorithms for minimizing such NFA, but there's a little improvement if you consider symmetries.

I've a specific regular language I'd like to compute a minimal automaton for:

$$
L_{k-distinct} :=\{w = \sigma_1\sigma_2...\sigma_k \mid \forall i\in[k]: \sigma_i\in\Sigma ~\text{ and }~ \forall j\ne i: \sigma_j\ne\sigma_i \}$$

But at the moment I can't seem to close the gap between the automaton I know to build for it and the lower bound I can prove for it.

I thought it might be fruitful to use some tool that given a language (it is finite for all $k,n$), searches (exhaustively if needed) for the smallest automaton which accept it, and see what the automaton looks like for small values of $k,n$.

Does anyone know a tool which builds a minimal automaton for a given language?

The following paper reports on an implementation of the Kameda-Weiner algorithm for computing a minimal NFA, as well on an approach using a SAT solver. I don't know whether the implementation is available, but perhaps you can contact the authors about this.

Jaco Geldenhuys, Brink van der Merwe, and Lynette van Zijl. Reducing Nondeterministic Finite Automata with SAT Solvers. Revised Selected Papers from the 8th International Workshop on Finite-State Methods and Natural Language Processing (FSMNLP 2009), LNCS 6062, Springer, pages 81-92, 2010.


Complexity of validity problem for Monadic First Order Logic? Monadic First Order Logic is FOL with no function symbols, and predicate symbols restricted to arity 1. For this question, let's say that the = symbol is also forbidden. I want to know the complexity of determining if a monadic FOL sentence is valid, ideally in the form of a completeness result (say, under some notion of reduction that the class NE is closed under).

According to this presentation, it was proved a century ago that if S is a satisfiable monadic FOL sentence, then S has a model of size at most $2^kr$, where $r$ is the number of variables and $k$ is the number of predicate symbols. From that it follows that the problem is in $NTIME(2^{n^2})$ and $SPACE(2^n)$: First, guess a (respectively, try every) structure of size $\leq 2^k r \leq 2^n n$. Then evaluate the sentence on that structure in the most straightforward deterministic way, by enumerating all the elements of the structure at every quantifier, and evaluating the quantifier-free parts of the sentence in polynomial time. That takes time $(2^n n)^r poly(n)$, which is in $O(2^{n^2})$. On the other side, it is easy to show that the problem is hard for $PSPACE$.

According to:

Leo Bachmair, Harald Ganzinger, Uwe Waldmann: Set Constraints are the Monadic Class. LICS 1993: 75-83

the problem of checking if a formula of the Monadic Predicate Calculus is satisfiable is NEXPTIME-complete. So your problem (formula validity) is coNEXPTIME-complete.

As cited in the paper, the $NTIME(c^{n / \log n })$ upper and lower bounds  (using different $c > 0$ constants) for the Monadic Predicate Calculus satisfiablility were established in:

Harry R. Lewis: Complexity Results for Classes of Quantificational Formulas. J. Comput. Syst. Sci. 21(3): 317-353 (1980) [pdf download]


Evaluating the expected value of negatively correlated random variables A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, X_n) \in \mathbb{Z}(\mathcal{P})$, $(X_i \in \{0,1\})$:

   $\mathbb{E}[X_i]=x_i$, for all $i \in [n]$.

  For any $S \subseteq [n]$, $\mathbb{E}[\prod_{i\in S} X_i] \leq \prod_{i \in S} x_i$ and $\mathbb{E}[\prod_{i\in S} (1-X_i)] \leq \prod_{i \in S} (1-x_i)$ (negative correlation).

An example is the dependent randomized rounding by Chekuri, Vondrak, and Zenklusen (http://arxiv.org/pdf/0909.4348v2.pdf).

We focus on the dependent randomized rounding. Given a point $x \in \mathcal{P}$, where $\mathcal{P}$ is a matroid polytope, let us assume that $X$ is the outcome of the random process (the dependent randomized rounding). Can we evaluate the value of $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$  for some $S \subseteq [n]$? Shall we use sampling for this purpose?

That would be great if you can comment on this.

I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here.
Can I ask you about the problem in which you need this value to be computed?


What is the fastest deterministic algorithm for incremental dynamic tree reachability? As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time.

The paper (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) introduces an algorithm for maintaining the transitive closure of a graph with O(n) amortized time pre  insertion. I wonder whether better algorithm exists for trees?

The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder.

There are several data structures that can maintain a list of items, allowing insertions immediately before or after one particular item, deletions, and constant time ordering queries, in constant time per operation; see e.g. http://erikdemaine.org/papers/DietzSleator_ESA2002/paper.pdf. Record for each node which tree it belongs to, and use one of these structures for the preorder and postorder of each tree. If these structures do not already do this for you, also use a linked list so you can read off the tree nodes in either order.

To add an edge from a node $x$ to a node $y$ (where prior to the addition, $y$ is the root of a tree) we need to merge the orderings for two trees. Do so by finding which of the two trees is smaller, adding its vertices into the ordering structures for the tree that is larger, and changing the node labels on the nodes in the smaller tree to point to the larger one. In this way, each vertex participates in $O(\log n)$ updates over the lifetime of the structure (every time it is part of the smaller tree, the size of the tree it is in doubles). More precisely, each tree with $k$ edges takes total time $O(k\log k)$ to build, so the amortized time per edge is logarithmic.


Reference request: complexity of $k$-partite $k$-SAT Let's consider following variation of $k$-SAT that I will call $k$-partite $k$-SAT:

given $n$ variables that are divided into $k$ groups and a $k$-SAT formula $\phi$ such that each clause has literal from each group. Is $\phi$ satisfiable?

There is an almost straightforward reduction from $k$-SAT to $k$-partite $k$-SAT that takes formula on $n$ variables and produces formula on $kn$ variables. This proves that this problem is exponentially hard under $ETH$.

On the other hand there a very simple $O^*(2^{(1-\frac{2}{k})n})$ time algorithm for this problem: branch over all variables except 2 groups. You will end up with $2$-SAT problem, that can be solved in polynomial time.

As we don't know algorithms with this kind of savings for $k$-SAT, I'd be surprised if there is a simple reduction from $k$-SAT to $k$-partite $k$-SAT that preserves number of variables.

So I have following question:

Was this problem studied before?
Is there an algorithm with running time $O^*(2^{(1-\epsilon)n})$, where $\epsilon$ is independent on $k$?
If answer for previous question is no, do we know that complexity goes to $2^n$ as $k$ goes to infinity under $SETH$?

Claim: If there exists an $\epsilon > 0$ such that for every $k'$, $k'$-partite $k'$-SAT can be solved in $2^{n(1-\epsilon)}$ time, then SETH fails.

Proof:
Suppose such an algorithm exists. We give an algorithm that, for every $k$ solves $k$-SAT in time $2^{n(1-\epsilon/2)}$.
Consider a $k$-SAT instance with $n$ variables, apply the sparsification lemma so that it produces $2^{n(\epsilon/2)}$ instances where, in every instance, every variable occurs in at most $(k/\epsilon)^{O(k/\epsilon)}$ clauses.
Each of these instances are $(k/\epsilon)^{O(k/\epsilon)}$-partite in the sense that one can find a coloring of the variables into $k' = (k/\epsilon)^{O(k/\epsilon)}$ colors such that no clause contains variables with the same color. If you want clauses of size exactly $k'$ you can replace clauses of size $k$ by $2^{k'-k}$ clauses of size $k'$.
Running the $2^{n(1-\epsilon)}$ time algorithm on each of the $2^{n(\epsilon/2)}$ instances of $k'$-partite $k'$-SAT gives an algorithm for $k$-SAT with running time $2^{n(1-\epsilon/2)}$ as claimed.

Note that the above proof essentially reduces $k$-SAT to $k^k$-partite $k^k$-SAT. So an algorithm with running time $2^{n(1-\frac{\log \log k}{\log k})}$ could still be possible, if very surprising.


Finding a 5-cycle in a sparse graph efficiently. (crossposted from MathOverflow)

Hi,

I was reading this thread: https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length

I want to find a 5-cycle in a graph.  Actually, what I really want is a shortest odd cycle of length at least 5, but maybe that is a little beside the point.  For my purposes, I treat $m$ and $n$ the same in the complexity analysis.

Can we do better than colour coding for finding a 5-cycle in this case?  Let me give a specific formulation of my question:

  What is the minimum $\alpha$ such that there is an $O(m^\alpha)$-time algorithm for detecting a cycle of length 5?  What is the algorithm?  And what is this $\alpha$ if you forbid impractical methods like Coppersmith-Winograd fast matrix multiplication?

To add to Mihai's answer:

Indeed, 5-cycle (and in general $k$-cycle) in sparse graphs can be solved much faster than $O(mn)$ time using the high degree / low degree trick. You need only look at another paper of Alon, Yuster and Zwick:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.4120

For example, a 5-cycle can be found in $O(m^{1.67})$ time, without any dependence on matrix multiplication. See Theorem 3.4 of the above linked paper.

Also, while it is not too hard to reduce 5-cycle detection to Boolean matrix multiplication (with constant factor overhead), a reduction in the opposite direction does not appear in the color-coding paper. A tight reduction (which preserves the runtime complexity) from Boolean matrix multiplication to 5-cycle detection is not known.


Best alien communication protocol? Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-positioning stars in various orbits, what have you.) Let's assume we have decided to make contact with them.

Once we initiate a dialog, how would we go about establishing a communications protocol and language? What methodology would we use to agree on a basic vocabulary and ways of expressing logical ideas? Is it ad-hoc or is there some way to optimize the process of establishing a common language based on symbolic manipulations. We would want to agree on a language quickly and minimize the resources required to encode and send messages (since they're quite slow to send).

Next, reciprocity: Once we have a shared language, how would we make sure that both sides reciprocate in trading secrets? That is, we don't want to be in a situation where we give away valuable technology without receiving anything in return. Can both sides prove that they posses certain technology? Is there a way to send results piecemeal, gradually, so that each side can have increasing confidence in the value of the message?

Your first question is the topic of Brendan Juba's PhD thesis on Universal Semantic Communication. You should take a look at it, as well as some of the papers on his website.

As for your second question, you might want to read about zero-knowledge proofs.


Stochastic version of a strongly NP-Complete problem Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ?
The problem Tree CVRP(Capacitated Vehicle Routing Problem) is proven to be strongly NP-Complete by Hamaguchi & Katoh (1998)( http://bit.ly/VdUBDz ). If the demands are made stochastic then does the problem remain strongly NP-Complete?

A first observation is that the stochastic version of an optimization problem will always be at least as hard as the deterministic version, since fixed constant values in an optimization instance are degenerate special cases of random-variable values.

Now to understand the computational complexity of stochastic optimization problems in more detail, it's important first to explicitly define the "order of quantification" for the problem, and also the measure of "success."

Suppose $x = (x_1, x_2, \ldots, , x_n)$ are the variables to be set by the optimizing party, and $r = (r_1, \ldots, r_m)$ are the "stochastic" variables.  For simplicity of discussion, let's assume these variables are all Boolean.  Let $F(x, r): \{0, 1\}^{n + m} \rightarrow [0, 1]$ be the objective function we want to maximize.

The $r_i$'s are going to be set uniformly at random by Nature, let's assume.  But, are these variables set before the optimizer's decision, or after?  Or, are the optimizer's decisions "interlaced" with the random settings?

(I'm assuming that in whatever model we use, the optimizer can at least "see" the random settings that have already been made by Nature.)

The different possibilities described above can be denoted concisely as

(O1)  $[x_1, \ldots, x_n, r_1, \ldots, r_m]$ (optimizer moves first);

(O2)  $[r_1, \ldots, r_m, x_1, \ldots, x_n]$ (nature moves first);

(O3)  $[x_1, r_1, x_2, r_2, \ldots, x_n, r_n, r_{n + 1}, \ldots, r_{m}]$  (alternation; assuming here that $m \geq n$).

So that's the "quantification order" question.  Next, we also have to decide how to measure the "success" of an optimizer's strategy.  There are two simple possibilities:

(S1)  Measure success as the expected output value of $F(x, r)$;

(S2)  Measure success as the probability that $F(x, r)$ meets or exceeds a desired threshold value $\alpha \in [0, 1]$.

To make my life easier, I'm only going to discuss (S1), but most of what I say also applies to (S2).

Finally, we have the issue of what kind of function $F$ is.  There are two fairly general options to consider:

(C1)  $F$ is a general poly-time computable function into $[0, 1]$;

(C2)  $F$ is defined by a collection of local Boolean constraints $\psi_1, \ldots, \psi_\ell$, each acting on $O(1)$ variables in $(x, r)$, and $F(x, r)$ equals the fraction of satisfied constraints.

OK, now having multiplied the number of questions to consider, I can at least answer some of them.  First, if one is asking for extremely accurate information about the achievable success, then the problem becomes ridiculously hard, even if there are no optimization variables!  (i.e., even if x is empty.)  For instance, if $F(r)$ is a SAT instance outputting 0 or 1 according to whether it is satisfied, then (S1) asks us to compute the fraction of accepting inputs, which is $\# P$-complete.  So I think it is more reasonable to settle for a .001-approximation (accurate to within $\pm .001$), or maybe more ambitiously for a $1/n^c$-approximation to the success measure, for each $c > 0$.  Now with these goals in mind:

-For (O1), in which the optimizer sets all the $x$-variables first, the problem is $MA$-complete to .001-approximate, if $F$ is a general Ptime-computable function.  (One has to define completeness for an approximation problem appropriately, and for the promise class $MA$, but morally this is the right complexity classification.)  The proof just follows the definitions.  If $F$ is as in (C2), then the problem is in $NP$, since we can use linearity of expectations to compute the expected value of $F(x, r)$ for any fixed $x$.

-For (O2), in which Nature sets the $r$-variables first, the problem is $AM$-complete to .001-approximate, whether $F$ is as in (C1) or (C2).  For (C1) this follows from an easy black-box application of the Cook's theorem plus the PCP theorem.  For (C2), I showed the $AM$-completeness result in the following paper:

http://eccc.hpi-web.de/report/2010/019/

-For (O3), interlaced variable-settings, the problem is $PSPACE$-complete to .001-approximate, even in the (C2) case; this was shown by Condon, Feigenbaum, Lund, and Shor in this paper:

http://cs-www.cs.yale.edu/homes/jf/CFLS.pdf

Hope this is helpful...


Linear-time algorithm for getting ends of diametral paths in special sequence of trees Recently in my research I have faced with the following subproblem:

  Given a tree $T, |V(T)| = n$ and its vertices are ordered $v_1, \ldots, v_n$ so that $T_i = T_{i-1} - v_i, 1 \le i \le n$ and $T_0 = T$ and every $T_i$ is a tree.

The question is:

  Is there any linear-time algorithm which gives $n$ pairs $v_{i_k}, v_{j_k}$, which are ends of a diametral path in $T_k$ for every $1 \le k \le n$ (any one if there are several ones)?

I think this algorithm can be useful for achieving linear-time recognition algorithms from explicit characterizations of various subclasses of trees.

ALSO, another way to think about it:

  Is there a data structure for a tree, such that we can insert a new leaf and query for a diametral path in amortized $O(1)$ time? (see comment by Chao Xu).

Ok,

I have an algorithm I believe is O(nlog*(n)), that's n log-star(n) (log-star n is constant for all practical purposes), but it's hard to prove and I suppose I could be wrong.  The running time guess comes from assuming the path compression step takes amortized O(log*(n)) as it does in a union-find data structure, but I don't remember the proof of that so I don't really know for certain that it applies here.  Nonetheless, I certainly can't generate any examples where the path-compression is generally slow and I can prove the other operations are amortized constant time.

Following Chao Xu's suggestion, I'll describe the "insert a new leaf" operation on the data structure.

Each vertex has to contain pointers to 4 other vertices in addition to remembering its depth.

Each vertex $v_i$ must remember:

$v_i$'s deepest descendant
$v_i$'s child on whose branch (1) is contained
$v_i$'s nearest ancestor $w_i$ for whom $w_i(2)$ is not an ancestor of $v_i$
Which child of $w_i$ is an ancestor of $v_i$

In fact for any given vertex (1), (3), and (4) may be outdated, but using path-compression we can bring it up to date in (hopefully) amortized O(log*n) running time using path-compression.

def get_deepest(v): # returns (1)
  if v.deepest == v:
    return v
  v.deepest = get_deepest(v.deepest)
  while True:
    deep_ancest,_ = get_nearest_ignoring_ancestor(v.deepest)
    if (not deep_ancest) or deep_ancest.depth <= v.depth:
      break
    v.deepest = get_deepest(deep_ancest)
  return v.deepest

def get_nearest_ignoring_ancestor(v): # returns tuple containing (3) and (4)
  if v.nia == None:
    return (None, root)
  elif v.nia.child_containing_deepest == v.nia_child_containing_self:
    v.nia,v.nia_child_containing_self = get_nearest_ignoring_ancestor(v.nia)
  return (v.nia, v.nia_child_containing_self)

Now when we add a new vertex $v$, we traverse upwards through each (3) updating the deepest vertex until we find one that doesn't update.  If we encounter a vertex $w$ which is on the primary path (this is easy to check because $w$.deepest() will be the same as root.deepest()), then we check if the path between the newly inserted node and the current deepest is longer than the currently known longest path.  Then that becomes the new diameter.  This check can be done in constant time since we know the depths of the current deepest, the newly inserted node, and also the node $w$ at which the paths pointing to the two diverge. Then the length (number edges in) the new path is just $d(v)+d(deepest)-2 d(w)$

It's easy to see that this algorithm is correct because any diameter must have an endpoint at the deepest node from the root (This is generally true of trees.  If you don't believe me you can verify it for yourself) and with every node we insert, we check that either

a) It's the deepest node (in which case, we've just increased the currently longest path by one)

OR

b) There exists an ancestor containing a deeper (or equal) node which is not on the deepest path (so the diameter can't have increased)

OR

c) We check the newly inserted node against the deepest node and compute the length of the new path to see if it's longer than the current longest.

To finish the Python pseudo-code for the algorithm:

#root is the root of the tree, it's parent is None
#cur_opp is the vertex currently farthest from get_deepest(root)

def add_node(v, parent):
  v.deepest = v
  v.child_containing_deepest = None
  v.nia = parent
  v.nia_child_containing_self = v

  root_deepest = get_deepest(root)

  while True:
    v_ancest,_ = get_nearest_ignoring_ancestor(v)
    if not v_ancest:
      check_update_path(root_deepest)
      break
    old_deepest = deepest(v_ancest)
    if v.depth > old_deepest.depth:
      old_deepest.nia = v_ancest
      old_deepest.nia_child_containing_self = v_ancest.child_containing_deepest
      v_ancest.child_containing_deepest = v.nia_child_containing_self
      v_ancest.deepest = v
      update_next = True
    else:
      break
  check_update_path(v)

def check_update_path(v):
  cur_deepest = get_deepest(root)
  if v == cur_deepest:
    return
  common = get_nearest_ignoring_ancestor(v)
  if get_deepest(common) != cur_deepest:
    return
  max_len = len_path(cur_opp, cur_deepest)
  new_len = len_path(v, cur_deepest)
  if new_len > max_len:
    cur_opp = v

def len_path(a,b):
  a_ancest = get_nearest_ignoring_ancestor(a)
  assert get_deepest(a_ancest) == b
  return a.depth + b.depth - 2 * a_ancest.depth

The longest path is just the path from cur_opp to get_deepest(root)

Now to show that the number of deepest-branch changes is amortized constant with each add, just imagine that each time we compare two depths and get d(a) == d(b) (when we stop), we reserve one time unit for later.  When a node changes deepest branches, the paths must have first been equal so we use up that time unit.

So now all that remains to prove is that the path-compression step is amortized fast and I unfortunately don't know how to do that.

Please note I haven't tested this code and it is almost certainly buggy.  Also, I may have left out some edge cases such as how to insert the first node or what to do in certain situations if a node already is on the primary path.  It shouldn't be too hard to account for these.


Finding sets of heavily intersecting objects, while minimizing their size Assume I have some array $a$ of length $n$.

If I place the elements contained in the array $a$ into a $\sqrt{n} \times \sqrt{n}$ matrix, then every row "intersects" with every column. That is, I cannot pick a row s.t. it will not intersect with all columns.
In addition, I can "reach" each element in the matrix via a column and via a row vector.
The row/column length is $\sqrt{n}$.

I'm not sure how to state this problem in more general terms or what would be a related field of research. Basically I am trying to find two sets $A$, $B$ of vectors/objects such that it holds that each element from $A$ intersects with all vectors from $B$ and in addition each element from $a$ should appear at least once in each set.

I was wondering whether the objects can be made even smaller by increasing the dimension to something bigger than 2.
For instance, for dimension 3 I could have one set of planes and one set of orthogonal vectors. For these two sets it holds that every element from one set will intersect with every element from the other set. However, when placing the elements from the array $a$ into such a 3 dimensional cube, I would have planes that are composed of $\sqrt[3]{n} \cdot \sqrt[3]{n}$ elements and $\sqrt[3]{n}$ sized vectors. Here, the sum of two objects from these two sets is bigger than in the matrix example.

I would like to minimize the total size of objects, one from each set for a given dimension.
What would be a related field of study to look at? Is dimension 2, i.e., the matrix already the best possible solution? If so, how would I show that?

If I understand right, you are interested in finite projective planes.  These are the maximum combinatoric set systems in which all sets intersect each other exactly once.  To briefly answer your question, you can "improve" your construction by getting up to $\Omega(n)$ sets of size $\Omega(n^{1/2})$ and still enforcing the property that any two sets intersect on exactly one element (note: this only works for certain $n$, e.g. $n$ = square of a prime).

I assume you have some unstated restriction on your sets that rules out the construction $\{1, 2\}, \{1, 3\}, \{1, 4\} ...$ in which case your sets have size two but all pairs intersect on exactly one element?


Does $\# \mathsf{P}\subseteq \mathsf{FP}^{\mathsf{PH}}$? The Toda's theorem is a relationship between two different complexity classes: $ \# \mathsf{P} $ and  $PH$. He proved that $ \mathsf{PH}\subseteq \mathsf{P}^{\#\mathsf{P}} $.

I wonder the following statement holds.

  $ $    $\#\mathsf{P} \subseteq \mathsf{FP}^{\mathsf{PH}}$

If we prove this statement, $\# \mathsf{P}$ and $\mathsf{PH}$, that is, counting and alternation are $roughly$ $equivalent$ classes.

If your statement holds, then the polynomial hierarchy collapses: $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{PH}}$ iff $\mathsf{\# P} \subseteq \mathsf{FP}^{\mathsf{\Sigma_k P}}$ for some fixed $k$ (by definition). But then by Toda's Theorem we have $\mathsf{PH} \subseteq \mathsf{P}^{\mathsf{\# P}} \subseteq \mathsf{P}^{\mathsf{FP}^{\mathsf{\Sigma_k P}}} = \mathsf{P}^{\mathsf{\Sigma_k P}} = \mathsf{\Delta_{k+1} P}$.


Maintaining multiple field dynamic values This question is posted on behalf of my friend, who is a networks engineer handling massive data (so not a toy problem). He needs to maintain a lookup/insertion/deletion structure storing nodes with multiple attributes. That is, there is a set of $k$ global properties, or key/value fields, where each node may maintain only a subset of them. E.g, $A$ is ($x=1$), $B$ is ($x=1$,$y=4$), $C$ is ($x=1$,$z=5$), where $x$, $y$, and $z$ are attributes. There should be no repetition of nodes, although one may be a subset of another in it's filled values. For example, here node $A$ is a subset of $B$.

The structure would initially be constructed from a large amount of nodes "on disk" (let us call this parameter $n$) in preprocessing and then would go in live query mode. Whenever a new query $Q$ comes in, the query $Q$ will also have between 1 to $k$ of the key/value pairs filled. The structure has to specify ALL matching nodes of the structure (e.g, $A(x=1)$, $B(y=4)$, $C(x=1,y=4)$ all would match $Q(x=1,y=4)$) and if $Q$ does not already exist in the structure, it has to be inserted. Given a query node, $Q$, a matching node $M$ is defined to be such that it's filled key-value pairs are a superset of those of $Q$

Which data structure would produce such a result in optimal insertion/lookup/deletion time, and of course, linear storage? Both amortized and worst case guarantees would be interesting, since this structure will handle a large number of queries. A link to relevant papers or literature would also help.

I thought about posting this on stackoverflow, but in this case the engineer is looking for a sound algorithm, not code, and preferably with theoretical performance guarantees. Apologies if it is fairly trivial for someone well-versed in data structures.

One possibility (that depends on the relative size of the attribute set and the record set) is to use an inverted index, which is a wildly successful structure for use in text searching. Rather than storing the documents and doing a search, you store a list of which documents contain which value of which attribute for each attribute value pair (again, this only works if the number of attribute-value pairs is not large). Then processing a query requires an intersection of the resulting lists.


Path replanning in path finding algorithms I'm working on a path finding algorithm for my thesis and I've gotten to a problem I need to solve where agents can replan their path if they need/have to. For example, if an agent is traversing across a corridor and then a barrier is inserted in, the agent has to replan because his old path is invalid. Another case is if the barrier already exists and the agent has to take a longer route, but while traveling, the barrier is removed and a significantly shorter route becomes available so the agent may replan but can still continue on his old path.

I have some ideas on how to work on the first case, but I'm at a loss for where to start for the second case. Does anyone know how other path planning algorithms deal with replanning, or can point me to any resources that can help me find some direction in tackling this problem?

The problem is known as the Canadian Traveler Problem.


A stronger multiplexing rule for soft linear logic? In (intuitionistic) linear logic the usual rules for the storage modality $!$ are promotion, dereliction, contraction, and weakening:

$$\frac{!\Gamma\vdash A}{!\Gamma\vdash !A}(prom) \qquad \frac{\Gamma,A \vdash C}{\Gamma,!A\vdash C}(der) \qquad \frac{\Gamma,!A,!A\vdash C}{\Gamma,!A\vdash C}(ctr) \qquad \frac{\Gamma\vdash C}{\Gamma,!A\vdash C}(wk)$$

Lafont's soft linear logic is obtained by observing that these rules are equivalent to soft promotion, multiplexing, and digging:

$$\frac{\Gamma\vdash A}{!\Gamma\vdash !A}(sp) \qquad \frac{\Gamma,\overbrace{A,\dots,A}^n\vdash C}{\Gamma,!A\vdash C}(mpx) \qquad \frac{\Gamma,!!A\vdash C}{\Gamma,!A\vdash C}(dig)$$

and then removing the digging rule.  Soft linear logic (SLL) is interesting because it corresponds closely to polynomial-time computation in various precise senses.  For instance, Lafont showed that polytime functions are precisely those representable in second-order SLL in a certain sense, while  McKinley showed that they are also those representable in a naive set theory based on SLL, and lambda calculi based on SLL can also characterize polytime computation (plus other complexity classes when augmented with additional features).

My question is what happens if in SLL we replace the multiplexing rule (which is actually a rule schema consisting of one rule for each external natural number $n$) with the following "strong multiplexing" or "weak contraction" rule?

$$\frac{\Gamma,!A,A\vdash C}{\Gamma,!A \vdash C}\qquad (*)$$

(and also weakening, which is a special case of ordinary multiplexing but not of $(*)$)

Ordinary contraction says that we can use $!A$ as two $!A$'s — hence any number of $!A$'s, and hence any number of $A$'s — while ordinary multiplexing says that we can use $!A$ as any number of $A$'s as long as we do it all at once.  So, for instance, if we have $!A$ and two branches of a derivation both need some $A$'s, then ordinary contraction says we can give them both a whole $!A$, while ordinary multiplexing says we need to decide right away before doing the branch how many $A$'s each branch needs.

The rule $(*)$ seems to be in between: it says that from $!A$ we can extract any number of $A$'s and keep the $!A$ around, but we can't get more than one $!A$.  So if we have $!A$ and two branches of a derivation both need some $A$'s, then we can give one of them a whole $!A$ but we need to decide right away how many $A$'s the other branch needs.

The question "what happens" is admittedly a bit vague, but it could be made precise in various ways.  Is rule $(*)$ conservative over ordinary multiplexing?  Is contraction conservative over rule $(*)$?  Does SLL+$(*)$ still correspond to polytime computation, in any or all of the ways that ordinary SLL does?  Or does it correspond to some larger complexity class?  I would be interested in answers to any of these questions.

(My reason for asking is partly curiosity, but also partly practical: it could be inconvenient for some purposes that ordinary multiplexing is a rule schema indexed by external natural numbers, whereas $(*)$ is a single rule.)

Your rule $(\ast)$ is sometimes referred to as "absorption".  I think the first who considered it was Jean-Marc Andreoli in his paper on focusing proofs. Indeed, it makes a lot of sense in proof search: read bottom-up, it says that when you have $?A$ (on the right), you may extract a copy of $A$ and try and do something with it, while keeping $?A$ for future use.

Of course, as you know, absorption plus weakening and promotion (the usual one, i.e., functoriality of $!(-)$ + comonad comultiplication) gives a system equivalent to full linear logic.  You are asking about the system obtained by also taking promotion to be strictly functorial (what Lafont calls "soft promotion").  Let me call it $\mathbf{PL}^-$, for reasons I'll clarify momentarily.

As you rightly observe, $\mathbf{PL}^-$ is much more powerful than $\mathbf{SLL}$.  Indeed, and this is essentially a computational reformulation of your answer, the untyped term calculus underlying $\mathbf{PL}^-$ is Turing-complete, whereas the untyped calculus underying $\mathbf{SLL}$ has exactly the same expressiveness as $\mathbf{SLL}$: its terms strongly normalize in $O(s^d)$ steps, where $s$ is the size and $d$ the exponential depth of the term being normalized (this is the key feature of so-called "light" logics: their normalization does not rely on the logical complexity of formulas.  Types/formulas are there only to ensure that the normal forms are of a prescribed shape: integers, strings, booleans, etc.).

Now I must apologize for invoking my own work, but it is truly relevant to your question: $\mathbf{PL}^-$ is actually the intersection of linear logic and a system I call parsimonious logic ($\mathbf{PL}$), which is a variant of linear logic based on the the fact that the exponential modality obeys the isomorphism

$$!A \cong (A\&1)\,\otimes\,!A$$

and nothing more (except functoriality, of course). With Kazushige Terui, we refer to this iso as Milner's law, because of its similarity with the structural equality $!P\equiv P\mathrel{|}\,!P$ in the $\pi$-calculus (especially if one considers the affine version of parsimonious logic, which is most frequent in applications). Milner's law does not hold in $\mathbf{LL}$, so $\mathbf{PL}$ is not a subsystem of linear logic. On the other hand, the $!(-)$ of linear logic is a comonad and has contraction, which is not the case in $\mathbf{PL}$, so this latter is not a supersystem of $\mathbf{LL}$. Categorically, a model of $\mathbf{PL}$ is just a SMCC with products (in fact, free copointed objects suffice) and with a monoidal endofunctor $!(-)$ satisfying Milner's law (naturally in $A$). Comparatively, models of $\mathbf{LL}$ are much more complex to describe.

As you see, the implication from left to right of Milner's law gives you precisely weakening and absorption (composing with the projections of $\&$, which is the product as usual). So the system you are asking about is $\mathbf{PL}$ with only "half" of Milner's law, and in fact $\mathbf{PL}^-=\mathbf{PL}\cap\mathbf{LL}$.

Not unlike $\mathbf{SLL}$, it turns out that $\mathbf{PL}$ has quite interesting complexity properties. However, quite unlike $\mathbf{SLL}$ and Girard's light linear logic, complexity is not controlled by the structure of the logical rules (they are Turing-complete) but by the types: simply-typed $\mathbf{PL}$ captures $\mathsf L$ (deterministic logspace), whereas $\mathbf{PL}$ with linear polymorphism (i.e., where the $X$ in $\forall X.A$ may only be instantiated with a $!$-free formula) captures $\mathsf P$ (deterministic polytime). I also conjecture that "parsimonious system F" ($\mathbf{PL}$ with full polymorphism) captures primitive recursion. When I say "captures" above I mean that one defines types $\mathsf{Str}$ of binary strings and $\mathsf{Bool}$ of booleans (more or less as usual) and looks at the class of problems decidable by terms of type $\mathsf{Str}\multimap\mathsf{Bool}$ (or instantiations of them when polymorphism is absent/limited).

The side of Milner's law that's missing from $\mathbf{PL}^-$ is necessary for the completeness with respect to logspace and polytime (for instance, without it you cannot type the predecessor with simple types $\mathsf{Nat}\multimap\mathsf{Nat}$). So simply-typed (resp. linear polymorphic) $\mathbf{PL}^-$ does not correspond to any class I know of: you will only be able to solve logspace (resp. polytime) problems in it, but you'll be missing some of those. However, when you have full second order (or when you are untyped), $\mathbf{PL}^-$ seems to be (is) just as expressive as $\mathbf{PL}$. In particular, one may play around with "parsimonious OCaml", which is a (fictional, I haven't implemented it :-) ) variant of OCaml following the type discipline prescribed by $\mathbf{PL}^-$. The funny thing about such a language is that it does not have general fixpoints, only linear fixpoints: when you write

$$\mathtt{letrec}\ \mathtt f\ \mathtt x = \mathtt{code}$$

$\mathtt{code}$ may only contain one occurrence of $\mathtt f$ (in every branch of an $\mathtt{if\ldots then\ldots else}$ statement). Since while loops are exactly linear (tail) recursions, parsimonious Ocaml is Turing-complete. However, there's lots of "natural" OCaml programs you'll have to non-trivially rewrite for them to run in parsimonious OCaml! (Pretty much every structural recursion on binary trees for example).  In a sense that I would like (but don't know how) to make precise, parsimonious logic (and hence the logic you are asking about) is the "logic of while loops". I think that this is the ultimate reason why it behaves so well from the complexity viewpoint.

I'm going to stop here and give you some pointers, in case you are more curious. There is a series of papers (by myself and co-authors) on parsimonious logic and complexity, all available on my web page. However, things are a bit scattered here and there and I think that the most readable account is in Chapter 3 of my habilitation thesis, so I suggest you go there instead.


Zero error randomized communication complexity vs deterministic communication complexity It is known that for $\Theta(1)$ error the worst case definition of randomized communication complexity and average case definition are equivalent. But when the error is $0$, the worst case randomized communication complexity is same as deterministic communication complexity.

Is any function known to have super-constant deterministic communication complexity but constant zero error randomized communication complexity?

More generally, what is a witness function that separates deterministic communication complexity and zero-error randomized communication complexity?

Any help is appreciated.

Indeed, for distjointness of sets of size $\log(n)$ out of $n$ items, it is known that
the $0$-error randomized communication complexity is $\Theta(\log n)$, while the deterministic
complexity is $\Theta(\log^2 n)$.

Recall that there can be at most a quadratic gap since the $0$-error randomized complexity is bounded from below by the non-deterministic and co-non-deterministic complexities.

See: http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf


Unification-based elimination rule for equality A few years back, I ran across the following left-rule for equality in sequent calculus:

$$
\frac{s \doteq t \leadsto \theta \qquad
       \theta(\Gamma) \vdash \theta(C)}
     {\Gamma, s \doteq t \vdash C}
$$

Here, $s \doteq t \leadsto \theta$ computes the most general unifier $\theta$ for $s$ and $t$, and then applies the substition to the conclusion $C$ and all the hypotheses in the context $\Gamma$.

The interesting thing about this unification is that it equates finds a substitution for universal (i.e., skolem) variables.

However, I cannot remember where I read this, and was wondering if anyone could help me find a reference to it.

I've often attributed this to Rules of definitional reflection by Schroeder-Heister, though the idea goes back beyond that to Girard and others; the rule you're looking for is an instance of the first display in Section 4. You also, however, need a rule that says that if the unification instance is unsatisfiable, then the assumption of equality has the force of a contradiction.

A more general account has been used recently in a lot of work by Dale Miller, David Baelde, and company (see, for instance, Least and greatest fixed points in linear logic). The more general formulation - which also doesn't originate with Miller et al - is that the rule is

$${\{\theta \in {\sf csu}(t,s) \mid \theta\Gamma \vdash \theta{C} \}}\over{\Gamma, t \doteq s \vdash C}$$

where ${\sf csu}(t,s)$ is the complete set of unifiers - the set of all unifying substitutions of $t$ and $s$. You might also prefer the equivalent way of writing this rule that I prefer (see here for example).

$${\forall \theta. \theta{t} = \theta{s} \longrightarrow \theta\Gamma \vdash \theta{C}}\over{\Gamma, t \doteq s \vdash C}$$

In any case, in a term language with decidable unification where the existence of a unifier implies the existence of a most general unifier, having either of these rules above can be shown to be equivalent to having these two rules:

$$
{{{\sf no~mgu}(t,s)}\over{\Gamma, t \doteq s \vdash C}}
\qquad
{{{\sf mgu}(t,s) = \theta \quad \theta\Gamma \vdash \theta{C}}\over{\Gamma, t \doteq s \vdash C}}
$$

(P.S. Frank discussed this in his logic programming course in lectures 6, 7, and 8, which may be where you remember it from.)


Are there PPAD-complete puzzles? Most puzzles that you can buy are in P, NP-complete (like Sudoku) or PSPACE-complete (like Sokoban), at least if you scale them up.
Are there any natural puzzles that are PPAD-complete?
What about other similar classes, like PPA, PPADS etc?

If we don't insist on natural, then of course practically any PPAD-complete problem would be a puzzle, just during the puzzle you would need to run the some Turing machine a couple of times.
What I have in mind would be for example finding another Hamiltonian cycle in a cubic graph, which is known to be in PPA, just now known to be complete.

In the most authoritative reference on PPAD-complete problems, there is no PPAD-complete puzzle mentioned.