$\Sigma$ is the alphabet of the grammar and so $\Sigma^k$ is the set of words of length $k$ from that alphabet. Finally $L\cap\Sigma^k$ is then the set of such words that are in $L$, i.e., that are ...

Let us say I am able to give an algorithm which classifies all modules (algebraic structure) of some rank. Will that be interesting to TCS researchers? Roughly speaking... It will be interesting to ...

A counterexample to this Murphy's Law could actually be the famous paper Baker, Theodore; Gill, John; Solovay, Robert, Relativizations of the $\cal P=?\cal N\cal P$ question, SIAM J. Comput. 4, 431-...

The OP wrote above that the question is answered by a post on @AndrejBauer's blog.

In the binary case they are two of the seven truth-table reducibilities $$m, btt(1), c, d, p, \ell, tt$$ based on polynomial clones. See Figure 1 in Culver's paper https://link.springer.com/article/10....

Well, if the philosophers are following the exact same strategy and there is nothing to distinguish them (like who is closest to the door etc.) then they will do exactly the same and deadlock must ...

Consider the case $n=3$. There are 27 possible runs of the algorithm. Let's see where the first vector ends up ($X_1$) in each case, and where the 2nd ends up ($X_2$). $$\text{Format:}\quad\sigma_1\... View answer 3 votes Since the article seems to be an effort at popularization of science, it probably made sense to the author to not discuss the details of that point. It seems analogous to defining uniform continuity ... View answer Accepted answer 3 votes No, we get counterexamples by considering resource-bounded randomness. In fact the gap between c.e. and \mathsf{CFL} is wide. Let R be exponential-time random. Then R is \mathsf{NP}-immune, i.... View answer Accepted answer 3 votes Yes, that's the Ideal Membership Problem and it is solved using Gröbner bases. View answer 3 votes I wasn't able to figure out whether \mathrm{GI}(1/2)\in\mathsf P, but here is a weaker result: The languages \mathrm{GI}(1/2) and \mathrm{GI} are not \mathsf P-inseparable. Proof: It suffices ... View answer Accepted answer 3 votes I guess ((AB)(CD)) is actually two ways, because you could do either (AB) or (CD) first. View answer Accepted answer 3 votes Note that from  m (0)  you can compute a version of Chaitin's \Omega . Moreover  m (x)  is left-c.e. uniformly in  x . So  m  has Turing degree 0'. View answer 3 votes When we say that a monotone machine is a set L of pairs of strings (x,y), the first component x is the part of the input tape being read in order to produce the output y. This set is c.e. (... View answer 3 votes There is also Microsoft Academic Search if you're looking for graphical display of coauthor graphs, although it does not appear to be a finished product content-wise. View answer Accepted answer 2 votes It's the \alpha^{\mathrm{th}} moment of the Tribus surprisal. This generalizes the statement that entropy = expected surprisal. Or in Ross's textbook, "expected surprise". View answer Accepted answer 2 votes I had a use for palindromes as follows: A string of length n and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal. Now ... View answer Accepted answer 2 votes It was mentioned in the comments that these are the positive threshold functions. As for other characterizations, I found the following to be interesting. Suppose we have a positive threshold ... View answer 2 votes When they define PRAM (page 11 of the arxiv preprint) they actually state that vis is a partial order (in particular, transitive): We define PRAM consistency by requiring the visibility partial ... View answer Accepted answer 2 votes Edit: answer obeying the "spirit" of the question: Let's use the rules$$S(xy)\to A(x,y)A(x,ayb)\to A(x,x)A(y,y)A(x,x)\to\epsilon$$Then we can derive S(aabb)\to A(a,abb)\to A(a,a)A(b,b)\... View answer 2 votes Regarding (3), yes, if a graph M has two vertex disjoint non-planar induced subgraphs G and H, then G\cup H (and hence M) is not toroidal. I don't know a reference but here's a proof ... View answer 2 votes This should work fine inasmuch as if f is now a random function, then you just get the expected sensitivity:$$\mathbb E s(f, x) = \sum_{y \in N(x)} \mathbb E I(f(x) \neq f(y)) = \sum_{y \in N(x)} \...

Assuming that pseudorandom generators and secure one‐way permutations exist, it follows that $\mathsf{NP}$‐complete sets are not $\mathsf P$‐immune. Christian Glaßer, A. Pavan, Alan L. Selman, and ...

As commenters @Lwins and @SashaNikolov have already stated, it is non-computably hard to compute a function as slow-growing as $f$. (So no really humanly comprehensible rate can be given.) Namely, ...

Let $J^A(e)$ be the output of the $e$th Turing machine equipped with oracle $A$, on input $e$. Here $J$ stands for "jump". (In case of non-halting, $J^A(e)$ is undefined.) An oracle $A$ is jump-...

Case 1. The distributions $U_n$ and $V_n$ are computable in the sense that we can eventually tell if your displayed inequality is violated, for fixed $n$ and $z$. It seems the answer to the first ...

Don't forget that even though the fan-in is unbounded, the number of gates is polynomially bounded in the number of variables $n$ (in the definition of $\mathsf{AC}$ for instance) .

The issue may be whether or not Schwartz and Sharir show that motion plan existence is many-one polynomial time reducible to $\exists\mathbb R$. If they need several queries to $\exists\mathbb R$ for ...

Here's a counterexample to this: call a language L "reducible" if it can be written as $L = A \cdot B$ with $A \cap B = \emptyset$ and $|A|,|B|>1$, otherwise call the language "irreducible". ...