Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.16627 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918080396918784 |
|---|---|
| author | Alaoui, Ahmed El Gamarnik, David |
| author_facet | Alaoui, Ahmed El Gamarnik, David |
| contents | We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the set of solutions to the symmetric binary perceptron model at any constraint-to-variable density. This result is in contrast to the question of finding \emph{a} solution to the same problem, where efficient (and stable) algorithms are known to succeed at sufficiently low density. This result suggests that the solutions found efficiently -- whenever this task is possible -- must be highly atypical, and therefore provides an example of a problem where search is efficiently possible but approximate sampling from the set of solutions is not, at least within these two classes of algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16627 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hardness of sampling solutions from the Symmetric Binary Perceptron Alaoui, Ahmed El Gamarnik, David Probability Data Structures and Algorithms We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the set of solutions to the symmetric binary perceptron model at any constraint-to-variable density. This result is in contrast to the question of finding \emph{a} solution to the same problem, where efficient (and stable) algorithms are known to succeed at sufficiently low density. This result suggests that the solutions found efficiently -- whenever this task is possible -- must be highly atypical, and therefore provides an example of a problem where search is efficiently possible but approximate sampling from the set of solutions is not, at least within these two classes of algorithms. |
| title | Hardness of sampling solutions from the Symmetric Binary Perceptron |
| topic | Probability Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.16627 |