- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Strongly refuting random constraint satisfaction problems...
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Strongly refuting random constraint satisfaction problems below the spectral threshold Schramm, Tselil
Description
Random CSPs are known to be unsatisfiable with high probability when the number of clauses is at least linear. However, the task of refuting random CSPs is hypothesized to be computationally hard if there are O(N) clauses--in fact, the best known efficient algorithms for the strong refutation of most k-CSPs require instances with at least \Omega(N^{k/2}) clauses, a polynomial factor beyond the unsatisfiability threshold at \Theta(N). In this talk, I will describe a new spectral algorithm that strongly refutes random CSPs with fewer clauses, given more time. Our algorithm interpolates between the efficient algorithms at the spectral threshold and brute-force search at the unsatisfiability threshold. This result also implies tight upper bounds on the value of sum-of-squares relaxations for random CSPs, as well as the value of sum-of-squares relaxations for random polynomial maximization over the unit sphere. Based on joint work with Prasad Raghavendra and Satish Rao.
Item Metadata
| Title |
Strongly refuting random constraint satisfaction problems below the spectral threshold
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2016-09-06T11:14
|
| Description |
Random CSPs are known to be unsatisfiable with high probability when
the number of clauses is at least linear. However, the task of
refuting random CSPs is hypothesized to be computationally hard if
there are O(N) clauses--in fact, the best known efficient algorithms
for the strong refutation of most k-CSPs require instances with at
least \Omega(N^{k/2}) clauses, a polynomial factor beyond the
unsatisfiability threshold at \Theta(N).
In this talk, I will describe a new spectral algorithm that strongly
refutes random CSPs with fewer clauses, given more time. Our algorithm
interpolates between the efficient algorithms at the spectral
threshold and brute-force search at the unsatisfiability threshold.
This result also implies tight upper bounds on the value of
sum-of-squares relaxations for random CSPs, as well as the value of
sum-of-squares relaxations for random polynomial maximization over the
unit sphere.
Based on joint work with Prasad Raghavendra and Satish Rao.
|
| Extent |
51 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: University of California, Berkeley
|
| Series | |
| Date Available |
2017-03-08
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0343097
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Graduate
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International