banner green v2

Programme

Please find the programme for each day of the conference below.

Wednesday 1 June 2022

MA100

Time

Event/Speaker

Talk Title

8.30-9.00

Welcome

 

9.00-10:30

Richard Peng

A Survey on Fast Flow Algorithms

 

Vera Traub

A Better-Than-2 Approximation for Weighted Tree Augmentation

10.30-11:00

Coffee Break

 

11:00-12:30

Mehtaab Sawhney

Discrepancy Minimization via a Self-Balancing Walk

 

Jason Li

Deterministic Mincut in Almost-Linear Time

 

Peyman Afshani

Lower Bounds for Semialgebraic Range Searching and Stabbing Problems

12:30-14:00

Lunch

 

14:00-15:30

Contributed Talks

 

15:30-16:30

Coffee break and poster session

 

16:30-19.00

Thatchaphol Saranurak

A Survey on Expander Graphs and their Usage in Dynamic Algorithms

 

Guy Blelloch

Parallel Minimum Cuts in %%O(m log^2(n))%% Work and Low Depth

 

John Kallaugher

A Quantum Advantage for a Natural Streaming Problem

 

Mahsa Eftekhari

A Time and Space Optimal Stable Population Protocol Solving Exact Majority

19:00-21:00

Reception

 

 

Contributed Talks

contributions

 Sukanya Pandey

Planar Multiway Cut with Terminals on Few Faces

 Javier Cembrano

Multidimensional Apportionment through Discrepancy Theory

 Raphael Meyer

Hutch++: Optimal Stochastic Trace Estimation

 Jakub Tarnawski

Online Edge Coloring via Tree Recurrences and Correlation Decay

 Marcel Dall'Agnol

A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy

 Sathyawageeswar Subramanian

Sublinear quantum algorithms for estimating von Neumann entropy

 Evangelos Kipouridis

Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor

 Spyros Angelopoulos

 Online Search With Best-Price and Query-Based Predictions

 Andreas Emil Feldmann

 The Parameterized Complexity of the Survivable Network Design Problem

 Hugo Rincon Galeana

 Continuous Tasks and the Asynchronous Computability Theorem

 Henrik Lievonen

 Online Algorithms with Lookaround

Dimitrios Los

 Balanced Allocations: Relaxing (without) the Second Choice

 Karol Węgrzycki

 Improving Schroeppel and Shamir's algorithm for subset sum via orthogonal vectors

 Gopinath Mishra

 Faster Counting and Sampling Algorithms using Colorful Decision Oracle

 Nikhil Ayyadevara

 The Randomized Competitive Ratio of Weighted k-server is at Least Exponential

Adam Polak

 Knapsack and Subset Sum with Small Items

 Suman Sourav

 Latency, Capacity, and Distributed Minimum Spanning Trees

Chen Amiraz

 Distributed sparse normal means estimation with sublinear communication

Thursday 2 June 2022

MA103

Time

Event/Speaker

Talk Title

8.30-9:00

Coffee

 

9:00-10:30

Amir Abboud

A Survey on Fine Grained Complexity

 

Joseph Mitchell

Approximating Maximum Independent Set for Rectangles in the Plane

10:30-11:00

Coffee break

 

11:00-12:30

Merav Parter

New Diameter Reducing Shortcuts: Breaking the %%O(\sqrt{n})%% Barrier

 

Shay Moran

A Theory of Universal Learning

 

Jan Vondrak

A Constant-factor Approximation Algorithm for Nash Social Welfare with Submodular Valuations

12:30-14:00

Lunch

 

14:00-15:30

Contributed Talks

 

15:30-16:30

Coffee break & poster session

 

16:30-18:30

Anna Karlin

A Survey on Metric TSP

 

Sayan Bhattacharya

Deterministic Rounding of Dynamic Fractional Matchings

 

Aviad Rubinstein

The Randomized Communication Complexity of Randomized Auctions

18:30-19:30

Business meeting

 

 


Contributed Talks

contributed talks

 Federico Fusco

A Regret Analysis of Bilateral Trade

 Luca Zanetti

Geometric Bounds on the Fastest Mixing Markov Chain

 Peter Kiss

Deterministic Dynamic Matching In Worst-Case Update Time

 Yael Hitron

Broadcast CONGEST Algorithms against Adversarial Edges

 Weiming Feng

Rapid mixing of Glauber dynamics via spectral independence for all degrees

 Ioana Bercea

 An extendable data structure for incremental stable perfect hashing

 Aris Filos-Ratsikas

FIXP-membership via Convex Optimization: Games, Cakes, and Markets

 Nick Fischer

Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime

 Asaf Petruschka

\~{O}ptimal Dual Vertex Failure Connectivity Labels

 Konstantin Zabarnyi

Multi-Channel Bayesian Persuasion

 Francesco d'Amore

Search via Parallel Lévy Walks on %%Z^2%%

Alexandros Hollender

Further Collapses in TFNP

 Oded Nir

 Secret Sharing, Slice Formulas, and Monotone Real Circuits

 Sayantan Sen

Interplay between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds

 Andreas Padalkin

Coordinating Amoebots via Reconfigurable Circuits

 Jiaheng Wang

Algorithm and complexity for approximating the number of hypergraph colourings in the local lemma regime

 Shay Sapir

Comparison of Matrix Norm Sparsification

Friday 3 June 2022

MA107

Time

Event/Speaker

Talk Title

8:30-9:00

Coffee

 

9:00-10:30

Martin Grohe

A Survey on Graph Isomorphism

 

Jakub Tetek

Better Sum Estimation via Weighted Sampling

10:30-11:00

Coffee break

 

11:00-12:30

Soheil Behnezhad

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

 

Yelena Yuditsky

Integer Programs with Bounded Subdeterminants and Two Nonzeros Per Row

 

William Kuszmaul

Stochastic and Worst-Case Generalized Sorting Revisited

12:30-14:00

Lunch

 

14:00-15:30

Contributed Talks

 

15:30-16:00

Coffee Break

 

16:00-18:00

Julia Chuzhoy

A Survey on the Graph Crossing Number

 

Rahul Savani

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS"

 

Greg Bodwin

Restorable Shortest Path Tiebreaking for Edge-Faulty Graphs

18:00-19:00

Poster session

 

 

Contributed Talks

Contributed Talks

 Sujoy Bhore

Euclidean Steiner Spanners: Light and Sparse

Jens Schlöter

Orienting (hyper)graphs under explorable stochastic uncertainty

Tomer Ezra

Combinatorial Contracts

Mary Scott

Aggregation and Transformation of Vector-Valued Messages in the Shuffle Model of Differential Privacy

Hicham Lesfari

Biased Majority Opinion Dynamics: Exploiting graph k-domination

Patrick Lambein-Monette

Fault-tolerant coloring of the asynchronous cycle

Parth Mittal

Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for Delta-Coloring

Abhiruk Lahiri

Geometric Dominating Set and Set Cover via Local Search

Sorrachai Yingchareonthawornchai

Vertex Connectivity in Polylogarithmic Max-Flows

Renan Gross

Noise sensitivity from fractional query algorithms and the axis-aligned Laplacian

Christian Coester

Shortest Paths without a Map, but with an Entropic Regularizer

Alexander Lindermayr

Robustification of Online Graph Exploration Methods

Goran Zuzic

Universally-Optimal Distributed Shortest Paths and Transshipment via Graph-Based L1-Oblivious Routing

Amir Ban

An Observational Learning Approach to Crowdfunding