Correspondence Colouring of Random Graphs

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


Duration: 1:00:00
412 views
7

Liana Yepremyan (Emory University)
https://simons.berkeley.edu/talks/liana-yepremyan-emory-university-2023-07-28
Structural Results

We show that Erdős-Renyi random graph with constant density has correspondence chromatic number O(n/\sqrt{logn}); this matches a prediction from linear Hadwiger’s conjecture for correspondence colouring. The proof follows from a sufficient condition for correspondence colourability in terms of the numbers of independent sets. We conjecture the truth to be of order O(n/logn) as suggested by the random correspondence assignment. This is joint work with Zdenek Dvorak.



Other Videos By Simons Institute for the Theory of Computing


2023-08-14An observation on Generalization
2023-08-14Towards Reliable Use of Large Language Models: Better Detection, Consistency, and Instruction-Tuning
2023-08-14Possible Impossibilities and Impossible Possibilities
2023-08-14Sparks of Artificial General Intelligence
2023-08-10Generating Approximate Ground States of Molecules Using Quantum Machine Learning
2023-08-10Quantum-Classical Cross-Correlations and the Post-selection Problem
2023-08-10Industry Applications of Hamiltonian Simulation and Beyond
2023-08-10What Can I Do With a Noisy Quantum Computer?
2023-08-10Quantum Machine Learning in the NISQ Era
2023-07-29Structure Of Boolean Almost Low Degree Functions On The Biased Cube
2023-07-29Correspondence Colouring of Random Graphs
2023-07-28Structures in Random Graphs: New Connections
2023-07-28Noncommutativity and Rounding Schemes for Combinatorial Optimization Parts 1 & 2
2023-07-28Some Remarks About Quantum and Classical Local Hamiltonian Optimization and SDP Rounding
2023-07-28Structure of Communication | Richard M. Karp Distinguished Lecture
2023-07-28Randomized versus Deterministic Decision Tree Size
2023-07-28Fourier Growth of XOR-Fibers of Communication Protocols
2023-07-27Sign-rank vs Margin
2023-07-27Tight Space Complexity of the Coin Problem
2023-07-27A New Upper Bound for the Heilbronn Triangle Problem
2023-07-26A Polynomial Bogolyubov type Result for the Special Linear Group


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Structural Results
Liana Yepremyan