CS Paper Radar

Daily listing

2026-11-17 · cs.CC

6 papers first submitted this day (UTC) in cs.CC — Computational Complexity. arXiv announces a day's submissions the next evening, so the newest day fills up over ~24 h.

Score = weighted mean ofCitations 20%Upvotes 10%Code stars 10%Venue 15%Code/data 10%Novelty 15%Momentum 15%Substance 5%how it works

Theory & Algorithms 6

Derandomized Sunflowers and Radical Lower Bounds

cs.CC math.CO ·2026-11-17 ·Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff
publishedtheory
Abstract · Full version of FOCS 2026 paper

Robust Sunflower lemmas imply that any large enough monotone DNF of width $w$ contains a sunflower, i.e., a DNF equivalent to the conjunction of a common core with a DNF that is heavily biased towards $1$. While these lemmas are typically proved in the context of the uniform distribution or i.i.d. distributions, they also hold for $O(w^2)$-wise independent distributions by Bazzi's theorem (Bazzi (SICOMP 2009); Tal (CCC 2017)), which states that width-$w$ DNFs cannot distinguish between such distributions and the uniform distribution. We prove a derandomization of robust sunflower lemmas for $O(w)$-wise independent distributions, which recovers the derandomization above with slightly weaker parameters. Notably, our result also holds for distributions whose marginals are "locally independent" and "approximately identically" distributed. It is not known whether such distributions fool general DNFs, which makes the derandomization via DNF-fooling techniques unavailable. Our proof of this derandomization is via the method of moments, which might be of independent interest. We apply this result to obtain improved separations between non-monotone arithmetic circuits and the radical of monotone circuits. Specifically, we construct an explicit family of multilinear polynomials $P_n$ that have small non-monotone arithmetic circuits such that any power of $P_n$ cannot be computed by monotone arithmetic circuits of sub-exponential size. This improves on a recent result of Cavalar, Fabris, Mukhopadhyay, Srinivasan and Yehudayoff (STOC 2026), who proved a non-explicit separation that was quasipolynomial. Our construction uses Nisan-Wigderson designs with an additional linear-algebraic expansion property.

0.56

Integral Tensor Isomorphism via Cubic Rings and Lattice Methods

cs.CC quant-ph ·2026-11-17 ·Thomas Huffstutler
theory
Abstract · 51 pages

We prove that isomorphism of integral $2\times3\times3$ tensors under $\mathrm{GL}_2(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})\times\mathrm{GL}_3(\mathbb{Z})$ is decidable in bounded-error quantum polynomial time. For a tensor $T=(A,B)$ with nonzero determinant form $\det(xA-yB)$, we use the parametrization of Wood by balanced modules to reduce the isomorphism problem to principality tests for compatible lattices, and use the algorithms of Bley, Hofmann, and Johnston to solve this in BQP. When the determinant form vanishes identically, we get either an integral $2\times2\times2$ core, or a polynomial kernel vector of degree one or two. The linear-kernel case yields another compatible lattice problem, while the quadratic-kernel case reduces to a fixed system of polynomial congruences and unimodular lifting. A quantifier-elimination argument decides these congruences in deterministic polynomial time given the prime factorization of the modulus, which quantum integer factorization supplies. Finally, we show that zero padding preserves integral $2\times2\times2$ tensor isomorphism, yielding a polynomial-time reduction from real-quadratic principality to the identically singular $2\times3\times3$ problem.

0.39

Entanglement Lower Bounds for Symmetric Quantum Circuits

cs.CC quant-phcs.LO ·2026-11-17 ·Davi Castro-Silva, Ryan Dancy, Sergii Strelchuk
theory
Abstract

Symmetric circuits require every symmetry of the input to extend to an automorphism of the circuit. In the classical setting, their connection to descriptive complexity yields strong unconditional lower bounds. We extend this approach to the quantum model of symmetric computation defined by Castro-Silva, Gur, and Strelchuk (ITCS 2026), proving a tradeoff between circuit size and entanglement width (the smallest $b$ such that, on every computational-basis input, the state after each layer factors into states on at most $b$ qubits each). Our main result identifies a graph property decidable in classical polynomial time that no polynomial-size family of symmetric quantum circuits on $n$-vertex graphs with entanglement width $o(n/\log n)$ can compute. The bound holds for circuits with arbitrary one-qubit and two-qubit gates and unrestricted depth, and remains valid under the weaker notion of symmetry with respect to even permutations of vertices. Our proof is based on a new quantum pebble game based on the partial trace. The resulting indistinguishability theorem transfers classical pebble-game lower bounds to quantum circuits with restricted entanglement. By contrast, without entanglement restrictions, we show that every graph property in BQP can be computed by a uniform family of polynomial-size symmetric quantum circuits. Restricting to circuits with no entanglement at all, we show that polynomial-size symmetric quantum circuits with entanglement width 1 can compute every graph property definable in fixed-point logic with counting. Finally, we give an efficient symmetric implementation of QAOA for MAX 3XOR, providing a starting point for studying entanglement lower bounds in quantum optimization algorithms.

0.34

Inapproximability of L1->L2 Subspace Distortion

cs.CC ·2026-11-17 ·Vijay Bhattiprolu
Abstract

We show, assuming NP is not contained in randomized quasipolynomial time, almost polynomial factor inapproximability for maximizing the $\ell_2/\ell_1$ ratio over a real subspace -- a problem also known as subspace distortion. This is a central problem in compressed sensing but also has connections to many areas such as real error correcting codes, dictionary learning, hypercontractive operator norms, small-set expansion, quantum information and random matrix theory. Distortion seems to be at the heart of building inapproximability theory for continuous optimization. Extending our results to the case of $\ell_2/\ell_p$ for all $p<2$ would lead to a near characterization of the convex sets over which one can efficiently and approximately maximize an arbitrary quadratic form. A recurring obstruction appears in hardness considerations of distortion -- how does one use a sparsity measure to test proximity to an exponential sized discrete set over the reals? This issue also appears in a host of other problems that involve measures of sparsity, shortness, density or expansion. We believe hardness of distortion is an intermediate step to understanding the complexity of small-set expansion and quantum separability, both of which are important directions of research. The main insight in our hardness reduction is the construction of a randomized affine linear map $T:\mathbb{R}^n\to \mathbb{R}^m$ such that the distortion of $Tx$ measures proximity to the hypercube $\{\pm 1\}^{n}$. Crucial to our construction is subsampling $x$ at *all* dyadic sample sizes, which gives an inverse polylogarithmic gap. This is a highly non-local tester, and thus departs from the local testing paradigm in PCP theory. Our reduction is also quite succinct, and so it suggests a rather simple distribution of subspaces for which approximately finding a planted sparse vector is intractable.

0.30

Computational Hardness of Online Stochastic Matching

cs.DS cs.CCcs.GT ·2026-11-17 ·Yifeng Teng, Zongjun Yang
theory
Abstract

In the online stochastic matching problem on a bipartite graph, offline vertices are given in advance, and online requests arrive sequentially from known distributions, each matched immediately and irrevocably to a free neighbor or rejected. Computational hardness results of the optimal online strategy have been known only for instances where online vertices have a fixed arrival order [Papadimitriou et al., 2024]. For random-order arrivals or even i.i.d. arrivals, it has been long open since the problem was proposed [Feldman et al., 2009]. In this paper, we give the first computational hardness results for online stochastic matching with random-order arrivals. In particular, we prove that for known i.i.d. arrivals, computing the online optimum is APX-hard, ruling out a Polynomial-Time Approximation Scheme unless P = NP, even in unweighted graphs with two offline neighbors per online vertex. For random-order arrivals, even when there is only one offline node (i.e., the prophet secretary setting), computing the optimal online policy is #P-hard, resolving an open problem since [Dütting et al., 2023].

0.28

A Dichotomy for Exact Quantum Circuit Amplitudes

cs.CC ·2026-11-17 ·Chenghua Liu, Boning Meng
Abstract

We classify the complexity of exactly computing computational-basis amplitudes for circuits over any fixed finite library of unitary qubit gates, with each gate allowed to act on any ordered tuple of distinct wires. Exact evaluation is polynomial-time computable if all gates permute the computational basis up to phases, all preserve product states, or all become Clifford under a common diagonal one-qubit unitary change of basis on every wire. For every other library, the problem is $\#\mathrm P$-hard under polynomial-time Turing reductions. Our proof connects circuit amplitudes to the Boolean Holant classification of tensor contractions on arbitrary graphs. For an algebraic library containing a nonmonomial gate and an entangling gate, we show how to simulate the joint use of a symmetric maximally entangled state and its adjoint at polynomial cost, using only amplitude queries over the original library. This lets us evaluate unrestricted contractions of the resulting gate and boundary tensors. Unitarity and the computational-basis boundaries then restrict the tractable cases to the three forms above. Algebraic specialization extends the dichotomy to arbitrary fixed complex gate entries under a symbolic exact-output convention.

0.17