Approximations of Submodular, XOS and Self-Bounding Functions by Juntas

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


Duration: 54:05
195 views
2

Jan Vondrák, IBM Almaden
Functional Inequalities in Discrete Spaces with Applications
http://simons.berkeley.edu/talks/jan-vondrak-2013-10-03



Other Videos By Simons Institute for the Theory of Computing


2013-10-28Scalable Graph-Parallel Inference Algorithms and Systems
2013-10-28Large Scale Response Prediction to Serve Ads on LinkedIn
2013-10-28MapReduce Algorithmics
2013-10-23The Effectiveness of Convex Programming in the Information and Physical Sciences
2013-10-09Influences in Gaussian Space
2013-10-09Reversing Hypercontractivity
2013-10-09A Two-Sided Estimate for the Gaussian Noise Stability Deficit
2013-10-09Majority is Stablest for Dependent Variables
2013-10-09Strong Noise Sensitivity and Random Graphs
2013-10-09Noise Stability and Central Limit Theorem for Random Effective Resistance
2013-10-09Approximations of Submodular, XOS and Self-Bounding Functions by Juntas
2013-10-09A Removal Lemma for Kneser Graphs and Product Graphs
2013-10-09On Hyperboundedness and Spectrum of Markov Operators
2013-10-09Two Generalizations of Cheeger's Inequality
2013-10-09On Graph Spectra and Small Set Expansion
2013-10-09Displacement Convexity of Entropy on Graphs
2013-10-09Discrete Ricci Curvature via Convexity of the Entropy
2013-10-09Spectral Gap of a Kinetically Constrained Spin Model on Trees: Power Law Scaling at Criticality
2013-10-09On the Suprema of Bernoulli Processes
2013-10-09Concentration of Lipschitz Functionals of Determinantal and Other Strong Rayleigh Measures
2013-10-09Concentration Inequalities for Non-Lipschitz Functions


Tags:
Simons Institute
Big Data
UC Berkeley
computer science
theory of computing
Jan Vondrák