Version control for collaboration (with word-level diffs)? Most papers are now written collaboratively, and collaborators are often located in different places.  I have always used version control systems for my documents and code, and have also found version control critical for collaborative software projects, but it seems many researchers in theory avoid their use for writing joint papers.  To convince my collaborators that version control (revision control) is a good idea for working together, there seem to be some prerequisites.  It is not possible to force everyone to worry about a specific set of conventions for line breaks and paragraphs, or to avoid tab/space conversions.

  Does someone offer free hosting of small shared document repositories, with text-document-friendly version control that can handle word-level diffs (not line-based)?

If not, then I would welcome other suggestions that are based on experience (let's avoid speculation, please).

I was thinking of Git, Subversion, Mercurial, darcs, or Bazaar, set up to handle word-level differences with wdiff, together with a simple way of setting up access secured by public keys (for instance via ssh).  However, none of the version control providers that I looked at seem to offer anything like this.  For scientific collaboration the "enterprise" features stressed by many of these companies are not very important (lots of branches, integration with trac, auditing by third parties, hierarchical project teams).  But word-level diffs seem critical yet unsupported.  In my experience, with line-level diffs for text files, everyone has to avoid reformatting paragraphs and editors that change tabs to spaces or vice versa cause problems; there also seem to be many spurious edit conflicts.  I have used wdiff and latexdiff quite successfully to help with manual merging of changes previously, so I am hoping a word-level diff would reduce such problems.

See related question at MO about tools for collaboration, and related questions over at TeX.SE, about version control for LaTeX documents and LaTeX packages for version control.  See also the SVN Hosting Comparison Review Chart for a large list of hosting providers, for just one of the main version control systems.

Edit: Jukka Suomela's answer to the TeX.SE question "Best LaTeX-aware diff and merge tools for subversion" seems to be the best suggestion so far, covering how to interpret the deltas on a word level.  Moreover, Jukka has explained how the differences between successive versions on the repository end are separate from the user-level differences used for conflict detection and merging of changes.  Jukka's answer at TeX.SE explicitly excludes simultaneous edits and merging, relying instead on the traditional atomic edit token to avoid edit conflicts.  Clarifying (and modifying) my original question, is there a way to ensure that edit conflicts can be resolved on a word difference basis, rather than on a line difference basis?  In other words, can wdiff or similar tools be integrated into the conflict detection part of the version control tools, similar to the way end-of-line differences and differences in whitespace can be ignored?

I've used git to collaborate on some documents written in latex. You'll have to adhere to some rules:

Start each sentence on a new line, latex ignores these newlines as long as there is no blank line
Use the same configuration for formatting (tab/spaces/max text width)
For best results, create a .gitattributes file in your repository and add the line *.tex    diff=tex. This makes diff aware of the tex syntax and leads to more meaningful output.

You can then use git diff --color-words and gitk --color-words to see word differences (also see this article Word-by-word diffs in Git on how to configure git to always use word-diff algorithm for displaying the git diff/git log).

To reduce the manual merges, I can recommend using separate files for sections and subsections (depending on the size of your document).


System F and System T names Does anyone know where do the names System "F" and System "T" comes from? I am not asking who introduced those names (Girard System F, and Gödel System T), but what the "F" and the "T" means.

I posted this to TYPES, but its probably worth copying here as well:

In "The system F of variable types, fifteen years later", Girard
remarks  that there was no particular reason for the name F:

  However, in [3] it was shown that the obvious rules of conversion for
   this system, called F by chance, were converging.

There may be another explanation in his thesis, but I haven't read it
since unfortunately I am not fluent in French.
However, since I am semi-literate in German, I did take a look at
Gödel's paper "Über eine noch nicht benüzte Erweiterung des finiten
Standpunktes", where System T (and the Dialectia interpretation for it)
was introduced. He names this system in a parenthetical aside:

  Das heisst die Axiome dieses Systems (es werde T genannt) sind formal
  fast dieselben wie die der primitiv rekursiven Zahlentheorie [...][1]

However, the previous page and a half were spent talking about the type
structure of system T, so it is reasonable to guess that T stands for
"types". But, no explicit reason is given in print.

[1] "This means the axioms of this system (dubbed T) are nearly
the same as those of primitive recursive number theory [...]"


Branch prediction in quantum algorithms Are there any good examples of branching efficiency / prediction in quantum algorihms? Specifically suppose I have a set of CNOT gates one after the other that have the control line on the same line as the output of the CNOT gate?

I agree with Artem, but perhaps this paper on a quantum circuit model for constructing conditional statements may be of some relevance to what you are trying to figure out.


Lower Bounds for Frege and Extended Frege Wikipedia [1] states that the best known lower bound for size of Frege proofs is quadratic, and that there is no known superlinear lower bounds for the number of lines of Frege proofs.

Questions:

1) What is the best known lower bound for the number of lines of extended Frege proofs?

2) What is the best known lower bound for the size of extended Frege proofs? Is it still quadratic as in Frege?

3) Tree-like Extended Frege can simulate DAG-like Extended Frege in a polynomial number of steps. Are there any superlinear lower bounds for size/number of lines on tree-like extended Frege?

4) What are the tautologies that lead to the linear lower bound for number of lines and to the quadratic lower bound for the size in Frege proofs as stated at wikipedia?

Obs: I'm aware of the fact that for constant depth Frege we have size lower bounds of the order of $2^{\Omega(n^{6^{-d}})}$. But I'm really interested in full power Frege and Extended Frege.

[1] https://en.wikipedia.org/wiki/Frege_system

1, 2, 4) The best known lower bounds on extended Frege are the same as for Frege: linear number of lines, and quadratic size. This applies e.g. to the tautologies $\neg^{2n}\top$ (basically, any tautology that is not a substitution instance of a shorter tautology, and whose sum of lengths of all subformulas is quadratic). This is proved in Krajíček’s Bounded arithmetic, propositional logic, and complexity theory for Frege systems, but the argument works for extended Frege systems as well.

3) It’s not entirely clear to me how exactly you define tree-like extended Frege (there has to be a mechanism allowing reuse of extension axioms), but I am not aware of any superlinear lower bounds on the number of lines in treelike Frege or extended Frege systems.


Good resources to learn loopy belief propagation What are some of the good references to understand loopy belief propagation and the need for it? I am looking for both theory and applications (for instance in coding/information and learning theory).

The following tech-report (a simplified version of an earlier paper by the same authors) on general BP (not only loopy-BP), but has fantastic insights.
It's a great place to start, if you already haven't.

http://www.merl.com/publications/docs/TR2001-22.pdf

Another good place is this book:
Information, Physics, and Computation - by Mezard and Montanari.


Partitioning a set of 2d polygons into intersection-connected subsets My question is given a set of 2d polygons how can I find the connected components of polygons according to a criteria based on intersection or proximity of them.

In other words I have a set of polygons. I want to group them into subsets where each polygon has at least one intersection with (one or more) other polygon(s) of the subset and no intersections with any other polygon in a different subset.
So if I have S = {A, B, C, D} and A intersects C and C intersects D the resulting partitions are: P1 = {A, C, D} and P2 = {B}.

I don't have any problems with an good approximate solution if its fast and doesn't generate false negatives (i.e. no (potential) intersection is lost).

I don't need to actually calculate the intersections just determine if they intersect.

In my case the polygons are complex but if a known answer only works for concave or simple polygons I would still like to know about  it!

I am actually not sure how to phrase this question which may account for my lack of findings of relevant papers.

What you want is to find the connected components of the intersection graph of the polygons, right? It would help to be more clear about what counts as an intersection: do the boundaries have to cross or does one polygon entirely inside another count as an intersection? And can the polygons have holes?

Regardless, a natural lower bound for running times for the problem is $\Omega(n^{4/3})$ where $n$ is the total number of segments in the input. Any faster and we could also improve the known time bounds for Hopcroft's problem of detecting an intersection between $n$ given points and $n$ given lines: expand each point into a small polygon (not so large that it intersects any line it didn't before) and test whether any of these expanded points belongs to a nontrivial connected component. This lower bound is mentioned briefly in my paper "Testing Bipartiteness of Geometric Intersection Graphs" which uses it to argue that bipartiteness of intersection graphs is strictly easier than connectivity; it in turn cites Jeff Erickson's paper "New lower bounds for Hopcroft’s problem", which proves an $\Omega(n^{4/3})$ lower bound in a reasonable but limited model of computation.


Probability that a random sorting network works Given $n$ inputs $x_0, \ldots, x_{n-1}$, we construct a random sorting network with $m$ gates by iteratively picking two variables $x_i, x_j$ with $i < j$ and adding a comparator gate that swaps them if $x_i > x_j$.

Question 1: For fixed $n$, how large must $m$ be for the network to correctly sort with probability $> \frac{1}{2}$?

We have at least the lower bound $m = \Omega(n^2 \log n)$ since an input that is correctly sorted except that each consecutive pair is swapped will take $\Theta(n^2 \log n^2)$ time for each pair to be chosen as a comparator.  Is that also the upper bound, possibly with more $\log n$ factors?

Question 2: Is there a distribution of comparator gates that achieves $m = \tilde{O}(n)$, perhaps by choosing close comparators with higher probability?

Here's some empirical data for question 2, based on D.W.'s idea applied to bitonic sort.  For $n$ variables, choose $j - i = 2^k$ with probability proportional to $\lg n - k$, then select $i$ uniformly at random to get a comparator $(i,j)$.  This matches the distribution of comparators in bitonic sort if $n$ is a power of 2, and approximates it otherwise.

For a given infinite sequence of gates pulled from this distribution, we can approximate the number of gates required to get a sorting network by sorting many random bit sequences.  Here's that estimate for $n < 200$ taking the mean over $100$ gate sequences with $6400$ bit sequences used to approximate the count:

It appears to match $\Theta(n \log^2 n)$, the same complexity as bitonic sort.  If so, we don't eat an extra $\log n$ factor due to the coupon collector problem of coming across each gate.

To emphasize: I'm using only $6400$ bit sequences to approximate the expected number of gates, not $2^n$.  The mean required gates does rise with that number: for $n = 199$ if I use $6400$, $64000$, and $
640000$ sequences the estimates are $14270 \pm 1069$, $14353 \pm 1013$, and $14539 \pm 965$.  Thus, it's possible getting the last few sequences increases the asymptotic complexity, though intuitively it feels unlikely.

Edit: Here's a similar plot up to $n = 80$, but using the exact number of gates (computed via a combination of sampling and Z3).  I've switched from power of two $d = j-i$ to arbitrary $d \in [1,\frac{n}{2}]$ with probability proportional to $\frac{\log n - \log d}{d}$.  $\Theta(n \log^2 n)$ still looks plausible.


How would I go about learning the underlying theory of the Coq proof assistant? I'm going over the course notes at CIS 500: Software Foundations and the exercises are a lot of fun. I'm only at the third exercise set but I would like to know more about what's happening when I use tactics to prove things like forall (n m : nat), n + n = m + m -> n = m.

One place to start is  the Coq reference manual (pdf). Chapter 4 describes the underlying logic of Coq, and ultimately everything is based on this. It's called the calculus of (co)inductive constructions, and many  papers describe. Getting your hands on the Coq'Art book Interactive Theorem Proving and Program Development provides a more leisurely but not cheap introduction to Coq.

To learn about how tactics work, have a look at this earlier question: How do 'tactics' work in proof assistants?

To build up the required theory, you need to learn about Type Theory. Most closely related to the theory underlying a proof assistant is probably Per Martin-Löf's Intutionistic Type Theory notes (or book) or the book Programming in Martin-Löf Type Theory, which is really about writing and proving theorems in type theory. A programming language perspective on type theory can be obtained from Pierce's Types and Programming Languages. Girard et al's Proofs and Types, which also addresses the importance of the Curry-Howard Correspondence, is another excellent reference.
Then you are probably well and truly ready to read Coquand and Huet's The Calculus of Constructions. Finally chase up some of the references in the back of the Coq manual.

There are other proof assistants, HOL, NuPRL, Mizar, Twelf, etc., and they have their theory too, so you can learn a lot too by reading in that direction.

Finally, for an overview of the history and future of proof assistants, check out the recent article by Herman Geuvers.


Parallel (NC) replacements for Gaussian elimination? Suppose one has an matrix $A$ with $c$ columns and $r$ rows with entries in the binary field $GF(2)$. One wants to determine

its rank, and
a basis for its null-space.

These can be computed easily in time $O(r^2 c)$ by Gauss elimination, but that is a very sequential algorithm.

Are there deterministic parallel (NC, polylogarithmic time, polynomial space) algorithms to compute these?

One may be able to assume that either $r$ or $c$ is small (maybe polylogarithmic) if it helps.

Yes, it is in $\mathsf{NC}^2$:

  Mulmuley, K. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7 (1987), no. 1, 101–104.

The following (earlier) paper shows that solving a system of linear equations reduces to computing the rank, and thus, together with the above result, solving the system (in particular, finding a basis for the nullspace) is also in $\mathsf{NC}^2$:

  Allan Borodin, Joachim von zur Gathen, John Hopcroft. Fast parallel matrix and GCD computations. Information and Control 52(3):241-25, 1982.


How/Why are linear systems so crucial to computer science? I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network flows, edge/vertex cover, travelling salesman etc.) I know that some of them are NP-hard, but the point being that they can be 'framed as a linear program' if not solved optimally.

That got me thinking: We've always been taught systems of linear equations, linear algebra all throughout school/college. And seeing the power of LPs for expressing various algorithms it's kinda fascinating.

Question: Although we have non-linear systems prevalent all around us how/why are linear systems so crucial to computer science? I do understand that they help simplify the understanding and are computationally tractable most of the times but is that it? How good is this 'approximation'? Are we over-simplifying and are the results still meaningful in practice? Or is it just 'nature' i.e. the problems that are the most fascinating are indeed simply linear?

Would it be safe to safe that 'linear algebra/equations/programming' are of the corner stones of CS? If not then what would be a good contradiction? How often do we deal with non-linear stuff (I don't necessarily mean theoretically but also from a 'solveability' standpoint i.e. just saying it's NP doesn't cut it; there should be a good approximation to the problem and would it land up being linear?)

The premise of the question is a little flawed: there are many who would argue that quadratics are the real "boundary" for tractability and modelling, since least-squares problems are almost as 'easy' as linear problems. There are others who'd argue that convexity (or even submodularity in certain cases) is the boundary for tractability.

Perhaps what is more relevant is "why do linear systems admit tractable solutions ?" which is not exactly what you asked, but is related. One perspective on this is composability. Since the defining property of a linear system is that $f(x + y) = f(x) + f(y)$, this imparts a kind of "memorylessness" to the system. To build up a solution to a problem I can focus on individual pieces and combine them with no penalty. Indeed, the premise of most algorithms for flow is precisely that.

This memorylessness imparts efficiency: I can break things into pieces, or work iteratively, and I don't lose by virtue of doing so. I can still make bad decisions (c.f. greedy algorithms) but the act of splitting things up itself doesn't hurt me.

This is one reason why linearity has such power. There are probably many others.


Counting distinct set covers I'm given a universal set $N = \{1, 2, \dots, n\}$, a family of sets $\mathcal{F} = \{ S_1, S_2, \dots, S_m \}$, $S_i \subseteq N$, and I need to count the number of distinct ways to cover the universal set using sets from $\mathcal{F}$.

I've found a couple of articles describing the usage of inclusion-exclusion principle to tackle a similar problem:

Set partitioning via inclusion-exclusion
Dynamic programming based algorithms for set multicover and multiset multicover problems

The papers describe how to compute the number of $k$-covers $c_k$. A $k$-cover is a tuple $(S_1, \dots, S_k)$ over $\mathcal{F}$ such that $S_1 \cup \dots \cup S_k = N$. According to the papers,
$$c_k(\mathcal{F}) = \sum_{X \subseteq N} (-1)^{|X|} a(X)^k$$ where
$a(X) = |\{S \in \mathcal{F} \mid S \cap X = \emptyset\}|$ (the number of sets in $\mathcal{F}$ that avoid $X$).

I like this method because it (at least, theoretically) allows to compute the number of covers in $O(n 2^n)$ time. A simple DP approach I can think of requires $O(|\mathcal{F}| 2^n)$ time and is too expensive since in my case $|\mathcal{F}|$ is slightly less than $2^n$.

I tried this formula on a simple example $\mathcal{F} = \{ \{1\}, \{2\}, \{1, 2\}\}$

$$
\begin{array}{c|c|r}
X & a(X) & (-1)^{|X|} \\
\hline
\emptyset & 3 & 1 \\
\{1\} & 1 & -1 \\
\{2\} & 1 & -1  \\
\{1, 2\} & 0 & 1
\end{array}
$$
$$
\begin{array}{c|c|c|c}
k & c_k(\mathcal{F}) & c_k \text{(computed)} & \text{Number of covers} \\
\hline
1 & 3 - 1 - 1 + 0 & 1 & 1\\
2 & 3^2 - 1^2 - 1^2 + 0 & 7 & 3 \\
3 & 3^3 - 1^3 - 1^3 + 0 & 25 & 1  \\
\end{array}
$$

I don't know how to interpret the values of $c_k$ I've got. They look really strange. Is this method correct? Or is there a simpler way to count set covers in $O(n 2^n)$ time?

Thanks to Andreas Björklund, I realized that $c_k$ is the number of all tuples with repetitions. I reread the article carefully and reformulated the problem in the following way:

Let $B = 2^{\mathcal{F}}$, $A_i = \{S \in 2^\mathcal{F} \mid S \cap \{i\} = \emptyset \}$ (i.e. set of all subsets of $\mathcal{F}$ that avoid singleton set $\{i\}$), and $C(\mathcal{F})$ is the number of distinct covers of $\mathcal{F}$. Then from the inclusion-exclusion principle we have:
$$C(\mathcal{F}) = \sum_{X \subseteq N} (-1)^{|X|} 2^{a(X)}$$
As before, $a(X)$ stands for the number of sets in $\mathcal{F}$ that avoid all of $X$.

I've tested this formula on a couple of examples, and it works like a charm. For the simple example from the question above we have:
$$2^3 - 2^1 - 2^1 + 2^0 = 5$$


Verifying unique solutions of SAT Consider the following problem: given a CNF formula and an assignment that satisfies this formula, is there another satisfying assignment for this formula ?

What is the complexity of this problem ? (It most surely is in NP, but is it also NP-hard ?)

What if you are not given the assignment and you just want do decide whether the formula has a unique satisfying assignment ?

Thanks.

The problem of deciding whether a given CNF formula has a satisfying assignment other than a given one is easily shown to be NP-complete by transforming a CNF formula to add one trivial solution.  This problem is called the “Another Solution Problem (ASP) of SAT” in [YS03], where it is used to give a systematic proof that (the decision versions of) the ASPs of many other problems are also NP-complete.

The problem of deciding whether a given CNF formula has a unique satisfying assignment or not (so you have to answer “no” if the formula has no satisfying assignments or more than one satisfying assignment) is US-complete.  US contains both UP and coNP.

References

[YS03] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.

Edit: An earlier version (revision 1) of this answer contained a confusion between the decision version and the search version.  It has been fixed.


Cayley subgraph isomorphism and complexity of linear subcode decision Let $G$ be an undirected Cayley graph over an abelian group. Let $H$ a regular graph whose independence number and chromatic number are known. Let $inj(G,H)$ be the number of injective homomorphisms from $G$ to $H$. It is known SUBGRAPH ISOMORPHISM is NP-complete. Consider the CAYLEY SUBGRAPH ISOMORPHISM problem:

Given an undirected Cayley $G$ and a regular $H$, is inj(G,H)>0?

Is the above problem NP-complete?

Since linear codes are abelian, I am extending the question. Given two $[n_i,k_i,d_i]$ linear codes $C_i$ for $i=1$ and $2$ and $n_1<n_2$, is deciding $C_1\cong D \subset C_2$ NP-complete? Note that code isomrphism is similar to graph isomorphism.

For your first question: yes, it is NP-complete. The complete graph is the Cayley graph of any group, if you take the entire group (say, except the identity, but that would just add a self-loop at every vertex) as the generating set. Then CLIQUE is a particular instance of your problem.

A more interesting question might be to restrict Cayley subgraph isomorphism to Cayley graphs where only a minimal, or say $O(\log|G|)$-sized, generating set is used.

For your second question, the answer is also yes, because not only is Code Equivalence similar to Graph Isomorphism, but GI reduces to Code Equivalence. Essentially the same reduction (due to Petrank and Roth) gives a reduction from Subgraph Isomorphism to Subcode Equivalence.


Entropy-like quantity For $p\in[0,1]^{\mathbb{N}}$ and $\alpha\ge1$, define
$$ H_\alpha(p) = \sum_{i\in\mathbb{N}}p_i|\log(p_i)|^\alpha.
$$
When $\sum_i p_i=1$ and $\alpha=1$, $H_1(p)$ is just the Shannon entropy of the distribution $p$. Has anyone encountered the object $H_\alpha$ anywhere in the literature? A reference would be much appreciated. I'm thinking of calling $H_\alpha$ hyperentropy for $\alpha>1$; is that term already taken by chance?

It's the $\alpha^{\mathrm{th}}$ moment of the Tribus surprisal.
This generalizes the statement that entropy = expected surprisal.
Or in Ross's textbook, "expected surprise".


O(N) leader election on torus with orientation and non-positional identity I'm really confused by this. Apparently there is a deterministic algorithm that does leader election on a torus with orientation and non-positional identity using only O(N) messages.  I'm unable to find to find any description of this algorithm, and I still don't understand how it is even possible.

On a general graph with sense of direction you should be able to do leader election using O(N log N) messages.  On complete graphs with sense of direction you do it with O(N) messages, because you have constant (1 message) communication with distant nodes.  But how could you do that on a torus?

Here are some relevant details: The system is asynchronous.  All processes start simultaneously.  Each node has a "sense of direction"; that is, each node knows which of its neighbors are north, east, south, or west.  Finally, each node has a unique ID (not related to its position in the torus).

The idea is growing territories. That is, a candidate broadcast to neighbors that are $\alpha^i$ away in iterations.

The trick is in the analysis! (so it s not really clear) -- by getting to know the worst case of candidates, and the number of messages they send + setting $\alpha$ to a certain constant - we get $O(n)$

The solution can be found in N. Santoro book in Chapter 3 (oriented torus)


Are the problems PRIMES, FACTORING known to be P-hard? Let PRIMES (a.k.a. primality testing) be the problem:

  Given a natural number $n$, is $n$ a prime number?

Let FACTORING be the problem:

  Given natural numbers $n$, $m$ with $1 \leq m \leq n$, does $n$ have a factor $d$ with $1 < d < m$?

Is it known whether PRIMES is P-hard? How about FACTORING?
What are the best known lowerbounds for these problems?

PRIMES is known to be hard for $\mathsf{TC^0}$.  See my paper with Saks and Shparlinski, "A Lower Bound for Primality" in JCSS 62 (2001).  No improvement on that front since then.


About switching from a computer scientist to a mathematician What is the possibility for a computer scientist to change his field into a pure mathematician ? and what's the most smooth way to do it ? any examples for people who could make it ?

Theoretical computer scientists are already mathematicians.  So you don't need to do anything!

Your later comment suggests that you're really asking about changing from one area of mathematics (like complexity theory) to another (like functional analysis).  The only way to do it is to just do it.  You want to be an analyst?  Great!  Just start doing analysis!  Read analysis books and papers, solve analysis problems, talk to lots of analyst faculty and students, attend analysis seminars, go to analysis conferences, ask analysis questions on MathOverflow, and so on.  Act like an analyst long enough (and well enough) and you'll become one.

In that respect, becoming a functional analyst is not so different from becoming anything else.  Want to be a programmer?  Program!  Want to be a writer?  Write!  Want to be a painter?  Paint!  Want to be a functional analyst?  Analyze functions!  (Meanwhile, don't forget to earn enough money to eat, and do not blow off the stupid administrative hurdles.)

And yes, lots of people successfully change fields/careers.  For example, Joan Birman started her academic career in physics, worked for several years as a systems analyst in the aircraft industry, spent several more years at home raising kids, went back to grad school in mathematics in her 40s, and became one of the most influential researchers in modern low-dimensional topology and geometric group theory.  For other examples, see these questions on MathOverflow.

One last suggestion: You might find the transition somewhat smoother (possibly even real-analytic) if you drop your prejudices about "pure" versus "applied" mathematics.  Forget about the labels; just do the work.


Most important new papers in computational complexity We often hear about classic research and publications in the field of computational complexity (Turing, Cook, Karp, Hartmanis, Razborov etc). I was wondering if there are recently published papers considered seminal and a must read. By recent I mean in the last 5/10 years.

The recent paper of László Babai showing that Graph Isomorphism is in Quasi-P is already a classic.

Here is a more accessible exposition of the result published in the ICM 2018 proceedings.


When does a bipartite graph have bounded treewidth? As the title says, I want to know when the treewidth of a bipartite graph is bounded by a constant. What families of graphs are both bipartite and bounded treewidth?
More generally, I would like to find a property $P$ such that for any bipartite graph $G$ the following statement is true: "the treewidth of $G$ is bound by a constant if and only if $G$ satisfies property $P$."

I think there is no simpler characterization than just the fact that the treewidth of $G$ is bounded. The intuition for why is that by subdividing each edge of a graph we get a bipartite graph with the same treewidth. In particular, we have a very simple reduction from determining the treewidth of a graph to determining the treewidth of a bipartite graph.


What would a quantum computer architecture look like? More specifically, assuming we manage to make an efficient quantum switch, some kind of "quansistor"(quantum transistor) and manage to resolve the problem of joining a bunch of them together without losing the quantum properties that we want, where in a modern computer would these quansistors come in to create a quantum computer? As in would the entire computer be made of quansistors? or would only some parts be quansistors and the rest be standard eletronics. would the logic of the processor(the ALU and such...) be made with quansistors? would the storage? down to what level? just the registers or the RAM too? I imagine that having the part of the storage that stores the instructions of the running program be affected by the randomness of quantum behaviour would cause some problems. Really my question comes down to where in the standard computer processing pipeline does the quantumness come in, in order to produce the intended theoretical behaviour of quantum computer?

Really my question comes down to where in the standard computer processing pipeline does the quantumness come in, in order to produce the intended theoretical behaviour of quantum computer?

The critical part to get the intended theoretical (scaling) behaviour of quantum computer is probably to achieve and maintain the coherence between the different qubits in the computer.

Let me illustrate this with a hypothetical architecture. Assume that you have ready made modules with a fixed number of qubits (say 49=7x7). Further assume that each module for itself is able to maintain coherence between its qubits (by using quantum error correction), and reliably operate on its qubits controlled by a classical computer (my mental model is similar to this simple model of a finite quantum coprocessor I asked about before, but it doesn't really matter for this illustration1).

Now assume that you scale your quantum computer by putting many of those modules together, using some suitable topology. The modules cannot talk directly to each other, but we may assume that the classical computer controlling those modules is able to freeze any quantum operation of the modules and then permute qubits between those modules according to the topology.

Now assume that the quantum operation of each module randomly changes its global phase in a way uncontrollable and unmeasurable by the controlling classical computer. This is not even true decoherence (as would occur in practice - the density matrix formalism could be used for a better model), but I guess it will be sufficient to destroy the intended theoretical (scaling) behaviour of quantum computer. But if the qubits of the different modules stay perfectly coherent with each other, and the global phase differences between the modules are known to the classical computer, then I guess it will be possible to achieve the intended theoretical (scaling) behaviour of quantum computer.

Edit Actually, the part of the model about initialization and measurement does matter a bit. Even if we assume that we know the global phase differences between the modules after initialization, we certainly have to assume that measurement is restricted to each module alone, and that coherence with other modules is lost after measurement. I still don't think that this will destroy the quantum speedup, since the global state can be (quantum/unitarily) transformed suitably before the measurement, hence one should still be able to perform any desired single measurement at the end of the quantum computation.


What is the motivation behind the definition of pseudorandom in Nisan/Wigderson? I am reading the classic "Hardness vs Randomness" by Nisan and Wigderson.  Let $B=\{0,1\}$, and fix a function $l\colon \mathbb{N} \to \mathbb{N}$.  They define a family of functions $G = \{G_n : B^{l(n)} \to B^n\}$ to be pseudorandom in case for every circuit of size $n$ we have

$(*) \ \ | P(C(x) = 1) - P(C(G(y))=1) | < 1/n$

(where $x \in B^{n},y \in B^{l(n)}$ are uniform random variables).

I understand that I am to think of $x$ and $y$ as random variables, and that I want to compare the distance between $x$ and $G(y)$ as random variables.  I get the intuition that circuits are being used as sort of "tests" in to see if $G$ can be "figured out."  What I am really struggling with is why the condition $(*)$ is the right one.  Does anyone have any advice on how to think of this definition?

There are two aspect that need to be mentioned.

The first is the general idea of defining a PRG by having its output look different than uniform to small circuits. This idea goes back to Yao and is really the strongest possible definition you can ask for when aiming explicitly at pseudo-randomness for computationally-bounded observers.

The second aspect is the choice of parameters where we limit the circuit size to be $n$ and the acceptance probability difference to be $1/n$, where $n$ is also the PRG output size. This choice is somewhat different than the usual crypto one where the circuit size is $poly(n)$ and the probability difference is required to be smaller than any $poly(n)$.  In our case specific parameters (rather than $poly(n)$) were needed as to get the tightest results including, in particular polynomial simulations.  While in principle one could have 3 different parameters, it turned out that our results had these working essentially in the same way so we folded them to a single one (in addition to the input size $l(n)$ which was viewed as a function of $n$).


What is First-Order Rewritable (and FO-Query)? I just wonder what FO Rewritable is, put an example to make it clearer for me. Also, I heard that a language that is FO Rewritable is very good, in what sense?

It is said as follow:

  A class C of TGDs is ﬁrst-order rewritable (or FO-rewritable) iff for every set of TGDs $\Sigma$ in C, and for every BCQ Q, there exists a ﬁrst-order query $Q_\Sigma$ such that for every database
  instance D, it holds $D\cup\Sigma\models Q$ iff $D\models Q_\Sigma$.

Since answering ﬁrst-order queries is in the class $\textrm{AC}_0$ in the data complexity, it immediately follows that for FO-rewritable TGDs, BCQ answering is in $\textrm{AC}_0$ in the data complexity.

Then my question can be extended into, what is a first-order query?

Link to the paper: http://portal.acm.org/citation.cfm?doid=1514894.1514897

Part of the answer is in your question: if your language is FO-rewritable, query answering is in $\textrm{AC}_0$ in data complexity, which is almost as good as it gets. However, keep in mind that you have to pay the cost of computing $Q_\Sigma$, which might be expensive, though you have to do it only once.

Other good thing is that, for a FO-rewritable language, you reduce the problem of answering a query over a database with dependencies to answering a query over a database without dependencies. But again, the size of the new query ($Q_\Sigma$) might be exponential (or worse, but I'm not so sure) in the size of $Q$ and $\Sigma$ (because you have to encode the TGDs in $Q_\Sigma$ somehow). Anyways, roughly speaking it means you are reducing a problem to a simpler problem. I guess that's why it's very good.


Complexity of linearized Ising model at 0 Suppose $Z_G(J,h)$ is a partition function of Ising model with coupling $J$ and magnetic field $h$ on graph $G$. What is the complexity of finding the gradient of Z at $\mathbf{0}$?

Specifically, if $n$ is the number of vertices, $E$ is a set of edges, $\mathcal{X}=\{1,-1\}^n$, the gradient is of the following function
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J \sum_{(i,j)\in E} x_i x_j + h \sum_i x_i\right)$$

Not a full answer, but hopefully at least helpful. Computing the ground state of such an Ising Hamiltonian is NP-hard, as it contains Max-2-SAT, even if the couplings are restricted to $\pm J$. This is simply because if you take a 2-SAT instance, you can add the term $Jx_ix_j - Jx_ix_0 - J x_jx_0 = \mbox{daig}(-1,-1,-1,3)$ which is minimized iff $x_i \vee x_j$. Thus adding such terms to form a Hamiltonian will result in a spectrum where the ground state corresponds to the assignment of variables which maximizes the clauses satisfied as this corresponds to the maximum number of negative terms in the Hamiltonian. By adding an ancilla system it is then possible to create many such levels (via the tensor product of the two Hilbert spaces) with different energy levels. By tweaking the terms in the ancilla system, you can manipulate the absolute value of the energy levels corresponding to the ground state of the primary system and different excited states of the ancilla system. This would seem to indicate that the general problem is NP-hard. In the specific case of your question, you seem to fix J to be constant and positive which would seem to cause a problem with representing the negation of a variable in any of the clauses, and so this argument may not apply.

You may also be interested in cond-mat/0309240 for some results relating Ising lattices with various complexity classes.

Hope this is useful.


Most optimal parallel method for calculating the integral of a 2D function I posted already this question to SO but got no answer so I try it now here:

In some crunching number program, I have a function which can be just 1 or 0 in three dimensions. I do not know in advance the function, but I need to know the total "surface" of the function which is equal to zero. In a similar problem I could draw a rectangle over the 2D representation of the map of United Kingdom. The function is equal to 0 at sea, and 1 at the earth. I need to know the total water surface. I wonder what is the best parallel algorithm or method for doing this.

I thought first about the following approach; a) divide 2D map area into a rectangular grid. For each point that belongs to the center of each cell, check whether it is earth of water. This can be done in parallel. At the end of the procedure I will have a matrix with ones and zeroes. I will get the area with some precision. Now I want to increase this precision, so b) choose the cells that are in the border regions between zeroes and ones (what is the best criterion for doing this?) and in those cells, divide them again into successive cells and repeat the process until one gets the desired accuracy. I guess that in this process, the critical parameters are the grid size for each new stage, and how to store and check the cells that belong to the border area. Finally the most optimal method, from the computational point of view, is the one that performs the minimal number of checks in order to get the value of the total surface with the desired accuracy.

You can partition your domain for subsequent parallel processing as follows. There are a few possible options. You can try a static geometric decomposition, including recursive bisection, quad or oct-trees and a space-filling curve.

Recursive bisection techniques are used to partition a domain (e.g., a finite element grid) into subdomains of approximately equal computational cost while attempting to minimize communication costs, that is, the number of channels crossing task boundaries
A divide and conquer approach is taken. The domain is first cut in one dimension to yield two subdomains. Cuts are then made recursively in the new subdomains until we have as many subdomains as we require tasks. Notice that this recursive strategy allows the partitioning algorithm itself to be executed in parallel. Advanced variants include recursive graph bisection and recursive spectral bisection.

Here is an example. In the following picture, assume that magenta points requires twice as much work as cyan ones.

Then, you continue applying recursive bisection by cycling through the axes until # pieces = # processors, obtaining something like the following:

The idea behind quad-trees is the following one. Partition all of space into quadrants (octants in 3-space). If any piece contains too much work, partition it into quadrants, and so on. See the next picture for an example.

The best general-purpose geometric load-balancing comes from space-ﬁlling curves.
The order in which points are visited in the space-ﬁlling curve determines how the geometric objects are grouped together to be assigned to the processors. The following image shows an Hilbert space-filling curve.

You problem may also be amenable to a solution using what is known as a scattered decomposition. Used when there is a structured domain space (e.g., an image) and the processing requirements are clustered, such as modeling a crash or processing an image with only a few items of interest. Suppose there are P processors. Cover the problem domain with non-overlapping copies of a grid of size P and assign each processor a cell in each of the grids. If you use more pieces:

Less load imbalance, i.e., computation time
More overhead and/or communication time

Finding a good tradeoff may require experimenting running the application and measuring how parallel time is affected by different scattering strategies.

Here is an example. The first picture show an example image that must be processed. Say it contains sea water and an island, and you may want to process the vegetation on the island. The image is partitioned using a very simple domain decomposition technique. The second picture shows an example of scattered decomposition.

Finally, you can use an advanced technique known as Adaptive Mesh refinement (AMR): grids are broken into blocks of ﬁxed extents, when needed blocks are reﬁned into children with same extents. Block size are chosen to optimize balance of cache efﬁciency (optimization possible since loops operate on ﬁxed size array), communication, and load balance.
Often balancing blocks per processor sufﬁces; if communication is excessive then use a space-ﬁlling curve. Rebalancing requires only simple collective communication operations to decide where blocks go. The technique can be used for arbitrary dimensions. If block size is 1, adaptive blocks are quad or oct-trees.
See the next picture for an example.

Hope this helps.


Complexity involving connected components of 0/1 matrix Assume a matrix has one component means we can traverse from a matrix entry $(i,j)$ which is $1$ to any other one by moving step of $(i\pm1,j),(i,j\pm1),(i\pm1,j\pm1)$ where each step you take you step on another $1$ and one can shown there that there are matrices that cannot be brought to one component.

  Is the decision problem "Can a given matrix $A$ be permuted into at most $k$ components?" in $coNP$ (it is clearly in $NP$ ("YES" certificate is a permutation with $\leq k$ components)) and could it be $NP$-complete (I think this problem is in $NPI$)? $k$ is part of input.

I do not have explicit matrices but a counting argument will easily give you existence.

So I give a sketch why the problem is NP-complete.
It is very sketchy, which you can take as a sign of trust that you're a smart guy, and not at all a sign of laziness on my part.
We will reduce a variant of PLANAR-SAT, where we also require that the edges connecting the variable to its negated and unnegated occurrences form adjacent intervals in the rotation of the vertex of the variable; e.g., if each variable occurs at most once negated.

The matrix will have a small top-left corner that will contain the important information, and many additional rows and columns to impose a structure on this part.
In particular, I claim that with properly chosen additional rows and columns, we can achieve that instead of arbitrary permutations, we can restrict the problem to permutations that do not change the rows and can swap only given pairs of adjacent columns, or otherwise the number of components would be larger than $k$.

If we can achieve this, then in the top-left corner we "draw" the graph of our PLANAR-SAT, such that at the heart of each vertex there is a pair of swappable columns.
Every other row is constant on these two columns, so only the neighborhood of the vertex is effected.
And at this vertex the negated clause-edges come from one side, the unnegated from the other, the swappable column decides which ones are connected to some main component.
Therefore, the CNF is satisfiable if and only if all clauses can be connected to the main component.

Since I didn't provide any details about the additional part, it is not clear how $k$ depends on $n$.
Can $k$ be kept constant?


Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs? This paper gives example
of polynomial GI for certain graphs.

Probably I am misunderstanding the paper, but appears
to me it implies polynomial GI for cubic, $4$-regular
and probably higher degree regular graphs.

GI for regular graphs is GI complete.

On p. 7 the graphs $H(a,b,c)$ are defined. They are a claw with
$a+b$ leaves, $a$ edges are subdivided and $c$ isolated
vertices are added.

On p. 8 Theorem 4. Isomorphism of $(H(0, b, c), \overline{H(0, b' , c' ))}$-free graphs is in $P$ when:

(2.) $c, c′ \le 1$ and $b, b' \ge 1$.

Take $c=c'=1,b=b'=5$.

$H=H(0,5,1)$ is $K_{1,5} + K_1$.

Both $H$ and $\overline{H}$ have degree $5$ vertex,
so neither can be induced subgraph of cubic or
$4$ regular graph.

By taking larger $b$ this works for higher
degree regular graphs.

Does the paper imply GI is in $P$ for cubic
and $4$-regular graphs?
Does the paper imply GI is in $P$ for higher
degree regular graphs (the running time might
depend on $b$, not sure)?

Their paper doesn't say anything about general regular graphs. Note that the $b$ is constant. Actually all of their excluded subgraphs are constant. Their polynomial time algorithm is consist of considering all possible $K_{2b+1}$'s in that case. This causes to running time $\Omega(n^{2b+1})$. Means if we want to use their algorithm for $r$-regular graph then we should use running time $\Omega(n^{2r+1})$, means when $r$ is not fix their algorithm is not polynomial time in the size of input. Actually we can say that they proved the problem in that case belongs to XP when the problem parametrized by $b$. Don't mix parametrized complexity with usual polynomial time algorithms.


What are the prospects of research in database field? I have been working with database management systems, and would like to focus on research in this very area some day.

I was having a look at the various research labs around the world,

http://www-07.ibm.com/in/research/
http://research.microsoft.com
http://research.google.com/

but did not find any dedicated Database research groups, or any exciting activity in this area.

How do the research prospects in the Database field look like?

As usual, to have an idea of what is happening in a field, have a look at the major conferences: SIGMOD/PODS, VLDB, ICDT, to name a few.


NP-complete problems related to Minimizing Variance I am interested in references to NP-complete problems that involve some non-linear terms (e.g. quadratic terms). So far I am aware of the "Quadratic Assignment problem" and "Quadratic Programming". The non-linear terms can be part of e.g. the constraints or the objective function. My motivation is to get some ideas for the following problem:

Let $k>0$ be an integer and $G=(V,E)$ an undirected graph such that the degree of each vertex is at least $k$. Each node of $G$ picks $k$ of its neighbors as its mates. For each node $v$ let $m(v)$ be the number of neighbors that selected $v$ as a mate. Then $\sum_{v\in V} m(v) = |V|k$. Given a number $C>0$. The mate-problem is to decide whether there exists a selection of mates such that the variance of this selection is less than $C$. In other words
$\sum_{v\in V} (m(v) - \mu)^2 < C$
where $\mu$ is the mean value, i.e. $\mu = \frac{1}{|V|}\sum_{v\in V}m(v)$.

Is this decision problem NP-complete? The case $C=0$ can be solved by a max-flow problem.

The problem should be solved in polynomial time since it can be reduced to the integral convex quadratic minimum-cost flow problem.

The essential part of the objective function is $\sum_{v \in V}m(v)^2$ since $\sum_{v \in V}m(v)$ does not change by a choice of mates.

Given a graph $G=(V,E)$ we construct the following network. The vertex set is $V_+ \cup V_- \cup \{s,t\}$, where $V_+ = \{v_+ \mid v \in V\}$ and $V_- = \{v_- \mid v \in V\}$ are copies of $V$, and $s,t \not\in V_+\cup V_-$.  The vertex $s$ is a source, and $t$ is a sink. The arcs are constructed as follows.

There is an arc from $s$ to each vertex in $V_+$.  The capacity is $k$, and the cost is $0$.
There is an arc from each vertex in $V_-$ to $t$.  The capacity is $+\infty$, and the cost is the square of flow on the arc.
There is an arc from $u_+ \in V_+$ to $v_- \in V_-$ if and only if there is an edge $\{u,v\} \in E$ in $G$.  The capacity is $1$, and the cost is $0$.

Now, we inject the $k|V|$ unit of flow to the network from $s$ toward $t$.  Then, a feasible integral flow corresponds to a mate assignment, and the total cost is $\sum_{v \in V} m(v)^2$.


What is the initialization time of a link-cut tree? Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two trees in the forest into one, while operation cut divide a tree in the forest into two trees.)

Several applications are known by using link-cut trees, and here I'm particularly interested in Goodrich's separator decomposition, which given a $n$-node plane graph $G$ one can obtain a corresponding binary tree where nodes are subgraphs of $G$, and the children of a node $H$ are the subgraphs of $H$ divided by the separator on $H$. Such a decomposition can be easily constructed in $O(n \log n)$ time (since a separator can be found in $O(n)$ time, and since the separator divides the graph so balanced, after $O(\log n)$ level of separations the leaves of the tree are of size $O(1)$). The main contribution of Goodrich is that he can construct such a decomposition in time $O(n)$, by maintaining and reusing the data structures used for finding separators in each level.

One of the data structures being used in the construction, is indeed the link-cut tree. In page 7 of the paper by Goodrich, he claimed that the initialization of the link-cut tree can be done in time $O(n)$. While I go through all the papers cited there, it seems to me that if we construct a link-cut tree via operation link, it takes time $O(n \log n)$ in total.

  Do I misunderstand something? Can the initialization of a link-cut tree be done in time $O(n)$?

Many thanks to Hsueh-I Lu, my teacher in National Taiwan University, who provides the following solution.

It turns out that the answer is rather simple; in the initialization of a data structure, we don't have to construct the structure by the queries and operations it supports. Of course, we cannot perform queries during the construction like we usually do if we build the tree by link operation; but in this separator decomposition application we don't need it.

That is to say, in the application to the separator decomposition, when we have to construct the link-cut trees L(T) for the spanning tree T on input graph G, instead of computing the structures and values of the trees L(T) by link operation, we directly compute the heavy-light path decomposition of the tree T, and construct the corresponding binary tree structure for each paths, and gluing the binary trees according to the path decomposition. All the steps can be done in linear time.

For each necessary values on the nodes of L(T), since each value can be compute from T in linear time (in this application), instead of assigning values on binary tree structures and updating when gluing the trees, we assign the precomputed values directly onto the nodes of the final link-cut trees L(T). There are only a constant type of values need to be assigned, and again this can be done in linear time.


What are the general direction and target question in the field of quantum error correction? After quantum error correction was introduced in mid '90s, in subsequent years many of the classical analogues regarding the structure of code (such as singleton bound, GV bound etc) were obtained in the quantum setting as well.
Of course, there was also the big break of stabilizer formalism, fault-tolerant computing and particular families of codes like Toric code and other surface codes.
What are the general directions and target questions in the area (like current status of decoding algorithms and codes with good parameters) and applications of it?
For example on the application side, one key area that we see nowadays is local codes and connections to qPCP or hamiltonian complexity. What are some (big or small) questions that we are trying to answer?

One big open question is the existence of "good" quantum LDPC codes. These are stabilizer quantum error correcting codes with constant check weight, constant rate and linear distance. Most recently there was a series of breakthroughs on this front by Hastings, Haah and O'Donnell (arXiv:2009.03921), Breuckmann and Eberhardt (arXiv:2012.09271) and Panteleev and Kalachev (arXiv:2012.04068).


Is #P contained in PSPACE? It's obvious that NP $\subseteq$ #P. How about #P $\subseteq$ PSPACE?

It strikes me as semi-obvious, since we can check whether an assignment (e.g. for SAT) is a solution in polynomial time (and hence space), and since each assignment can be checked separately, we can re-use the memory needed for this check, and thus use only a polynomial amount of space to check every assignment (plus a counter to track how many of the assignments were solutions).

For the sake of completeness, let me update this answer with a direct proof. My original answer will remain below in case anyone finds it interesting. The basic idea of the direct proof is exactly as Evgenij suggests: check whether each possible assignment is satisfiable, keep a counter of satisfiable instances, and reuse space wherever possible.

Claim: #$P \subseteq FPSPACE$

Proof: Assume #$SAT$ is #$P$-complete; then it suffices to show a polynomial-space algorithm to solve #$SAT$. Here is a linear-space, exponential-time algorithm.

Initialize two counters of $k \le n$ bits to all 0, for number of variables $k$ in the $3CNF$ formula given as input. The first counter will keep track of which assignment we are checking (1 = true, 0 = false, for each variable $x_1$ to $x_k$). The second will keep track of the number of satisfying assignments (there are at most $2^k$ of them).

We will also need enough space ($n$ bits) to write the formula, and enough space to do "scratch work" for one clause (some very small constant number of bits, since every clause will have exactly 3 literals by definition of #$SAT$).

Here is the description of the algorithm:

For all possible assignments
   For all clauses in the Boolean formula
      Check if the assignment satisfies the given clause
   If the assignment satisfied every clause
      Increment the assignment counter
Output the value in the assignment counter

Note that once we finish work on one possible assignment, we don't need any information from it again to compute whether other assignments satisfy the formula; the only information we keep is whether it was satisfied -- in the second counter. In particular, since we can just apply binary addition of 1 to the assignment we are testing in order to always get the next assignment, and since every assignment can be checked by considering only one clause at a time (and re-using the same space for computation on every clause), the dominating factor in the space requirement is simply writing the formula itself. Alternatively, we just read from an input tape and never explicitly write the formula, then in the worst case, $k = n$ and it still takes $O(n)$ space to write the possible assignments and keep track of the number of satisfying assignments. Q.E.D.

Below is my original answer:

Although this already essentially answered, let me give a proof of a different vein (straight out of Arora/Barak):

Let #$SAT_D$ = {($\phi, K$) : $\phi$ is a 3CNF formula and it has exactly $K$ satisfying assignments}

In Chapter 17, there is a proof that #$SAT$ is #$P$-complete.
In Chapter 8, there is a proof that #$SAT_D \in IP$.

Since $IP = PSPACE$, #$P \subseteq FPSPACE$.


Full Completeness vs Full Abstraction of a program translation Compiler verification efforts often come down to proving the compiler fully abstract: that it preserves and reflects (contextual) equivalences.

Instead of providing full abstraction proofs, some recent (categorical based) compiler verification work by Hasegawa [1,2] and Egger et. al. [3] prove the full completeness of various CPS translations.

Question:
What is the difference between full completeness and full abstraction?

To me, completeness just looks like equivalence reflection for a translation and fullness appears to be a consequence of equivalence preservation.

Note: Both Curien [7] and Abramsky [8] explore the relationship between definability, full abstraction, and to some extent full completeness. I suspect these resources may have the answer to my question, but after a surface read I have yet to confirm that.

Some Background:
The term "full completeness" was coined by Abramsky and Jagadeesan [4] to characterize the correctness of a game-semantic model of Multiplicative Linear Logic.

Blute [5] provides the following definition:

  Let $\mathcal{F}$ be a free category. We say that a categorical model
  $\mathcal{M}$ is fully complete for $\mathcal{F}$ or that we have
  full completeness of $\mathcal{F}$ with respect to $\mathcal{M}$ if, with respect to some interpretation of the generators, the unique free
  functor $[\![ - ]\!] : \mathcal{F} \rightarrow \mathcal{M}$ is full.

As far as I can tell, Hasegawa in [6] is the first to adapt full completeness to describe a program translation instead of a categorical semantic model. In this case, the Girard translation from simply typed lambda calculus to the linear lambda calculus.
Later, in [1], he defines full completeness of the CPS translation $(\cdot)^\circ$ as:

  If $\Gamma^{\circ};\emptyset \vdash N : (\sigma^\circ \rightarrow o) \multimap o$ is derivable in the linear lambda calculus, then there
  exists $\Gamma \vdash M : \sigma$ in the computational lambda calculus
  such that $\Gamma^{\circ};\emptyset \vdash M^\circ = N : (\sigma^\circ
 \rightarrow o) \multimap o$ holds in the linear lambda calculus.

(where $o$ is a base type in the linear lambda calculus (target language), but not in the computational lambda calculus (source language).)

To me, Hasegawa's definition seems like a fullness and should really be combined with completeness to get full completeness.

Egger et. al. [3] define full completeness of a CPS translation $(\cdot)^v$ as a combination of (1) completeness and (2) fullness:

  (1): If $\Theta \vdash M,N : \tau$ and $\Theta^v | - \vdash M^v =_{\beta\eta} N^v : !\tau^v$ then $\Theta \vdash M =_{\lambda_c} N : \tau$

  (2): If $\Theta^v | - \vdash t : !\tau^v$ then there exists a term
  $\Theta \vdash M : \tau$ such that $\Theta^v | - \vdash M^v =_{\beta\eta} t : !\tau^v$

(where $=_{\lambda_c}$ is Moggi's computational equational theory)

[1] "Linearly Used Effects: Monadic and CPS Transformations into Linear Lambda Calculus", Hasegawa 2002

[2] "Semantics of Linear Continuation-Passing in Call-by-Name", Hasegawa 2004

[3] "Linear-use CPS Translations in the Enriched Effect Calculus", Egger et. al. 2012

[4] "Games and Full Completeness for Multiplicative Linear Logic", Abramsky and Jagadeesan 1992

[5] "Category Theory for Linear Logicians", Blute 2003

[6] "Girard Translation and Logical Predicates", Hasegawa 2000

[7] "Definability and full abstraction", Curien 2007

[8] "Axioms for Definability and Full Completeness", Abramsky 1999

Unfortunately, there are too many things are going on here.  So, it is easy to mix things up.  The use of "full" in "full completeness" and "full abstraction" refer to completely different ideas of fullness.  But, there is also some vague connection between them.  So, this is going to be a complicated answer.

Full completeness:  "Sound and complete" is a property you want for a traditional logic to have with respect to its semantics.  Soundness means that whatever you can prove in the logic is true in the semantic model.  Completeness means that whatever is true in the semantic model is provable in the logic.  We say that a logic is sound and complete for a particular semantic model.  When we come to constructive logic, such as Martin-Lof type theory or linear logic, we care not only about whether formulas provable, but also what their proofs are.  A provable formula may have many proofs and a constructive logic wants to keep them apart.  So, a semantics for a constructive logic involves specifying not only whether a formula is true, but also some abstract semantic notion of "proof" ("evidence") for its truth.  Abramsky and colleagues coined the term "full completeness" to mean that the proofs in the logic can express all the semantic proofs in the model.  So, "full" refers to proofs here.  A "complete" logic can prove everything it needs to.  A "fully complete" logic has all the proofs that it needs to have.  So "full completeness" means "constructive completeness" or "proof completeness".  This has nothing to do with full abstraction.

Full abstraction: "Adequate and fully abstract" is a property you want for the semantic model of a programming language.  (Note the first difference: we are now dealing with the properties of the semantic model, not the properties of the language!)  Adequacy means that, whenever two terms have the same meaning in the semantic model, they are observationally equivalent in the programming language (with respect to some notion of execution).  Full abstraction means that, if two terms are observationally equivalent, they have the same meaning in the semantic model.  These ideas can be related to soundness and completeness, but in a somewhat contrived way.  If we think of the semantic model of a programming language as a "logic" or a "proof method" to talk about observational equivalence, then adequacy means that this proof method is sound; full abstraction means that this proof method is complete.  There is no notion of "full completeness" here because nobody has yet produced a semantic model that represents a constructive proof method.  (But, such a thing is theoretically possible, and one of these days somebody might do so.)

In your case, you are interested in translations rather than semantic models.  The properties of adequacy and full abstraction can be extended to deal with translations as follows.  You think of the target language as your "semantic model", i.e., a formalism that you fully understand somehow.  If so, you have some notion of equivalence for it.  Then, we say that the translation is adequate if, whenever the translations of two source programs are equivalent in the target language, they are observationally equivalent in the source language.  We say that it is fully abstract if, whenever two source programs are observationally equivalent in the source language, their translations are equivalent in the target language.

In reality, I don't know of any target languages that we really fully "understand".  All we know is some other notion of observational equivalence for the target language.  In that case, the translation is adequate if the observational equivalence of the translations in the target language implies observational equivalence in the source language.
$$ \tau(M) \cong \tau(N) \Longrightarrow M \cong N$$
The translation is fully abstract if the observational equivalence of the terms in the source language implies the observational equivalence of the translations in the target language.
$$M \cong N \Longrightarrow \tau(M) \cong \tau(N)$$
Some authors take "fully abstract translation" to mean the combination of these two properties:
$$M \cong N \iff \tau(M) \cong \tau(N)$$

Egger et al seem to be similarly extending the idea of full completeness to translations.  In their set-up, formulas are types and proofs are terms.  Their translation translates types as well as terms.  They call their translation fully complete if the translation of a type $A$ has only those terms that are obtained by translating the original terms of type $A$.
$$\forall N : \tau(A).\; \exists M : A.\, \tau(M) = N$$

Now for the vague connection between full completeness and full abstraction.  Proving that a semantic model or a translation is fully abstract often involves some of definability.  This is because our languages are generally higher-order.  So, if the semantic model or the target language has too many "contexts" then it will be able to poke our terms or semantic meanings in undesirable ways and spoil their equivalence.  "Undesirable ways" means in ways that the programming language itself cannot poke them.  So, to get full abstraction, we need to ensure that the "contexts" available in the semantic model or the target language do come from those in the source language in some form.  Note that this relates to the full completeness property.

Why do we want such properties?  It has nothing to do with compilers!  We want these properties in order to claim that the source language embeds into the target language.  If we are happy with a particular target language (as being clean, understandable, somehow fundamental or God-given) then, if the source language embeds into it, then we can claim that there is nothing new in the source language.  It is just a fragment of the target language that we know and love.  It is just syntactic sugar.  So, fully abstract translations are given by people to establish that particular target languages are great.  They are also sometimes given by people who have a big or complicated language to deal with.  So, instead of defining a semantics for it directly, they translate it to some core language and then give semantics to the core language.  For instance, the Haskell report does this.  But the full abstraction of these translations is rarely ever proved because the source languages are big and complicated.  People take it on faith that the translation is good.

Once again, this has nothing to do with compilers.  Compilers are rarely ever adequate or fully abstract.  And, they don't need to be!  All that a compiler needs to do is to preserve the execution behavior of complete programs.  The target language of a compiler is generally huge, which means that it has lots of contexts that can mess up equivalence.  So, equivalent programs in the source language are almost never contextually equivalent when compiled.


What's new in compiler optimization techniques over last few years? I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex.
But it will also be interesting to know about the latest inventions in the field of peephole optimizations.

I'm not sure how novel it is, or if it's too much on the applied side for your interest, but Hoopl shows how a control/data flow optimization can be modularised, with propagation of facts about control-graph vertices being independent of the language and specific optimization.

They reference a 2002 algorithm of Lerner, Grove and Chambers which composes simple optimizations into a "superoptimization".


is Zero knowledge Proof same as commitment schemes? I am studying about the zero knowledge proofs and I am looking for a practical (example based) approach to undrestand its process. I have studied the theory a little bit and I find it interesting yet confusing.

My exact question is given a prover A and verifier B. How can prover A prove that he is in the possession of some value 'X' without disclosing 'X' to B. 'X' could be A's last name or A's telephone number.

I am trying to compare this approach with commitment schemes (i.e. Hashing 'X' and comparing the hashes). I know that in the commitment schemes the value 'X' must be shared with B.

"is Zero knowledge Proof same as commitment schemes?"

No, although if one makes soundness be only computational

(i.e., arguments rather than proofs) ,  then existence of such zero-knowledge protocols

is equivalent to existence of instance-dependent commitment schemes.

"How can prover A prove that he is in the possession of some value 'X'

without disclosing 'X' to B. 'X' could be A's last name or A's telephone number"

How would the verifier check validity of the claimed 'X' if A did disclose 'X' to B?

Your hashing remark suggests that what you're thinking

about is actually proving knowledge of a preimage:

i.e., both parties know 'Y', and A is proving knowledge of a 'W' such that  H(W) = Y .


How do you compute the fixed point of a best-response function efficiently? I have a polynomial time best-response function that has the same properties as a game-theory game (convexity, compactness, set-valued).  I don't know that much topology, but my understanding is that the Kakutani fixed-point theorem confirms that this function has a fixed point, i.e., there exists a strategy profile whose best response is itself.

The "game" I have is not really a game, in the sense that there are no payoffs; there is only a best-response function.

My question is:  Given such a function, can one find a fixed-point quickly?  Ordinarily, there are polytime approximation algorithms for this task (finding a Nash equilibrium), but here I do not have the game in normal form, or an easy way to put it in normal form given the lack of payoffs specified.

Edit:  More specific information:  Given a fixed input, find a polytime machine bounded by n^8+8 s.t. the machine outputs its description on the input.  (There are ways of making this convex by allowing mixing over the edges of the machine.)

A fixed point of a best response function is a Nash equilibrium -- the fact that you do not have the payoff matrix cannot make the problem easier (since if you know the payoff matrix, you also know the best response function, but not vice versa). Unfortunately, there are not in general good algorithms for computing approximate Nash equilibria in multi-player games. It is known that in general settings, computing a fixed point of a function is equivalent in difficulty to computing a Nash equilibrium -- see for instance http://homepages.inf.ed.ac.uk/kousha/nash_focs07_full_j_spec_issue_sub.pdf

There are not believed to be efficient algorithms for computing fixed points for general (best response) functions, and it is open whether they can be approximated well in general.


What is the best and easy (regarding implementation) way of computing three edge independent trees in a 3-connected graph? I am searching for an implementation of an algorithm that constructs three edge independent spanning trees from a 3-edge connected graph. Any response will be appreciated. Thanks in Advance.

The problem can be reduced to the edge orientation problem. Where if tree width (number of independent trees) is c, we need to orient the edges such that each vertex has an outdegree of at most c.

For planar graphs, where c = 3, an O(n log n) algorithm is given by [1]. For general graphs, a simple O(m + n) time algorithm computing a (2c - 1) orientation is shown in [2]. Other algorithms computing exact c orientation are harder including [3] and [4].

[1] Grossi and Lodi. Simple planar graph partition into three forests. Discrete Applied Mathematics, 84:121-132, 1998.

[2] Srinivasa R. Arikati, Anil Maheshwari, and Christos D. Zaroliagis. Efficient computation of implicit representations of sparse graphs. Discrete Applied Mathematics, 78:1-16,1997.

[3] Harold N. Gabow and Herbert H. Westermann. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica, 7:465-497, 1992.

[4] J. C. Picard and M. Queyranne. A network flow soloution to some non-linear 0-1 programming problems, with applications to graph theory. Networks, 12:141-160, 1982.


How to describe the set of "all computable functions" using Coq? Would the set of all computable functions be just the set of all maps of the form

f : forall n : nat, P n -> nat

where P : nat -> Prop, and (P n) has a proof whenever (f n) is defined - so, n is in the domain of f. Is this some smaller set of maps actually computable by Coq, or is this what I want?

If not, is there an existing formalization? Using lambda calculus, or combinators K and S, or some basic concept of an algorithm?

Perhaps along with a proof of the Snm theorem - that says this set is enumerable?

The usual definition of partial recursive functions using Turing machines and classical logic (with a few novelties) has been implemented in Coq: see

Zammit, Vincent (1997) A Proof of the S-m-n theorem in Coq. Technical report. University of Kent, The University of Kent, Canterbury, Kent, UK


Approximation Ratio of Local search for $k-$center problem In the $k-$center problem, you're given $V$ points in Eucledian space, and you're asked to get a subset $C\subset V, |C|=k$ such that $\max _{v\in V}d(v, Closest-Center(C,v))$ is minimized.

Now I am aware of the greedy $2-$Approximation where you start with a random center, $C=\{c_1\}$. Then at each step, add the point furthest from $C$ iteratively until $|C|=k$

However, my question is about the local search approach. Namely, start with a set of random $k$ centers $C=\{c_1, ..., c_k\}$, then at each step, for every $(c_i, v), \forall v\in V-C, \forall c_i\in C$, check if $C-\{c_i\}+\{v\}$ improves the cost. There are $O(nk)$ such pairs, and it takes $O(n)$ time for each pair to compute it's cost for a total time of $O(n^2k)$ per iteration. Repeat this until your $k$ centers don't change after $I$ iterations (Where $I$ is trivially $O(n^k)$ ).

My question is, once the algorithm terminates, does the local search guarantee any approcimation ratio on the maximum distance? Is there any literature on this? I read in a paper that in the $k-$median problem, this approach would give a $5-$approximation.

Local search (with a single swap) doesn't give you a good approximation factor in the worst case for $k$-center, as illustrated by the following example.

Take a simplex in $\mathbb{R}^{k-1}$, and put $k$ points at each of the $k$ vertices, for a total of $k^2$ points.

Note that between each pair of vertices of the simplex the distance is 1.  The optimal solution takes one point from each vertex, obtaining cost zero.  And that's the only way to obtain cost zero.. any other type of solution has cost 1.

So if you start local search with $C$ being any solution that is more than one swap away from such an optimal solution, no local improvement (in one step) is possible.  For example, start local search with $C$ containing all $k$ of the points at a single vertex.  That solution has cost 1, and no single swap (or even $k-2$ swaps) can reduce the cost below 1.


The relationship between QCMA and QMA in the Turing and Communication model First my background about computational complexity is still beginner.

Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial Boolean functions in a QCMA and QMA in communication model. However, Aharonov and Naveh [AN02] conjecture that QMA = QCMA in the Turing model.

[KP14] state the following open problem:

Thus, in order to show that QCMA = QMA; we need nonalgebrizing techniques.

I just don't understand how they relate the communication model with the Turing model?

According to my understanding is that communication model is different than Turing model. that is, we have different results, proofs, etc. therefore, [KP14] argue that any separation in the two-way communication model would imply using non-algebrizing techniques, how could it be?

thanks in advance

Consider two complexity classes, say P and NP. To show that a proof that P=NP would need non-relativizing techniques, one has to describe an oracle relative to which the classes are not equal. For this the usual approach is to take an exponential separation between deterministic and non-deterministic query complexity and then use a standard argument to turn this into the oracle separation.

For algebrization one needs the stronger statement that even if the weaker class (here P) is given access to the polynomial extension of the oracle the classes remain different. Aaronson and Wigderson give some direct constructions for that, but the easiest argument is that a separation in communication complexity (e.g. an exponential separation between deterministic and non-deterministic communication complexity) can take the place of the query complexity separation. Compare Theorem 4.11 in the algebrization paper.

Of course many such separations are known (e.g. non-disjointness is easy for non-deterministic protocols but hard for deterministic protocols).
The separation that is left open in our paper is QCMA- vs. QMA-communication complexity (in the two-way model). Giving an exponential separation would immediately imply that any proof that QMA=QCMA (for Turing machines) would need non-algebrizing techniques (of course this inclusion might not be true).

Again, the reasoning here is that an algebrizing proof of QCMA=QMA would (by definiton) also work for the algebraic oracle model (for any oracle) and algorithms in this one could be simulated in the communication complexity model, contradicting a separation result there.


Is SAT a context-free language? I am considering the language of all satisfiable propositional logic formulae, SAT (to ensure that this has a finite alphabet, we would encode propositional letters in some suitable way [edit: the replies pointed out that the answer to the question may not be robust under varying encodings, so one needs to be more specific -- see my conclusions below]). My simple question is

  Is SAT a context-free language?

My first guess was that today's (early 2017) answer should be "Nobody knows, since this relates to unresolved questions in complexity theory." However, this is not really true (see answer below), though not completely false either. Here is a short summary of things we know (starting with some obvious things).

SAT is not regular (because even the syntax of propositional logic is not regular, due to matching parentheses)
SAT is context-sensitive (it is not hard to give an LBA for it)
SAT is NP-complete (Cook/Levin), and in particular decided by nondeterministic TMs in polynomial time.
SAT can also be recognized by one-way nondeterministic stack automata (1-NSA) (see W. C. Rounds, Complexity of recognition in intermediate Level languages, Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5)
The word problem for context-free languages has its own complexity class $\textbf{CFL}$ (see https://complexityzoo.uwaterloo.ca/Complexity_Zoo:C#cfl)
$\textbf{CFL}\subseteq\textbf{LOGCFL}\subseteq\textbf{AC}^{\textbf{1}}$, where $\textbf{LOGCFL}$ is the class of problems logspace reducible to $\textbf{CFL}$ (see https://complexityzoo.uwaterloo.ca/Complexity_Zoo:L#logcfl). It is known that $\textbf{NL}\subseteq\textbf{LOGCFL}$.
It is not known whether $\textbf{NL}\subsetneq\textbf{NP}$ or $\textbf{NL}=\textbf{NP}$ (in fact, even $\textbf{NC}^{\textbf{1}}\subsetneq\textbf{PH}$ is open; I think I got this from S. Arora, B. Barak: Computational Complexity: A Modern Approach; Cambridge University Press 2009). Hence, there cannot be any $\textbf{NP}$-complete problem that is known to not be in $\textbf{LOGCFL}$. Hence, it must be unknown if SAT is in $\textbf{LOGCFL}$.

However, this last point still leaves the possibility that SAT is known to not be in $\textbf{CFL}$. In general, I could not find much about the relationship of $\textbf{CFL}$ to the $\textbf{NC}$ hierarchy that might help to clarify the epistemic status of my question.

Remark (after seeing some initial answers): I am not expecting the formula to be in conjunctive normal form (this will not make a difference to the essence of the answer, and usually arguments still apply since a CNF is also a formula. But the claim that the constant-number-of-variables version of the problem is regular fails, since one needs parentheses for syntax.).

Conclusion: Contrary to my complexity-theory inspired guess, one can show directly that SAT is not context-free. The situation therefore is:

It is known that SAT is not context-free (in other words: SAT is not in $\textbf{CFL}$), under the assumption that one uses a "direct" encoding of formulae where propositional variables are identified by binary numbers (and some further symbols are used for operators and separators).
It is not know if SAT is in $\textbf{LOGCFL}$, but "most experts think" that it is not, since this would imply $\textbf{P}=\textbf{NP}$. This also means that it is unknown if other "reasonable" encodings of SAT are context-free (assuming that we would consider logspace an acceptable encoding effort for an NP-hard problem).

Note that these two points do not imply $\textbf{CFL}\subsetneq\textbf{LOGCFL}$. This can be shown directly by showing that there are languages in $\textbf{L}$ (hence in $\textbf{LOGCFL}$) that are not context-free (e.g., $a^nb^nc^n$).

Just an alternative proof using a mix of well known results.

Suppose that:

variables are expressed with the regular expression $d = (+|-)1(0|1)^*$
and that the (regular) language (over $\Sigma = \{0,1,+,-,\land,\lor\})$ used to represent CNF formulas is: $S = \{ d^+ (\lor d^+)^*(\land (d^+ (\lor d^+)^*))^* \}$; just note that $S$ grabs all valid CNF formulas up to variable renaming.

For example $\varphi = (x_1 \lor x_2) \land -x_3$ is written as: $s_{\varphi} = +1 \lor +10 \land -11 \in S$ (the $\lor$ operator has the precedence over $\land$).

Suppose that $L = \{ s_{\varphi} \in S \, \mid $ s.t. the corresponding formula $\varphi$ is satisfiable $\}$ is CF .

If we intersect it with the regular language: $R = \{ +1^a \land  -1^b \land -1^c \mid a,b,c > 0 \}$ we still get a CF language. We can also apply the homomorphism: $h(+) = \epsilon$, $h(-) = \epsilon$ and the language remains CF.

But the language we obtain is: $L' = \{ 1^a \land 1^b \land 1^c \mid a \neq b, a \neq c\}$, because if $a=b$ then "source" formula is $+x_a \land -x_a \land -x_b$ which is unsatisfiable (similarly if $a=c$). But $L'$ is a well known non CF language $\Rightarrow$ contradiction.


Are single hidden-layered neural networks at least as good as multi hidden-layered neural networks? If I have a multi hidden-layered neural network that is getting a better approximation for a function than a single one, does that mean that there is something "fishy" about my multi layered one because of the Universal Approximation Theorem?

I am assuming here that all weights are pre-initialized to 1 (I have my reasons) and they are trained on the same exact dataset.

Short answer: Not necessarily. Likely nothing fishy is going on.

Longer answer:
The Universal Approximation Theorem (UAT) says nothing about an individual network's capacity to approximate a function. Moreover it says nothing about trainability or generalization.

The UAT roughly says that for any $\epsilon>0$ and any continuous real-valued function $F$ on compact domain $\Omega$ there exists a feed-forward network $f$ with a single hidden layer (with appropriate weights) such that $| F(x)-f(x)|<\epsilon$ for all $x\in\Omega$. Inductively using the shallow UAT, one can prove a deep UAT. So in theory depth offers no more expressiveness.

Note that this merely guarantees the existence of some appropriately tuned neural network, and not that any particular network can be trained up to that desired accuracy.

On the other hand, deep neural networks have been seen to be often much better in many applications. This is often attributed to their ability to learn hierarchical representations of the data. The UAT says nothing about generalization, which is the bar by which success is usually measured in practice. Here it is argued that deep networks can approximate compositional functions with less parameters than shallow counterparts.

But on the other-other hand, it was noticed that sometimes adding more depth can hurt when training a network. But why should it? One could in principle just set the new layer to be the identity. Apparently the later layers were actually trying to approximate the identity but doing it very poorly. So why not learn how different your layer is from the identity? This observation led to Residual Learning which in turn led to some really, really deep networks.


Difference between CTMC, DTMC, and MDP I've been reading the Handbook of Model Checking recently; I'm especially interested in probabilistic model checking, so have been led to the PRISM model checker. For background, I am very familiar with TLA+ and use of its model checker for safety & liveness properties. My goal is to specify & model-check a simple probabilistic consensus protocol like snowflake (pdf).

One thing which confuses me is the difference between Markov Decision Problems (MDPs), Discrete-Time Markov Chains (DTMCs), and Continuous-Time Markov Chains (CTMCs). I'd assumed probabilistic model-checking was just a way of assigning weights to nondeterministic steps; things like network messages being dropped, nodes crashing, random choice of nodes to send messages to, that sort of thing. Why are these different models necessary? What can you express in one but not the other?

I see on this page the documentation says:

  In every state of the model, there is a set of commands (belonging to any of the modules) which are enabled, i.e. whose guards are satisfied in that state. The choice between which command is performed (i.e. the scheduling) depends on the model type.

But aren't we model-checking it in some way where it doesn't matter which action is "performed", since both possible transitions are checked via some breadth-first search mechanism?

The "probabilistic" element in probabilistic model checking is that the system being checked is probabilistic, not that we add probabilities to an existing deterministic or non-deterministic system.
Thus, what you are checking is whether a probabilistic system satisfies some property. For example "is it true that with probability at least 0.5, the system will reach an error state?"

Now, a probabilistic system is given by a set of states, and transitions between the states. However, this does not give a concrete definition of such systems. Specifically, there are two aspects to be considered:

Are the transitions dependent on an action (e.g. user input, or some environment interaction)
Is time discrete or continuous?

For property 1, if there is no user input, then the system just progresses with time, and is called a Markov Chain (assuming it's behaviour is independent of time). Otherwise, it is called a Markov Decision Process (MDP), where in each step an action is "played", and that determines the probabilities of moving to the next steps.

Now for property 2 - if time is discrete, then at every time point the system progresses. This gives rise to Discrete time Markov chains (DTMC, or often called just MC). If time is continuous, then (after modelling specifically what is meant by that), you get Continuous time Markov chains (CTMC).

You could also speak of continuous time MDPS, although this model is slightly less common. I'm not sure if PRISM supports it.

Different models are used for different settings. For example, CTMCs are common in modelling asynchronous protocols, or chemical reactions, whereas DTMCs are useful for synchronous probabilistic systems.


Vertex isoperimetric number of a graph - NP-hard? The vertex isoperimetric number of a graph $G=(V,E)$ is
$i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$.
Several academic papers state that the problem of computing the vertex isoperimetric number of a graph is NP-hard, without proof or reference.

Can you give a reference where the following problem is shown NP-complete: given a graph $G$ and a number $t$, the question is to decide whether $G$ has vertex isoperimetric number at most $t$?

The following paper:
On an isoperimetric problem for Hamming graphs
L.H. Harper. contains the following:

  The vertex-isoperimetric problem is NP-complete [8] in
  general, so no polynomially bounded solution is known and it is unlikely that one
  exists.

Where reference [8] is
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,

This book usually either contains a proof or a reference to the proof.
Unfortunately I have no access to the book at the moment.


A generalization of the geometric closest pair problem to balls In one version of the classical closest pair problem, one is given a set $S \subseteq \mathbb{R}^2$ and asked to find distinct $x, y \in S$ such that $\|x - y\|$ is minimized for some norm $\| \cdot \|$. This problem admits a well-known $O(n \log n)$ divide and conquer solution for $L^p$ spaces (Wikipedia).

Instead of a point set, I have instead a finite set of closed balls $S = \{B_{r_i} (\mathbf{x}_i) : \mathbf{x}_i \in \mathbb{R}^2\}$, and I would like to solve the associated distance problem. That is, for a given $p$, I want to find distinct $i$, $j$ such that the distance between $B_{r_i}(\mathbf{x}_i)$ and $B_{r_j}(\mathbf{x}_j)$ is minimal.

I have been unable to adapt the divide and conquer technique to this situation. Has any work been done on this problem? I care specifically about an asymptotically fast solution for the case $p = 1$, though I am also interested in the general solution (my examples and scribblings so far indicate that the case $1 \leq p \leq \infty$ may be easier than the case $0 < p < 1$). Is it known, for instance, whether this problem is $\Theta(n^2)$ for $0 < 1 < p$?

Edit: I will make the simplifying assumption that the balls' interiors do not intersect (though their boundaries may).

As Suresh says in his comment, you can extract the closest pair from the additively-weighted Voronoi diagram of the centers of the balls.  The closest pair of balls (in your case, diamonds) will have adjacent Voronoi regions.

The additively weighted Voronoi diagram of $n$ points in the plane can be constructed in $O(n\log n)$ time with high probability using a standard randomized incremental algorithm.  The same algorithms work, with only minor modifications, for diagrams in the Euclidean metric ($L_2$), the Manhattan metric ($L_1$), the supremum metric ($L_\infty$), or the $L_p$ metric for any other fixed $p\ge 1$.


Name of graph partition that balances edges between sets with edges remaining within sets Is there a common name for this problem:

Let G=(V, E) be an undirected graph.  Partition V into sets $S_1$, $S_2$, ..., $S_k$, such that (the number of edges between sets) + (the number of "non"-edges within sets) is minimized.

To be clear: define "extra edges" to be the set of edges with endpoints in different sets; define "missing edges" to be the set of edges in the complement of G with endpoints in the same set.  The goal is to find a partition that minimizes the sum of "extra edges" and "missing edges".

(The sets need not be of similar size.)

This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by Bansal, Blum, and Chawla (full version). They give a (huge) constant factor approximation for the problem and prove it's NP-hard. Charikar, Guruswami, and Wirth show the problem is APX-hard, and improve the approximation factor to 4 via region growing. There is a beautiful and simple combinatorial algorithm (a variant of QuickSort), due to Ailon, Charikar, and Newman, that gives a factor 3 approximation. I believe the current best known approximation ratio is due to Chawla, Makarychev, Schramm, and Yaroslavtsev, and is around 2.06.


Visualizing the parse structure of a range concatenation grammar The above is a good visualization of a derivation for a specific sentence in a context free language. You can find many more on Google Images by searching "context free grammar."

Let's consider the language $\{a^nb^nc^n : n>0\}$ for which no CFG exists but a RCG does. What does the visualization for the parse structure of the sentence "aaaaabbbbbccccc" look like? You can draw the visualization in MS Paint: I don't care how ugly it is as long as it isn't confusing. But you must submit a picture for an answer.

Edit: answer obeying the "spirit" of the question:

Let's use the rules
$$S(xy)\to A(x,y)$$
$$A(x,ayb)\to A(x,x)A(y,y)$$
$$A(x,x)\to\epsilon$$
Then we can derive $S(aabb)\to A(a,abb)\to A(a,a)A(b,b)\to\epsilon$.
In this case the parse tree is:

  $$
\begin{eqnarray*}
&S(aabb)\\
&\downarrow \\
&A(a,abb)\\
&\swarrow\quad\searrow \\
&A(a,a)\quad A(b,b)\\
&\searrow\quad\swarrow \\
&\epsilon\\
\end{eqnarray*}
$$

Original answer obeying the "letter" of the question:

Using @MarzioDeBiasi's grammar
$$\begin{eqnarray*}S(xyz)&{\color{red}\rightarrow}&A(x,y,z),\\
A(ax,by,cz)&{\color{green}\rightarrow}&A(x,y,z),\\
A(a,b,c)&{\color{blue}\rightarrow}&\epsilon,\end{eqnarray*}$$
the picture is:

  $$\begin{eqnarray*}
&S(aaaaabbbbbccccc)\\
&{\color{red}\downarrow}\\
&A(aaaaa,bbbbb,ccccc)\\
&{\color{green}\downarrow}\\
&A(aaaa,bbbb,cccc)\\
&{\color{green}\downarrow}\\
&A(aaa,bbb,ccc)\\
&{\color{green}\downarrow}\\
&A(aa,bb,cc)\\
&{\color{green}\downarrow}\\
&A(a,b,c)\\
&{\color{blue}\downarrow}\\
&\epsilon\end{eqnarray*}$$