New answers tagged reference-request
0
I'm going to partially answer point 2 here. If you allowed the inductive type to appear even strictly positively in another inductive's index, and you had impredicative Prop, you could derive an inconsistency through an equality type with a type that does occur negatively, as Dan stated in the comments. Here's an example in Coq, with the inductive type ...
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 = ...
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
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.
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.
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 ...
4
Recall that a distribution $Y$ over $\{0, 1\}^n$ is called $\epsilon$-biased if for every nonempty set $P \subseteq [n]$, we have
$$
\left|\mathbb{E}[\oplus_{i \in P} Y_i] - \frac{1}{2}\right| \leq \frac{\epsilon}{2}.
$$
In other words, an $\epsilon$-biased distribution is a primitive kind of pseudorandom generator: it fools parity functions with error $\...
Top 50 recent answers are included
