Proofs, beliefs and algorithms through the lens of Sum of Squares

sumofsquares.org · 145 words · saved by 2 readers

7.1. SOS and the unit sphere—Sparse vectors, tensor decomposition, dictionary learning, and quantum separability (pdf version) (video) 7.2. Finding a sparse vector in a subspace (pdf version) (video) 7.4. Tensor decomposition via sum of squares (pdf version) (video) 7.5. Dictionary learning via tensor decomposition (pdf version) 8.1. Quantum entanglement, log rank conjecture, and sum of squares (pdf version) (video) 9.1. SOS and the Unique Games conjecture—a love hate relationship (pdf version) (video) 9.2. The small set expansion hypothesis (pdf version) (video) 9.4. On approaches for proving the Unique Games Conjecture (pdf version) (video) 10.1 Is sos an “optimal algorithm”? (pdf version) (video) 10.2 Digression to boosting, experts, dense models, and their quantum counterparts (pdf version) (video) 10.3 Optimality of sos among similar sized sdp’s for csp’s (pdf version) (video)

Boaz Barak and David Steurer work in progress (Fall 2016) Background (pdf version) Notation (pdf version) ⊕ A random graph with a hidden clique. The sum-of-squares algorithm maintains a set of beliefs about which vertices belong to the hidden clique. Despite learning no new information, as we invest more computation time, the algorithm reduces uncertainty in the beliefs by making them consistent with increasingly powerful proof systems. Initially the beliefs have maximum uncertainty and correspond to the uniform distribution but they eventually converge on the correct hidden clique (red…

Proofs, beliefs and algorithms through the lens of Sum of Squares

saved by

related reading