CS Paper Radar

Asymmetry and Complexity of Nondeterministic Computations

Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira

cs.CC ·submitted 2026-10-14 13:38 UTC · v1
theory

Abstract

Symmetry of Information (SoI) [ZL70] is a fundamental theorem of classical Kolmogorov complexity whose status for time-bounded computation is closely related to central open problems in complexity theory and cryptography. In a recent development, [HMO26] showed that SoI fails for $rKt$ complexity, namely in the setting of randomized computation. By contrast, many basic properties of Kolmogorov complexity are known to remain valid in the presence of nondeterminism [HLO26], suggesting that SoI may provide a fruitful structural principle for exploring the relative power of randomness and nondeterminism in computation. Our results reveal that the validity of SoI for nondeterministic computation, namely for $nKt$ complexity, is a subtle question connected to several frontiers. We show that symmetry of information holds on average for randomized extensions of $nKt$, while its worst case validity would imply breakthrough complexity separations. Although the standard cryptographic argument for asymmetry does not extend to the nondeterministic setting, we provide evidence that information remains asymmetric in nondeterministic computations. Among other results, we show that SoI would imply a collapse of exponential time classes to low levels of the polynomial hierarchy. Then, building on the work of [Hir22b, GK22, KK26, HMO26], we develop a general framework connecting symmetry of information, meta-complexity, and explicit constructions in the nondeterministic setting. More precisely, we prove that suitable formulations of these three notions are quantitatively equivalent. We apply different aspects of this correspondence to make progress on complexity lower bounds and on the failure of SoI for nondeterministic computation. These consequences are unconditional and provide some of the strongest known lower bounds in meta-complexity.

Closest papers

Nearest neighbours by meaning across the whole index.

The Gap Between Average-Case and Worst-Case Complexity

cs.CC ·2026-10-13 ·Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
publishedtheory similarity 0.71
Abstract

Understanding the average-case complexity of $\mathsf{NP}$ is a central goal in complexity theory and cryptography. A necessary milestone is to understand the corresponding average-case versus worst-case question for the polynomial hierarchy ($\mathsf{PH}$). In a celebrated result, Hirahara [Hir21] proved that if every distributional problem in $\mathsf{PH}$ is easy on average, then every language in $\mathsf{PH}$ admits worst-case algorithms running in time $2^{O(n/\log n)}$. Remarkably, although the statement of Hirahara's theorem makes no reference to meta-complexity, all known proofs appear to use time-bounded Kolmogorov complexity and its associated meta-computational problems in an essential way. We show that the reliance on techniques and perspectives from meta-complexity is not simply a coincidence. Building on previous work of Hirahara [Hir20] and on a recent result of Hu, Lu, and Oliveira [HLO25], we prove that relating the average-case and worst-case complexities of $\mathsf{PH}$ is in fact equivalent to a purely meta-computational implication: efficient algorithms for a standard gap version of $\mathsf{MINpKT}$ with $\mathsf{PH}$ oracle access imply efficient algorithms for a mild gap version. Crucially, in these promise problems the standard gap separates a YES instance with time bound $t$ from a NO instance with time bound $\mathsf{poly}(t)$, whereas the mild gap keeps the YES threshold $t$ and moves the NO threshold to $t+\mathsf{poly}(n)$. Together with prior work, this equivalence points to the study of gap reductions as a potentially promising route toward understanding the relation between average-case and worst-case complexity. We make progress by proving that the gap in running time can be eliminated in the average-case setting. Finally, we prove that in the worst-case setting any efficient reduction between the two problems must use nonrelativizing techniques.

0.28

(Implicitly) Characterizing Probabilistic Polynomial Time as Used in Cryptography

cs.PL cs.CR ·2026-10-10 ·Ugo Dal Lago, Giulia Giusti
published similarity 0.69
Abstract · Extended version of a paper to appear in the proceedings of FSTTCS 2026

In this paper, we show how a recently introduced $λ$-calculus for randomized computation, called $λ\mathbf{BLL}$, can accurately capture the notions of first- and second-order polytime computations used in cryptographic definitions and proofs. These results, spelled out in the style of so-called \emph{implicit computational complexity}, imply that $λ\mathbf{BLL}$ is sufficiently powerful to express experiments and adversaries as used in cryptography, and that reductions, when formulated within the calculus, are guaranteed to be complexity-preserving. Remarkably, while polynomial-time soundness holds for the full calculus, polynomial-time completeness already follows in presence of a minimal finite set of basic functions.

0.28

A Complexity-Theoretic Approach to Proofs of Space

cs.CR cs.CC ·2026-08-10 ·Marshall Ball, Jiaxin Guan
published similarity 0.67
Abstract

A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information. To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions. We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.

0.22

Computational Cryptography from Pseudoentanglement

cs.CR quant-ph ·2026-09-24 ·Ilia Ryzov, Manuel Goulão, Faedi Loulidi, David Elkouss
similarity 0.65
Abstract

The advent of pseudoentanglement and computational entanglement theory bootstrapped a wave of research at the intersection of computer science and information theory. In parallel, computational cryptography has undergone substantial development, prompted by the introduction of pseudorandom states and followed by the establishment of a baseline for the computational hardness required for quantum cryptography, from which EFI pairs emerge as a central primitive. We study the connection between pseudoentanglement and computational cryptography through EFI pairs. Our goal is to enable the use of resources arising from computational entanglement theory in the field of cryptography. For this, we establish the relation between operational instances of pseudoentanglement and the hierarchy of minimal assumptions for computational cryptography. We show that the existence of pseudoentanglement under two different operational definitions, with efficient state generation, is a sufficient condition for the existence of EFI pairs. Combined with a previously established result that the converse also holds under the second definition, this allows us to also demonstrate their equivalence. This places pseudoentanglement alongside other minimal assumptions in cryptography, not only offering an alternative perspective on this fundamental problem, but also building a bridge that allows insights from either area to inform the other. While proving these theorems, we introduce and demonstrate technical lemmas in quantum information and computational entanglement theory, relating the computational entanglement measures to the distance between states, establishing distinguishing conditions for mixtures of two families given pairwise distances between their states, and demonstrating the first continuity relation for a computational entanglement measure.

0.26

The Complexity of Unpredictability

cs.CC ·2026-11-04 ·Aryan Agarwala, Dani Dorfman
theory similarity 0.65
Abstract

We initiate the study of middle-bit predictors: functions that take as input a string with one missing bit and try to predict that bit. These are closely related to next-bit predictors, a classical object in pseudorandomness. We study the deterministic complexity of computing an unpredictable distribution (UNPRED). Given a list of middle-bit predictors in circuit form and a parameter $ε>0$, output a multiset of strings such that each predictor succeeds with probability less than $1/2+ε$ on a uniformly sampled string from the multiset. We write $\mathsf{UNPRED}^{\mathsf{TC}^1}$ for the restriction to $\mathsf{TC}^1$ predictors. We show that UNPRED offers a unified route towards resolving several major open problems in catalytic computation, the biggest of which is whether deterministic polynomial time (P and FP) can simulate catalytic logspace (CL and SearchCL). It is believed that $\mathsf{SearchCL}\subseteq\mathsf{FP}$. We prove $$\mathsf{UNPRED}\in\mathsf{FP}\implies\mathsf{SearchCL}\subseteq\mathsf{FP}\implies\mathsf{UNPRED}^{\mathsf{TC}^1}\in\mathsf{FP}.$$ Thus, the questions of whether UNPRED is in FP and whether SearchCL is contained in FP are almost equivalent, up to the restriction to $\mathsf{TC}^1$ circuits. We also show that any deterministic polynomial-time algorithm for $\mathsf{UNPRED}^{\mathsf{TC}^1}$ must exploit properties of $\mathsf{TC}^1$ circuits, either in the algorithm itself or in its analysis. To our knowledge, this would also be the first algorithm to use the structure of $\mathsf{TC}^1$ circuits in this way to solve a natural problem, thus advancing our understanding of Boolean circuits. Together, our results provide strong evidence that middle-bit predictors could be the key to unlocking several major open problems in catalytic computation, pseudorandomness, and Boolean circuit complexity.

0.26

Improved lower bounds for decomposable randomized encoding

cs.CC cs.CRcs.DM ·2026-09-16 ·Justin Holmgren, Kewen Wu
theory similarity 0.64
Abstract · 24 pages

A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $Ω(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $Ω(n^2)$ lower bound on DRE size for non-explicit Boolean functions.

0.46

$\mathsf{EFI}\Leftrightarrow\mathsf{1PRS}$

cs.CR quant-ph ·2026-10-13 ·Rishabh Batra
similarity 0.63
Abstract

A series of recent works has established EFI pairs as the "minimal" assumption for quantum cryptography. Recently, Cavalar et al. [CCC+26] showed that EFI pairs are equivalent to non-uniform expanding single-copy pseudorandom state generators (1PRS), and obtained a non-uniform meta-complexity characterization of EFI pairs. We remove the non-uniformity in their construction and prove that EFI pairs are equivalent to expanding 1PRS. As a corollary, we obtain the first uniform meta-complexity characterization of EFI pairs. Together with the equivalence of statistically verifiable one-way state generators and commitments proved by Batra and Jain [BJ24], this gives a quantum analogue of the classical equivalence between one-way functions, commitments, and pseudorandom generators.

0.10

On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle

cs.CR cs.CC ·2026-11-02 ·Alexander Hoover, Giuseppe Persiano, Kevin Yeo
theoryhot direction similarity 0.63
Abstract

Information-theoretic MPC among $n$ parties with $t$ corruptions can securely evaluate a circuit $C$ with $O(|C| \cdot t/(n-t))$ online communication in the preprocessing model and $O(|C| \cdot t/(n-2t))$ communication in the honest majority setting. Damgård, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same $Ω(|C| \cdot t/(n-t))$ lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an $Ω(|C|)$ communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when $n = O(\log λ)$, beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with $\mathrm{poly}(λ, \log |C|)$ communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits $C$ such that every blackbox protocol with $o(|C|)$ quantum communication must perform $Ω(|C|)$ cryptographic operations.

0.33