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

derandomizationgraph coloringgraph productlow-degree long code

Mathematics Subject Classification ID

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

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)