Hardness of Maximum Independent Set in Structured Hypergraphs

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


Duration: 33:14
458 views
1

Rishi Saket, IBM T.J. Watson Research Center
Real Analysis in Testing, Learning and Inapproximability
http://simons.berkeley.edu/talks/rishi-saket-2013-08-26



Other Videos By Simons Institute for the Theory of Computing


2013-09-04Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions
2013-09-04Moment-Matching Polynomials
2013-09-04Approximate Constraint Satisfaction Requires Large LP Relaxations
2013-09-04The Analysis of Partially Symmetric Functions
2013-09-04Majority is Stablest: Discrete and SOS
2013-09-04Robust Gaussian Noise Stability
2013-09-04Beyond Locality-Sensitive Hashing
2013-09-04A Characterization of Strong Approximation Resistance
2013-09-04The Complexity of Somewhat Approximation Resistant Predicates
2013-09-04Approximation Algorithms For Projection Games
2013-09-04Hardness of Maximum Independent Set in Structured Hypergraphs
2013-09-04An Analytic Approach to Parallel Repetition
2013-09-04Approximation Resistance from Pairwise Independent Subgroups
2013-06-14What Should a Computational Theory of Cortex Explain?
2013-06-14The Gospel According to TCS
2013-06-14The Mathematics of Causal Inference, with Reflections on Machine Learning and the Logic of Science
2013-06-14Evolution and Computation
2013-06-14Market Design and Computer-Assisted Markets: An Economist's Perspective
2013-06-14Consumer Behavior and Algorithm Design
2013-06-14Programming Nanoscale Structure Using DNA-Based Information
2013-06-14The Online Revolution: Learning Without Limits


Tags:
Simons Institute
Real Analysis
UC Berkeley
computer science
theory of computing
Rishi Saket