Partition into triangles in a 3-partite graphe Let $G=(X\cup Y\cup Z,E)$ be a 3-partite graph such that:

$|X|=|Y|=|Z|=q$.
$2 \leq d(v) \leq 6$ for all $v \in X\cup Y\cup Z$, where $d(v)$ is the degree of v.
$\sum_{x \in X} d(x)=\sum_{y \in Y}d(y)=\sum_{z \in Z} d(z)$

Can we partition $G$ into $q$ vertex-disjoint triangles?

A recent paper by Custic, Klinz, Woeginger "Geometric versions of the three-dimensional assignment problem under general norms", Discrete Optimization 18: 38-55 (2015) contains (and proves) the following proposition:

  Proposition 5.1: Partition into triangles on 6-regular tripartite graphs is NP-complete.

Now just follow the reduction in the proof with a NO-instance, and you will get a 6-regular tripartite graph on $3q$ vertices that cannot be partitioned into $q$ triangles.


random sampling DAGs via nilpotent matrix sampling The adjacency matrix of an acyclic graph is known to be a nilpotent matrix (all eigenvalues are zero). I am interested in sampling DAG adjacency matrices or equivalently sample random nilpotent matrices (the equivalence is a question in fact) and so far I have simplified the process to the following:

step 1. randomly permute the nodes
step 2. sample a strictly upper triangular matrix (zero diagonal)

the first step is required to make sure we shuffle the topological ordering roots and step 2 is constructing a random topological ordering. The matrix is nilpotent as by construction the eigenvalues are zero.
I'm interested in an answer to either question 1 or 2.

Would this process generate all possible DAGs with positive probability?
Are all nilpotent matrices adjacency matrices of DAGs AND would the process above generate with positive probability every nilpotent matrix?

Any pointers or hints will be greatly appreciated,
Best regards

For question 2 the first answer is "yes": if $M$ is a $0-1$-nilpotent matrix, then it is the adjacency matrix of some digraph.
Now $M^k_{i,j}$ is well-known to be the number of paths of length $k$ between vertices $i$ and $j$. Meanwhile, there exists some integer $\nu$ such that $M^k=0$ for $k \ge \nu$, so there are no paths of size greater than $\nu$ in the graph, in particular there cannot be any oriented cycle, hence the graph is a DAG.
For the rest of your questions, I have a mixed answer: indeed your going to get all adjacency matrices (as you're saying, this is just shuffling the topological order) ; and since the set of strictly upper triangular $0-1$-matrices of size $n$ along with the set of permutations of $n$ elements, each DAG of order $n$ will appear with positive probability.
Now I'm guessing what you want is that this probability is greater than some bound for any $n$, and this seems doubtful. Take for instance the path of size $n$, up to relabeling there are $n!$ of them. But there are $2^{(n-2)n \over 2}$  strictly upper triangular $0-1$-matrices of size $n$ and $n!$ way to shuffle each of them, so the probability of getting a path goes to $0$ exponentially fast.


Separating words and graph isomorphism I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's.
In both cases the ultimate goal is to differentiate some object, though the conditions are quite different.
I would like to know what people more familiar with Babai's proof think about whether some of the ideas there are applicable to word separation or not.

I hadn't thought about the Separating Words problem before, but based on looking at the Robson paper referenced in the linked answer, I don't immediately see how techniques from GI would apply.

At a high level, note that techniques for GI such as Luks's and Babai's all compute the automorphism group of a graph, and are very group-theoretic in nature. In the Separating Words Problem, I don't see how groups like this would naturally arise (though perhaps I've just missed it).

At a more detailed level, before asking whether Babai's algorithm has any application here, it is worth asking whether Luks's technique could apply, as this is the framework of Babai's algorithm. (Babai's main improvement was to handle the bottleneck case of Luks's algorithm - Johnson groups - much more efficiently.) Again, my answer to this is more or less the same as in the previous paragraph.

For example, is there a natural symmetry group (aside from a permutation of the alphabet) that preserves the length of the separating word? Even if there were, I don't see how the techniques would apply, but it might at least provide a foothold.

Now, of course, there are lots of combinatorial and group-theoretic lemmas proved along the way in Babai's paper, and it's impossible to say that those won't be relevant, but at least at first glance I don't see how.


Advice on undergraduate research I am a junior in college who is very interested in doing some sort of REU/research internship in theoretical computer science this summer, as I would like to get research experience before potentially applying to grad school. However, I have not had much luck in finding many research opportunities. The most theoretical focused one I stumbled upon was at the Toyota Technological Institute at Chicago, but I want to apply to more than just one program, of course. If anyone has any advice or knows of any good research opportunities for an undergrad in theoretical computer science I would love to know, as I am beginning to have difficulty finding other options.

Here is a tweet thread by Prof. Vijay about research for undergraduate students.
Also, you can apply for a summer research internship in Europe.

INRIA France, contact individual groups if they have an intern opening.
Max-Planck Institute, Germany, Offering remote internship also, This year's deadline 31st Dec/31st Jan
IST, Austria
EPFL, Switzerland

Edit 1: Just now I got this link.


STCONN in $O(n)$ time? This is a very basic question on $s$-$t$-connectivity in directed graphs. As a baseline, using DFS (or BFS), one can solve the problem on a graph $G=(V,E)$ in $O(n+m)$ time and $O(n)$ space, where $n=|V|$ and $m=|E|$.
However, I have seen mentioned in several places that DFS/BFS let you solve the problem in $O(n)$ time and space. For instance:

Two basic results on the complexity of $\mathsf{STCONN}$ exist for over 20 years. The first follows from the discovery of the very efficient algorithms for graph traversal, BFS (Breadth-First Search) and DFS (Depth-First Search), which use only linear time and space in $n$, the number of vertices.
Theorem 4. $\mathsf{STCONN}\in\mathrm{TISP}(n,n)$.

from [1]. How does that work? (Sorry if this question is trivial...) I would have thought maybe this followed from taking $n$ as the input size (not the number of vertices), but the text before does contradict this interpretation.

[1] Avi Wigderson.
The Complexity of Graph Connectivity. MFCS 1992: 112-132

Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking $s$ and $t$ to correspond to the first and last indices respectively, we can prove that $\Omega(n^2)$ bits of the matrix may need to be read to decide STCONN even under the promise that the $(n/2)\times(n/2)$ square blocks in the top-left and bottom-right are all ones (with the necessary adjustments for odd $n$).
Indeed, we have some $\Omega(n^2)$ entries unaccounted for in the matrix, and there is an $s$-$t$ path iff any one of them is a $1$. So in the worst case, we might need to read all of these $\Omega(n^2)$ bits to prove $s$-$t$-non-connectivity (or half of them if the graph is known to be undirected, which doesn't change the order of growth). We can turn this into a lower bound against randomized algorithms by considering the case that with 50% probability we either add or don't add in a $1$ uniformly at random: we must read some $\Omega(\varepsilon n^2)$ bits to gain a $\varepsilon$ advantage over a random coin flip.
Graphically, this corresponds to the case where $s$ and $t$ each lie within disjoint cliques of size $n/2$, and we wish to determine if there is at least one edge joining these cliques. One can also do the same thing with any other pair of connected structures of order $\Omega(n)$ each.


Binary rank of binary matrix Let $M$ be a binary ($0-1$) matrix of size $n \times m$. We define binary rank of $M$ as the smallest positive integer $r$ for which there exists a product decomposition $M = UV$, where $U$ is $n \times r$ and $V$ is $r \times m$, and all entries of $U$ and $V$ come from $\{0, 1\}$.

My question is that is there known algorithmic way to determine the binary rank of $M$; and Singular value decomposition that support the binary rank. Any reference in this regard would highly help.

This is equivalent to the biclique partition number of a bipartite graph. You can think of M as representing a bipartite graph $G$ on $[n] \times [m]$ in the natural way: $M_{i,j}$ is 1 if and only if there is an edge $(i,j)$ in G (where $i$ is an element of the left partition, and $j$ an element of the right partition). Then $M$ has binary rank $r$ if and only if the edges of the corresponding bipartite graph $G$ can be partitioned into $r$ complete bipartite subgraphs. To see this, take an optimal factorization $M = UV^\intercal$, denote the columns of $U$ by $u_1, \ldots, u_r$, and the columns of $V$ by $v_1, ..., v_r$. $M=UV^\intercal$ is equivalent to $M = \sum_{i = 1}^r{u_i v_i^\intercal}$, and $u_i v_i^\intercal$ represents a complete bipartite graph on the vertices $S_i \cup T_i$, where $S_i$ is the set of left vertices for which $u_i$ is the indicator vector, and $T_i$ is the set of right vertices for which $v_i$ is the indicator vector.

Computing the biclique partition number is NP-hard, and hard to approximate. See these two papers for some results and references: [1], [2].


Is it possible to generate a collision free hash function from an equality function? I'm wondering if it's possible to go from an arbitrary equality function:

Eq :: (obj, obj) -> bool

to an identity/collision-free hash function:

Id :: obj -> int

Where Id has the properties:

Eq(a, b) implies Id(a) == Id(b)
!Eq(a, b) implies Id(a) != Id(b)

This would be extremely helpful since it would allow indexable key-generation via Id(obj) for arbitrary types without the need to implement a hash function for those types (only an equality function).

So, basically, I'm looking for something with the signature:

F :: ( (obj, obj) -> bool ) -> (obj -> int)

That is to say,

F :: Eq -> Id

My intuition is that there's no purely functional way to do this (where Eq, Id, and F are all stateless), but I've been unable to prove this and would like confirmation.

It is of course possible to achieve this with a stateful Id function that keeps track of all previously Id'd objects and compares them to any input with Eq to determine if an id should be reused. This, however, seems to perform poorly after being executed on a large number of objects - linear time and space proportional to the number of unique objects operated on is the best I can do.

Is there in fact a purely functional way to achieve this that I'm missing? If not, is there an efficient stateful solution?

Question 1: Can I write a function $f$ with the type
  $\forall\alpha,\;(\alpha\to\alpha\to\mathbb{B})\to(\alpha\to t)$
  such that $f\;e$ is an injection for
  all equivalence relations $e$?

The answer is negative. Neel Krishnaswami noticed that $f\;(=_{t'})$ is an injection only if $|t'|\le|t|$, which is not the case when $t'$ is $t\to\mathbb{B}$. Tsuyoshi Ito noticed that an even stronger statment must be true: $f\;e$ is a constant function.

Here is a proof that was shown to me by Rasmus Petersen. Go to the free theorem generator and type in "(a->a->Bool)->(a->Integer)". (The last type is Integer instead of $t$ so that the website knows that it is a type, not a type variable.) The free theorem for this type is $$\forall t\,t'\,\forall R\,\forall p\,p',\;\bigl(\forall (x,x')\,(y,y'),\;p\;x\;y=p'\;x'\;y'\bigr)\Rightarrow\bigl(\forall (x,x'),\;f\;p\;x=f\;p'\;x'\bigr).$$ Here, $t$ and $t'$ are types; $R$ is a relation on these types; (in our case) $p$ and $p'$ are equivalence relations on $t$ and, respectively, $t'$; and we have $xRx'$ and $yRy'$. We now pick a relation $R$ such that the premise is satisfied and the right hand side of the conclusion reduces to a constant: $R=\{(x,())\}$, where $x$ is some fixed but arbitrary element of $t$, and $t'=\mathbb{U}=\{()\}$ is the unit type. $$f\;p\;x=f\;(=_\mathbb{U})\;()$$

Q.E.D. The notes I posted in a comment contain a longer proof, and more explanations.

  Question 2: Can I implement it if $f$
  keeps some state?

Neel's observation still holds. You can't.

  Question 3: Huh? But I did implement
  a version that works slow!

First, I believe your implementation is not polymorphic.
Second, and more important, even if there is no injection from $\mathbb{Z}\to\mathbb{B}$ to $\mathbb{Z}$, there is one from the elements of $\mathbb{Z}\to\mathbb{B}$ that your program constructs in some finite time.

(If you give up polymorphism but not state, then there is a way to find a counterexample to any potential implementation. I learned this from Paulo Oliva, but I don't know how yet.)

  Question 4: That's all good and
  theoretical. Can you also tell me
  something actually helps me write my
  program?

After all those impossibility results, I think it's reasonable to settle for the question: "How do I implement a hash function without collisions for some given type $t$?'' The standard solution is hash-consing, a technique first described by Ershov in 1957 (in Russian, and in 1958 in English) that should be much better known than it is.

If the equivalence relation is (reference) equality, then there is a very simple hash: Just take the address of the object. So we can recast the problem as follows: "How do we ensure that we build at most one element from each equivalence class?" Let's use structural equality as equivalence relation. If we want to build an object whose parts are $x_1,\ldots,x_n$ we call $\mathit{mk}\;x_1\ldots x_n$. In that function, we first lookup the tuple $(x_1,\ldots,x_n)$ in a dictionary and, if a value is found, we return it. (Since $x_1,\ldots,x_n$ were built before, they are class representatives.) Otherwise, we construct a new data structure.

For a different equivalence relation you need to adapt hash-consing, exploiting properties of your particular equivalence.

The implementation is a bit trickier than this description might suggest. Some (hidden) test data is here.

PS: I mentioned some people from which I learned some parts of the answer. Naturally, if those parts are wrong, it is likely I misunderstood what I've been told.


Relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$ I would like to know if there exists a relativized world where ${\bf P^A}={\bf NP^A}\not = {\bf PP^A}$. I am also interested to know if there exists a relativized world where ${\bf P^B} \not = {\bf NP^B} = {\bf PP^B}$.

I don't know a reference, but I think both of these should be doable.

For your first oracle: for starters you'll want an oracle (call it $A_1$) that encodes exponentially-large $MAJORITY$ instances, and that thereby separates both $P^{A_1}$ and $NP^{A_1}$ from $PP^{A_1}$.  Then you want a second oracle (call it $A_2$) that encodes the solutions to all $PH^{A_1}$ problems, in a "staggered" fashion such that accessing the $k^{th}$ level of the hierarchy requires queries of size (say) $n^k$ (and hence you can only get a constant number of alternations in polynomial time).  This second oracle should cause $P^{A_1,A_2} = NP^{A_1,A_2} = PH^{A_1,A_2} = PH^{A_1}$.  (Note that $A_2$ is just an "outer" layer, meaning that any queries to $A_2$ can be simulated by $PH^{A_1}$ queries.)  Finally, you'll want to appeal to Yao's and Hastad's $AC^0$ lower bounds (i.e., the switching lemma) to show that a $PH^{A_1}$ machine still can't solve the $MAJORITY$ instances in $A_1$, and therefore $PP^{A_1}$ (and certainly $PP^{A_1,A_2} = PP^{PH^{A_1}}$) remains larger.

For your second oracle, you'll want to construct $B$ in such a way that you need to solve an $NP$ search problem in order to "unlock" a part of the oracle string that then boosts your power up to $PSPACE$.  (Here we exploit the fact that $NP^{PSPACE}$ and $PP^{PSPACE}$ are both $PSPACE$.)  A subtlety is that the secret part of the oracle can't just decide an unrelativized $PSPACE$-complete language: it also needs to provide the answers to $PSPACE$ computations that query $B$ itself.  Fortunately, it's known how to achieve that in stages, avoiding the circularity: basically, you encode the outputs of the $PSPACE^B$ machines that only query $B$ on inputs of size $p(n)$ or less, in a part of $B$ that requires queries of size $>p(n)$ to access, and that's therefore "out of reach" for those machines (but not for other $PSPACE^B$ machines).  Meanwhile, the $P^B$ machines are left "completely in the dark" by all this.


PCP research proposal Hi I am taking an undergraduate taking a course in Probabilistic checkable Proofs. I will greatly appreciate if you can suggest some good research ideas and pertaining reading for someone who is just getting started. Thanks!

Here are some recent papers on PCPs with small query complexity that I found interesting:

arxiv.org/pdf/1305.1979
eccc.hpi-web.de/report/2013/179/download
wisdom.weizmann.ac.il/~dinuri/mypapers/DH.pdf
eccc.weizmann.ac.il/report/2015/085
cs.utexas.edu/~danama/papers/par-rep/final3.pdf
cs.utexas.edu/~danama/papers/par-rep-limit/paper.pdf
eccc.hpi-web.de/report/2016/160

Also, this paper is somewhat older, but it is interesting and can help understanding the context to some of the previous papers. In addition, if I may recommend a paper of my own, I think this paper contains open problems that might be useful.


PiSigma: why does 'unfold' bind a variable? I'm trying to understand the paper ΠΣ: Dependent Types without the Sugar by implementing an interpreter and type checker for the language. In doing so, I've seen that the unfold t as x -> u syntax for recursive definitions (syntax is defined in Section 2.1) binds a variable, but I don't see why that's needed. None of the examples in the paper actually use the variable binding -- they all use a shorthand form unfold t (meaning unfold t as x -> x).

I do see that the type checking rule for it (from section 5) uses the variable binding, but I don't understand the implications of this. As far as I can tell unfold t as x -> u is entirely equivalent to let x = unfold t in u.

Can someone provide an example of when the variable binding is helpful or necessary? Is there some term that type-checks with the long form of unfold but not with the short form and let?

I don't think there's any magic/necessary reason. IMO, it's written that way to make it more straightforwardly obvious that unfold is an analytic/checking elimination rule; just like why split is written the way it is rather than being written as first and second projections, and why case is written the way it is rather than being written like uneither in Haskell.

Re the "analytic" bit, note how the other elimination rules are either synthetic/inferring (beta) or bidirectional (bang)


Are there analogous works to PPSZ algorithm for #P? The PPSZ algorithm tells us that we can do SAT-solving for
$k-$CNF in time at-most $2^{1-(1-o(1))\frac{\pi^2}{6k}}$.
My question is that do we know such results for counting problems in class #P too ? For example, for #SAT do we know any algorithm that provably runs better than $O(2^n)$ ?

There are several #k-SAT algorithms in the literature which can beat $2^n$. Here is a randomized one that gets
$2^{n(1-1/O(k))}$ time (like PPSZ):
https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoMatthewsPaturi_2012_soda.pdf
There is also a deterministic algorithm with $2^{n(1-1/O(k))}$ runtime behavior. Here is a link:
http://tmc.web.engr.illinois.edu/detapsp_soda.pdf
A caveat: this second algorithm uses exponential space. I believe it is open to find a deterministic algorithm with a similar running time and polynomial space. Be sure look on Google scholar for related references too.


Question on deduction that a certain problem requires exponential space My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space.

Regular expressions with squaring are like ordinary regular expression but with a squaring operation. Let $RSQ(\Sigma) = \{ E \mbox{ is a regex with squaring} : L(E) \ne \Sigma^{\ast} \}$ be the test if some RegEx with squaring describes every word. In the paper the following is shown:

  Theorem 2.1: There is a finite set $\Sigma$ such that if $M$ is any machine which recognizes $RSQ(\Sigma)$, then there is a constant $c > 1$ such that $M$ requires space (and hence time) $c^n$ on some input of length $n$ for infinitely many $n$.

By coding accepting computations by such regular expressions they continue to show that if $L \subseteq \{0,1\}^*$ is any language with a space bound of $2^n$, then we can reduce the membership problem of $L$ to $RSQ(\Sigma)$ for some $\Sigma$ (the alphabet needs to be enlarged to account for describing sequences of instantaneous descriptions of Turing machines).

Then the argument for the above Theorem relies on the following fact (Fact 2 in the paper) taken from another paper:

  Let $S_1(n)$, $S_2(n)$ be tape constructable functions such that
  $$
 \inf_{n\to \infty} \frac{S_1(n)}{S_2(n)} = 0
\qquad \mbox{ and } S_2(n) \ge \log(n).
$$
  Then there is a language $L \subseteq \{0,1\}^*$ accepted by some space $S_2(n)$ machine but by no space $S_1(n)$ machine.

It is used in the following manner:

  Proof of Theorem 2.1: let $L$ be as in Fact 2 [the statement above] with $S_2(n) = 2^n$. Let $\Sigma$ be such that $L$ reduces to $RSQ(\Sigma)$.

  If $RSQ(\Sigma)$ is accepted by some space $S(n)$ machine, then $L$ is accepted by some space $S(cn) + cn$ machine for some constant $c$ [this is a general property of reductions as stated earlier].
  $$
 \inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0
$$
  implies that $S(n) \ge d^n$ for some constant $d > 1$ and all $n$ which are multiples of $c$.

How do they know that $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$? Somehow the order of quantifiers in the statement of the fact seem not to match that kind of deduction. It does not say that if we have any machine with $S'(n)$ which also accepts $L$ then we must have
$$
 \inf_{n\to \infty} \frac{S'(n)}{S(n)} > 0.
$$
It just says that if this equals zero, then we can choose some language accepted in space bound $S(n)$ but not in space bound $S'(n)$, so it depends on the firstly choosen $S'(n)$. But the argument of the proof does not seem to use it that way. Also the introduction "Let $L$ be as in Fact 2 [...]" seems problematic, for what space bound function $S'(n)$ in the numerator is $L$ choosen?

So how do this argument works? What am I missing here? Can someone please explain?

EDIT: Just let me add that if I accept $\inf_{n\to \infty} \frac{S(cn) + cn}{2^n} > 0$ then $S(n) \ge d^n$ for some $d > 1$ and all multiplies of $c$ is clear to me. For then we know for some $\varepsilon > 0$ we have
$$
 S(cn) > 2^n\varepsilon - cn
$$
for all $n > N$ for some $N$. Write with $d > 1$ then $2^n = (d + \delta)^n \ge d^n + n d^{n-1}\delta \ge d^n +
 d^{n-1}\delta$ and as $\lim_{n\to \infty} \frac{c\varepsilon^{-1}n}{d^{n-1}} = 0$ we have $c\varepsilon^{-1}n \le d^{n-1}\delta$ for all $n$ sufficiently large, which gives $S(cn) \ge \varepsilon d^n$. Now choose $1 < \hat d < d$ and we find $\lim_{n\to \infty} \frac{\hat d^n}{\varepsilon d^n} = 0$, hence $\varepsilon d^n \ge \hat d^n$ for sufficiently large $n$. So understanding the following conclusions is not the problem.

Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard Space Hierarchy Theorem. The standard version of the Space Hierarchy Theorem has the quantifiers rearranged:

  For every space-constructible $S_2(n)$, there exists $L \in \mathbf{DSPACE}(S_2(n))$ such that for every space constructible
  $S_1(n) \leq o(S_2(n))$, $L \not \in \mathbf{DSPACE}(S_1(n))$.


How hard is it to determine the chromatic number of a unit distance graph? For example, is it NP-complete to decide whether a unit distance graph is 3-colorable?

Okay, this seems easy. Below I sketch why it is NP-hard to decide if a unit distance graph has a $3$-coloring. They key observation is that in a $3$-coloring any two vertices $u$ and $v$ at distance $\sqrt 3$ must get the same color if the two vertices at unit distance from them are also present in the graph. With this gadget we can convert the decision problem of the $3$-colorability of any graph $G$ into the decision problem of the $3$-colorability of a unit distance graph $G'$as follows.

Map the vertices of $G$ into the plane such that no two are at unit distance. Connect every two adjacent vertices with a polygonal path that consists of segments of length $\sqrt 3$ and one segment of length $1$. Add the endpoints of the segments to the vertices of $G'$, and also the two vertices at unit distance from the ends of segments of length $\sqrt 3$. Now $G'$ is $3$-colorable if and only if $G$ is $3$-colorable if there are no additional coincidences among the vertices of $G'$ but we can pick the paths in a generic way.

With a little more care, we can also show that the problem remains NP-complete if we restrict it to planar unit distance graphs. For this, we need to use that it is NP-hard to decide whether a planar graph with maximum degree $4$ has a $3$-coloring. We can repeat the previous construction, just if we map the vertices of $G$ far away in the plane, then the respective paths won't cross. (For this reduction, maximum degree $6$ would suffice.)
This also proves that it's NP-hard to decide whether the chromatic number of a coin graph is $3$ or $4$.

A similar construction also shows that deciding whether a unit distance graph is $4$-colorable is also NP-complete using that there is a unit distance graph in whose only $4$-coloring two given vertices at distance $\frac 83$ must get the same color. Using this gadget, $\frac 83$ can play the role of $\sqrt 3$ in the previous construction.


Is there any hidden subgroup of a symmetric group which can be efficiently determined? There have been a number of cases where efficient hidden subgroup algorithms have been found for specific non-Abelian groups with very specific structures. Why haven't we found any efficient quantum algorithm to find a hidden subgroup in a symmetric group even when the structure of the hidden subgroup is heavily restricted (e.g. the hidden subgroup could be a very special direct or semidirect product)?

From what I understand, it is partially because we don't have any techniques currently that take advantage of structure of the hidden subgroup itself. Weak Fourier sampling solves the problem whenever the hidden subgroup is normal (but this is not a property of the subgroup itself - analogous to being a direct product etc - but rather how the subgroup sits within the larger group), but that's no help for the symmetric group because its only normal subgroup is the alternating group (for $n \geq 5$).

From the examples of [1] - which shows that in the symmetric group strong Fourier sampling produces distributions for the hidden trivial group vs a hidden random involution that are exponentially close - and [2], it would seem that there may be some hope if the hidden subgroup is promised to be relatively large. But you would need to either be able to show that Fourier sampling succeeds in this case, or to come up with a different method that (likely) really took advantage of the largeness of the hidden subgroup.

Moore, Russell, and Sniady [3] also showed that the other relatively successful method - a Kuperberg-style sieve - doesn't work efficiently in a group very close to the symmetric group (namely, $S_n \wr S_2 = (S_n \times S_n) \rtimes S_2$), to distinguish a hidden trivial group from a hidden involution.

[1] Moore, C., A. Russell, and L. J. Schulman. The Symmetric Group Defies Strong Fourier Sampling. SIAM J. Comput. 37, p. 1842, 2008. Preliminary version in FOCS 2005. (arXiv version)

[2] Grigni, M., L. J. Schulman, M. Vazirani, and U. Vazirani. Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem.
Combinatorica 24, p. 137, 2004. Preliminary version in STOC 2001.

[3] Moore, Russell, and Sniady. On the impossibility of a quantum sieve algorithm for graph isomorphism. SIAM J. Comput. 39 (2010), no. 6, 2377–2396. Preliminary version in STOC 2007.


P/poly vs NP separation based on circuit trees instead of DAGs there are various theorems that relate major complexity class separations to circuit family DAGs sizes, in particular for P/poly vs NP. in contrast,

  are there theorems/conjectures that relate P/poly vs NP separation to the size of circuit trees (aka formulas)?

note of course that CNF/SAT is a boolean formula. an example in this form would be something like if a CNF circuit family $C_n$ requires size $\Omega(g(n))$ clauses to compute function $f$ (alternately, can compute $f'$ in $O(g'(n))$ clauses) then NP $\not\subset$ P/poly, but the question is not limited to CNF & is asking about formulas in general. ([1] is a somewhat related question)

[1] Complexity of converting a boolean circuit to a boolean formula

The class of functions computable by formulas of polynomial size is equivalent to the (nonuniform) class $\mathsf{NC}^1$ of functions computable by (bounded fanin/fanout) circuits of logarithmic depth. Proving the two implications is a nice exercise. In one direction, you can recursively "untangle" each level of a circuit by creating copies of gates. This increases the size by a constant factor for each of the $O(\log n)$ levels of the circuit. The other direction is proven by balancing the tree of the formula.

Also, $\mathsf{NC}^1$ is equivalent, by Barrington's theorem, to width 5 polynomial size branching programs.

We know  that the uniform version of $\mathsf{NC}^1$ is contained in $\mathsf{L} \subseteq \mathsf{P}$ ($\mathsf{L}$ stands for deterministic logspace). It is not known whether any of these containments is proper AFAIK. Also it is not known whether the non-uniform $\mathsf{NC}^1$ is a proper subset of $\mathsf{P/\text{poly}}$.


Is there such a thing as a state-based programming language? As anyone knows who has read Alan Turing's paper describing the Turing Machine (On Computable Numbers, With an Application to the Entscheidungsproblem), the syntax he uses is vastly different from that of modern languages (and closer to the densely symbolic mathematical writing of the time). This is not very surprising, since he wrote the paper about a decade before the first working electronic computer was finished and several decades before the first compiler was written. More interestingly, though, is the fact that the paradigm Turing uses seems pretty foreign as well. I would expect it to be procedural, but in fact it's what I would call "state-based": he describes a finite set of possible states in which the machine might find itself, and, given a particular state and an input value, he describes what actions the machine should take. In essence, then, the Turing machine is a finite state machine that has access to an infinite strip of rewritable memory locations. Since Turing proves that this machine is functionally equivalent to any other sufficiently powerful mechanical computational device, we can see that his state-based programming language can implement all the algorithms that other languages can implement.

As far as I know, however, there is no modern programming language that actually uses this paradigm. I suppose this is probably because it's a bit of a pain to wrap one's head around, and because it doesn't provide a very natural way of thinking about most algorithms, but I'd still be surprised if no one has at least tried something like this. And there may be some applications for which such a language would work extremely well. For instance, a processor can be represented quite directly as Turing's "universal" machine, which takes as input a coded representation of another machine and then performs the work that machine would perform; so might it be possible to design new processors by "compiling" something akin to Turing's language into a circuit layout for an FPGA? (True, the compiler might not come up with the optimal layout, and this approach might be too abstract to fully characterize the details of chip design, but this is just an example of something I think might work.)

So, my question is: does anyone know of any modern programming languages based on the original Turing machine language, or any languages that use a paradigm akin to this "state-based" paradigm?

The short answer is no.

The long answer is that such languages are invented on a regular basis, but if they see any significant degree of use, for good semantic reasons they never remain in this mode for very long.

The basic problem is that it is very difficult to build programs compositionally using state machines. The modular construction of programs rests on two pillars: the variable, and the procedure abstraction. Variables let you define data in one place, and use it in another, and procedures let you parameterize a computation by some data. Without these features, it is extremely hard to build larger programs out of smaller programs.

State machines lack both of these features, and one of the first nontrivial theorems of computability (the $snm$ theorem) is the proof that Turing machines can implement them. However, the $snm$ theorem is too impractical to use as a practical calling convention, since it essentially says that the calling convention for programs is to  pass arguments by passing strings which are interpreted as programs. This doesn't matter for the purposes of computability theory, but it ends up imposing order-of-magnitude slowdowns in practice (i.e., "interpretive overhead"). So people invariably add a primitive variable and procedure call mechanism to every language that sees serious use.

In fact, the lambda calculus demonstrates that you can build a Turing complete language out of nothing but variables and procedural abstractions. Unlike TMs, however, it's surprisingly practical to program in pure lambda calculus. The technical reason for this is that both lambda calculus and TMs form "closed categories" -- that is, they have the algebraic structure necessary to represent variables and procedures. However, the lambda calculus turns out to be basically a syntactic presentation (in the sense of generators and relations) of this algebraic structure, and so it makes it a lot more convenient to work with this structure.


Does such model exists? I have a problem on distributed graph, with the following model:
1. There is a Global Graph $G=(V,E)$
2. There are $k$ computers.
3. Each computer $1 \leq i \leq k$ knows ALL the nodes of the graph, i.e. $V$, and subset of the edges, i.e. computer $i$ knows $V_i \subseteq V$.
4. Each computer observes different subset of edges, i.e., for all $i,j$ : $V_i \cap V_j = \emptyset$.

I searched for papers which handle the same model, but I didn't find anything. Do you know if such model is being studied?

The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"):

Woodruff & Zhang: "When Distributed Computation is Communication Expensive" http://arxiv.org/abs/1304.4636

See also this work for closely related models:

Klauck et al.: "Distributed Computation of Large-scale Graph Problems" http://arxiv.org/abs/1311.6209

You may also be interested in the "congested clique" model, which is the special case such that $k = |V|$ and computer number $i$ is aware of the edges incident to node number $i$.


Search a string for a list of words I have  a large number of long strings, and I need to search them for a given list of words  as fast as reasonably possible. (Neither the strings nor the words are constants)
I learned that I can preprocess the strings that I'm going to be searching for my words by building a suffix array and  an lcp array, and that I should be able to make the searches faster by doing so.
I was wondering, however, if I could preprocess the wordlist in some way as well. It is quite possible that the words will have common parts. I would like to build something like a "word genealogy tree" (or another structure that would achieve the same effect ) where the  substring that can be found in a family of words would be at the top and which would then branch down (for both the prefixes and the suffixes of the ancestor) as the descendants would go.
I imagine that this would allow me to discard whole branches or trees quickly if an ancestral node failed to match.
Could you please direct me to a suitable strategy that would help me achieve my goal (in this or any other reasonably efficient way)?
Note: I can't really make use of much existing code (can make use of ideas, though). I'm pretty much limited to the standard c library.

Searching in a string that changes often, and looking for a set of words, I would use Aho-Corasick, an extension of KMP that builds a tree (based on the set of words) and looks for the words in parallel.


What is the relation/difference between axiomatic and denotational semantics one one side, and the data flow analysis(DFA) on the other sied? I am supposed to write a small paper about DFA in OOP for a CS class in theory. But I am required to connect that (DFA) to axiomatic and denotational semantics!
I read few resources about axiomatic/denotational semantics but no one is talking specifically about their relation to Data Flow Analysis.
Can you please guide me about that, or at least guide me to a book, chapter or a paper that talks about that?

The textbook that might be most relevant to your question is Principles of Program Analysis
by Nielson, Nielson and Hankin. It does cover dataflow analysis and its relationship to denotational semantics. It does not deal with axiomatic semantics though.


Smallest set not included in a collection of sets Given as input an integer $n$ and a set $S$ of sets of elements of $\{1, ..., n\}$, what is the complexity of finding a set $T$ of elements of $\{1, ..., n\}$ such that $T$ has minimal cardinality and $T$ is included in none of the sets of $S$?

Let $[n] = \{ 1, 2, \dotsc, n \}$, and let $\mathcal{F} = \{S_1, S_2, \dotsc, S_m \} \subseteq 2^{[n]}$ be the input set family. Unless I misunderstood your problem formulation, we want to find a minimum-size set $T \subseteq [n]$ such that $T \not\subseteq S_i$ for all $i = 1, 2, \dotsc, m$.

To answer your question, note that $T \not\subseteq S_i$ if and only if $T \cap ([n] \setminus S_i) \not= \emptyset$. That is, $T$ has to intersect the complement of each $S_i$. But this means that your problem is, essentially, equivalent to the hitting set problem (consider hitting set with input $\mathcal{G} = \{ [n] \setminus S_i \  \colon \  i = 1, 2, \dotsc, m  \}$):

  Hitting Set.
  Given a set family $\mathcal{F} \subseteq 2^{[n]}$ and integer $k$, does there exists a set $T \subseteq [n]$ with $|T| \le k$ and $T \cap S \not= \emptyset$ for all $S \in \mathcal{F}$?

Hitting set is known to be NP-complete and cannot be, loosely speaking, solved faster than in time $O(2^n)$ unless the Strong Exponential-time Hypothesis fails.


Evaluate boolean circuit on batch of similar inputs Suppose I have a boolean circuit $C$ that computes some function $f:\{0,1\}^n \to \{0,1\}$.  Assume the circuit is composed of AND, OR, and NOT gates with fan-in and fan-out at most 2.

Let $x \in \{0,1\}^n$ be a given input.  Given $C$ and $x$, I want to evaluate $C$ on the $n$ inputs that differ from $x$ in a single bit position, i.e., to compute the $n$ values $C(x^1),C(x^2),\dots,C(x^n)$ where $x^i$ is the same as $x$ except that its $i$th bit is flipped.

Is there a way to do this that is more efficient that independently evaluating $C$ $n$ times on the $n$ different inputs?

Assume $C$ contains $m$ gates.  Then independently evaluating $C$ on all $n$ inputs will take $O(mn)$ time.  Is there a way to compute $C(x^1),C(x^2),\dots,C(x^n)$ in $o(mn)$ time?

Optional context: If we had an arithmetic circuit (whose gates are multiplication, addition, and negation) over $\mathbb{R}$, then it would be possible to compute the $n$ directional derivatives ${\partial f \over \partial x_i}(x)$ in $O(m)$ time.  Basically, we could use standard methods for computation of the gradient (back-propagation / chain rule), in $O(m)$ time.  That works because the corresponding function is continuous and differentiable.  I'm wondering whether something similar can be done for boolean circuits.  Boolean circuits aren't continuous and differentiable, so you can't do the same trick, but maybe there is some other clever technique one can use?  Maybe some kind of Fourier trick, or something?

(Variant question: if we have boolean gates with unbounded fan-in and bounded fan-out, can you do do asymptotically better than evaluating $C$ $n$ times?)

I'd consider it unlikely that such a trick is easy to find and/or will give you significant gains, as it would give nontrivial satisfiability algorithms. Here's how:

First of all, while ostensibly easier, your problem can actually solve the more general problem of, given a circuit $C$ and $N$ inputs $x_0, \ldots, x_{N-1}$, evaluate $C$ at all the inputs faster than $\tilde{O}(N\cdot|C|)$ time. The reason is that we can tweak $C$ into a circuit $C'$ of size $|C| + \tilde{O}(Nn)$ which, on input $0^i10^{N-1-i}$, outputs $C(x_{i})$. Basically, we just make a little lookup table that sends $0^i10^{N-1-i}$ to $x_i$, and wire it into $C$.

Nontrivial algorithms for batch evaluation of boolean-circuits can then be used to make fast satisfiability algorithms. Here's an example in the simple case where we suppose we have an algorithm doing evaluation in time $\tilde{O}(|C|^{2-\epsilon} + (N\cdot|C|)^{1-\epsilon/2} + N^{2-\epsilon})$ for any constant $\epsilon > 0$. On input a circuit $C$, we can decide satisfiability by expanding $C$ into a circuit $C'$ of size $2^{n/2}\cdot |C|$ which is just the OR over all possible choices of the first $n/2$ inputs to $C$ (leaving the other inputs free). We then batch-evaluate $C'$ on all of its $2^{n/2}$ inputs. The end result is that we find a satisfying assignment to $C'$ iff $C$ is satisfiable. The running time is $\tilde{O}(2^{(n/2)(2-\epsilon)}\cdot |C|^{2-\epsilon}) = \tilde{O}(2^{n(1-\epsilon/2)}\cdot \textrm{poly}(|C|))$.


Can decoying provide security against traffic analysis? Eve is an intelligence agency with the capability to scan all cleartext communications and do traffic analysis against encrypted communications.

There are n Alices, who each want to communicate secretly with some of the other Alices. So, they want the content of their communication to be secret, and the fact that they are actively trying to communicate secretly to be secret.

There are also N>>n Bobs, who disagree with mass surveillance but don't want to do anything  which would give them any legal liability, such as transmitting illegal material (IE, they don't want to run TOR nodes).

So the Bobs decide to help by sending junk communications to other Bobs, which are indistinguishable from encrypted data. An individual Bob, if challenged, can show that his transmissions are junk, thus avoiding legal liability (NB -  I Am Not A Lawyer). For the purpose of the exercise Eve in not allowed to challenge 'many' Bobs.

Eve wins if she can distinguish the Alices from the Bobs, or at least, as many Alices as possible. In particular, Eve may start by knowing at least some of the Alices; we don't want the security of the other Alices to collapse if she does.

A dumb approach is as follows: For each period of time, each Bob (or masquerading Alice) chooses another Bob(Alice) to communicate with at random from a public list. The Bobs send junk, the Alices send their encrypted message. In this scheme, the Alices are indistinguishable from the Bobs, but the Alices only obtain 1/N of the bandwidth of an individual communication, which is very low since N is large, and have very high latency, since they have to wait many time periods before they happen to communicate with who they want.

Is it possible to do better?

How can Bobs prove that their transmissions are junk? Given that the transmissions can be encrypted using information theoretically secure one-time pads (OTPs), it is not possible to prove that they are not significant messages. Even if the messages from Bobs would be assumed to be encrypted with a single cipher of a good grade (AES?) it would be very hard to show that there is no key that decodes a given message into meaningful content, because, assuming such a method would exist, it would simultaneously show that the cipher (AES?) is broken. A statistical method showing that a message from a Bob cannot be an AES-encrypted message would correspond to a distinguisher for AES and that would also signal that it is a weak cipher.


Coloring Planar Graphs Consider the set of planar graphs where all the internal faces are triangles. If there is an interior point of odd degree the graph cannot be three colored. If every interior point has even degree can it always be three colored? Ideally I'd like a small counterexample.

Yes, this is a corollary of the Three Color Theorem, see at the bottom here:
http://kahuna.merrimack.edu/~thull/combgeom/colornotes.html


Easier and Harder instances of NP-complete problems? Following previous questions here and here around $NP$-complete problems (and P vs NP).

Are there "easier" or "harder" (sets of) instances of an $NP$-complete problem?

If yes (which i assume), how a polynomial-time mapping between $NP$-complete problems maps between easier or harder (sets of) instances?

A conjecture  (related to directions of previous questions) is that there should be considerable mapping betwen "easier" to "harder" and "harder" to "easier" (if i may, with probability almost 1).

PS. This in effect tries to study (a little more in depth) the role of polynomial-time mappings used in $NP$-complete reductions.

Thankx

If P=NP, then all NP-complete problems are equally difficult from the perspective of polynomial-time reductions.

On the other hand, if P!=NP, then we have ways to differentiate NP-complete problems, for example:

Approximable problems - NP-complete problems where we can find a polynomial-time algorithm that gives us almost the desired answer (within a constant factor).  For example, there is a trivial algorithm to produce a Vertex Cover within a factor of $2$ of optimal, although the optimal answer is NP-complete.
Somewhat approximable problems - NP-complete problems that can be approximated, but not within a constant factor.  The classic example is the set cover problem, which can be approximated within a fraction of roughly $ln n$ for $n$ sets, but cannot be approximated with a less than logarithmic fraction (unless P=NP).
Unapproximable problems - NP-complete problems for which (under accepted assumptions) no polynomial-time algorithm exists that approximates the solution within any polynomial factor.  An example is the max-clique problem.
Fixed-parameter tractable - problems that run in polynomial time if you fix one parameter.  The classic example again is vertex-cover, which can be computed in time $O(2^k n)$ for a vertex cover of size $k$ in a graph of size $n$.

In short, under accepted assumptions, there are varying difficulties of NP-complete problems.


On equivalence of NLBA and DLBA Where I can find reference and documents on the work made for proving whether DLBA are equal NLBA nr not?
What is the underlying problem? Why it is still an open question in TCS?

The 1998 chapter about the second LBA Problem, from Schöning and Pruim Gems of TCS mentions the first LBA problem.
The chapter does not say much more than the wikipedia article though, apart from mentioning the related Savitch's theorem, whose optimality is a notorious open question.

Perhaps by looking at papers quoting the Kuroda or Savitch paper you could get a picture of recent results in the field?


Extending cographs with product operation Let $\mathcal{C}$ be the class of undirected graphs defined inductively as follows:

A single vertex is in $\mathcal{C}$;
If $G\in\mathcal{C}$ then its complement $\overline{G}$ is in $\mathcal{C}$;
If $G,H\in\mathcal{C}$ then their disjoint union $G\oplus H$ is in $\mathcal{C}$;
If $G,H\in\mathcal{C}$ then their tensor product $G\otimes H$ is in $\mathcal{C}$.

This class of graphs appears in linear logic: this is how coherent spaces are defined.
I would like to now if this class have been studied from the point of view of graph theory. Does it have a name? Does it admit other characterizations?
If we restrict the definition to the first three lines we get cographs. But when we add the product operation we can create the 4-nodes path $P_4$, clique-width is then $>2$. But is the clique-width bounded for the whole class?
Thank you in advance for your help.
Update after daniello's answer
It was not clear for me how to generate paths of arbitrary lengths. This can be done by induction as follows, where the induction hypothesis is:
"$\forall n$, there is a graph $G_n$ of $\mathcal{C}$ containing $P_n$ as an induced subgraph"

The paths $P_2$ and $P_3$ are clearly in $\mathcal{C}$. Take $G_2$ and $G_3$ to be respectively $P_2$ and $P_3$.

For $n\geq 4$, we define $G_n$ as the tensor product of $G_{n-1}$ (obtained by IH) with the graph $H_n$ whose set of vertices is $[1,n]$ and which contains an edge between every pair of vertices except between $n$ and $n-3$. The graph $H_n$ is clearly a cograph thus belongs to $\mathcal{C}$. It is not very hard to see that $G_{n-1}\otimes H_n$ contains $P_n$ as an induced subgraph.

A path has cliquewidth $3$, but the tensor product of two paths of length $n$ will contain a $\Omega(n) \times \Omega(n)$ size grid as an induced subgraph. And $n \times n$ grids are known to have cliquewidth $\Omega(n)$ (see “The rank-width of the square grid“ by Vít Jelínek)


Are equally weighted MSTs closely related? Suppose we have an undirected connected graph $G=(V,E)$ that has several minimum spanning trees. We say two trees $T_1, T_2$ are connected if they share exactly $|V|-2$ edges(*).  In other words $T_1$ can be obtained from $T_2$ by removing exactly one edge $e_1$, and adding another edge $e_2$.

Now suppose we draw a new graph $H$ that its vertices are the MSTs of the graph $G$, and there is an edge between them if they share $|V|-2$ edges. The question is, is graph $H$ connected?

One can view the problem also this way: can we obtain other minimum spanning trees by greedily looking for edges that can be replaced with another edge, without increasing the total weight along the way?

(*) Given that trees have $|V|-1$ edges, two distinct trees cannot have more than $|V|-2$ in common. So this is the maximum number of edges in common they can have.

Yes. More generally, any spanning tree can be reached from any arbitrarily-chosen MST by a sequence of single-edge replacement operations that never decrease the weight. When such a sequence is used to reach another MST, it can also never increase the weight, because then it would have to decrease it at some other step. See e.g.

H.N. Gabow, Two Algorithms for Generating Weighted Spanning Trees in Order, SIAM J. Comput. 6, 1977, 139–150. http://epubs.siam.org/doi/pdf/10.1137/0206011


Computation of reals: floating point vs TTE vs domain theory vs etc Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised exact computation of reals. Clearly, the problem of floating point precision has not dwindled in relevance, so why haven't these theories become more mainstream and why aren't there more conspicuous implementations of them?

For example, are there domains of applications where we don't care much about floating point errors? Are there significant complexity concerns?

I work in real-number computation, and I wish I knew the real answer. But I can speculate. It's a sociological problem, I think.

The community of people who work on exact real arithmetic consists of theoreticians who are not used to developing software. So they usually relegate the task of implementation to students (a notable exception is Norbert Müller's iRRAM), or they have their own toy implementations.

People who do have the necessary programming mojo do not have the necessary theoretical background. Without solid theoretical footing it is difficult to design exact real arithmetic correctly. For instance, it is a mistake to add lots of real numbers in a for loop, as you will get unacceptable performace due to loss of precision. If you want to add lots and lots of reals, you should do it with a tree-like structure, taking into account the magnitudes of the partial sums. Another thing which is difficult to get across is that < and = as total boolean function on the reals simply do not exist (you can have = but it either returns false or it diverges, and < diverges when given two equal reals).

Lastly, it is not clear at all that we know how to implement libraries for exact real arithmetic. They're not the usual pieces of libraries which just define some datatypes and some functions on them. Often exact real arithmetic requires special modes of control. For instance, iRRAM takes over the main execution of the program (it literally hijacks main), as well as standard input and output, so that it can rerun the program when loss of precision occurs. My library for real arithmetic in Haskell happens in a Staged monad (which is essentially the Reader monad). Most people expect the real numbers to be "just another datatype", but I have my doubts about that.


Set packing with maximum coverage objective We are given a universe $\mathcal{U}=\{e_1,..,e_n\}$ and a set of subsets $\mathcal{S}=\{s_1,s_2,...,s_m\}\subseteq 2^\mathcal{U}$.

Set-Packing asks how many disjoint sets we can pack, and is defined as follows:

Given a number $k\in[m]$, is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that all of the sets in $\mathcal{S'}$ are disjoint?

Maximum-Coverage, allows intersecting sets, but asks how much of the universe can we cover by $k$ sets:

Given numbers $k\in[m]$,$r\in[n]$ is there a set $\mathcal{S'} \subseteq \mathcal{S}$,  $|\mathcal{S'}|=k$ such that $|\cup_{s\in\mathcal{S''}}s|\geq r$?

I'm interested in what seems to be a combination of the two, a disjoint cover, which aims at covering as much of $\mathcal{U}$ as possible.

Disjoint-Maximum-Coverage:

Is there a set $\mathcal{S'} \subseteq \mathcal{S}$ such that $|\cup_{s\in\mathcal{S'}}s|\geq k$ (i.e. it covers at least $k$ elements) and the sets in $\mathcal{S'}$ are disjoint?

What can we say about the approximation hardness of $DMC$?
Is this problem known under a different name?

Related results:

Both Set-Packing and Maximum-Coverage are known to be $APX$-Hard (and even stronger than that - Unless $P=NP$, $SP$ can't be approximated within $ln(|S|)(1-o(1))$, and $MC$ has a tight bound using the greedy algorithm).

$MC$ is approximable within $1-\frac{1}{e} + o(1)$, while the best known bound for $SP$ is a $O(\sqrt S)$ approximation.

Optimization version of 3D matching is a special case of your problem. Approximating Maximum 3D Matching is $APX$-complete. However, it is approximable within 3/2$+\epsilon $ for any  $\epsilon >0$

References:

Hurkens, C. A. J., and Schrijver, A. (1989), On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems,
SIAM J. Disc. Math. 2, 68-72.

Kann, V. (1991), Maximum bounded 3-dimensional matching is MAX SNP-complete, Inform. Process. Lett. 37, 27-35.


Complexity of counting when there is no parsimonious reduction Let $\#A$ be a counting problem in $FP$ and let $\#B$ a counting problem with unknown complexity.  Suppose there is a polynomial-time, one-to-many reduction from $B$ to $A$, but there is no specific relation between the solutions of $A$ and those of $B$.

For example, $i$ solutions of $A$ could be related to one solution of $B$, and $j$ other solutions of $A$ could be related to a different solution of $B$ and so on. I only know that I can cover all solutions of $B$ via the reduction, and nothing more about solutions of $B$.

Is it possible to conclude that $\#B$ is in $FP$? Or do I have to find a strict parsimonious reduction or weak parsimonious reduction in a way that I could obtain the exact number of solutions of $B$ (possibly with help from the reduction)?

I don't think that having a non-parsimonious reduction helps in proving that a counting problem is in FP. Eg. if either 1 or 2 instances are mapped to 1, and which of these depends on something NP-hard, then you do not know anything about the complexity of your problem. Of course, you might have a special reduction from which you get some extra information.


Under what models do we know linear time sorting? The best we know for general case sorting is $O(n\log n)$ (which is also $\theta(n\log n)$ is decision tree model) and the problem of $O(n)$ sorting is open for turing machine models.

Under what models do we know $O(n)$ algorithms and how far they are deemed away from general models?

One obvious answer is "spaghetti sort", or in other words - sorting in a spaghetti model.

Intuitively, the spaghetti model says that your integers are given as lengths of (uncooked) spaghetti, and you sort them by placing them on a table, and then lowering your hand until you hit the tallest spaghetto (for spaghetto is the singular of spaghetti). You take that one out, and repeat.

A bit more formally, this model gives you the operation $\arg\max\{a_1,\ldots, a_n\}$ in $O(1)$.

Determining how "far" this is from a general model is a vague question. There is a trivial lower bound of $\Omega(n)$ on computing the maximum of $n$ elements in a RAM model (and an even worse bound of $\Omega(n\log n)$ in a single-tape Turing Machine), so this is not a realistic model.
You could say that it's equivalent to a RAM model with oracle access to $\max$. I'm not sure how interesting that is.

Another cute aspect of this model is to consider it's physical properties, in the intuitive spaghetti description: recall that in this description, you lower your hand onto the spaghetti. Now, if you actually want to do this to an arbitrary number of spaghetti, then you would need an increasingly large hand.
So this model induces a notion of "hand size" complexity.


A Boolean function that is not constant on affine subspaces of large enough dimension I'm interested in an explicit Boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ with the following property: if $f$ is constant on some affine subspace of $\\{0,1\\}^n$, then the dimension of this subspace is $o(n)$.

It is not difficult to show that a symmetric function does not satisfy this property
by considering a subspace $A=\\{x \in \\{0,1\\}^n \mid x_1 \oplus x_2=1, x_3 \oplus x_4=1, \dots, x_{n-1} \oplus x_n=1\\}$. Any $x \in A$ has exactly $n/2$ $1$'s and hence $f$ is constant the subspace $A$ of dimension $n/2$.

Cross-post: https://mathoverflow.net/questions/41129/a-boolean-function-that-is-not-constant-on-affine-subspaces-of-large-enough-dimen

The objects you are searching for are called seedless affine dispersers with one output bit.  More generally, a seedless disperser with one output bit for a family $\mathcal{F}$ of subsets of $\{0,1\}^n$ is a function $f : \{0,1\}^n \to \{0,1\}$ such that on any subset $S \in \mathcal{F}$, the function $f$ is not constant.  Here, you are interested in $\mathcal{F}$ being the family of affine subspaces

Ben-Sasson and Kopparty in "Affine Dispersers from Subspace Polynomials" explicitly construct seedless affine dispersers for subspaces of dimension at least $6n^{4/5}$.  The full details of the disperser are a bit too complicated to describe here.

A simpler case also discussed in the paper is when we want an affine disperser for subspaces of dimension $2n/5+10$.  Then, their construction views ${\mathbb{F}}_2^n$ as ${\mathbb{F}}_{2^n}$ and specifies the disperser to be $f(x) = Tr(x^7)$, where $Tr: {\mathbb{F}}_{2^n} \to {\mathbb{F}}_2$ denotes the trace map: $Tr(x) = \sum_{i=0}^{n-1} x^{2^i}$.  A key property of the trace map is that $Tr(x+y) = Tr(x) + Tr(y)$.


What is the complexity of minimum weight odd T-join? Let $G=(V,E)$ be an undirected graph and let $T \subseteq V$. A subset $J$ of $E$ is called a $T$-join if $T$ is equal to the set of vertices of odd degree in the graph $(V, J)$. Further $J$ is an odd (even) $T$-join if it contains an odd (even) number of edges.

It is well known that the following problem has a strongly polynomial time solution (Schrijver, Theorem 29.1):

  Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find a $T$-join of minimum total weight.

However, I am interested the complexity of the following problem:

  Given a graph $G = (V,E)$, a weight function $w \in \mathbb{Q}^E$, and the vertex set $T \subseteq V$, find an odd (or even) $T$-join of minimum total weight.

The problem is still interesting even if we assume all edge weights are non-negative. In fact, efficient algorithms for both the odd and even case with non-negative weights would imply efficient algorithms for both cases with negative weights.

Cook, Espinoza, and Goycoolea describe an $O(2^{|T|} + |T|^2|V|^2 + |V|^3)$ time algorithm for a slight variation on the problem where edges are colored red and blue and you want an odd number of red edges. The colored variant is equivalent though simple reductions. Unlike the algorithms for minimum weight $T$-join that ignore parity, the algorithm by Cook et al. takes time exponential in $|T|$. Also, their algorithm depends upon the weights being non-negative, as the reduction to the non-negative case could increase the cardinality of $T$.

Also, there are strongly polynomial time algorithms for finding shortest simple $s,t$-paths with an odd number of edges, and shortest $s,t$-walks with an odd number of edges that do not repeat any edges. Again, these algorithms assume non-negative weights. Both are described by Schrijver. Note that the odd path and walk problems are not special cases of the odd $T$-join problem where $|T| = 2$. A minimum weight odd $T$-join with $T = \{s,t\}$ could contain an even $s,t$-path and an odd cycle as separate components.

So in summary:

  Is there a (strongly) polynomial time algorithm to find a minimum weight odd (or even) $T$-join? Is the problem NP-hard?

Geelen and Kapadia appear to have a randomized algorithm for this problem.
http://arxiv.org/abs/1504.07647


AM/MA and NP in analogy to P and BPP Arora and Barak show that $\mathsf{AM}$ can be expressed as $\mathsf{BP}\cdot \mathsf{NP}$ i.e the set of languages that have randomized reductions to 3SAT. $\mathsf{MA}$ is also a natural randomized generalization of $\mathsf{NP}$ in that you replace the deterministic verifier by a randomized one.

Is there a sense in which one of these is a closer fit in the "P is to BPP as NP is to ?"  relation ?

This is of course a very subjective matter, but here is something that might be interpreted as saying that $\mathbf{MA}$ is a closer fit: The same assumptions that imply that $\mathbf{P} = \mathbf{BPP}$ also imply that $\mathbf{NP} = \mathbf{MA}$, but those assumptions are not known to imply $\mathbf{NP} = \mathbf{AM}$.
In addition, the assumption that $\mathrm{promise}\mathbf{P} = \mathrm{promise}\mathbf{BPP}$ implies that $\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{MA}$, but is not known to imply $\mathrm{promise}\mathbf{NP} = \mathrm{promise}\mathbf{AM}$.

However, there is an alternative view saying that $\mathbf{MA}$ is the non-deterministic variant of $\mathbf{BPP}$ while $\mathbf{AM}$ is the probabilistic variant of $\mathbf{NP}$. The foregoing facts can also be interpreted as evidence for this view.


Are Reversal-bounded Multicounter Machines closed under reversal? This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines.

Reversal-bounded multicounter machines are described at length in his paper "Reversal Bounded Multicounter Machines and their Decision Problems". Essentially, the bound on reversals refers to the number of times any of the counter are allowed to switch from incrementing to decrementing.

Let $DCM$ be the family of languages accepted by deterministic reversal-bounded multicounter machines, and $NCM$ the nondeterministic class.

Let $L^R = \{w^R | w \in L \}$ where $w^R$ is $w$ reversed.

I'm wondering, for $L \in DCM$, is $L^R \in DCM$? Are there subclasses of $DCM$ which have this property?

"Formal Modelling of Viral Gene Compression" by Daley and McQuillan tells that $NCM$ is closed under reversal, but I have found no such reference for the deterministic case.

DCM is not closed under reversal.  I don't know of a reference, but it is easy to show it using the expressveness lemmata of Chiniforooshan, E., Daley, M., Ibarra, O.H., Kari, L., Seki, S.: One-reversal counter machines and multihead automata: revisited.

In particular, they state that for any DCM language $L$, there is a word $w$ such that $L \cap w\Sigma^*$ is a nontrivial regular language.  Now let $D$ be the following hinted version of the complement of the prefixes of the Dyck language:
$$D = \{a^nw_1w_2\cdots w_k \mid w_i \in \{[, ]\} \land |w_1w_2\cdots w_n|_] > |w_1w_2\cdots w_n|_[\}.$$
In other words, $D$ is the complement of the Dyck where the number of $a$'s in the prefix gives a position witnessing the unbalancing of the parentheses.  Also, $(\{a\}^*)^{-1}D$ is the complement of the prefixes of the Dyck.  Note that $D$ is in DCM.  Now consider $D^R$ and a word $w \in \Sigma^* = \{a, [,]\}^*$.  Then either $D^R \cap w\Sigma^*$ is finite, or it is nonregular, hence $D^R \notin$ DCM.

I don't know of any interesting subclass of DCM closed under reversal.  (Ad placement!) However, we studied a model called Unambiguous constrained automata which is close but not comparable to DCM, and which enjoys closure under reversal --- constrained automata, or Parikh automata, themselves are equivalent to NCM in the nondeterministic case, and a strict subset of DCM in the deterministic case.


Mulmuley's GCT program It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been several positive commentaries from famous complexity theorists about the program. According to Mulmuley it will take a long time to achieve the desired results.  Entering the area is not easy for general complexity theorists and needs considerable efforts to get a handle on algebraic geometry and representation theory.

Why is GCT considered to be capable of settling P vs. NP? What is the value of the claim if it is expected to take more than 100 years to reach there? What are its advantages to other current approaches and those that may rise in the next 100 years?
What is the current state of the program?
What is the next target of the program?
Has there been any fundamental criticism of the program?

I would prefer answers that are understandable by a general complexity theorist with the minimum background from algebraic geometry and representation theory assumed.

As pointed out by many others, much has already been said on many of these questions by Mulmuley, Regan, and others. I will offer here just a brief summary of what I think are some key points that haven't yet been mentioned in the comments.

As to why GCT is considered plausibly capable of showing $P \neq NP$ many answers have already been given elsewhere and in the comments above, though I think no one has yet mentioned that it appears to avoid the known barriers (relativization, algebrization, natural proofs). As to its value - I think even if it takes us 100 years, we will learn something new about complexity along the way by studying it from this angle.

Some progress is being made on understanding the algebraic varieties, the representations, and the algorithmic questions that arise in GCT. The principal researchers I know of who have done work on this are (in no particular order): P. Burgisser, C. Ikenmeyer, M. Christandl, J. M. Landsberg, K. V. Subrahmanyan, J. Blasiak, L. Manivel, N. Ressayre, J. Weyman, V. Popov, N. Kayal, S. Kumar, and of course K. Mulmuley and M. Sohoni.
More concretely, Burgisser and Ikenmeyer just presented (STOC 2011) some modest lower bounds on matrix multiplication using the GCT approach ($n^2 + 2$, compared to the currently best known $\frac{3}{2}n^2 +O(n)$). Although these lower bounds are not new bounds, they at least give some proof-of-concept, in that the representation-theoretic objects hypothesized to exist in GCT do exist for these modest lower bounds on this model problem.
N. Kayal has a couple papers on the algorithmic question of testing when one polynomial is in the orbit of another or is a projection of another. He shows that in general these problems are NP-hard but that for special functions like permanent, determinant, and elementary symmetric polynomials, these problems are decidable in P. This is a step towards some of Mulmuley's conjectures (that certain harder problems - deciding orbit closure - are in P for special functions such as determinant).

I don't have much more specific to say on this than the answer to 2.
As far as I know there has not been fundamental criticism, in the sense that I have not seen any criticism which really discredits the program in any way. There has certainly been discussion about why such techniques should be necessary, the value of the program given the long time horizons expected, etc., but I would characterize these more as healthy discussion than fundamental criticism.


Fast algorithm to distribute points evenly in a 2D grid In an NxN grid, I want to select M points ($1 \leq M \leq N^2$) so that they are distributed as evenly as possible, spread out everywhere, edge to edge. Can you suggest a fast algorithm for distributing points evenly over a grid?
I won't yet try to formally define "evenly", because it's not an exact requirement. Low runtime is the most important factor here, so algorithms like "do a random distribution and refine until it satisfies a criteria" are bad, I prefer doing it in a simple nested loop.

Examples
Let me illustrate with some examples.
When M is a square number, the solution is simple, let's say N=5 and M=9:
trivial
#.#.#
.....
#.#.#
.....
#.#.#

It can also work in some special cases when M can be written as a sum of squares, and there's no interference between the squares, for example N=5 and M=13=9+4:
two square patterns
#.#.#
.X.X.
#.#.#
.X.X.
#.#.#

But this wouldn't exactly work for M=10, because after you select 9 points in a square pattern, there's no good place to put the 10th one.
My first shot at this was an image dithering algorithm. It looked pretty good when M was big enough, but with small M's, the error distribution makes it biased towards the edges. For example with N=3 and M=1, dithering yields a bad result when a good result is pretty obvious:
bad  good
...  ...
...  .#.
..#  ...

Let me show another example of a bad and good distribution with N=5 and M=5:
bad    good   bad    good
#....  #...#  .....  .#...
.#...  .....  .#.#.  ....#
..#..  ..#..  ..#..  ..#..
...#.  .....  .#.#.  #....
....#  #...#  .....  ...#.

I'll tell you an idea for a formal definition of "evenly". But as I said, it doesn't have to be exactly like that, it's more of an intuitive thing. So how about this: let's take every 2x2, 3x3, ... N-1xN-1 subsquare and count the point density in each of them. The deviation of those numbers should be as small as possible. Let's see for N=4 and M=4:
one   two
#.#.  #..#
....  ....
#.#.  ....
....  #..#

One:

2x2 sums: 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4, 1/4
3x3 sums: 4/9, 2/9, 2/9, 1/9
stddev: 0.06991

Two:

2x2 sums: 1/4, 0, 1/4, 0, 0, 0, 1/4, 0, 1/4
3x3 sums: 1/9, 1/9, 1/9, 1/9
stddev: 0.10758

(Even though number two has a higher deviation, it is spread edge to edge, so I prefer it a little, but number one works as well. Dealing with the edges is a not-so important edge-case.)

The optimal centroidal Voronoi tessellation for the infinite 2D grid is a hexagon tiling.

You can get one of these by placing points at even coordinates on even rows and odd coordinates for odd rows. Depends on the number of points you need.

Start with that then run Lloyd's algorithm for a few iterations to tidy up the corners and edges.

I would compute it offline on a unit square to good precision, then dilate it to your chosen rectangle with a simple linear transformation.


The utility of Renyi entropies? Most of us are familiar with — or at least have heard of — the Shannon entropy of a random variable, $H(X) = -\mathbb{E} \bigl[ \log p(X)\bigr]$, and all the related information-theoretic measures such as relative entropy, mutual information, and so on. There are a few other measures of entropy that are commonly used in theoretical computer science and information theory, such as the min-entropy of a random variable.

I've started seeing these so-called Renyi entropies more often as I browse the literature. They generalize the Shannon entropy and the min-entropy, and in fact provide a whole spectrum of entropic measures of a random variable.
I work mostly in the area of quantum information, where the quantum version of Renyi entropy is also considered quite often.

What I don't really understand is why they are useful. I've heard that oftentimes they're easier to work with analytically than say Shannon/von Neumann entropy or min-entropy. But they also can be related back to Shannon entropy/min-entropy, as well.

Can anyone provide examples (classical or quantum) of when using Renyi entropies is "the right thing to do"? What I'm looking for is some "mental hook" or "template" for knowing when I might want to use Renyi entropies.

Thanks!

Renyi entropy is analogous, in some sense, to $\ell_p$-norms, so let's first recall why those norms are useful.

Suppose we have a vector of numbers $a \in \mathbb{R}^n$. We want to have a single number that represents, in some sense, how does the typical element of $a$ look like.

One way to do so is to take the average of the numbers in $a$, which roughly corresponds to the $\ell_1$ norm: $\mathbb{E}_{1 \le i \le n}[|a_i|]$. This is often useful, but for some applications it has the following problems: First, the $\ell_1$ norm does not give us a good upper bound on the largest element of $a$, because if there is a single large element and many zeroes, the $\ell_1$ norm will be significantly smaller than the largest element. On the other hand, the $\ell_1$ norm also does not give us a good bound on how small the elements of $a$ are, for example, how many zeroes $a$ has - this problem occurs in exactly the same scenario as before.

Of course, when the elements of $a$ have a lot of variance, such as in the extreme scenario as above, no single number can give solve both problems above. We have a tradeoff. For example, if we only want to know the largest element, we can use the $\ell_\infty$ norm, but then we will lose all information about the smaller elements. If we want the number of zeroes, we can look at the $\ell_0$ norm, which is just the size of the support of $a$.

Now, the reason for considering $\ell_p$ norms is that they give us the whole continuous tradeoff between the two extremes. If we want more information on the large elements we take $p$ to be larger, and vice versa.

Same goes for Renyi entropies: Shanon's entropy is like $\ell_1$ norm - it tells us something about the "typical" probability of an element, but nothing about the variance or the extremes. The min-entropy gives us information on the element with the largest probability, but loses all information about the rest. The support size gives the other extreme. The Renyi entropies give us a continuous tradeoff between the two extremes.

For example, many times the Renyi-2 entropy is useful because it is on the one hand close to Shanon's entropy, and thus contains information on all the elements on the distribution, and on the other hand gives more information on the elements with the largest probability. In particular, it is known that bounds on the Renyi-2 entropy gives bounds on the min-entropy, see, e.g., Appendix A here: http://people.seas.harvard.edu/~salil/research/conductors-prelim.ps


Finite-State Automata over a real-valued alphabet Consider a finite state set $Q$, with a distinguished start state $s\in Q$, as well as two functions: a transition function $\delta:Q\times\mathbb{R}\to Q$ and a final output function $F:Q\to\mathbb{R}$. The tuple $(Q,s,\delta,F)$ defines a mapping $f:\mathbb{R}^*\to\mathbb{R}$ --- that is, from finite sequences of reals to reals --- in exactly the same way as a classic DFA over a finite alphabet $\Sigma$ defines a mapping
$\Sigma^*\mapsto\{0,1\}$.
Have such DFA analogs over the real alphabet been considered before?

Automata over infinite alphabets have been studied in many contexts (see e.g., this paper as a starting point).
Usually, the model is somewhat different than what you suggest, since just having an infinite alphabet is not very interesting, for the following reason:
Given an automaton with $n$ states, there are only $2^{n^2}$ transition matrices. Thus, if your alphabet has more than $2^{n^2}$ letters, then some letters will induce the same transitions. That is, you can partition them to classes of equivalent symbols.
This essentially reduces the model back to finitely many letters.
Note that the final weights do make a difference, but this has more to do with the standard model of weighted automata.
Typically, we're interested in infinite alphabets in the context of data words: these are words over a finite domain $D$, that represents variables whose range is an infinite domain. Then, a common model is that of variable automata, which have been studied a lot (e.g., this paper and references therein).


Minimizing a submodular function given noisy oracle access Let $f\colon 2^{[n]} \to \mathbb{R}$ be a submodular function (one can assume $f$ is bounded, if this helps). We are given noisy oracle access to $f$: on any $S$ and for any $\tau > 0$, one can obtain an additive $\tau$-approximation of $f(S)$ (at cost $\operatorname{poly}(1/\tau)$).

I am interested in what is known in minimizing (up to some arbitrary (additive) accuracy $\alpha>0$) $f$, given this sort of access:

If we had exact oracle access, then this could be done in polynomial time, exactly; what about robustness to approximate queries? Is there any algorithm (or, on the other side of the spectrum, lower bounds) for it?

A FOCS'15 paper by Lee, Sidford, and Wong [LSW15] can be leveraged to obtain such minimization guarantees -- cf. Section 5 (specifically, Corollary 5.4) in our recent paper ([BCELR16]).

  Corollary 5.4. Let $g\colon 2^{[m]} \to \mathbb{R}$ be a submodular function. There exists an algorithm that, when given access to an approximate oracle $\mathcal{O}^{\pm}_g$ for $g$, and for input  parameters $\xi, \delta\in(0,1)$,  returns with probability at least $9/10-2\delta$ a value $\nu \in \mathbb{R}$ such that $\nu\leq \min_{S \subseteq [m]} \{g(S)\} + \xi$.

  The algorithm performs $m\log\left(\frac{mM}{\xi}\right)$ calls to $\mathcal{O}^{\pm}_g$ with parameters $\frac{\xi^2}{128m^5M^2}$ and $\frac{\delta}{Cm^2\log\left(\frac{mM}{\xi} \right)}$, where $M\stackrel{\rm def}{=} \max\left\{{2}\max_{S \subseteq [m]}\{\lvert{g(S)}\rvert\},\xi/2 \right\}$ and $C>0$ is an absolute constant.

  The running time of the algorithm is
  $$
O\!\left( m^2\cdot \Phi_g\left( \frac{\xi^2}{128m^{5}M^2}, \frac{\delta}{Cm^2\log\frac{mM}{\xi}} \right)\log{\frac{mM}{\xi}}  + m^3 \log^{O(1)}\frac{mM}{\xi}\right) \;,
$$
  where $\Phi_g$ is the running time of $\mathcal{O}^{\pm}_g$.

[LSW15] A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong. FOCS'15. http://arxiv.org/abs/1508.04874

[BCELR16] Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron. arXiv, 2016. https://arxiv.org/abs/1607.03938


Mistake in Wikipedia CSG example? I'm confused about the example given in Wikipedia article about Context-sensitive grammar:

https://en.wikipedia.org/wiki/Context-sensitive_grammar

Disclamer: I've already changed discussed section in wikipedia article, so current state of article will differ from what I'm discussing in this question. Original version is here: https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366

  The following grammar, with start symbol S, generates the canonical
  non-context-free language { anbncn : n ≥ 1 } :

  S       →       a   b   c
  S   →   a   S   B   c
  c   B   →   W   B
  W   B   →   W   X
  W   X   →   B   X
  B   X   →   B   c
  b   B   →   b   b

They do not claim directly that this grammar is context-sensitive, but next sentence implies that that they consider it as context-sensitive:

  rules 3 to 6 allow for successively exchanging each cB to Bc (four
  rules are needed for that since a rule cB → Bc wouldn't fit into the
  scheme αAβ → αγβ)

So they appeal to the canonical form of context-sensitive grammar rules: αAβ → αγβ, implying that whole grammar is context-sensitive.

What I'm confused about is rule #3, which seems to be not fitting scheme αAβ → αγβ. I consider terminal $c$ here as part of $\alpha$, variable $B$ as $A$ in scheme, $\beta$ is empty. This implies that $cB$ can not produce $WB$, as $c$ should be saved on same place ($cB\rightarrow c\dots$).

Did I missed something or this grammar was really placed here mistakenly (as it is not real context-sensitive)?

If I am not mistaken, a simpler CS grammar is possible.  Here it is:

$S \rightarrow ABSc$
$S \rightarrow Abc$
$BA \rightarrow XA$
$XA \rightarrow XY$
$XY \rightarrow AY$
$AY \rightarrow AB$
$A \rightarrow a$
$Bb \rightarrow bb$.

A derivation for the string $aaabbbccc$ is

$\Rightarrow_1 ABSc\\\Rightarrow_1 AB\textbf{ABSc}c\\\Rightarrow_2 ABAB\textbf{Abc}cc\\\Rightarrow_3 A\textbf{XA}BAbccc\\\Rightarrow_4 A\textbf{XY}BAbccc\\\Rightarrow_5 A\textbf{AY}BAbccc\\\Rightarrow_6 A\textbf{AB}BAbccc\\\dots\\\Rightarrow_{3-6}AAB\textbf{AB}bccc\\\Rightarrow_{3-6}AA\textbf{AB}Bbccc\\\Rightarrow_{7...}\textbf{aaa}BBbccc\\\Rightarrow_8 aaaB\textbf{bb}ccc\\\Rightarrow_8 aaa\textbf{bb}bccc$


What is the actual time complexity of Gaussian elimination? In an answer to an earlier question, I mentioned the common but false belief that “Gaussian” elimination runs in $O(n^3)$ time.  While it is obvious that the algorithm uses $O(n^3)$ arithmetic operations, careless implementation can create numbers with exponentially many bits.  As a simple example, suppose we want to diagonalize the following matrix:

$$\begin{bmatrix}
2 & 0 & 0 & \cdots & 0 \\
1 & 2 & 0 & \cdots & 0 \\
1 & 1 & 2 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
1 & 1 & 1 & \cdots & 2 \\
\end{bmatrix}$$

If we use a version of the elimination algorithm without division, which only adds integer multiples of one row to another, and we always pivot on a diagonal entry of the matrix, the output matrix has the vector $(2, 4, 16, 256, \dots, 2^{2^{n-1}})$ along the diagonal.

But what is the actual time complexity of Gaussian elimination?  Most combinatorial optimization authors seem to be happy with “strongly polynomial”, but I'm curious what the polynomial actually is.

A 1967 paper of Jack Edmonds describes a version of Gaussian elimination (“possibly due to Gauss”) that  runs in strongly polynomial time.  Edmonds' key insight is that every entry in every intermediate matrix is the determinant of a minor of the original input matrix.  For an $n\times n$ matrix with $m$-bit integer entries, Edmonds proves that his algorithm requires integers with at most $O(n(m+\log n))$ bits.  Under the “reasonable” assumption that $m=O(\log n)$, Edmonds' algorithm runs in $O(n^5)$ time if we use textbook integer arithmetic, or in $\tilde{O}(n^4)$ time if we use FFT-based multiplication, on a standard integer RAM, which can perform $O(\log n)$-bit arithmetic in constant time.  (Edmonds didn't do this time analysis; he only claimed that his algorithm is “good”.)

Is this still the best analysis known?  Is there a standard reference that gives a better explicit time bound, or at least a better bound on the required precision?

More generally: What is the running time (on the integer RAM) of the fastest algorithm known for solving arbitrary systems of linear equations?

I think the answer is $\widetilde O(n^3 \log( \|A\| + \|b\|))$, where
we omit the (poly)logarithmic factors.  The bound is presented in
"W. Eberly, M. Giesbrecht, P. Giorgi, A. Storjohann,
G. Villard. Solving sparse integer linear systems. Proc. ISSAC'06,
Genova, Italy, ACM Press, 63-70, July 2006", but it is based on a
paper by Dixon: "Exact solution of linear equations using P-adic
expansions, John D. Dixon, NUMERISCHE MATHEMATIK, Volume 40, Number 1,
137-141".


Questions about special types of partial assignments Considering the definition

  "2-SAT: Given a CNF formula whose clauses have exactly 2 literals,
  does there exist an assignment of $\mathsf{TRUE}$ or $\mathsf{FALSE}$ to the variables
  that will satisfy the formula?"

Question 1: Is it necessary to give an assignment, or is it sufficient to prove that an assignment exists? (This question has been answered by Vijay D.)

Question 2: A reliable assignment is a partial assignment which is guaranteed to deliver only satisfying assignments under DPLL. I.e., DPLL can never resolve an empty clause and therefore never produces an unsatisfying assignment. A reliable assignment is different from an implicant as it does not necessarily satisfy all clauses. However, an implicant is a special case of a reliable assignment.

I would prefer using the correct term for this type of assignment.

Question3: Reliable assignments appear in my SAT solving algorithm as an entire set with cost O(n^2). A set of implicants can be generated by distributive expansion of the disjunctions defining the reliable assignments with cost O(2^n). Due to the construction, each implicant is necessarily defined by the conjunction of a subset of reliable assignments.

Does such a set of reliable assignments appear in other algorithms?

Context

The reliable assignments appear in the context of Partial Distributive Expansion

Detailed examples are available at Prime Implicants and Reliable Assignments.

The full context is an integrated SAT algorithm for a complete set of solutions. Here is an informal rationale on what I have to cover eventually. Any hints welcome.

Answer to your primary question: You have posed a Yes/No question. By definition, a Yes/No answer suffices. There is no requirement to produce any kind of assignment as an answer. If you modify the problem to require a certificate for the Yes/No answer, the answer will depend on what constraints you impose on the certificate and the certification algorithm (should it be linear-time verifiable, etc.).

Answer about terminology: The most common term I know of for what you call ``micromal'' is minimal assignment. I do not have a good sense for how standard this terminology is. If the partial assignments are represented as formulae, you obtain the very standard notion of prime implicants.

There is some confusion about terminology in your answer so I will expand on this issue below.

Assignments and Partial Assignments

  A partial assignment is a partial function in $\mathit{Var} \to \{\mathsf{true}, \mathsf{false}\}$.

A partial assignment $\pi$ refines a partial assignment $\theta$ if for every variable $x$ on which $\theta$ is defined, $\pi$ is also defined and $\theta(x) = \pi(x)$. This definition allows $\pi$ to assign values for variables not assigned to by $\theta$.

A total assignment is a partial assignment that is a total function. A partial assignment represents the set of total assignments that refine it (meaning, that extend it). Observe that these definitions make no reference to formulae.

You can define the truth value of a formula under a partial assignment in a fairly standard manner. The only difference to defining the truth value of a formula under an assignment is that a formula may be $\mathsf{true}$, $\mathsf{false}$ or $\mathsf{unknown}$ under a partial assignment.

Minterms and Cubes

A literal in propositional logic is a Boolean variable or its negation. A cube is a conjunction of literals. A cube is a minterm is a cube in which every variable occurs exactly once.

There is a correspondence between minterms and partial assignments. Every partial assignment  $\pi$ defined on exactly $k$ variables can be represented by a minterm $\ell_0 \land \cdots \land \ell_{k-1}$, such that $\ell_i = x_i$ if  $\pi$ is defined on $x_i$ and sends $x_i$ to $\mathsf{true}$ and $\ell_i = \neg x_i$ if $\pi$ sends $x_i$ to $\mathsf{false}$. Observe that a total assignment $\sigma$ refines a partial assignment $\pi$ exactly if the assignment $\sigma$ satisfies the cube representation of $\pi$. We can similarly move in the other direction and represent cubes as partial assignments.

Prime Implicants and Minimal Assignments

Everything above was stated without needing the notion of a formula which is being solved. Let $F$ be a Boolean formula.

An implicant $C$ of a formula $F$ is a cube that implies $F$. The implicant $C$ is a prime implicant if there is no smaller cube that is an implicant.

The dual notion is of an implicate. An implicate $C$ of a formula $F$ is a clause $C$ that is implied by $F$. A prime implicate is an implicate that with no sub-clause that is an implicate.

The connection to your question is: If a partial assignment $\pi$ represents an implicant for a formula $F$, then every total assignment that refines $\pi$ satisfies $F$. Moreover, if no $\theta$ refined by $\pi$ represents an implicant, then $\pi$ represents a prime implicant. The literature on prime implicants is vast, but you only need to follow work that is based on modern SAT solvers because they will be using partial assignments.

Formalizing your question

I think it would help to use more precise terms in formalizing your question. Here are some examples.

Consider a partial assignment $\pi$ and a formula $F$.

What is $\pi$ called if every total assignment $\theta$ that refines $\pi$ satisfies $F$? That is, $\pi$ represents a subset of the satisfiying assignments of $F$.
What is $\pi$ called if every total assignment $\theta$ that satisfies $F$ also refines $\pi$? That is, $\pi$ represents a superset of the satisfying assignments of $F$.

Some comments. There is a unique, maximally defined partial assignment that contains a superset of all satisfying assignments to $F$. You can construct this by taking the conjunction of all literals implied by $F$.

There is no unique partial assignment that represents only satisfying assignments of $F$. There are multiple, maximal ones, corresponding to prime implicants.

References about implicants

These references are within a model checking context as I am more familiar with that context. There are discussions of minimizing assignments and manipulation of implication graphs in both these papers.

Minimal Assignments for Bounded Model Checking, Ravi and Somenzi, 2004. (I did not find a freely available PDF, but maybe you can mail the authors if you don't have Springer access).
Applying SAT Methods in Unbounded Symbolic Model Checking, McMillan, 2002.

About your algorithm

There are certain things you are doing in your algorithm which makes me wonder if you are familiar with modern SAT algorithms.  You are describing a mix of the original Davis-Putnam and the Davis-Logeman-Loveland algorithm from the 60s. Specifically, Steps 4 and 5 are implemented differently today in what is called the unit rule.

Please confirm if this is what you mean by  reliable assignment.

  A partial assignment $\pi$ is reliable for a formula $F$ if some
  extension of $\pi$ satisfies $F$.

I think that this definition is equivalent to yours but much much shorter. A better term would be feasible. Note that a partial assignment that is not reliable in the sense defined here is called a conflict.

I would suggest looking at the following CS Theory answers. (and all have answers shamelessly from me)

Starting SAT solver papers
CNF Rule Hierarchy Discovery
Good reference about approximate methods for solving logic problems


graphs from real-life problems Where can I find graphs relevant to real-life problems?

Two repositories I know of are:

University of Florida's Sparse Matrix Collection
Bodlaender's TreewidthLib

The UCI Network Data Repository has a collection of social networks, with additional attributes (not just vertices and edges). They also have a set of links to similar collections elsewhere.


Beigel-Tarui transformation of ACC cricuits I am reading the appendix about ACC lower bounds for NEXP in Arora and Barak's Computational Complexity book.
http://www.cs.princeton.edu/theory/uploads/Compbook/accnexp.pdf
One of the key lemmas is a transformation from $ACC^{0}$ circuits to multilinear polynomials over the integers with polylogarithmic degree and quasipolynomial coefficients, or equivalently, the circuit class $SYM^{+}$, which is the class of depth two circuits with quasipolynomially many AND gates at its bottom level with polylogarithmic fan-in, and a symmetric gate at the top level.

In the appendix to the textbook, this transformation has three steps, assuming that the gate set consists of OR, mod $2$, mod $3$, and the constant $1$. The first step is to reduce the fan-in of the OR gates to polylogarithmic order.

Using the Valiant–Vazirani Isolation Lemma, the authors obtain that given an OR gate over $2^{k}$ inputs of the form $OR (x_{1},...,x_{2^{k}})$, , if we pick $h$ to be a pairwise independent hash function, from $[2^{k}]$ to $\{  0,1 \}$, then for any nonzero $x \in \{0,1\}^{2^{k}}$,with probability at least $1/(10k)$ it will hold that $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2$.

  Isn't the probability of $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2$ at least $1/2$ ? It seems that $1/10k$ is a weak lower bound.

The second step is moving to arithmetic gates and pushing multiplications down. In this step, we will transform Boolean circuits with a given binary input string to an arithmetic circuit with an integer input.

Here they note that $OR(x_{1},...,x_{k})$ is replaced with $1-x_{1}x_{2}\cdots x_{k}$, and $MOD_{p}(x_{1},...,x_{k})$ is replaced with $(\Sigma_{i=1,...,k}  x_{i})^{p-1}$ using Fermat's Little Theorem.

  Why does this replacement give an equivalent $SYM^{+}$ circuit ?

Isn't the probability of $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2 = 1$ at least 1/2 ? It seems that $1/(10k)$ is a weak lower bound.

In fact the answer is no. (It would be that $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod }  2 = 1$ holds with probability at least $1/2-\varepsilon$, if we were working with an $\varepsilon$-biased hash family, and indeed using $\varepsilon$-biased hash functions gives a way to improve the parameters of the construction. But pairwise independence is not necessarily $\varepsilon$-biased.)

It seems they are missing one additional step here. To apply Valiant-Vazirani directly, you would need to also randomly choose the range of the hash function. Rather than picking random pairwise-independent $h : [2^k]\rightarrow\{0,1\}$, it seems you should pick random $\ell \in \{2,\ldots,k+1\}$ and then pick random pairwise-independent $h : [2^k]\rightarrow \{0,1\}^{\ell}$. (Here I am deliberately using Arora-Barak's statement of Valiant-Vazirani, found on page 354.)
 Let $s$ be the number of $x_i=1$. Valiant-Vazirani says that when you have chosen $\ell$ such that $2^{\ell-2} \leq s \leq 2^{\ell-1}$, then the probability that $\Sigma_{i:h (i) =1}  x_{i} = 1$ (over the integers!) is at least $1/8$.

So by picking random $\ell$ and picking random pairwise independent $h: [2^k]\rightarrow\{0,1\}^{\ell}$, then you have probability at least $1/(8k)$ that $\Sigma_{i:h (i) =1}  x_{i} \mbox{mod } 2 = 1$. To simulate the random choice of $\ell$ in the circuit, you could simply take the $OR$ over all possible $\ell$ (their number is logarithmic in $2^k$, after all), so the probability of success becomes at least $1/8$ again. So rather than having $O(k\log s)$ hash functions with range $\{0,1\}$, you'll want $O(k)$ different sets of hash functions (each set having a different range), with $O(\log s)$ hash functions in each set.

  Why does this replacement give an equivalent SYM+ circuit ?

A SYM of AND (i.e, SYM+) circuit of size $K$ is essentially equivalent to having a multivariate polynomial $h : \{0,1\}^n \rightarrow \{0,\ldots,K\}$ with at most $K$ monomials, a lookup table $g : \{0,\ldots,K\}\rightarrow \{0,1\}$, and computing $g(h(x_1,\ldots,x_n))$. (For instance, a proof can be found in Beigel-Tarui.) The intuition is that each monomial in $f$ is an AND gate, and $g$ is the SYM gate. I say "essentially equivalent" because the multilinear polynomial $h$ could also have negative coefficients for some terms, and negative coefficents are not obviously implementable in SYM of AND. But I claim (and Beigel and Tarui claim) that this is not a problem. Think about it :)