Derandomized graph product results using the low degree long code

DOI10.4230/LIPICS.STACS.2015.275MaRDI QIDQ2955002zbMATH OpenFDO

Authors Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

Publication date 24 January 2017

Full work available at URL https://arxiv.org/abs/1411.3517

zbMATH Keywords

graph coloringderandomizationgraph productlow-degree long code

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Making the Long Code Shorter
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• Derandomized graph products

Cited in

(2)

• Derandomized graph products
• On derandomized composition of Boolean functions

This page was built for publication: Derandomized graph product results using the low degree long code

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2955002)