High-dimensional expansion in random geometric graphs

Speaker: Sidhanth Mohanty , MIT

Date: Wednesday, October 11, 2023

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type: Seminar

Room Description: 32-G575

Host: Noah Golowich, MIT

Contact: Noah Golowich, nzg@csail.mit.edu

Relevant URL:

Speaker URL: https://sidhanthm.com/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Sidhanth Mohanty: High-dimensional expansion in random geometric graphs

Abstract: High-dimensional expansion is a generalization of expansion to hypergraphs where the expansion of certain random walks are witnessed by local neighborhoods.

This talk is on the topic of constructing natural probability distributions over sparse high-dimensional expanders (HDXes). On one hand, (standard/1-dimensional) sparse expanders are plentiful, since a constant degree random graph is an expander with high probability. On the other hand, most natural random models over hypergraphs fail to exhibit 2-dimensional expansion unless the average degree exceeds sqrt(number of vertices).

However, sparse HDXes are known to exist due to algebraic and number theory based construction. We describe some progress towards constructing sparse HDXes based on random geometric graphs on the unit sphere.

Based on joint work with Siqi Liu, Tselil Schramm, and Elizabeth Yang. https://arxiv.org/abs/2210.00158

Research Areas:
Algorithms & Theory

Impact Areas:
Big Data

See other events that are part of the Algorithms and Complexity Seminar 2023.

Created by Noah Golowich Email at Tuesday, October 10, 2023 at 2:04 PM.