dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Graph Sparsification and Kadison-Singer Problem

  • Start Date: March 1, 2023
  • Event Start Time: 11:00 AM
  • Event End Time: 12:00 PM
  • Seminar Series: Theoretical Computer Science Seminar
  • Presenter(s): Surya Teja Gavva - Rutgers University
  • Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
  • Event Additional Info: <p>See:&nbsp;<a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p>
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    The solution to the Kadison-Singer problem proves the existence of a subgraph that acts as a spectral sparsifier for a given graph. In this talk, we explore the question of finding such a subgraph efficiently. We provide explicit signings on some classes of graphs and show some algorithms to find the subgraphs in special graphs like circulant graphs and random regular graphs. Particularly interesting is the variety of ideas from Fourier analysis, discrepancy theory, random matrices, and the contiguity of random graph models needed to analyze the problem.

    Based on joint work with Peng Zhang.