ARC Colloquium: Kuikui Liu(Univ. of Washington)

Event Details
  • Date/Time:
    • Monday January 27, 2020
      11:00 am - 12:00 pm
  • Location: Groseclose 402
  • Phone:
  • URL:
  • Email:
  • Fee(s):
    N/A
  • Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model - Groseclose 402 at 11:00am

Full Summary: No summary paragraph submitted.

Algorithms & Randomness Center (ARC)

Kuikui Liu (Univ. of Washington)

Monday, January 27, 2020

Groseclose 402 - 11:00 am

 

Title:  Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model

Abstract: 

We say a probability distribution µ is spectrally independent if an associated correlation matrix has a bounded largest eigenvalue for the distribution and all of its conditional distributions. We prove that if µ is spectrally independent, then the corresponding high dimensional simplicial complex is a local spectral expander. Using a line of recent works on mixing time of high dimensional walks on simplicial complexes [KM17; DK17; KO18; AL19], this implies that the corresponding Glauber dynamics mixes rapidly and generates (approximate) samples from µ. As an application, we show that natural Glauber dynamics mixes rapidly (in polynomial time) to generate a random independent set from the hardcore model up to the uniqueness threshold. This improves the quasi-polynomial running time of Weitz’s deterministic correlation decay algorithm [Wei06] for estimating the hardcore partition function, also answering a long-standing open problem of mixing time of Glauber dynamics [LV97; LV99; DG00; Vig01; Eft+16].

 Joint work with Nima Anari and Shayan Oveis Gharan

----------------------------------

Speaker's Webpage

Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836

Click here to subscribe to the seminar email list: arc-colloq@Klauscc.gatech.edu

Additional Information

In Campus Calendar
No
Groups

ARC

Invited Audience
Postdoc, Public, Graduate students
Categories
Seminar/Lecture/Colloquium
Keywords
No keywords were submitted.
Status
  • Created By: Francella Tonge
  • Workflow Status: Published
  • Created On: Jan 10, 2020 - 10:17am
  • Last Updated: Jan 13, 2020 - 2:00pm