Skip to main content

An Invariance Principle for the Multi-slice, with Applications

Author(s): Braverman, Mark; Khot, Subhash; Lifshitz, Noam; Minzer, Dor

To refer to this page use:
Abstract: Given an alphabet size m∈N thought of as a constant, and k⃗ =(k1,…,km) whose entries sum of up n , the k⃗ -multi-slice is the set of vectors x∈[m]n in which each symbol i∈[m] appears precisely ki times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ( [m]n,μn ) in which μ(i)=ki/n . This answers a question raised by [21]. As applications of the invariance principle, we show: 1)An analogue of the “dictatorship test implies computational hardness” paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an r -ary CSP Pr for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most 2r+12r+o(1) satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size o(1) . 2)A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3)In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs H called ζ -forests, which is a natural extension of the well-studied case of matchings.
Publication Date: Feb-2022
Citation: Braverman, Mark, Khot, Subhash, Lifshitz, Noam and Minzer, Dor. "An Invariance Principle for the Multi-slice, with Applications." 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) (2022). doi:10.1109/FOCS52979.2021.00030
DOI: 10.1109/FOCS52979.2021.00030
ISSN: 1523-8288
EISSN: 2575-8454
Type of Material: Conference Article
Journal/Proceeding Title: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
Version: Author's manuscript

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.