Hardness of Bipartite Expansion.

DOI10.4230/LIPIcs.ESA.2016.55zbMath1397.68101OpenAlexW2543065049MaRDI QIDQ4606326

Rishi Saket, Subhash A. Khot

Publication date: 2 March 2018

Full work available at URL: https://dblp.uni-trier.de/db/conf/esa/esa2016.html#KhotS16

zbMATH Keywords

inapproximabilityPCPsubmodular minimizationbipartite expansion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Orion: zero knowledge proof with linear prover time ⋮ On the complexity of fair house allocation

This page was built for publication: Hardness of Bipartite Expansion.