Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property

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


Duration: 45:12
239 views
0

Davin Gamarnik, Massachusetts Institute of Technology
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/david-gamarnik-2016-04-01



Other Videos By Simons Institute for the Theory of Computing


2016-04-04Path Coupling, Metrics, and Sampling Problems in Graphs and Hypergraphs
2016-04-04Towards Understanding the Complexity of the Ising Partition Function
2016-04-04Approximation Algorithms for Partition Functions of Edge-Coloring Models
2016-04-04Geometric Perspectives on Problems in Complexity Theory
2016-04-04The Complexity of Approximating Small Degree Boolean #CSP
2016-04-04Dichotomies for Counting Subgraphs
2016-04-04Counting Approximation Complexity Classification Through Clones and Invariants
2016-04-04Dichotomy Theorems for Generalized Chromatic Polynomials
2016-04-04Canonical Paths for MCMC: From Art to Science
2016-04-04Enumerator Polynomials: Completeness and Intermediate Complexity
2016-04-04Finding a Large Submatrix of a Random Matrix, and the Overlap Gap Property
2016-03-29The Complexity of Computing Quantities
2016-03-22Decoding the Human Microbiome
2016-03-21Threshold Phenomena in Combinatorics
2016-03-11Discovery of Transcription Factor Binding Motifs from Large Sequence Sets
2016-03-11Algorithms for Single Cell RNAseq Analysis
2016-03-11Spectral Algorithms for Learning HMMs and Tree HMMs for Epigenetics Data
2016-03-11Accurate, Fast, and Model-Aware Transcript Expression Quantification with Salmon
2016-03-11Reconstructing Dynamic Signaling and Regulatory Networks
2016-03-11Co-occupancy Networks for Histone Modifications and Chromatin Associated Proteins
2016-03-11Beyond Enhancer Modularity: Locus-level Control of Gene Expression in Development


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Counting Complexity and Phase Transitions
Davin Gamarnik