On the Power of Holographic Algorithms with Matchgates

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


Duration: 48:16
714 views
4

Jin-Yi Cai, University of Wisconsin-Madison
The Classification Program of Counting Complexity
https://simons.berkeley.edu/talks/jin-yi-cai-2016-03-29



Other Videos By Simons Institute for the Theory of Computing


2016-04-15Dynamics of 3D Enhancer-Gene Associations Across Diverse Human Cell Types and Tissues
2016-04-15Profiling Cell/Tissue Specific Gene Regulatory Networks
2016-04-15Network Perspective on Expression Changes and Expression Noise in D. melanogaster Chromosomal Deleti
2016-04-15Variation of Regulatory Networks Across Organisms
2016-04-15Cross-Species Interactome Mapping Reveals Network Evolution Principles from Yeasts to Human
2016-04-15Spatial Gene Expression Patterns in Drosophila
2016-04-15Moving Beyond Local Patterns: New Ways to Reason about Biological Network Comparisons
2016-04-15Mapping the Online World: Social Connectedness in the Digital Age
2016-04-04Spin Systems: Hardness of Approximate Counting via Phase Transitions
2016-04-04Approximately Counting Graph Homomorphisms
2016-04-04On the Power of Holographic Algorithms with Matchgates
2016-04-04Counting Matrix Partitions of Graphs
2016-04-04How to Not Prove Two Important Theorems
2016-04-04The Computational Complexity of Counting List H-Colourings, and Related Problems
2016-04-04The Complexity of Computing Averages
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


Tags:
Simons Institute
UC Berkeley
computer science
theory of computing
Counting Complexity and Phase Transitions
Jin-Yi Cai