45 papers
Dit artikel bewijst dat het benaderingsprobleem van de dekkingsstraal op roosters in de -norm NP-moeilijk is voor expliciete waarden van groter dan ongeveer 35,31, waarbij de benaderingsfactor naar $9/8p$ naar oneindig gaat.
Deze paper sluit de complexiteitskloof voor d-QBF met weinig existentiële variabelen door aan te tonen dat de dubbel-exponentiële tijd afhankelijkheid van het aantal existentiële variabelen optimaal is onder de ETH, terwijl voor het beperkte geval van twee kwantorenblokken een bijna optimale bijna-exponentiële algoritme wordt gepresenteerd.
Dit artikel introduceert AlphaEvolve, een op een groot taalmodel gebaseerd agent dat code mutaties uitvoert en daarmee de ondergrenzen voor vijf klassieke Ramsey-getallen heeft verbeterd, terwijl het tevens bestaande resultaten succesvol reproduceerde en matchte.
Dit artikel presenteert een expliciete constructieve bovengrens voor de verandering in circuitsgrootte bij verstoringen van de waarheidstabel, bevestigt deze theoretische schatting via een telescopisch argument en valideert de strakheid van de bound voor in de AIG-basis door middel van exhaustieve SAT-gebaseerde verificatie.
Dit artikel presenteert een unificerend raamwerk voor dichotomiestellingen over complexiteit van Booleaanse tensornetwerken, dat onopgeloste problemen classificeert op basis van eindige groepen van 2x2-matrices en specifieke gevallen oplost of reduceert.
Dit paper verbetert de looptijd voor -benaderingsalgoritmen voor -median en -means clustering in laagdimensionale Euclidische ruimtes en bewijst een bij benadering overeenkomende ondergrens onder de Gap Exponentiële Tijd Hypothese.
In dit artikel betoogt de auteur dat er ondanks het ontbreken van consensus inderdaad quantumvoordeel is bereikt en schetst hij de volgende stappen voor theorie en experimenten op dit gebied.
Deze paper weerlegt een 23 jaar oude conjectuur door aan te tonen dat Tetris met slechts één type tetromino (behalve de O-vorm) NP-moeilijk is, terwijl het probleem voor domino's en specifieke $1\times k$-vormen wel in polynomiale tijd oplosbaar is.
Dit artikel bewijst dat onder de Learning with Errors-aanname geen kwantumalgoritme het -Frege-bewijssysteem kan automatiseren, wat de eerste hardheidresultaten vormt tegen kwantumbewijssuggestie en een nieuw verband legt tussen kwantumberekening en propositional bewijzen.
Deze paper presenteert een nieuw schema voor differentieel privé schatten van zwarte-bok statistieken dat een afweging biedt tussen statistische en orakel-efficiëntie, vergezeld van ondergrenzen die de near-optimale aard van het schema aantonen.
Dit artikel presenteert een polynomiale tijd-algoritme om isomorfisme te testen voor uitbreidingen van abelse groepen door -gegenereerde groepen, waarbij de methode onder meer een nieuwe polynomiale tijd-algoritme voor het berekenen van de eenheidsgroep van een eindige ring gebruikt.
Dit artikel vergelijkt drie waarheidsdefinities voor kwantumsatisfiabiliteit in een vaste eindige dimensie en bewijst dat de standaard Hilbert-lattice-semantiek strikt ruimer is dan zowel de globale commutatieve als de lokale partiële-Boolese semantiek, wat wordt aangetoond door een expliciet scheidingsformule die in de eerste wel maar in de andere twee niet satisfieerbaar is.
Dit artikel introduceert een raamwerk voor basisverandering dat het mogelijk maakt om resultaten over tensorfuncties van specifieke velden uit te breiden naar algemene velden, waardoor wordt bewezen dat de slice-rang voor 3-tensors over elk veld lineair begrensd is door de geometrische rang en dat de asymptotische slice-rang bestaat.
Dit paper introduceert een nieuwe methode die backtracking en substitutie combineert om aan te tonen dat de bilineaire complexiteit van het vermenigvuldigen van $3 \times 3\mathbb{F}_2$ minimaal 20 is, waarmee een langdurig lagergrensrecord van 19 wordt verbeterd.
Dit artikel presenteert deterministische algoritmen voor het factoriseren van schaarse polynomen met een beperkte individuele graad, waaronder een polynoomtijd-algoritme voor het vinden van alle schaarse delers en een verbeterde complexiteit voor het herleiden van factoren uit een product via blackbox-toegang.
Dit artikel introduceert een unificerend, domein-onafhankelijk raamwerk voor het berekenen van de bus-factor door projecten als bipartiete grafen te modelleren, bewijst dat zowel de exacte berekening als de geïntroduceerde robuustheidsgebaseerde maatstaf NP-moeilijk zijn, en presenteert efficiënte lineaire benaderingsalgoritmen die projectrisico's informatiever en stabieler inschatten dan bestaande methoden.
Dit paper introduceert een alternatief voorstel voor een quantum-informatievoordeel gebaseerd op parallel herhaalde CHSH-spellen, dat een efficiëntere verificateur en een robuustere, minder geheugenintensieve quantumbewijzer biedt dan het recente experiment van Kretschmer et al.
Dit artikel bewijst dat het verschil tussen de minimale grootte van een Boolese schakeling en een formule in de AIG-basis altijd 0 of 1 is, en dat delen van subexpressies alleen nodig is wanneer het aantal essentiële variabelen een bepaalde drempel overschrijdt.
Dit artikel introduceert permutatie-matchpuzzels op roosters, karakteriseert de oplosbaarheid ervan via een acyclische voorwaarde, levert een tellende formule voor oplossingen, biedt een lineaire algoritme voor het repareren van onoplosbare gevallen, en toont aan dat de veralgemening met willekeurige permutaties NP-compleet is.
Dit artikel toont aan dat er een klasse van polynomiale tijdproblemen bestaat met een intrinsieke causale structuur die, ondanks logische parallelle mogelijkheden, fundamenteel beperkt is tot lineaire causale tijd en dus geen asymptotische snelheidswinst toestaat door parallelle uitvoering.