Видео 18
Просмотров 669

Alexander Estes: The Submodular Adaptive Switching Problem

59:42

Diptarka Chakraborty: Tight Lower Bound on Equivalence Testing in Conditional Sampling Model

1:03:01

Jeff Giliberti: Online fractional knapsack in the random order model

40:30

Calum MacRury: Online Contention Resolution Schemes for the Matching Polytope of Graphs

57:24

D Ellis Hershkowitz: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies

55:44

Zongrui Zui: Optimal bounds on private graph approximation

53:52

Dung Nguyen: Differentially private exact recovery for stochastic block models

UMD Capital Area Theory Seminar - Fall 2024
Speaker: Dung Nguyen
Title: Differentially private exact recovery for stochastic block models
Date: September 19, 2024
Abstract: The goal of community detection in graphs is to recover the underlying labels/attributes of nodes (e.g., political affiliation) based on their connectivity. Stochastic block models (SBMs) are widely studied network models for community detection algorithms. In the standard form of an SBM, the n vertices (or nodes) of a graph are divided into multiple pre-determined communities (or clusters). Connections between pairs of vertices are generated randomly and independently with pre-defined probabilities, depending on the commu...

Видео

Alexander Estes: The Submodular Adaptive Switching Problem

59:42

Alexander Estes: The Submodular Adaptive Switching Problem

Просмотров 129 часов назад

UMD Capital Area Theory Seminar - Fall 2024 Speaker: Alexander Estes Title: The Submodular Adaptive Switching Problem Date: September 12, 2024 Abstract: We define and study an optimization problem called the adaptive switching problem. Suppose that there is a system with a finite number of configurations and a set of times, called a time scale, at which the configuration may be switched. The ti...

Diptarka Chakraborty: Tight Lower Bound on Equivalence Testing in Conditional Sampling Model

1:03:01

Diptarka Chakraborty: Tight Lower Bound on Equivalence Testing in Conditional Sampling Model

Просмотров 424 месяца назад

UMD Capital Area Theory Seminar - Spring 2024 Speaker: Diptarka Chakraborty Title: Tight Lower Bound on Equivalence Testing in Conditional Sampling Model Date: May 23, 2024 Abstract: We study the equivalence testing problem where the goal is to determine if the given two unknown distributions on [n] are equal or far in the total variation distance in the conditional sampling model wherein a tes...

$Jeff Giliberti: Online fractional knapsack in the random order model$ 40:30 $Jeff Giliberti: Online fractional knapsack in the random order model$

Jeff Giliberti: Online fractional knapsack in the random order model

Просмотров 105 месяцев назад

UMD Capital Area Theory Seminar - Spring 2024 Speaker: Jeff Giliberti Title: Online fractional knapsack in the random order model Date: April 4, 2024 Abstract: In this talk, I will present a simple 4.4-competitive algorithm for the online fractional knapsack problem under random arrivals. Despite being a classical combinatorial optimization problem, the fractional knapsack in the online setting...

Calum MacRury: Online Contention Resolution Schemes for the Matching Polytope of Graphs

57:24

Calum MacRury: Online Contention Resolution Schemes for the Matching Polytope of Graphs

Просмотров 365 месяцев назад

UMD Capital Area Theory Seminar - Spring 2024 Speaker: Calum MacRury Title: Online Contention Resolution Schemes for the Matching Polytope of Graphs Date: April 11, 2024 Abstract: Online Contention Resolution Schemes (OCRS's) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS's have led...

D Ellis Hershkowitz: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies

55:44

D Ellis Hershkowitz: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies

Просмотров 356 месяцев назад

UMD Capital Area Theory Seminar - Spring 2024 Speaker: D Ellis Hershkowitz Title: Polylogarithmic Universal Steiner Trees and Strong Sparse Partition Hierarchies Date: March 7, 2024 Abstract: This talk concerns universal Steiner trees (USTs). Informally, a UST is a single spanning tree that is a good approximation for every instance of Steiner tree. More formally, an α-approximate universal Ste...

Zongrui Zui: Optimal bounds on private graph approximation

53:52

Zongrui Zui: Optimal bounds on private graph approximation

Просмотров 227 месяцев назад

UMD Capital Area Theory Seminar - Spring 2024 Speaker: Zongrui Zui Title: Optimal bounds on private graph approximation Date: January 25, 2024 Abstract: We propose an efficient ε-differentially private (DP) algorithm, that given a simple weighted n-vertex, m-edge graph G with a maximum unweighted degree Δ(G), outputs a synthetic graph which approximates the spectrum with \tilde{O}(Δ(G)) bound o...

Da Qi Chen: Timeliness in Through Telephones: Approximating Information in Vector Clock Models

1:01:17

Da Qi Chen: Timeliness in Through Telephones: Approximating Information in Vector Clock Models

Просмотров 119 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Da Qi Chen Title: Timeliness in Through Telephones: Approximating Information Freshness in Vector Clock Models Date: December 8, 2023 Abstract: Consider an information dissemination problem where the root of an undirected graph constantly updates its information. The goal is to keep every other node in the graph about the root as freshly info...

Ama Koranteng: Relative Survivable Network Design

53:47

Ama Koranteng: Relative Survivable Network Design

Просмотров 189 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Ama Koranteng Title: Relative Survivable Network Design Date: November 17, 2023 Abstract: One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum k-Edge-Connected Spanning Subgraph problem (k-ECSS), as well as nonuniform demands such as the ...

Eklavya Sharma: Fair Allocation of Indivisible Goods

45:00

Eklavya Sharma: Fair Allocation of Indivisible Goods

Просмотров 3610 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Eklavya Sharma Title: Fair Allocation of Indivisible Goods Date: October 27, 2023 Abstract: This talk is about the problem of fairly allocating indivisible goods among multiple agents. Envy-freeness up to any item (EFX) and maximin share fairness (MMS) are arguably the most compelling fairness concepts proposed till now. Unfortunately, despit...

Magdalen Dobson: Nearest Neighbors from Theory to Practice

56:03

Magdalen Dobson: Nearest Neighbors from Theory to Practice

Просмотров 2310 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Magdalen Dobson Title: Nearest Neighbors from Theory to Practice Date: November 10, 2023 Abstract: This talk will cover recent advances, both theoretical and practical, in high-dimensional approximate nearest neighbor search. First, we introduce partition-based methods such as locality-sensitive hashing, which work by partitioning a high-dime...

Aadirupa Saha: Building Personalized Decision Models with Federated Human Preferences

1:02:39

Aadirupa Saha: Building Personalized Decision Models with Federated Human Preferences

Просмотров 4010 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Aadirupa Saha Title: Building Personalized Decision Models with Federated Human Preferences Date: November 9, 2023 Abstract: Customer statistics collected in several real-world systems have reflected that users often prefer eliciting their liking for a given pair of items, say (A,B), in terms of relative queries like: "Do you prefer Item A ov...

Shangdi Yu: Framework for Parallel Hierarchical Agglomerative Clustering

1:02:13

Shangdi Yu: Framework for Parallel Hierarchical Agglomerative Clustering

Просмотров 2010 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Shangdi Yu Title: Framework for Parallel Hierarchical Agglomerative Clustering Date: October 30, 2023 Abstract: We study the hierarchical clustering problem, where the goal is to produce a dendrogram that represents clusters at varying scales of a data set. We propose the ParChain framework for designing parallel hierarchical agglomerative cl...

Sruthi Gorantla: Ex-Post Group Fairness and Individual Fairness in Ranking

45:12

Sruthi Gorantla: Ex-Post Group Fairness and Individual Fairness in Ranking

Просмотров 4911 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: Sruthi Gorantla Title: Ex-Post Group Fairness and Individual Fairness in Ranking Date: October 10, 2023 Abstract: Fair ranking tasks, which ask to rank a set of items to maximize utility subject to satisfying group-fairness constraints, have gained significant interest in algorithmic fairness, information retrieval, and machine learning liter...

George Li: Near-Optimal Differentially Private k-Core Decomposition

54:59

George Li: Near-Optimal Differentially Private k-Core Decomposition

Просмотров 11211 месяцев назад

UMD Capital Area Theory Seminar - Fall 2023 Speaker: George Li Title: Near-Optimal Differentially Private k-Core Decomposition Date: October 20, 2023 Abstract: Recent work by Dhulipala, Liu, Raskhodnikova, Shi, Shun, and Yu [DLRSSY, FOCS 2022] initiated the study of the relationship between parallel and distributed graph algorithms and differentially private graph algorithms, giving the best kn...