45 Arbeiten
Diese Arbeit stellt SCORE, eine Programmiersprache zur Manipulation von Variablen und Stacks, vor, deren Operationen mithilfe eines Beweisassistenten als totale Bijektionen zertifiziert werden, um reversible Berechnungsmodelle zu ermöglichen, die für die Untersuchung der Komplexitätstheorie essenziell sind.
Diese Arbeit zeigt, dass jede nicht-adaptive, -abfragende relaxiert lokal dekodierbare Kodierung (RLDC) mit einer ausreichend kleinen Fehlerwahrscheinlichkeit auch als -abfragende lokal dekodierbare Kodierung (LDC) mit vergleichbaren Parametern dient, wodurch die Trennung zwischen diesen Konzepten für kleine Abfragezahlen eingeschränkt und verbesserte untere Schranken für RLDCs, RLCCs und PCPPs abgeleitet werden.
Dieses Buch fasst die jüngsten Fortschritte beim effizienten Listen-Decodieren von Reed-Solomon-Codes und verwandten polynombasierten Codes zusammen, die eine Korrektur bis zur informationstheoretischen Kapazität mit optimaler Listenlänge und nahezu linearer oder sogar sublinearer Laufzeit ermöglichen.
Die Arbeit stellt einen randomisierten Algorithmus in polynomialer Zeit vor, der das Lernen von Read-Once-Determinanten und das zugehörige Problem der Zuweisung von Hauptminoren (PMAP) durch die Untersuchung einer Eigenschaft dichter Matrizen, der sogenannten „Rank-One Extension Property", löst.
Diese Arbeit präsentiert einen Quantenalgorithmus auf Basis von MNRS-Quantenwalks, der für das Testen des approximativen Graphenisomorphismus eine polynomiale Beschleunigung gegenüber klassischen Verfahren in der Query-Komplexität nachweist.