45 papers
Dit paper introduceert SCORE, een programmeertaal voor het manipuleren van variabelen en stacks, en bewijst met behulp van een bewijshulpmiddel dat alle operaties in deze taal totale bijecties zijn, waardoor het een reversibel computationeel model biedt dat geschikt is voor het bestuderen van computationele complexiteit.
Deze paper toont aan dat elke niet-adaptieve q-query RLDC met een voldoende kleine foutkans in de geluidsheid ook een q-query LDC oplevert, waardoor de relatie tussen deze coderingsvormen wordt versterkt en betere ondergrenzen voor RLDCs, RLCCs en PCPPs worden afgeleid.
Dit boek biedt een overzicht van de recente doorbraken in het lijstdecoderen van Reed-Solomon-codes en aanverwante polynoomcodes, waaronder efficiënte algoritmen die tot aan de informatietheoretische capaciteit werken met een optimale lijstgrootte en bijna-lineaire of sublineaire looptijd.
Deze paper presenteert een willekeurig gepolynoom tijd-algoritme voor het leren van read-once determinanten en het oplossen van het zwarte-kastversie van het Principal Minor Assignment-probleem door gebruik te maken van een eigenschap van dichte matrices die de rank-one extensie-eigenschap wordt genoemd.
Dit onderzoek presenteert een quantumalgoritme voor het testen van benaderende graf-isomorfie dat via quantum walks een query-complexiteit van bereikt, waarmee een polynomiële snelheidswinst wordt gevestigd ten opzichte van klassieke methoden.