The Library
Hypercontractivity on high dimensional expanders
Tools
Tools
Tools
Gur, Tom, Lifshitz, Noam and Liu, Siqi (2022) Hypercontractivity on high dimensional expanders. In: The 54th ACM Symposium on Theory of Computing (STOC 2022), Rome, Italy, 20-24 Jun 2022. Published in: STOC 2022 : Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing pp. 176-184. ISBN 9781450392648. doi:10.1145/3519935.3520004
|
PDF
WRAP-Hypercontractivity-high-dimensional-expanders-Gur-2022.pdf - Accepted Version - Requires a PDF viewer. Download (596Kb) | Preview |
Official URL: https://doi.org/10.1145/3519935.3520004
Abstract
We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities are effective for global functions, which are functions that are not significantly affected by a restriction of a small set of coordinates. As applications, we obtain Fourier concentration, small-set expansion, and Kruskal–Katona theorems for high dimensional expanders. Our techniques rely on a new approximate Efron–Stein decomposition for high dimensional link expanders.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Computer programming, Metamathematics , Algebra, Boolean, Fourier analysis | |||||||||
| Journal or Publication Title: | STOC 2022 : Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | |||||||||
| Publisher: | ACM | |||||||||
| ISBN: | 9781450392648 | |||||||||
| Official Date: | 10 June 2022 | |||||||||
| Dates: |
|
|||||||||
| Page Range: | pp. 176-184 | |||||||||
| DOI: | 10.1145/3519935.3520004 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Reuse Statement (publisher, data, author rights): | © ACM, 2022. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in STOC 2022 : Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, June 2022 http://doi.acm.org/10.1145//3519935.3520004 | |||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||
| Date of first compliant deposit: | 3 March 2022 | |||||||||
| Date of first compliant Open Access: | 3 March 2022 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | The 54th ACM Symposium on Theory of Computing (STOC 2022) | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Rome, Italy | |||||||||
| Date(s) of Event: | 20-24 Jun 2022 | |||||||||
| Related URLs: | ||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
