Counterexample to majority optimality in NICD with erasures
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911227855241216 |
|---|---|
| author | Ivanisvili, Paata Xie, Xinyuan |
| author_facet | Ivanisvili, Paata Xie, Xinyuan |
| contents | We asked GPT-5 Pro to look for counterexamples among a public list of open problems (the Simons ``Real Analysis in Computer Science'' collection). After several numerical experiments, it suggested a counterexample for the Non-Interactive Correlation Distillation (NICD) with erasures question: namely, a Boolean function on 5 bits that achieves a strictly larger value of $\mathbb{E}|f(z)|$ than the 5-bit majority function when the erasure parameter is $p=0.40.$ In this very short note we record the finding, state the problem precisely, give the explicit function, and verify the computation step by step by hand so that it can be checked without a computer. In addition, we show that for each fixed odd $n$ the majority is optimal (among unbiased Boolean functions) in a neighborhood of $p=0$. We view this as a little spark of an AI contribution in Theoretical Computer Science: while modern Large Language Models (LLMs) often assist with literature and numerics, here a concrete finite counterexample emerged. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_20013 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counterexample to majority optimality in NICD with erasures Ivanisvili, Paata Xie, Xinyuan Probability Computational Complexity Information Theory Combinatorics 68Q87, 94A15, 06E30 We asked GPT-5 Pro to look for counterexamples among a public list of open problems (the Simons ``Real Analysis in Computer Science'' collection). After several numerical experiments, it suggested a counterexample for the Non-Interactive Correlation Distillation (NICD) with erasures question: namely, a Boolean function on 5 bits that achieves a strictly larger value of $\mathbb{E}|f(z)|$ than the 5-bit majority function when the erasure parameter is $p=0.40.$ In this very short note we record the finding, state the problem precisely, give the explicit function, and verify the computation step by step by hand so that it can be checked without a computer. In addition, we show that for each fixed odd $n$ the majority is optimal (among unbiased Boolean functions) in a neighborhood of $p=0$. We view this as a little spark of an AI contribution in Theoretical Computer Science: while modern Large Language Models (LLMs) often assist with literature and numerics, here a concrete finite counterexample emerged. |
| title | Counterexample to majority optimality in NICD with erasures |
| topic | Probability Computational Complexity Information Theory Combinatorics 68Q87, 94A15, 06E30 |
| url | https://arxiv.org/abs/2510.20013 |