45 papers
Dit artikel presenteert een volledige analyse van een sublineair algoritme dat de gemiddelde graad van een graf met begrensd arboriciteit benadert met een querycomplexiteit van , waardoor de logaritmische verliezen en de complexiteit van de oorspronkelijke beschrijving worden vermeden.
Dit artikel bewijst nieuwe scheidingen tussen klassieke en kwantumcirkels met geringe diepte, toont aan dat kwantumcirkels met oneindige poetzetsels en modulaire poorten gelijkwaardig zijn aan klassieke drempelcirkels, en concludeert dat hogedimensionale kwantumsystemen in deze context geen extra voordeel bieden boven standaard qubit-implementaties.
Dit artikel initieert een systematische studie naar de computationele complexiteit van eigenschapstesten door hiërarchiestellingen te bewijzen en een fijnmazige ondergrens voor de tijdcomplexiteit van het benaderen van halfruimten af te leiden, waarmee een fundamenteel verschil tussen query- en tijdcomplexiteit wordt aangetoond.
Deze paper bewijst dat het bepalen van een winnende strategie in Yu-Gi-Oh! TCG een onbeslisbaar probleem is dat zelfs -compleet is, wat betekent dat het minstens zo moeilijk is als het Halting-probleem en dat het zelfs de complexiteit van het bepalen van tellbare welordeningen overtreft.
Dit artikel identificeert zes onafhankelijke dimensies waarin generatie en herkenning binnen de formele taaltheorie fundamenteel verschillen, weerlegt het simplistische idee dat generatie altijd makkelijk is, en verbindt deze asymmetrie met concepten als verrassing (surprisal) en de operationele beperkingen van grote taalmodellen.
Dit werk presenteert nieuwe algoritmen voor polynoomberekeningen die zowel tijd- als ruimte-efficiënt zijn, met name door de ontwikkeling van de eerste quasi-lineaire methode voor interpolatie van schaarse polynomen en het bestuderen van de complexiteit van fundamentele bewerkingen onder ruimtelijke beperkingen.
Dit artikel onderzoekt de klassieke simulatie van kwantumkringen gevolgd door schaarse klassieke post-processing, waarbij het een noodzakelijke en voldoende voorwaarde formuleert voor simulatie en aantoont dat constant diepe kringen onder deze omstandigheden efficiënt kunnen worden gesimuleerd met behulp van probabilistische algoritmen en commuterende kwantumkringen.
Dit artikel herinterpreteert het vinden van NP-getuigen als een informatieverwervingsproces en toont in het 'psocid'-model aan dat de fundamentele beperking van gelijkheidsprobes, die slechts verwaarloosbaar weinig wederzijdse informatie onthullen, leidt tot een onoverbrugbare kloof tussen de benodigde en verkregen informatie, waardoor de exponentiële complexiteit van de zoektocht wordt verklaard.
Dit artikel bewijst dat het Maximum Partial List H-Coloring-probleem voor elke vaste graaf H in polynomiale tijd oplosbaar is op P5-vrije grafen, waarmee een open vraag van Agrawal et al. wordt beantwoord en een bestaand algoritme wordt verbeterd.
Dit artikel onderzoekt de complexiteit van beperkte fragmenten van Decision DNNF, met name -OBDD en gestructureerde Decision DNNF, door nieuwe methoden voor ondergrenzen te ontwikkelen, exponentiële scheidingen aan te tonen en een efficiëntere variant voor CNF-formules met begrenste incidentie-treewidth te introduceren.
Deze paper presenteert efficiënte klassieke algoritmen voor het -probleem en verwante varianten, waarmee wordt aangetoond dat er geen exponentiële kwantumsnelheidswinst meer bestaat voor deze eerder als kwantum-veelbelovend beschouwde problemen.
Deze paper introduceert een nieuwe methode genaamd 'deferred local-ratio' die, gecombineerd met 'climbing', een $4/3O(m\cdot\sqrt{n})$.
Dit artikel presenteert een volledige classificatie van de gedistribueerde complexiteit voor lokale optimalisatieproblemen in gerichte cycli, waarbij het aantoont dat de complexiteit voor zowel deterministische als probabilistische modellen valt binnen één van vier specifieke klassen en dat deze klasse automatisch kan worden bepaald en een optimale algoritme kan worden gegenereerd.
Dit paper legt uit dat lineaire RNN's beter paralleliseerbaar zijn dan niet-lineaire RNN's doordat ze logische diepte-circuits simuleren die in de complexiteitsklasse NC1 vallen, terwijl niet-lineaire RNN's P-complete problemen kunnen oplossen wat een fundamenteel parallelisatiebeperking vormt.
Dit paper introduceert een geïntegreerde aanpak voor het selecteren van eerlijke top- kandidaten over meerdere beschermde groepen, waarbij zowel de hardheid van het probleem wordt geanalyseerd als een nieuwe maatstaf voor utiliteitsverlies wordt voorgesteld om robuustere en efficiëntere oplossingen te garanderen.
Dit artikel presenteert de ontwikkeling en simulatie van kwantumalgoritmen, gebaseerd op Grover's zoekalgoritme, die een kwadratische versnelling bieden voor het oplossen van het NP-volledige Netwerksignaalcoördinatieprobleem en zijn robuuste varianten, zelfs bij polynoom-precisie.
Dit artikel beschrijft een efficiënt algoritme dat de gestructureerde sparsiteit van een polynoomstelsel over een eindig lichaam benut om via opeenvolgende resultanten een univariate polynoom te berekenen, waarmee de oplossing aanzienlijk sneller kan worden gevonden dan met brute-force of standaard Gröbner-basis-methoden.
Dit artikel vestigt een exacte correspondentie tussen de expressiviteit van recurrente grafische neurale netwerken en die van recurrente rekenkringen over de reële getallen, waarbij beide modellen elkaars berekeningen kunnen simuleren.
Deze paper presenteert een nieuw algoritme met looptijd $2^{O(k \log k)} nk$, en bewijst dat deze complexiteit scherp is onder de Exponentiële Tijd Hypothese.
Dit artikel bevestigt dat de Aaronson-Ambainis-vermoeden waar is voor een niet-verwaarloosbaar deel van willekeurige restricties van een polynoom, mits de variantie niet te laag is.