45 Arbeiten
Die Arbeit beweist erstmals die NP-Härte des approximativen Covering-Radius-Problems für Gitter in der -Norm für explizite Werte von und zeigt, dass der Approximationsfaktor asymptotisch gegen $9/8$ konvergiert.
Diese Arbeit schließt die Lücke zur optimalen Laufzeit für d-QBF mit wenigen existenziellen Variablen, indem sie unter der ETH beweist, dass eine doppel-exponentielle Abhängigkeit von der Variablenzahl unvermeidbar ist, während sie für den Fall mit nur zwei Quantorenblöcken einen fast optimalen Algorithmus mit verbesserter Laufzeit angibt.
Die Arbeit stellt mit AlphaEvolve, einem auf großen Sprachmodellen basierenden Code-Mutations-Agenten, einen einheitlichen Meta-Algorithmus vor, der nicht nur die unteren Schranken für fünf klassische Ramsey-Zahlen verbessert, sondern auch bekannte exakte Werte erfolgreich rekonstruiert.
Diese Arbeit stellt explizit eine obere Schranke von für die Änderung der optimalen Schaltkreisgröße bei einer Störung der Wahrheitstabelle dar, erweitert sie auf den allgemeinen Hamming-Abstand und bestätigt sie durch exhaustive SAT-basierte Berechnungen für im AIG-Basis-System, wobei die Tightness der Schranke nachgewiesen wird.
Dieses Papier stellt ein umfassendes Rahmenwerk vor, das die Komplexitätsdichotomien für alle ungelösten Zählprobleme von Booleschen Tensor-Netzwerken durch die Klassifizierung der zugrunde liegenden endlichen Gruppen von binären Funktionen in neun Fälle vereint und dabei spezifische Fälle wie zyklische Gruppen löst oder Fortschritte erzielt.
Diese Arbeit verbessert den Laufzeitkomplexitätsfaktor für -Approximationsalgorithmen des -Median- und -Means-Clustering in niedrigdimensionalen euklidischen Räumen auf $2^{\tilde{O}(1/\varepsilon)^{d-1}} \cdot n \cdot \text{polylog}(n)$ und beweist unter der Gap-Exponential-Time-Hypothese, dass diese Laufzeit bis auf polylogarithmische Faktoren optimal ist.
Der Autor des Artikels arXiv:2603.09901v1 argumentiert, dass der Nachweis eines quantenmechanischen Vorteils trotz fehlender allgemeiner Konsens bereits 2019 erbracht wurde, und skizziert anschließend weitere Schritte für Theorie und Experimente auf diesem Gebiet.
Diese Arbeit widerlegt eine 23 Jahre alte Vermutung, indem sie die NP-Härte des Tetris-Clairings und des Überlebens für fast alle Tetromino-Typen unter dem Standard-Rotationssystem nachweist, während sie gleichzeitig polynomielle Algorithmen für Domino- und $1\times k$-Steine liefert.
Unter der Annahme der Sicherheit des Learning-with-Errors-Verfahrens beweisen die Autoren, dass kein Quantenalgorithmus den -Frege-Beweiskalkül effizient automatisieren kann, was die ersten Härteergebnisse gegen eine effiziente Beweissuche durch Quantenalgorithmen darstellt.
Diese Arbeit stellt ein differenziell privates Verfahren zur Schätzung von Black-Box-Statistiken vor, das einen effizienten Kompromiss zwischen der benötigten Datenmenge und der Anzahl der Funktionsauswertungen ermöglicht und durch fast optimale untere Schranken gestützt wird.
Die Arbeit präsentiert einen Polynomzeit-Algorithmus zum Isomorphietest für Erweiterungen abelscher Gruppen durch -erzeugte Gruppen, der insbesondere abelsch-zyklische und abelsch-einfache Erweiterungen umfasst und dabei auf einem neuen Verfahren zur Berechnung der Einheitengruppe endlicher Ringe basiert.
Die Arbeit vergleicht drei Satisfiability-Semantiken für Quantenlogik in festen Dimensionen und zeigt, dass die Standard-Hilbert-Gitter-Semantik strikt mächtiger ist als die global-kommutierende und die lokal-partielle-Boolesche Semantik, indem sie eine explizite Formel als Separator konstruiert.
Diese Arbeit stellt ein Basiswechsel-Rahmenwerk vor, das es ermöglicht, Ergebnisse zu Tensorfunktionen von spezifischen auf allgemeine Körper zu erweitern, wodurch gezeigt wird, dass der Slice-Rank für beliebige 3-Tensoren über jedem Körper linear durch den geometrischen Rang beschränkt ist und quasi-supermultiplikativ ist, was die Existenz des asymptotischen Slice-Ranks garantiert.
Diese Arbeit stellt eine neue Methode zur Bestimmung unterer Schranken für die bilineare Komplexität der Matrixmultiplikation über endlichen Körpern vor, die durch eine Kombination aus Substitutionsmethode und systematischer Backtracking-Suche mit dynamischer Programmierung erstmals beweist, dass die Komplexität der Multiplikation von $3 \times 3\mathbb{F}_2$ mindestens 20 beträgt.
Diese Arbeit präsentiert deterministische polynomialzeitliche Algorithmen zur Faktorisierung und zum Wiederauffinden von dünnbesetzten Polynomen mit beschränktem individuellem Grad sowie neue strukturelle Ergebnisse über deren Anzahl irreduzibler Faktoren, die frühere Arbeiten verbessern und teilweise offene Fragen klären.
Diese Arbeit stellt ein einheitliches, domänenunabhängiges Framework zur Berechnung des Bus-Faktors vor, das das Problem als kombinatorische Optimierung auf bipartiten Graphen modelliert, die NP-Schwere der exakten Berechnung beweist und effiziente Approximationsalgorithmen sowie einen neuartigen, auf Netzwerkrüstigkeit basierenden Maßstab für eine stabilere Risikobewertung entwickelt.
Dieser Artikel stellt ein alternatives Protokoll für einen quanteninformationsbasierten Vorteil vor, das auf parallel wiederholten CHSH-Spielen beruht, eine informationsbasierte Speichermaßzahl verwendet und im Vergleich zum Ansatz von Kretschmer et al. einen effizienteren Verifizierer sowie einen rauschrobusteren Quantenbeweis bietet.
Die Arbeit beweist, dass die Lücke zwischen der minimalen Größe einer Booleschen Schaltung und einer Booleschen Formel über dem AIG-Basis immer 0 oder 1 beträgt, wobei ein Wert von 1 ausschließlich durch eine einzige Gatterteilung mit Fan-out 2 entsteht, sobald die Anzahl der essentiellen Variablen einen bestimmten Schwellenwert überschreitet.
Diese Arbeit charakterisiert die Lösbarkeit von Permutations-Match-Puzzles auf -Gittern durch eine acyclische Bedingung, liefert eine Hook-Längen-Formel für die Anzahl der Lösungen und zeigt, dass das Finden minimaler Reparaturen bei einer Verallgemeinerung auf beliebige Permutationen NP-vollständig ist.
Die Arbeit zeigt, dass ein bestimmtes polynomiell lösbares Entscheidungsproblem mit kausalen Ausfühungsbeschränkungen eine inhärente sequenzielle Struktur aufweist, die es unmöglich macht, eine asymptotische parallele Beschleunigung zu erreichen, da die Informationsausbreitung pro Zeiteinheit auf einen Schritt begrenzt ist und keine -Schaltkreise existieren, die das Problem in realer Parallelzeit lösen können.