- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Small set expansion in Johnson graphs (=slices of hypercube)
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Small set expansion in Johnson graphs (=slices of hypercube) Moshkovitz, Danna
Description
For natural numbers t<l<k, the nodes of the Johnson graph are sets of size l in a universe of size k. Two sets are connected if their intersection is of size t. The Johnson graph arises often in combinatorics and theoretical computer science: it represents a "slice" of the noisy hypercube, and it is the graph that underlies direct product tests as well as a candidate hard unique game. We prove that any small set of vertices in the Johnson graph either has near perfect edge expansion or is not pseudorandom. Here "not pseudorandom" means that the set becomes denser when conditioning on containing a small set of elements. In other words, we show that slices of the noisy hypercube -- while not necessarily small set expanders like the noisy hypercube -- can only have small non-expanding sets of a certain simple structure. The result was motivated, in part, by works of Dinur, Kindler, Khot, Minzer and Safra, which hypothesized and made partial progress on a similar result for the Grassmann graph, and showed that it would imply the proof of the 2 to 2 Conjecture in PCP. In turn, our result served as a crucial step towards the full result for the Grassmann graphs completed subsequently by Khot, Minzer and Safra. This is joint work with Subhash Khot, Dor Minzer and Muli Safra
Item Metadata
Title |
Small set expansion in Johnson graphs (=slices of hypercube)
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2018-08-13T11:03
|
Description |
For natural numbers t<l<k, the nodes of the Johnson graph are sets of size l in a universe of size k. Two sets are connected if their intersection is of size t. The Johnson graph arises often in combinatorics and theoretical computer science: it represents a "slice" of the noisy hypercube, and it is the graph that underlies direct product tests as well as a candidate hard unique game.
We prove that any small set of vertices in the Johnson graph either has near perfect edge expansion or is not pseudorandom. Here "not pseudorandom" means that the set becomes denser when conditioning on containing a small set of elements. In other words, we show that slices of the noisy hypercube -- while not necessarily small set expanders like the noisy hypercube -- can only have small non-expanding sets of a certain simple structure.
The result was motivated, in part, by works of Dinur, Kindler, Khot, Minzer and Safra, which hypothesized and made partial progress on a similar result for the Grassmann graph, and showed that it would imply the proof of the 2 to 2 Conjecture in PCP. In turn, our result served as a crucial step towards the full result for the Grassmann graphs completed subsequently by Khot, Minzer and Safra.
This is joint work with Subhash Khot, Dor Minzer and Muli Safra
|
Extent |
61.0
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: University of Texas at Austin
|
Series | |
Date Available |
2019-03-27
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0377620
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Researcher
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International