Small set expansion hypothesis
id:
small-set-expansion-hypothesis-246-2305213
title:
Small set expansion hypothesis
text:
The small set expansion hypothesis or small set expansion conjecture in computational complexity theory is an unproven computational hardness assumption. Under the small set expansion hypothesis it is assumed to be computationally infeasible to distinguish between a certain class of expander graphs called "small set expanders" and other graphs that are very far from being small set expanders. This assumption implies the hardness of several other computational problems, and the optimality of cer
brand slug:
wiki
category slug:
encyclopedia
description:
Computational hardness assumption
original url:
https://en.wikipedia.org/wiki/Small_set_expansion_hypothesis
date created:
date modified:
2024-01-08T09:41:42Z
main entity:
{"identifier":"Q117322981","url":"https://www.wikidata.org/entity/Q117322981"}
image:
fields total:
13
integrity:
14