Linear and sublinear algorithms for graphlet sampling @SimonsInstituteTOC

Simons Institute | Linear and sublinear algorithms for graphlet sampling @SimonsInstituteTOC | Uploaded 2 months ago | Updated 1 hour ago
Marco Bressan (University of Milan)
https://simons.berkeley.edu/talks/marco-bressan-university-milan-2024-06-20
Extroverted Sublinear Algorithms

In this talk we will consider the following problem, known as graphlet sampling: given an integer k ≥ 3 and a simple graph G, sample a connected induced k-vertex subgraph of G uniformly at random. We will discuss algorithms for this problem with linear and sublinear preprocessing time, as well as some recent adaptations to the semi-streaming and MPC settings.

A tutorial on on neurosymbolic techniques

From Entropy to Artistry: on Thermodynamics and Generative AI

KiVA: Kid-inspired Visual Analogies for Large Multimodal Models

AI as a tool for discovery in animal communication

Automata-based approach for quantum circuit/program verification

A Quasi-Monte Carlo Algorithm for Smooth Kernel Evaluation

Maximum Matching in $O(log log n)$ Passes in Dynamic Streams

Distributed Controller Synthesis for Deadlock Avoidance

Linguistic Interaction in Humans and Machines