Endliche Feld-Beschränkte Isometrie, Fourier-Barrieren und strukturelle Grenzen von linear robusten PCP-Systemen

Dieses Papier analysiert die algebraische Durchführbarkeit von linear robusten probabilistisch überprüfbaren Beweissystemen durch die Untersuchung der Finite Field Restricted Isometry Property (FF-RIP). Aufbauend auf vorheriger Arbeit, die robuste PCPs als entscheidende fehlende Komponente für uneingeschränkte Beweis-Komplexitäts-Untere Schranken identifizierte, entwickelt es einen einheitlichen Rahmen, der harmonische Analyse, algebraische Geometrie und Methoden der zufälligen Matrizen vereint. Das Papier beweist, dass starke FF-RIP äquivalent zur Existenz großer Salem-Typ-Mengen über endlichen Feldern ist und begründet scharfe uneingeschränkte Unterschranken, die zeigen, dass bekannte Konstruktionen im Wesentlichen optimal sind. Dynamische und Random-Walk-Ansätze scheitern aufgrund struktureller Metastabilität. Diese Ergebnisse zeigen, dass die algebraische Komponente robuster PCP-Konstruktionen tiefgreifenden und intrinsischen pseudorandomness-Barrieren gegenübersteht und nicht nur technischen Schwierigkeiten.