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

Cut Query Algorithms Using Star Contraction

  • Start Date: October 19, 2022
  • Event Start Time: 11:00 AM
  • Event End Time: 12:15 PM
  • Seminar Series: Theoretical Computer Science Seminar
  • Presenter(s): Yuval Efron - Columbia University
  • Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
  • Presentation Type: Stand Alone Presentation
  • Abstract:

    In this talk I'll discuss a simple combinatorial randomized procedure, which is styled Star Contraction. Then, I'll discuss applications of this technical procedure, with the central one being a randomized cut query algorithm that with constant probability computes the edge connectivity of a simple graph with O(n) cut queries. I'll also discuss applications to quantum cut queries and the semi-streaming model. Finally, I'll talk about some interesting open problems.
    Based on work which will appear in FOCS 2022