Roei Tell: Derandomization - Part 3
Roei Tell, University of Toronto, presents a three-part tutorial on derandomization at the Frontiers in Complexity Theory workshop for graduate students held at DIMACS July 29 - August 1, 2024. This is Part 3.
Description: The focus of this tutorial is derandomization, and in particular new developments in hardness vs randomness. We will first introduce textbook results, such as the reconstructive paradigm (Nisan-Wigderson, Impagliazzo-Wigderson) and hardness amplification. Then we will study new tools in this area from recent years, focused on constructions of targeted pseudorandom generators from functions hard for uniform algorithms. We'll conclude with very recent applications -- in particular, we will see the construction of a pseudodeterministic polynomial-time algorithm that finds prime numbers!
Link to workshop webpage: http://dimacs.rutgers.edu/events/details?eID=2785
Видео Roei Tell: Derandomization - Part 3 канала DIMACS CCICADA
Description: The focus of this tutorial is derandomization, and in particular new developments in hardness vs randomness. We will first introduce textbook results, such as the reconstructive paradigm (Nisan-Wigderson, Impagliazzo-Wigderson) and hardness amplification. Then we will study new tools in this area from recent years, focused on constructions of targeted pseudorandom generators from functions hard for uniform algorithms. We'll conclude with very recent applications -- in particular, we will see the construction of a pseudodeterministic polynomial-time algorithm that finds prime numbers!
Link to workshop webpage: http://dimacs.rutgers.edu/events/details?eID=2785
Видео Roei Tell: Derandomization - Part 3 канала DIMACS CCICADA
Комментарии отсутствуют
Информация о видео
13 августа 2024 г. 23:58:24
01:47:19
Другие видео канала
Kasper Green Larsen - Tutorial (Part 3) - Multiphase & OMV Conjectures & Implications to Dynamic LBs
Kobbi Nissim - A Computer Scientist and a Legal Scholar Do the Wright Thing
Andrew Gelman - Information, Incentives, and Goals in Election Forecasts
Zhicheng Zhang - talk #2 on Quantum recursive programs
Luca Accorsi -- Guidelines for the Computational Testing of ML Approaches to VRPs
2015 12 15 3 Yaniv Erlich
Peter Melchior - Source Separation in Astronomy with Constrained Matrix Factorization
Abiy Tasissa -- A Matrix Completion Framework for the Euclidean Distance Geometry Problem
Lijie Chen: Recent Developments in Derandomization I
Jørgen Skålnes - A Branch-and-cut Embedded Matheuristic for the Inventory Routing Problem
Lecture 7: Algorithms for k-SAT
Sanyam Jain Ultra Wide Band for Contact Tracing and Social Distancing Recording
Patrick Klein -- Combinatorial Optimization enriched ML to Solve the Dynamic VRP with Time Windows
Rahul Ilango: Metacomplexity - Part 3
Lecture 11: Hardness of Approximation in P, Part 1
Janani Sundaresan -- Random Order Streaming Lower Bounds for Connected Components
Fred Roosta - Newton's Method Without Smoothness or Complexity
Keynote: Renato Werneck - Last Mile Deliveries at Amazon
Eric Neyman - From Proper Scoring Rules to Max-Min Optimal Forecast Aggregation
Keynote: Marina Meila - Manifold Coordinates with Physical Meaning
