On the usefulness of predicates

1 hour 5 mins 25 secs, 242.55 MB, iPod Video 480x270, 29.97 fps, 44100 Hz, 506.24 kbits/sec

Share this media item:

Embed this media item:

<iframe width="_width_" height="_height_" src="https://sms.cam.ac.uk/media/1122111/embed" frameborder="0" scrolling="no" allowfullscreen></iframe>

Choose size:

About this item

Available Formats

About this item

Description:	Håstad, J (KTH NADA) Tuesday 29 March 2011, 14:00-15:00

Created:

2011-03-31 14:43

Collection:

Discrete Analysis

Publisher:

Isaac Newton Institute

Håstad, J

Language:

eng (English)

Credits:

Author:	Håstad, J
Director:	Steve Greenham


Abstract:	One successful application of discrete harmonic analysis has been the analysis of Max-CSPs, maximum constraint satisfaction problems. In the Max-CSP defined by a predicate P of arity k we are presented with a list of k-tupels of literals and the goal is to find assignments to the variables in order to maximize the number of resulting k-bit strings that satisfy P. A predicate P is approximation resistant if, even for instances where the optimal assignments satisfies (almost) all constraints, it is infeasible to do find an assignment that satisfies substantially more constraints than what is obtained by picking a random assignment. We study a more general question of given the promise of the existence of an assignment that satisfies all the constraints given by P, to efficiently finding an assignment that satisfies a weaker predicate (or more general function) Q. In particular we say P is useless if it is infeasible to do substantially better than random for any Q. In this talk we describe this framework and derive results on uselessness based on NP ≠ P and the Unique Games Conjecture.

Abstract:

One successful application of discrete harmonic analysis has been the analysis of Max-CSPs, maximum constraint satisfaction problems.

In the Max-CSP defined by a predicate P of arity k we are presented with a list of k-tupels of literals and the goal is to find assignments to the variables in order to maximize the number of resulting k-bit strings that satisfy P.

A predicate P is approximation resistant if, even for instances where the optimal assignments satisfies (almost) all constraints, it is infeasible to do find an assignment that satisfies substantially more constraints than what is obtained by picking a random assignment.

We study a more general question of given the promise of the existence of an assignment that satisfies all the constraints given by P, to efficiently finding an assignment that satisfies a weaker predicate (or more general function) Q.

In particular we say P is useless if it is infeasible to do substantially better than random for any Q.

In this talk we describe this framework and derive results on uselessness based on NP ≠ P and the Unique Games Conjecture.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	907.52 MB	View	Download
WebM	640x360	1.58 Mbits/sec	770.32 MB	View	Download
Flash Video	484x272	568.76 kbits/sec	272.51 MB	View	Download
iPod Video *	480x270	506.24 kbits/sec	242.55 MB	View	Download
MP3	44100 Hz	125.02 kbits/sec	59.70 MB	Listen	Download
Auto	(Allows browser to choose a format it supports)