1/2

🧠 Что такое Expander-графы и почему это важно?

Помню лет 10-15 назад тема экспандер-графов была очень сильно на слуху. Не знаю как сейчас, вспомнил в связи с нейросетями и их #Interpretability, но даже не знаю, применяются ли там экспандеры...

Однако тема очень прикольная даже независимо от применений...

Expander-граф — это особый тип графа, в котором каждая небольшая группа узлов сильно связана с остальными. То есть даже если случайным образом выбрать 10-20% всех вершин, эти вершины будут иметь множество связей с оставшимися. Граф сохраняет свою «связность» даже при случайном удалении больших частей узлов или рёбер.

📌 Почему это важно? Это имеет большое значение:

— В криптографии: Expander-графы обеспечивают устойчивость к сбоям и атакам.
— В алгоритмах: Они помогают моделировать надёжные и устойчивые системы.
— В теории сложности: Они играют важную роль в решении задач, таких как SAT, и в дискуссиях о проблеме P vs NP.

#ExpanderGraphs #Algorithms #Complexity #SAT #PvsNP

Продолжение 👇

2/2. продолжение. начало тут.

Некоторые подходы к решению задачи SAT используют Expander-графы для создания «жёстких» экземпляров — таких, которые сложно упростить даже при использовании приближённых методов. Это позволяет лучше понять границы между «быстро решаемыми» и «на практике неразрешимыми» задачами.

🔍 Пример: экспандер из 100 узлов, где каждый узел связан с 10 другими. Даже если удалить 20-30% рёбер, граф часто остаётся связанным. Это и есть эффект расширения (expansion).

Кроме того, В таких графах информация распространяется быстро, даже если начинается только с небольшой части узлов. Это свойство делает их так же идеальными для моделирования процессов, таких как заражение, распространение вирусов, распространение новостей и многого другого.

⚙️ Вообще, не зависимо от применений, тут много очень прикольных свойств возникет и это всё не так тривиально, как может показаться на первый взляд, имхо. Надо бы посмотреть более пристально в сторону экспандеров... Думаю, что продолжение на эту тему следует...

#ExpanderGraphs #Algorithms #Complexity #SAT

@easy_about_complex