Minimal achievable approximation ratio for MAX-MQ in finite fields

DOI10.1016/j.tcs.2009.02.003zbMath1168.68052OpenAlexW2089939069MaRDI QIDQ1019747

Shang-Wei Zhao, Xiao-Shan Gao

Publication date: 28 May 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.003

zbMATH Keywords

approximation algorithmapproximation ratioMAX-MQmultivariate quadratic polynomial equations

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Number-theoretic algorithms; complexity (11Y16) Approximation algorithms (68W25)

Related Items (3)

Polly cracker, revisited ⋮ A New Method for Solving Polynomial Systems with Noise over $\mathbb{F}_2$ and Its Applications in Cold Boot Key Recovery ⋮ Solving polynomial systems with noise over \(\mathbb{F}_2\): revisited

Cites Work

• A well-characterized approximation problem
• Some optimal inapproximability results
• Unnamed Item
• Unnamed Item

This page was built for publication: Minimal achievable approximation ratio for MAX-MQ in finite fields