13 papers
A Subsampling Theorem for Constraint Satisfaction Problems with Large Arity
Martino Bernasconi, Matteo Castiglioni, Andrea Celli +2
Subsampling theorems for constraint satisfaction problems (CSPs) guarantee that the value of the CSP is approximately preserved after restricting it to small random subsets of vari…
Quantum Separability in Polynomial Time
Giulio Malavolta
The quantum separability problem asks whether a bipartite density matrix is separable or is -far from every separable state. We give a randomized polynomial-time algorithm for…
MPC in the Quantum Head (or: Superposition-Secure (Quantum) Zero-Knowledge)
Andrea Coladangelo, Ruta Jawale, Dakshita Khurana +2
The MPC-in-the-head technique (Ishai et al., STOC 2007) is a celebrated method to build zero-knowledge protocols with desirable theoretical properties and high practical efficiency…
Uncertainty Principles for the Number Theoretic Transform
Giulio Malavolta, Alon Rosen
Motivated by polynomial identity testing with exponentials (Li and Wu, ITCS'26), we study uncertainty principles for the number-theoretic transform (NTT). We show that the NTT sati…
A Modular Approach to Succinct Arguments for QMA
James Bartusek, Jiahui Liu, Giulio Malavolta
Succinct argument systems are of central importance to modern crytpography, enabling the efficient verification of computational claims. In the classical setting, Kilian (STOC 92)…
Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits
Damiano Abram, Giulio Malavolta, Lawrence Roy
We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors $\mathbf{x} \otimes \ma…