Bjørn Kjos-Hanssen
Moderator
  • Member for 11 years, 3 months
  • Last seen this week
Entropy-like quantity
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
Al-Mubaid's Similarity Measure for Ontological Concepts
0 votes

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

View answer
Proof refutation: Amateur reviews of ambitious CoRR papers
6 votes

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

View answer
Are string palindrome questions practically interesting?
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
Term for a set that is not immune
Accepted answer
4 votes

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\}$. (...

View answer
Is the unbounded fan-in model realistic?
1 votes

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

View answer
Is the Chi-square divergence a Bregman divergence?
Accepted answer
4 votes

$\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
Chomsky-Schutzenberg Hierarchies explained for physicist (general)
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
Does $\exists\mathbb{R}=\mathbf{PSPACE}$?
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
Bootstrapping results that really bootstrap
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
Why colon to denote that a value belongs to a type?
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
Irreducible languages
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
What type of mathematical problems interesting for TCS researchers?
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
Validity of a modal argument about "vagueness"
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
Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?
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
The TOC Blog Aggregator is Offline
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
Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?
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
Is there any research on approximation of reals with computable numbers
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
Is algorithmic information theory still evolving?
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
Example where equivalence is easy but finding class representative is hard
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
Number of equivalence classes in regular languages as a function of DFA size
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 ...

View answer
Can boolean algebra be expressed in simply typed lambda caclulus?
3 votes

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

View answer
"Verifiable information": is this a known concept?
4 votes

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

View answer
Eilenberg's rational hierarchy of nonrational automata & languages -- where is it now?
4 votes

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

View answer
Function that is guaranteed to be one-way if one-way functions exist?
Accepted answer
12 votes

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

View answer
Which monotone Boolean functions are representable as thresholds on sums?
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
Confusion about a formal definition of PRAM consistency
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
Is there a useful notion of being “approximately computable”
Accepted answer
12 votes

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

View answer
Examples of nontrivial non-discriminatory functions
Accepted answer
1 votes

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

View answer
Sorting a programs instructions until it works
Accepted answer
6 votes

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

View answer