On non-optimally expanding sets in Grassmann graphs

被引：0
|
作者：
Irit Dinur
Subhash Khot
Guy Kindler
Dor Minzer
Muli Safra
机构：
[1] Weizmann Institute of Science,Department of Computer Science and Applied Mathematics
[2] New York University,Department of Computer Science, Courant Institute of Mathematical Sciences
[3] The Hebrew University of Jerusalem,School of Computer Science and Engineering
[4] Institute for Advanced Study,School of Computer Science
[5] Tel Aviv University,undefined
来源：
Israel Journal of Mathematics | 2021年 / 243卷
关键词：
D O I：
暂无
中图分类号：
学科分类号：
摘要：
We study the structure of non-expanding sets in the Grassmann graph. We put forth a hypothesis stating that every small set whose expansion is smaller than 1–δ must be correlated with one of a specified list of sets which are isomorphic to smaller Grassmann graphs. We develop a framework of Fourier analysis for analyzing functions over the Grassmann graph, and prove that our hypothesis holds for all sets whose expansion is below 3/4.
引用
收藏
页码：377 / 420
页数：43
相关论文
共 50 条
  • [1] On non-optimally expanding sets in Grassmann graphs
    Dinur, Irit
    Khot, Subhash
    Kindler, Guy
    Minzer, Dor
    Safra, Muli
    ISRAEL JOURNAL OF MATHEMATICS, 2021, 243 (01) : 377 - 420
  • [2] On Non-optimally Expanding Sets in Grassmann Graphs
    Dinur, Irit
    Khot, Subhash
    Kindler, Guy
    Minzer, Dor
    Safra, Muli
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 940 - 951
  • [3] REPROCESSING OF NON-OPTIMALLY EXPOSED HOLOGRAMS
    PHIPPS, GS
    ROBERTSON, CE
    TAMASHIRO, FM
    APPLIED OPTICS, 1980, 19 (05): : 802 - 811
  • [4] Perceptual Awareness of Optic Flows Paced Optimally and Non-optimally to Walking Speed
    Motyka, Pawel
    Kozlowska, Zuzanna
    Litwin, Piotr
    PERCEPTION, 2021, 50 (09) : 797 - 818
  • [5] Reactivation of Non-Optimally Orientated Faults Due to Glacially Induced Stresses
    Steffen, Rebekka
    Steffen, Holger
    TECTONICS, 2021, 40 (11)
  • [6] Determination of the Optimally Efficient Sets in Special Classes of Graphs
    Talmaciu, Mihai
    STUDIES IN INFORMATICS AND CONTROL, 2012, 21 (04): : 447 - 452
  • [7] On embeddings of Grassmann graphs in polar Grassmann graphs
    Pankov, Mark
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2016, 488 : 184 - 198
  • [8] On Independent Sets, 2-to-2 Games, and Grassmann Graphs
    Khot, Subhash
    Minzer, Dor
    Safra, Muli
    STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2017, : 576 - 589
  • [9] DECREASED EFFICIENCY OF DEEP SLEEP IN CHILDREN AND ADOLESCENTS WITH NON-OPTIMALLY CONTROLLED TYPE 1 DIABETES
    Ciljakova, M.
    Vojtkova, J.
    Durdik, P.
    Sujanska, A.
    Michalovicova, M.
    Pozorciakova, K.
    Lettrichova, J.
    Banovcin, P.
    DIABETES TECHNOLOGY & THERAPEUTICS, 2016, 18 : A42 - A43
  • [10] A self-stabilizing algorithm for optimally efficient sets in graphs
    Hedetniemi, Sandra M.
    Hedetniemi, Stephen T.
    Jiang, Hao
    Kennedy, K. E.
    McRae, Alice A.
    INFORMATION PROCESSING LETTERS, 2012, 112 (16) : 621 - 623
12345