A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs

Autor: d'Orsi, Tommaso, Trevisan, Luca

We define a novel notion of ``non-backtracking'' matrix associated to any symmetric matrix, and we prove a ``Ihara-Bass'' type formula for it. We use this theory to prove new results on polynomial-time strong refutations of random constraint satisfac

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::51ec3633b8df6cfa6002930b819d8ffd
http://arxiv.org/abs/2204.10881

Mixed Size XOR Strong Refutation

Autor: Dowling, Brendan L.

An esteemed 2016 paper set a new lower bound on the clause density required to strongly refute a k-XOR formula in polynomial time. This paper used the sum of squares algorithm in conjunction with an improved bound for the injective tensor norm to rea

Externí odkaz: http://rave.ohiolink.edu/etdc/view?acc_num=case1600985815652235

Quantum Algorithms for the $$k$$-xor Problem

Autor: Lorenzo Grassi, María Naya-Plasencia, André Schrottenloher

Publikováno v: Advances in Cryptology – ASIACRYPT 2018-24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2–6, 2018, Proceedings, Part I
ASIACRYPT 2018-24th Annual International Conference on the Theory and Application of Cryptology and Information Security
ASIACRYPT 2018-24th Annual International Conference on the Theory and Application of Cryptology and Information Security, Dec 2018, Brisbane, Australia. pp.527-559, ⟨10.1007/978-3-030-03326-2_18⟩
Lecture Notes in Computer Science
Lecture Notes in Computer Science-Advances in Cryptology – ASIACRYPT 2018
Lecture Notes in Computer Science ISBN: 9783030033255
ASIACRYPT (1)

International audience; The k-xor (or generalized birthday) problem is a widely studied question with many applications in cryptography. It aims at finding k elements of n bits, drawn at random, such that the xor of all of them is 0. The algorithms p

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0204d0dbd2a9db57beaa24df3d2a82ff

Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.