Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!

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


Duration: 36:16
175 views
0

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

Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!

Anup Bhattacharya (Indian Statistical Institute, Kolkata, India)
Arijit Bishnu (Indian Statistical Institute, Kolkata, India)
Gopinath Mishra (Indian Statistical Institute, Kolkata, India)
Anannya Upasana (Indian Statistical Institute, Kolkata, India)



Other Videos By Simons Institute for the Theory of Computing


2021-01-15Dynamic inference in probabilistic graphical models
2021-01-15A Largish Sum-of-Squares Implies Circuit Hardness and Derandomization
2021-01-15Metrical Service Systems with Transformations
2021-01-15Tight Hardness Results for Training Depth-2 ReLU Networks
2021-01-15Polynomial-time trace reconstruction in the low deletion rate regime
2021-01-15Self-testing of a single quantum device under computational assumptions
2021-01-15Circular Trace Reconstruction
2021-01-15Comparison Graphs: a Unified Method for Uniformity Testing
2021-01-15Complexity measures on symmetric group and beyond
2021-01-15The Variable-Processor Cup Game
2021-01-15Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!
2021-01-15A New Model for Ant Trail Formation and its Convergence Properties
2021-01-15The Quantum Supremacy Tsirelson Inequality
2021-01-15Sample efficient identity testing and independence testing of quantum states
2021-01-15Understanding the Relative Strength of QBF CDCL Solvers and QBF Resolution
2021-01-15A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits
2021-01-15The Strongish Planted Clique Hypothesis and Its Consequences
2021-01-15Pipeline Interventions
2021-01-15Pseudorandom Generators for Unbounded-Width Permutation Branching Programs
2021-01-15Sharp Threshold Rates for Random Codes
2021-01-15The Complexity of Finding Fair Independent Sets in Cycles