Erasure-Resilient Sublinear-Time Graph Algorithms

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=DPXXPttZrhQ


Duration: 25:14
219 views
5

12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
http://itcs-conf.org/

Sublinear Algorithms for Graphs with Incomplete Information

Amit Levi (University of Waterloo)
Ramesh Krishnan S. Pallavoor (Boston University)
Sofya Raskhodnikova (Boston University)
Nithin Varma (University of Haifa)



Other Videos By Simons Institute for the Theory of Computing


2021-01-19Probabilistic Systems Part 1: discrete time Markov chains
2021-01-19Probabilistic reachability
2021-01-19Rewards and expected reachability for DTMCs
2021-01-19Probabilistic Systems Introductions
2021-01-19Introduction to Automata on Infinite Words 6
2021-01-19Introduction to Automata on Infinite Words 5
2021-01-19Introduction to Automata on Infinite Words 2
2021-01-19Introduction to Automata on Infinite Words 4
2021-01-19Introduction to Automata on Infinite Words 1
2021-01-15Computation Over the Noisy Broadcast Channel with Malicious Parties
2021-01-15Erasure-Resilient Sublinear-Time Graph Algorithms
2021-01-15Distributed load balancing: a new framework and improved guarantees
2021-01-15Learning and Strongly Truthful Multi-task Setting Peer Prediction: A Variational Approach
2021-01-15Batching and Optimal Multi-stage Bipartite Allocations
2021-01-15Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisions
2021-01-15High-entropy dual functions and locally decodable codes
2021-01-15Randomness and Fairness in Two-Sided Matching with Limited Interviews
2021-01-15Counterexamples to the Low-Degree Conjecture
2021-01-15Majorizing Measures for the Optimizer
2021-01-15Block Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
2021-01-15Lower Bounds for Off-Chain Protocols: Exploring the Limits of Plasma