Marcin Kotowski
  • Member for 11 years, 2 months
  • Last seen more than 2 years ago
Drunken birds vs drunken ants: random walks between two and three dimensions
Accepted answer
17 votes

Probability on Trees and Networks by Peres and Lyons mentions this in Chapter 2 (page 50): One way to make sense of this is to ask about the type of spaces intermediate between $\mathbb{Z}^2$ and $\...

View answer
How would I go about learning the underlying theory of the Coq proof assistant?
14 votes

As for typed lambda calculus, intuitionistic logic, various proof systems and Curry-Howard isomorphism, which are all parts of Coq mathematical background, I strongly recommend "Lectures on the Curry-...

View answer
Nonlocal Games and Quantum Communication
11 votes

What about "Consequences and Limits of Nonlocal Strategies" by Cleve, Hoyer, Toner and Watrous? It gives a pretty good introduction and then you can check e.g. other paper by Watrous

View answer
On the relation for the Myhill-Nerode theorem/syntactic monoid of a language
Accepted answer
10 votes

The syntactic monoid of a language $L$, which is $\Sigma^{\ast}$ quotiented by $\sim_{L}$, is usually bigger than the set of equivalence classes of $\Sigma^{\ast}$ quotiented by $\equiv_{L}$. ...

View answer
What kind of mathematical background is needed for complexity theory?
7 votes

Representation theory of finite groups (also over finite fields) can be surprisingly useful for various tasks, including: matrix multiplication algorithms (Cohn--Kleinberg-Szegedy-Umans) ...

View answer
What's the point of $\eta$-conversion in lambda calculus?
7 votes

$\eta$-reduction captures the notion of extensionality - two functions are considered equal iff they give the same outputs on the same inputs. One way of formalizing this notion is the following: if ...

View answer
Small steps for better TCS conferences?
6 votes

(this is not specific to TCS conferences, but would work for better conferences in general) A nice idea I saw in a mathematical conference for young researchers is asking every participant to write a ...

View answer
Quantum Bell-Type Inequalities
Accepted answer
6 votes

Werner and Wolf's paper "Bell inequalities and entanglement" (http://arxiv.org/abs/quant-ph/0107093) gives a brief and readable introduction and discussion of Bell inequalities as faces of correlation ...

View answer
Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?
3 votes

First, prepare a state $\frac{1}{\sqrt{3}}((-1)^{f(0)}|00\rangle + (-1)^{f(1)}|01\rangle + |11\rangle)$ (which can be done easily using single black-box query and unitaries). Notice that two such ...

View answer
What is an accessible introduction to Percolation Theory?
2 votes

Lyons and Peres' "Probability on Trees and Networks" (available here) has a few nice chapters on percolation (and the whole book is a good recommendation for anyone interested in probability and ...

View answer