Analytic Approach to Guasirandomness

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


Duration: 53:06
257 views
8

Dan Král (Masaryk University)
https://simons.berkeley.edu/node/22588
Graph Limits Nonparametric Models and Estimation

A combinatorial structure is said to be quasirandom if it resembles a random structure in a certain robust sense. The notion of quasirandom graphs, developed in the work of Rödl, Thomason, Chung, Graham and Wilson in 1980s, is particularly robust as several different properties of truly random graphs, e.g., subgraph density, edge distribution and spectral properties, are satisfied by a large graph if and only if one of them is. We will discuss recent results on quasirandomness of various kinds of combinatorial structures (in particular, directed graphs, permutations and Latin squares) obtained using analytic tools provided by the theory of combinatorial limits.



Other Videos By Simons Institute for the Theory of Computing


2022-09-28Efficiently Exploiting Model Structure in Network Causal Inference with and without...
2022-09-28Symmetry and Convergence
2022-09-28Higher Order Fluctuations in Dense Random Graph Models
2022-09-27A Deterministic Theory of Low Rank Matrix Completion
2022-09-27Common Graphs with Arbitrary Chromatic Number
2022-09-27Higher-Order Graphon Theory: Fluctuations, Inference, and Degeneracies
2022-09-27A Large Deviation Principle for Block Models
2022-09-27Mean-field approximations for high-dimensional Bayesian Regression
2022-09-27Response of Graphs to Competing Constraints
2022-09-27Sparse Random Graphs: Interplay of Local and Global Structure
2022-09-26Analytic Approach to Guasirandomness
2022-09-26Random Cluster Model on Regular Graphs
2022-09-17Generalization and Robustness in Offline Reinforcement Learning
2022-09-17Adaptivity and Confounding in Multi-armed Bandit Experiments
2022-09-16When Can We Use Weak Function Approximation to Solve Large Scale Planning Problems in MDPs?
2022-09-16Dynamic Regret Minimization for Bandits without Prior Knowledge
2022-09-16Oracle-Efficient Online Learning or: How to Use Non-Robust Optimization for Robust Learning
2022-09-16Adaptive Monopoly Regulation
2022-09-16Information Collection Through Strategic Agents
2022-09-16Incentivized Exploration
2022-09-15Attributes: Selective Learning and Influence


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Graph Limits Nonparametric Models and Estimation
Dan Král