Hierarchies, Extended Formulations and Matrix-Analytic Techniques (2017)
2017-11-06..2017-11-09
Berkeley, United States
| title | author | length |
|---|---|---|
| Constructing Extended Formulations | Volker Kaibel | 01h 07m |
Six constructive recipes and concrete bounds: disjunctive programming yields convex-union formulations (used to get log‑n matching polytopes via perfect‑hash… | ||
| Small (Explicit) Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits | Sam Fiorini | 34m |
The talk presents an explicit small extended formulation for knapsack cover inequalities by connecting them to monotone Boolean circuit constructions. It… | ||
| Computing the Nucleolus of Weighted Cooperative Matching Games in Polynomial Time | Kanstantin Pashkovich | 28m |
Proves a polynomial-time algorithm to compute the nucleolus for weighted cooperative matching games on general graphs, not just bipartite or unit-weight cases… | ||
| A Lower Bound on the Positive Semidefinite Rank of Convex Bodies | Hamza Fawzi | 29m |
Claim: PSD rank m of a convex body is at least on the order of sqrt(log D) where D is the degree of the algebraic boundary of the polar. Proof turns the SDP… | ||
| Bounds for Matrix Factorization Ranks via Semidefinite Programming and... | Monique Laurent | 32m |
An SDP hierarchy gives computable lower bounds for nonnegative, PSD, CP and CPSD factorization ranks by encoding Gram factorizations as evaluations of… | ||
| Using Symmetry in Semidefinite Programming | Annie Raymond | 30m |
Claims that certifying nonnegativity of an SN‑invariant polynomial on the k‑subset {0,1} hypercube admits sum‑of‑squares certificates whose semidefinite… | ||
| Sparse Polynomial Interpolation: Compressed Sensing, Super-resolution, or Prony? | Jean-Bernard Lasserre | 30m |
Compares three concrete methods for sparse polynomial interpolation: polynomial as atomic measure on torus, evaluate at z0^beta equals beta moment explains why… | ||
| Pseudocalibration and SoS Lower Bounds | Sam Hopkins, Aaron Potechin | 01h 02m |
A mechanical construction called pseudo-calibration projects the relative-density function of a planted distribution to a low-degree projection in the graph… | ||
| Weak Decoupling, Polynomial Folds, and Approximate Optimization over the Sphere | Vijay Bhattiprolu | 27m |
Claims a concrete tradeoff: powering a degree-D polynomial to degree Q and using SOS yields an n^{Q} time algorithm that achieves roughly an n / Q^{Q/2}… | ||
| Spectral Aspects of Symmetric Matrix Signings | Alexandra Kolla | 30m |
Connection between graph lifts and signed adjacency matrices guides several concrete results: existence of Ramanujan graphs follows from choosing a 2-lift… | ||
| From Weak to Strong LP Gaps for all CSPs | Madhur Tulsiani | 32m |
Madhur Tulsiani, Toyota Technological Institute at Chicago
https://simons.berkeley.edu/talks/madhur-tulsiani-11-9-17
Hierarchies, Extended Formulations and… | ||
| LP, SOCP, and Optimization-Free Approaches to Polynomial Optimization | Amir Ali Ahmadi | 32m |
Presents LP and SOCP substitutes for sum of squares by enforcing DSOS/SDSOS LP and SOCP relaxations (diagonally dominant or scaled diagonally dominant Gram… | ||
| Matrix Completion and Sums of Squares | Greg Blekherman | 29m |
Characterizes exactly when nonnegative quadratic forms on a variety X equal sums of squares: equivalently the dual slice of the PSD cone has only rank‑1… | ||
| SOS and the Dreaded Bit-complexity | Ryan O'Donnell | 33m |
Claims that degree-D Sum-of-Squares proofs are computable in n^{O(D)} time are misleading: semidefinite feasibility suffers big-R / little-r bit-size issues… | ||
| Maximizing Sub-determinants and Connections to Permanents and Inequalities on Stable Polynomials | Mohit Singh | 29m |
Presents a new polynomial saddle-point relaxation for maximizing det(VB^T VB) under partition matroid constraints, solved efficiently by exploiting… | ||
| Spectrahedra and Directional Derivatives of Determinants | James Saunderson | 32m |
Starts from a definite determinantal polynomial and takes the directional derivative in the identity direction, producing the degree n−1 polynomial equal to… | ||
| Counting and Optimization Using Stable Polynomials | Nima Anari | 01h 07m |
Shows that for distributions whose generating polynomial is real-stable the log of the set size is approximable by the sum of edge marginals up to a… | ||
| Independent Set Polytopes: Query vs. Communication Perspective | Mika Göös | 58m |
Constructs n‑node graphs whose independent set polytope provably requires extension complexity nearly maximal namely exp(n / log n), via a reduction from a… | ||
| Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs | Raghu Meka | 39m |
Proves a lifting theorem: for the inner-product gadget with B ≳ c log n the non-negative rank of a pattern matrix Mf is at least exp(Ω(B · degree-plus(f)))… | ||
| From Proofs to Algorithms for Machine Learning Problems | David Steurer | 01h 04m |
Claims that many ML estimation gaps close when identifiability admits a concrete low-degree proof: sum-of-squares proofs capture the certificate, yield convex… | ||
| Nonnegative Polynomials, Nonconvex Polynomial Optimization, and Applications to Learning | Georgina Hall | 27m |
Shows NP-hardness of testing a cubic polynomial’s monotonicity over a box, then gives an SOS relaxation that certifies monotone polynomial regressors and… | ||
| Fast Spectral Algorithms from Sum-of-Squares Analyses | Tselil Schramm | 39m |
Shows how to turn a degree-6 SOS guarantee for robust order‑4 symmetric tensor decomposition into a near‑linear spectral procedure: assume the square‑reshaping… | ||
| Computing the Independence Polynomial in Shearer's Region for the LLL | Nick Harvey | 30m |
Gives a constructive LLL method that starts from a fractional coloring and rounds coordinates one by one while keeping the point inside Shearer's region… | ||
| Quantum Entanglement, Sum of Squares, and the Log Rank Conjecture | Pravesh K. Kothari | 36m |
Given a basis for an n×n matrix subspace with a promised rank‑one element (wanting ≈1% Frobenius error), the result gives a concrete algorithm: a… | ||
| nothing matches | ||