Local Testing for Membership in Lattices

DOI10.4230/LIPIcs.FSTTCS.2016.46zbMath1391.68121arXiv1608.00180MaRDI QIDQ4636596

Mahdi Cheraghchi, Elena Grigorescu, Karthekeyan Chandrasekaran, Venkata Gandikota

Publication date: 19 April 2018

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

zbMATH Keywords

lattices; complexity theory; property testing; locally testable codes

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

94B60: Other types of codes

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W20: Randomized algorithms