5

If you look at the MNSW proof carefully, the base case can be taken to be the trivial fact that a $0$-round protocol for $\textrm{GT}_n$ with $n = 1$ requires one bit of communication. If the goal is simply to convince oneself from first principles that $\textrm{R}^\to(\textrm{GT}_n) = \Omega(n)$, this is immediate by reduction from the AUGMENTED-INDEX ...


5

I don't know about a survey, but I've found a recent PhD thesis, which seems to be well written: Heinlein, Matthias (2019): Erdős-Pósa properties. Open Access Repositorium der Universität Ulm. Dissertation. http://dx.doi.org/10.18725/OPARU-11828 The first chapter gives a summary of the problem, known proof techniques and provides references to recent ...


3

The Ph.D. thesis of Pranab Sen (http://www.tcs.tifr.res.in/~pgdsen/pages/phdthesis/thesis.pdf) provides a $\Omega(n^{1/t}t^{-2})$ lower bound for $t$ round bounded error CC for Greater-than. I think the proof covers the case when $t=1$. In addition, there is a $\Omega(n^{1/t}t^{-3})$ for quantum CC in the same thesis.


3

I met once a similar notion to what you want in one paper by Mark Zhandry's paper under the name $k$-wise equivalent. I cannot find further references or pointers from that paper, but I think this name nicely describes your something. Concretely, the original definition in the paper is about the distributions over the functions $f: X\rightarrow Y$, and ...


1

Here is an example exploiting positivity of an index to prove false: module Whatever where open import Level using (Level) open import Relation.Binary.PropositionalEquality open import Data.Empty variable ℓ : Level A B : Set ℓ data _≅_ (A : Set ℓ) : Set ℓ → Set ℓ where trefl : A ≅ A Subst : (P : Set ℓ → Set ℓ) → A ≅ B → P A → P B Subst P trefl PA = ...


1

Try these: Quantum Error Correction by Todd Brun Quantum Error Correction: An Introductory Guide by Joschka Roffe For surface codes, Dan Browne's lecture notes might help.


Only top voted, non community-wiki answers of a minimum length are eligible