2 citations · 8 across the 17 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Strongly Refuting Random CSP without Literals
Siu On Chan, Tommaso d'Orsi, Jeff Xu
Under what condition is a random constraint satisfaction problem hard to refute by the sum-of-squares (SoS) algorithm? A sufficient condition is t-wise uniformity, that is, each co…
cs.CC2025
On Finding Randomly Planted Cliques in Arbitrary Graphs
Francesco Agrimonti, Marco Bressan, Tommaso d'Orsi
We study a planted clique model introduced by Feige where a complete graph of size is planted uniformly at random in an arbitrary -vertex graph. We give a simple dete…
cs.CC2022
A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs
Tommaso d'Orsi, Luca Trevisan
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 resul…