Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > 2-TO-2 GAMES THEOREM:
Reports tagged with 2-to-2 Games Theorem:
TR18-078 | 23rd April 2018
Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

Small Set Expansion in The Johnson Graph

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers
t < l < k, the nodes of the 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 ... more >>>




ISSN 1433-8092 | Imprint