Title	Candidate Hard Unique Game
Creator	Moshkovitz, Dana
Publisher	Banff International Research Station for Mathematical Innovation and Discovery
Date Issued	2016-09-06T16:07
Description	We propose a candidate reduction for ruling out polynomial-time algorithms for unique games, either under plausible complexity assumptions, or unconditionally for Lasserre semidefinite programs with a constant number of rounds. We analyze the completeness and Lasserre solution of our construction, and provide a soundness analysis in a certain setting of interest. Addressing general settings is tightly connected to a question on Gaussian isoperimetry. Our construction is based on our previous work on the complexity of approximately solving a system of linear equations over reals, which we suggested as an avenue towards a (positive) resolution of the Unique Games Conjecture. The construction employs a new encoding scheme that we call the {\em real code}. The real code has two useful properties: like the long code, it has a unique local test, and like the Hadamard code, it has the so-called {\em sub-code covering} property.
Extent	31 minutes
Subject	Mathematics; Computer science; Theoretical computer science
Type	Moving Image
File Format	video/mp4
Language	eng
Notes	Author affiliation: MIT
Series	BIRS Workshop Lecture Videos (Banff, Alta)
Date Available	2017-03-08
Provider	Vancouver : University of British Columbia Library
Rights	Attribution-NonCommercial-NoDerivatives 4.0 International
DOI	10.14288/1.0343101
URI	http://hdl.handle.net/2429/60825
Affiliation	Non UBC
Peer Review Status	Unreviewed
Scholarly Level	Researcher
Rights URI	http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository	DSpace

Open Collections

BIRS Workshop Lecture Videos

Candidate Hard Unique Game Moshkovitz, Dana

Description

Item Metadata

Item Media

Item Citations and Data

Rights