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

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

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

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \...

In a way, if we imagine time continuing indefinitely then with probability 1, random numbers, obtained from I guess the collapse of the wave function in quantum mechanics, will form a non-computable ...

I suppose the scientific consensus is that while we are very far from there, in principle a digital artificial intelligence could mimic a human intelligence. For some recent work on the Church-...

Archdeacon's survey Topological Graph Theory was almost mentioned already: http://www.math.u-szeged.hu/~hajnal/courses/PhD_Specialis/Archdeacon.pdf

Predicting the stock market is hard! Can TCS make this sentiment more formal? If stocks are modeled as random variables like geometric Brownian motions then prediction becomes a concern of ...