Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies

DOI10.1137/070691140zbMath1178.68670OpenAlexW1991486419MaRDI QIDQ3395039

Subhash A. Khot, Assaf Naor

Publication date: 20 August 2009

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070691140

zbMATH Keywords

semidefinite programmingGrothendieck's inequalitycomputational convex geometryMax-E3-Lin-2refutation of random SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (9)

Inapproximability of Matrix \(\boldsymbol{p \rightarrow q}\) Norms ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ On the Ball-Constrained Weighted Maximin Dispersion Problem ⋮ On solving biquadratic optimization via semidefinite relaxation ⋮ Unnamed Item ⋮ Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems ⋮ Approximation algorithms for optimization of real-valued general conjugate complex forms ⋮ Probability Bounds for Polynomial Functions in Random Variables ⋮ Hardness and Approximation Results for L_p-Ball Constrained Homogeneous Polynomial Optimization Problems

This page was built for publication: Linear Equations Modulo 2 and the $L_1$ Diameter of Convex Bodies