New answers tagged

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