4 citations · 20 across the 25 of their papers we have counts for
31 papers
Limitations on Autoregressive Token Generation via Sequential Sampling
Gal Arnon, Andrej Bogdanov, Paul Lou +3
We study autoregressive token generation through the notion of sequential samplers: A circuit that samples the next symbol only given the previous ones and possibly a small amount…
From Chunks to Functional Evidence: Function-Aware Retrieval for EDA Documentation QA
Xiaotian Qiu, Kairui Liu, Shi Chenyi +3
Retrieval-Augmented Generation (RAG) is widely used to ground answers in documents. For complex technical documentation, however, the primary bottleneck is often not model reasonin…
The Grothendieck Game and Self-Testing Continuous Groups
Alexander Kulpe, Giulio Malavolta, Simon Schmidt +1
Self-testing certifies quantum states and measurements from observed correlations alone, without requiring a description of the devices that produce them. In this work we establish…
Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
Martino Bernasconi, Giulio Malavolta
We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the local factors of dimension is chosen from a convex set. We give a det…
Succinct Arguments for QMA from Collapsing Hash Functions
James Bartusek, Giulio Malavolta
We prove the existence of succinct arguments for QMA, assuming only the existence of collapsing hash functions. This is the first scheme that relies only on unstructured ``Minicryp…
Sharper Bounds for the Complex Grothendieck Constant
Steven Heilman, Chris Jones, Giulio Malavolta
We show that , where is the complex Grothendieck constant. The upper bound improves on Haagerup's bound of $1.40490913\ldots…
Robustness of Hidden-Variable Theories and Matrix Scaling
Giulio Malavolta, Harold Nieuwboer, Akshay Ramachandran +1
Motivated by quantum foundations and complexity theory, Aaronson formalized a hidden-variable theory inspired by a proposal by Schrödinger. To any quantum state and unitary, this S…
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 t…
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)…
The Grothendieck Constant is Strictly Larger than Davie-Reeds' Bound
Chris Jones, Giulio Malavolta
The Grothendieck constant is a fundamental quantity in functional analysis, with important connections to quantum information, combinatorial optimization, and the geometry…
The Knowledge Complexity of Quantum Problems
Giulio Malavolta
Foundational results in theoretical computer science have established that everything provable, is provable in zero knowledge. However, this assertion fundamentally assumes a class…
Computational Monogamy of Entanglement and Non-Interactive Quantum Key Distribution
Alex B. Grilo, Giulio Malavolta, Michael Walter +1
Quantum key distribution (QKD) enables Alice and Bob to exchange a secret key over a public, untrusted quantum channel. Compared to classical key exchange, QKD achieves everlasting…
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…
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…
How to Verify that a Small Device is Quantum, Unconditionally
Giulio Malavolta, Tamer Mour
A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine. In this…
A New World in the Depths of Microcrypt: Separating OWSGs and Quantum Money from QEFID
Amit Behera, Giulio Malavolta, Tomoyuki Morimae +2
While in classical cryptography, one-way functions (OWFs) are widely regarded as the "minimal assumption," the situation in quantum cryptography is less clear. Recent works have pu…
A bound on the quantum value of all compiled nonlocal games
Alexander Kulpe, Giulio Malavolta, Connor Paddock +2
A cryptographic compiler introduced by Kalai et al. (STOC'23) converts any nonlocal game into an interactive protocol with a single computationally bounded prover. Although the com…
Permutation Superposition Oracles for Quantum Query Lower Bounds
Christian Majenz, Giulio Malavolta, Michael Walter
We propose a generalization of Zhandry's compressed oracle method to random permutations, where an algorithm can query both the permutation and its inverse. We show how to use the…
Exponential Quantum One-Wayness and EFI Pairs
Giulio Malavolta, Tomoyuki Morimae, Michael Walter +1
In classical cryptography, one-way functions are widely considered to be the minimal computational assumption. However, when taking quantum information into account, the situation…
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
David Cui, Giulio Malavolta, Arthur Mehta +5
Nonlocal games are a foundational tool for understanding entanglement and constructing quantum protocols in settings with multiple spatially separated quantum devices. In this work…
Public-Key Encryption with Quantum Keys
Khashayar Barooti, Alex B. Grilo, Loïs Huguenin-Dumittan +4
In the framework of Impagliazzo's five worlds, a distinction is often made between two worlds, one where public-key encryption exists (Cryptomania), and one in which only one-way f…
Weakening Assumptions for Publicly-Verifiable Deletion
James Bartusek, Dakshita Khurana, Giulio Malavolta +2
We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state ge…