Paley graph extractor conjecture

Let pp be an odd prime, let n=log2pn=\lceil\log_2 p\rceil, and let Extp:Fp×Fp{0,1}\operatorname{Ext}_p:\mathbb{F}_p\times\mathbb{F}_p\to\{0,1\} be the Paley graph extractor defined from the quadratic character of Fp\mathbb{F}_p. A two-source (k,ϵ)(k,\epsilon)-extractor is an extractor for two independent sources on {0,1}n\{0,1\}^n whose min-entropy is at least kk and whose error is at most ϵ\epsilon. Paley graph extractor conjecture. For every 0<α<10<\alpha<1, Extp\operatorname{Ext}_p is a two-source (αn,ϵ)(\alpha n,\epsilon)-extractor for some negligible ϵ\epsilon. This is the conjecture introduced by Chor and Goldreich and is supported in the paper by the Paley graph conjecture; it remains open.

Sources & referencesView supporting material

Primary source

Shohei Satake, “On the Paley RIP and Paley graph extractor”, arXiv:2405.08608 (2024).

Additional references

2 papers in this index state this conjecture (2023–2024). The statement above is taken from the most recent of them; the others are arXiv:2309.09124.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.