45 Arbeiten
Dieser Artikel stellt einen vereinfachten und optimierten Algorithmus zur -Approximation des durchschnittlichen Grades in Graphen mit beschränkter Arboreszenz vor, der logarithmische Verluste vermeidet und eine Abfragekomplexität von erreicht.
Diese Arbeit beweist neue Trennungen zwischen klassischen und flachen Quantenschaltkreisen, zeigt, dass Quantenschaltkreise mit unendlichen Gattersets Threshold-Gates implementieren können, und stellt fest, dass höherdimensionale Hilbert-Räume in diesem Kontext keinen Vorteil gegenüber Qubit-Implementierungen bieten.
Dieses Papier untersucht systematisch die Rechenkomplexität im Property Testing, indem es Hierarchiesätze für die Beziehung zwischen Abfrage- und Zeitkomplexität herleitet und unter fine-grained Annahmen wie der k-SUM-Vermutung eine fundamentale Lücke zwischen diesen beiden Komplexitätsmaßen für die Approximation des Abstands zu Halbräumen aufzeigt.
Die Autoren zeigen, dass die Frage, ob eine gegebene berechenbare Strategie im Yu-Gi-Oh!-TCG von einem bestimmten Spielzustand aus gewinnt, unentscheidbar und sogar -vollständig ist, indem sie das Problem auf die Menge der abzählbaren Wohlordnungen reduzieren und dabei legale Decks verwenden.
Die Arbeit identifiziert sechs Dimensionen, darunter neuartige Aspekte wie Richtung und Zeitlichkeit, die eine fundamentale operationale Asymmetrie zwischen der Erzeugung und der Erkennung formaler Sprachen aufzeigen, wobei sie die verbreitete Annahme widerlegt, dass Erzeugung immer einfacher sei als Parsing, und die anhaltende Trennung dieser Prozesse in modernen KI-Modellen kritisch beleuchtet.
Diese Habilitationsschrift entwickelt zeit- und speichereffiziente Algorithmen für Polynomberechnungen unter Raumrestriktionen, wobei sie sowohl fundamentale Operationen als auch die Interpolation und Faktorisierung dünnbesetzter Polynome behandelt.
Diese Arbeit charakterisiert die klassische Simulierbarkeit von Quantenschaltkreisen, die einer dünnbesetzten klassischen Nachverarbeitung unterliegen, und zeigt, dass bestimmte ansonsten schwer simulierbare Schaltkreise wie IQP oder Clifford-Magic-Schaltkreise effizient simulierbar sind, während Schaltkreise mit konstanter Tiefe durch einen probabilistischen Algorithmus unter Zugriff auf kommutierende Quantenschaltkreise simuliert werden können.
Dieses Papier interpretiert die Suche nach NP-Zeugnissen als informations-theoretischen Prozess und zeigt im „psocid"-Modell, dass bei strukturlosen, gleichverteilten Prioritäten und nur durch Gleichheitsabfragen begrenzte Informationsgewinnung eine zuverlässige Wiederherstellung des Zeugnisses aufgrund einer fundamentalen Diskrepanz zwischen benötigten und erzielbaren Informationen unmöglich ist, was die exponentielle Komplexität der Suche auf eine informationstheoretische Ursache zurückführt.
Dieser Artikel zeigt, dass das Maximum Partial List H-Coloring-Problem auf P_5-freien Graphen für jeden festen Graphen H in polynomialer Zeit lösbar ist, wodurch eine offene Frage von Agrawal et al. beantwortet und ein bestehender Algorithmus von Chudnovsky et al. verbessert wird.
Dieser Artikel untersucht die Komplexität eingeschränkter Fragmente von Decision DNNF, indem er eine neue Methode zur Herleitung von Untergrenzen für das Modell -OBDD entwickelt, exponentielle Trennungen zwischen verschiedenen Entscheidungsdiagrammen aufzeigt und die Effizienz von Apply-Operationen sowie die Leistungsfähigkeit eines relaxierten Modells für CNF-Formeln mit beschränkter Incidence-Treeweite analysiert.
Diese Arbeit widerlegt die Annahme einer exponentiellen Quantenbeschleunigung für das -Problem, indem sie effiziente klassische Algorithmen für alle in der Studie von Chen, Liu und Zhandry behandelten Instanzen vorstellt.
Diese Arbeit stellt einen $4/3$-Approximationsalgorithmus für das Tree Augmentation Problem vor, der eine neuartige „deferred local-ratio"-Technik nutzt und dabei schneller als bestehende LP-basierte Ansätze ist.
Diese Arbeit präsentiert eine vollständige Klassifizierung der verteilten Komplexität lokaler Optimierungsprobleme in gerichteten Zyklen, die zeigt, dass die Komplexität für jede Approximation in deterministischen und randomisierten LOCAL-Modellen genau eine von vier möglichen Stufen annimmt, und bietet zudem einen effizienten Algorithmus zur automatischen Bestimmung dieser Komplexitätsklasse sowie zur Synthese optimaler verteilter Algorithmen.
Diese Arbeit erklärt die überlegene Parallelisierbarkeit linearer RNNs im Vergleich zu nichtlinearen RNNs durch eine Verbindung zu Komplexitätsklassen, wonach lineare RNNs logarithmische Tiefenschaltungen darstellen, während nichtlineare Varianten P-vollständige Probleme lösen können, was eine fundamentale Barriere für ihre effiziente Parallelisierung darstellt.
Diese Arbeit stellt einen integrativen Ansatz zur Verallgemeinerung der fairen Top--Auswahl auf mehrere geschützte Gruppen vor, der durch eine neue Härteanalyse die Berechnungskomplexität aufdeckt, eine alternative Disparitätsmessung über den Nutzenverlust einführt und durch eine zweigleisige Lösung sowohl theoretische Erkenntnisse als auch starke empirische Ergebnisse auf realen Datensätzen liefert.
Diese Arbeit stellt Quantenalgorithmen vor, die das NP-vollständige Problem der Netzwerksignal-Koordination sowie dessen robuste Variante mittels Grovers Suchalgorithmus lösen und dabei eine quadratische Beschleunigung gegenüber klassischen Ansätzen erreichen, was durch Simulationen und Tests auf einem echten Quantencomputer verifiziert wurde.
Dieser Artikel stellt einen effizienten Algorithmus vor, der die strukturierte Sparsity eines Polynomsystems über einem endlichen Körper ausnutzt, um durch aufeinanderfolgende Resultantenberechnungen eine univariate Gleichung zu finden und so die Lösung deutlich schneller als Brute-Force- oder Standard-Gröbner-Basis-Methoden zu ermitteln.
Diese Arbeit stellt eine exakte Korrespondenz zwischen der Ausdruckskraft von rekurrenten Graph-Neuronalen Netzen und rekurrenten arithmetischen Schaltkreisen über den reellen Zahlen her, indem sie beide Modelle wechselseitig simulieren und somit ihre rechnerische Äquivalenz nachweist.
Die Arbeit präsentiert einen $2^{O(k \log k)} n$-zeitlichen Algorithmus für das Optimal-Morse-Matching-Problem auf CW-Komplexen mit beschränkter Baumweite und beweist unter der Annahme der Exponentialzeit-Hypothese, dass keine wesentlich schnellere Lösung existiert.
Die Autoren zeigen, dass die Aaronson-Ambainis-Vermutung für einen nicht vernachlässigbaren Anteil zufälliger Einschränkungen eines Polynoms gilt, sofern dessen Varianz hinreichend groß ist.