### Abstract

Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ < 1/4, the SOS/Lasserre SDP hierarchy at degree 4[1/4γ]certifies the statement "the maximum independent set in the Frankl-Rödl graph FR^{n}_{γ} has fractional size o( 1)". Here FR^{n}_{γ} = (V,E) is the graph with V = {0,1 }^{n} and (x, y) ∈ E whenever δ(x,y) = (1 - γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound "x(FR^{n}_{1/4}) = ω(l)", even though FR^{n}_{1/4} is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "x(FR^{n}_{1/4}) > 3". Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |

Publisher | Association for Computing Machinery, |

Pages | 1644-1658 |

Number of pages | 15 |

ISBN (Print) | 9781611973389 |

State | Published - Jan 1 2014 |

Externally published | Yes |

Event | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: Jan 5 2014 → Jan 7 2014 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |
---|---|

Country | United States |

City | Portland, OR |

Period | 1/5/14 → 1/7/14 |

### Fingerprint

### ASJC Scopus subject areas

- Software
- Mathematics(all)

### Cite this

*Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014*(pp. 1644-1658). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery,.

**Hypercontractive inequalities via SOS, and the frankl-rodl graph.** / Kauers, Manuel; O'Donnell, Ryan; Tan, Li Yang; Zhou, Yuan.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014.*Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 1644-1658, 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, United States, 1/5/14.

}

TY - GEN

T1 - Hypercontractive inequalities via SOS, and the frankl-rodl graph

AU - Kauers, Manuel

AU - O'Donnell, Ryan

AU - Tan, Li Yang

AU - Zhou, Yuan

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ < 1/4, the SOS/Lasserre SDP hierarchy at degree 4[1/4γ]certifies the statement "the maximum independent set in the Frankl-Rödl graph FRnγ has fractional size o( 1)". Here FRnγ = (V,E) is the graph with V = {0,1 }n and (x, y) ∈ E whenever δ(x,y) = (1 - γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound "x(FRn1/4) = ω(l)", even though FRn1/4 is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "x(FRn1/4) > 3". Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

AB - Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant 0 < γ < 1/4, the SOS/Lasserre SDP hierarchy at degree 4[1/4γ]certifies the statement "the maximum independent set in the Frankl-Rödl graph FRnγ has fractional size o( 1)". Here FRnγ = (V,E) is the graph with V = {0,1 }n and (x, y) ∈ E whenever δ(x,y) = (1 - γ)n (an even integer). In particular, we show the degree-4 SOS algorithm certifies the chromatic number lower bound "x(FRn1/4) = ω(l)", even though FRn1/4 is the canonical integrality gap instance for which standard SDP relaxations cannot even certify "x(FRn1/4) > 3". Finally, we also give an SOS proof of (a generalization of) the sharp (2, q)-hypercontractive inequality for any even integer q.

UR - http://www.scopus.com/inward/record.url?scp=84902095948&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902095948&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84902095948

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1644

EP - 1658

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery,

ER -