1 Search Results for "Medarametla, Dhruv"

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.40

Bounds on the Norms of Uniform Low Degree Graph Matrices

Authors: Dhruv Medarametla and Aaron Potechin

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract

The Sum Of Squares hierarchy is one of the most powerful tools we know of for solving combinatorial optimization problems. However, its performance is only partially understood. Improving our understanding of the sum of squares hierarchy is a major open problem in computational complexity theory. A key component of analyzing the sum of squares hierarchy is understanding the behavior of certain matrices whose entries are random but not independent. For these matrices, there is a random input graph and each entry of the matrix is a low degree function of the edges of this input graph. Moreoever, these matrices are generally invariant (as a function of the input graph) when we permute the vertices of the input graph. In this paper, we bound the norms of all such matrices up to a polylogarithmic factor.

Cite as

Dhruv Medarametla and Aaron Potechin. Bounds on the Norms of Uniform Low Degree Graph Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 40:1-40:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{medarametla_et_al:LIPIcs.APPROX-RANDOM.2016.40,
  author =	{Medarametla, Dhruv and Potechin, Aaron},
  title =	{{Bounds on the Norms of Uniform Low Degree Graph Matrices}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{40:1--40:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.40},
  URN =		{urn:nbn:de:0030-drops-66638},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.40},
  annote =	{Keywords: sum of squares hierarchy, matrix norm bounds}
}

Refine by Author
1 Medarametla, Dhruv
1 Potechin, Aaron

Refine by Classification

Refine by Keyword
1 matrix norm bounds
1 sum of squares hierarchy

Refine by Type
1 document

Refine by Publication Year
1 2016

1 Search Results for "Medarametla, Dhruv"

Bounds on the Norms of Uniform Low Degree Graph Matrices

Abstract

Cite as

Thanks for your feedback!

Could not send message