 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 BIRS Workshop Lecture Videos /
 Sum of Squares Bounds for the Ordering Principle
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Sum of Squares Bounds for the Ordering Principle Potechin, Aaron
Description
The ordering principle, which says that if there is an ordering on n elements then one of them must be less than all of the others, is an important example in proof complexity. The ordering principle is important because while it has a short resolution proof, any resolution proof must have width $\Omega(n)$ and any polynomial calculus proof must have degree $\Omega(n)$. Thus, with some adjustments, the ordering principle gives a tight example for the size/width tradeoffs of BenSasson and Wigderson for resolution and the size/degree tradeoffs of Impagliazzo, Pudlak, and Sgall for polynomial calculus (as it requires $n^2$ variables to express the ordering principle). A natural question is whether the sum of squares hierarchy also requires degree $\Omega(n)$ to prove the ordering principle or if sum of squares can do better. As it turns out, sum of squares can do better. In this talk, I will describe how the sum of squares hierarchy can prove the ordering principle using degree roughly $n^(1/2)$. Time permitting, I will also describe ideas for a sum of squares lower bound.
Item Metadata
Title 
Sum of Squares Bounds for the Ordering Principle

Creator  
Publisher 
Banff International Research Station for Mathematical Innovation and Discovery

Date Issued 
20200121T16:01

Description 
The ordering principle, which says that if there is an ordering on n elements then one of them must be less than all of the others, is an important example in proof complexity. The ordering principle is important because while it has a short resolution proof, any resolution proof must have width $\Omega(n)$ and any polynomial calculus proof must have degree $\Omega(n)$. Thus, with some adjustments, the ordering principle gives a tight example for the size/width tradeoffs of BenSasson and Wigderson for resolution and the size/degree tradeoffs of Impagliazzo, Pudlak, and Sgall for polynomial calculus (as it requires $n^2$ variables to express the ordering principle).
A natural question is whether the sum of squares hierarchy also requires degree $\Omega(n)$ to prove the ordering principle or if sum of squares can do better. As it turns out, sum of squares can do better. In this talk, I will describe how the sum of squares hierarchy can prove the ordering principle using degree roughly $n^(1/2)$. Time permitting, I will also describe ideas for a sum of squares lower bound.

Extent 
30.0 minutes

Subject  
Type  
File Format 
video/mp4

Language 
eng

Notes 
Author affiliation: University of Chicago

Series  
Date Available 
20200720

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionNonCommercialNoDerivatives 4.0 International

DOI 
10.14288/1.0392460

URI  
Affiliation  
Peer Review Status 
Unreviewed

Scholarly Level 
Researcher

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivatives 4.0 International