Bjørn Kjos-Hanssen
Moderator
• Member for 11 years, 3 months
• Last seen this week

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".

There is a whole study of hierarchical clustering. You start with a discrete set of nodes and iteratively connect the ones that are closest according to some similarity measure. The branches of the ...

If you make an arXiv trackback you will not be ignored, in the sense that future readers of the ambitious arXiv paper may check the trackbacks. You even get a mild form of peer review for your posts, ...

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 ...

If a set $A$ is Turing reducible to a set $B$ then we say that $B$ computes $A$. Every noncomputable set $A$ computes an immune set, namely $\hat A = \{\sigma: \sigma \text{ is a prefix of }A\}$. (...

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) .

$\chi^2$-divergence is not a Bregman divergence. I'll show it for sample size $n=1$. We would have $$(x-y)^2/x=f(x)-f(y)-f'(y)(x-y)$$ If $y=0$ and $x>0$ this says $$x=f(x)-f(0)-xf'(0),$$ $$1=\... View answer 3 votes \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 ... View answer Accepted answer 1 votes 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 ... View answer 4 votes Huang's recent proof of A', the Sensitivity Conjecture, involved proving an A known to imply it. See Aaronson's blog: From pioneering work by Gotsman and Linial in 1992, it was known that to ... View answer 5 votes Björn, There's probably an earlier reference but for one thing, the colon was used in the Pascal programming language: View answer Accepted answer 1 votes 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". ... View answer 3 votes 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 ... View answer Accepted answer 1 votes How about just a blanket statement with no assumptions: A and B may be the same part of C This would seem to be valid by the same reasoning! However it is only so if "may" ranges over all models ... View answer Accepted answer 7 votes Chaitin in his 1976 paper Chaitin, Gregory J., Information-theoretic characterizations of recursive infinite strings, Theor. Comput. Sci. 2, 45-48 (1976). ZBL0328.02029. studied sets such that ... View answer Accepted answer 15 votes In 2007, Princeton professor Arvind Narayanan created the TOC Blog Aggregator. In 2018, CSTheory.se Moderator Suresh Venkatasubramanian (@SureshVenkat) stepped down from moderating here, but took ... View answer 3 votes 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-... View answer 4 votes It's funny you should ask, because computability and diophantine approximation has actually been a popular topic in recent years. In particular Becher and Slaman and coauthors have many results and ... View answer 7 votes A modern tweak on algorithmic information theory is algorithmic randomness which was developed intensively in the 2000s (2009-2009) and is still quite active. The most notorious open problem there ... View answer 1 votes A famous example from descriptive set theory: Let us define an equivalence relation \sim on \mathbb R by$$r\sim s\iff r-s\in\mathbb Q.$$This is a rather "easy" equivalence relation, in ... View answer 1 votes Answer to Question 1, What is the smallest n for which |T/{\sim}|=|T|? We have$$n=\max_{|w|=|x|=s,\\ w\ne x}\mathrm{sep}(w,x) where $\mathrm{sep}(w,x)$ is the smallest number of states in ...

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

$K\subseteq\{0,1\}^\omega$ is $\mathsf{R}$-verifiable if and only if $K$ is a $\Pi^0_1$ class (in Cantor space), a concept that has been studied extensively in computability-theory. They are also ...

An accepted answer to this question was given by J.-E. Pin at Mathematics Stack Exchange.

Yes, such a function was found by Levin himself, published somewhat recently: The tale of one-way functions. Problems of Information Transmission (= Problemy Peredachi Informatsii), 39(1):92-103, ...

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 ...

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 ...

If the family function $f(x,n)=f_n(x)$ is computable then these are exactly the $\Delta^0_2$ functions, or equivalently, the functions that are Turing reducible to the halting set $0'$, which are very ...

Let $n=1$. Let $\mu$ be the usual Lebesgue length measure on $[1/2,1]$, and let $\mu$ be the negative of the usual Lebesgue length measure on $[0,1/2]$. In particular, Lebesgue measure is $|\mu|$. ...

This can be done by running all the $n!$ permutations in parallel and wait for one of them to output $1,2,6,24$ on inputs $1,2,3,4$. (Of course, that does not guarantee that you found the correct ...