The arXiv listing for cs.CC, moderated for scope, not refereed.
Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPs Yotam Dikstein, Izhar Oppenheim, Inga Valentiner-Branth [arXiv:2611.16295]Proves that suitable skeleta of Kac–Moody–Steinberg complexes have
\(r\)-swap coboundary expansion at least
\(r^{-O(1)}\), the first inverse-polynomial bound for bounded-degree complexes; substituted into an existing analysis, this gives two-query PCPs with perfect completeness, soundness
\(\varepsilon\) and proof length
\(n(\log n)^{\exp(\mathrm{poly}(1/\varepsilon))}\).
Towards Understanding the Complexity of CAQE: A Proof-Theoretic Analysis of its Core Procedure Benjamin Böhm, Olaf Beyersdorff [arXiv:2611.19613]Formalises runs of the basic CAQE QBF algorithm as proofs in a system
\(\mathrm{CAQE}^{\mathrm{Core}}\) and shows that, on QCNFs of bounded quantifier alternation, Q-resolution with an NP oracle simulates it; QCDCL simulates it on
\(\Sigma_3^b\) QCNFs after preprocessing, and in that setting both systems are strictly stronger.
Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means Karthik C. S., Dor Minzer [arXiv:2611.14892]Proves near-optimal lower bounds under an Almost-ETH hypothesis for
\((1+\varepsilon)\)-approximation of high-dimensional Euclidean
\(k\)-means, ruling out running times of the form
\(2^{(k/\varepsilon)^{1-\beta}}\cdot\mathrm{poly}(n,d)\) and so nearly matching the known
\(2^{\tilde O(k/\varepsilon)}\) algorithms.
A short proof of the Aaronson-Ambainis Conjecture via the completion framework Thomas Huffstutler, David Miloschewsky, Supartha Podder [arXiv:2611.12795]Gives a short proof of the Aaronson–Ambainis conjecture: a partial Boolean function defined on a
\(\delta\)-fraction of inputs can be computed by a deterministic algorithm, correctly on a
\(1-\varepsilon\) fraction of its domain, with
\(O(Q(f)^6/(\varepsilon\delta)^2)\) queries.
Constant query LCCs over the reals Zeev Dvir [arXiv:2611.13281]Constructs constant-query locally correctable codes over the real numbers, which had been conjectured not to exist; the codes use low-degree polynomial evaluations on an integer grid, and decoding samples random quadratic curves through the grid.
On Non-Deterministic Representation of Boolean Functions Sudharshan Rajagopalan, Nitin Saurabh [arXiv:2611.11966]Proves that almost all Boolean functions on
\(n\) variables have non-deterministic degree at most
\(n/2 + O(\sqrt{n\log n})\), confirming a conjecture of Iyer et al.
Weak Composition Theorems for Randomized Communication Pachara Sawettamalya [arXiv:2611.16192]Proves that, up to additive terms, computing
\(g\circ f^n\) in randomised communication requires, information-theoretically, solving at least
\(\mathrm{Inf}(g)\) instances of
\(f\); this is the first composition lower bound that applies to every choice of inner function
\(f\) and outer function
\(g\).
Exact Quantum Algorithms for Composed Boolean Functions Gagan Chiruvella, Chandrima Kayal, Rajat Mittal, Manaswi Paraashar et al. [arXiv:2611.16412]Proves that
\(Q_E(f\circ g) = O(mD + Q_E(f) Q_{1/(4D)}(g))\) for an outer function
\(f\) of degree
\(D\) and an inner function
\(g\) on
\(m\) bits, by combining approximate inner evaluations with a finite exact correction.
The multiplicative complexity of the three-bit low-half multiplier Bshara Alhodali, Gregory Morse [arXiv:2611.15992]Proves, without enumeration and with a full Lean 4 formalisation, that the multiplicative complexity of the three-bit low-half multiplier is exactly six, a value previously established by SAT search.
Simulating Space Bounded Read-\(k\) PTMs with Space Bounded Read-Once PTMs Kuan Cheng, Shengtang Huang, Ruiyang Wu [arXiv:2611.17690]Shows that read-
\(k\) probabilistic Turing machines with space
\(S\) and time
\(T\) can be simulated by read-once ones in space
\(O(k^2(S+\log(n+T))+\log(1/\varepsilon))\), so read-
\(k\) \(\mathrm{BPL}\) equals
\(\mathrm{BPL}\) for every constant
\(k\).
Independent set reconfiguration is hard at treewidth four Hussein Abbas, Haydar Hamieh, Amer E. Mouawad, Ali Slim [arXiv:2611.20205]Proves that Independent Set Reconfiguration is hard on graphs of treewidth four under both token sliding and token jumping, narrowing the long-open gap between polynomial-time solvability on trees and known hardness at some unspecified constant treewidth.
\(\mathsf{EQP}\subseteq\mathsf{IP}\) Does Not Relativize Sinan Oral, Supartha Podder [arXiv:2611.12746]Constructs a recursive oracle relative to which a unary language lies in
\(\mathrm{EQP}\) but outside both
\(\mathrm{IP}\) and
\(\mathrm{PH}\), extending the
\(\mathrm{BQP}\) versus
\(\mathrm{IP}\) oracle separation of Bouland et al. to exact quantum computation through a Forrelation variant with correlation exactly
\(\pm 1/2\).
Go under Chinese Rules with a Succinct Game History is Complete for Exponential Space Markus Bläser, Felix Czerner [arXiv:2611.18201]Proves that Go under Chinese rules, with its no-repetition rule, is complete for exponential space when the game history is given succinctly.
Polynomial-Space Quantum Algorithms from Classical Branching: Colouring, Domination and Monotone Local Search Sebastian Senge [arXiv:2611.12714]Gives bounded-error, polynomial-space quantum algorithms without quantum random access memory, built from classical branching, including 4-Colouring in time
\(O(1.3032^n)\) (previously
\(O(1.3231^n)\)) and improved bounds for
\(k\)-Colouring for several values of
\(k\) between 5 and 18.
Uniform Quantum Average-Case Fine-Grained Hardness of Arithmetized \(k\)-Orthogonal Vectors Dhruv Prasad Deshpande, Abhishek Mishra [arXiv:2611.14411]Shows that, for every fixed
\(k \ge 3\) and assuming the basic decision version of QSETH, no uniform quantum algorithm running in time
\(O(n^{k/2-\varepsilon})\) evaluates the arithmetized
\(k\)-Orthogonal Vectors polynomial correctly with probability
\(3/4\) over uniformly random inputs.
\(\mathsf{SVP}_\infty\) Is NP-Hard for Power-of-two Cyclotomic Ideals Yansong Feng, Jiaqi Liu, Hengyi Luo, Yanbin Pan [arXiv:2611.14334]Proves that exact decision-SVP in the coefficient
\(\ell_\infty\)-norm is NP-complete for principal ideals and rank-two free modules over
\(\mathbb{Z}[X]/(X^n+1)\) with
\(n\) a power of two, by polynomial-time reductions from Subset Sum.
Two-Stage Mixed-Integer Quadratic Programming in Polynomial Time Alberto Del Pia [arXiv:2611.14837]Gives a polynomial-time algorithm for mixed-integer quadratic programs with two-stage structure, a Lenstra-type result that has to rely on such structure because MIQP is NP-hard even without integer variables.
Individually Fair Facility Location Rajni Dabas, Samir Khuller, Milind Maiti [arXiv:2611.16138]Proves that for individually fair facility location, with any fixed radius violation below three, no deterministic polynomial-time algorithm achieves a sublogarithmic cost factor unless
\(\mathrm{P}=\mathrm{NP}\), even with uniform opening costs and radii, which contradicts a recently claimed constant-factor guarantee.
The Tournament Equilibrium Set Is PSPACE-Complete, Even under Hereditary Uniqueness Ethan Dickey, Athina Terzoglou [arXiv:2611.17312]Proves that deciding membership in Schwartz's tournament equilibrium set is PSPACE-complete, closing the gap between the known NP-hardness and the PSPACE upper bound, and that hardness persists under hereditary uniqueness.
Local Modifications of Nearest-Neighbor and Min-Plus Representations Liliia Redina [arXiv:2611.13787]Bounds how much changing a Boolean-valued function at
\(d\) inputs can enlarge its nearest-neighbour and integer min-plus representations, showing for example that
\(m+2d\) anchors suffice for nearest-neighbour representations on finite subsets of
\(\mathbb{R}^n\),
\(n\ge 2\), and that the coefficient 2 is optimal.
Type-logical grammars and formal languages Richard Moot [arXiv:2611.12618]Shows that type-logical grammars with the standard rules for product, associativity, extraction and infixation have an NP-complete fixed recognition problem, and that first-order linear logic grammars can simulate the quasi-linear grammars of Book and Greibach.
Pair-Merge Tokenisation Is Hard to Approximate on Binary Strings and Strongly NP-Hard on Unary Datasets Kundan Baliga, Aiden Xie, Aditya Byju [arXiv:2611.13568]Proves that, unless
\(\mathrm{P}=\mathrm{NP}\), no polynomial-time algorithm can choose
\(k\) BPE-style pair merges that shorten a single binary string to within a factor
\(c n/\log n\) of optimal, and that the problem is strongly NP-hard on unary datasets.
Feedback Vertex Set, Max Cut, and Edge Coloring on the Strong Product of a Graph and a Path Jan Diester, Kolja Kühn, Manuel Rapp, Samuel Schneider et al. [arXiv:2611.13917]Proves Max Cut NP-hard on induced subgraphs of the strong product of two paths, answering a question of Dvořák, Huynh, Joret, Liu and Wood, and shows 3-Edge Colouring NP-hard on its subgraphs and equivalent to the planar case on its induced subgraphs.
Sowing the Seeds of Intractability: Kalah is PSPACE-complete Ethan Dickey, Ethan Mader [arXiv:2611.17252]Proves that deciding whether a player can force a win in generalised Kalah, with the number of pits per side part of the input and stone counts in unary, is PSPACE-complete.
On Applications of Polynomial-Time Group Isomorphism Algorithm Wenkang Zhang, Zhinan Wang, Jincheng Zhuang [arXiv:2611.18084]Builds on the Qiao–Zhang polynomial-time algorithm for finite group isomorphism in the multiplication-table model to obtain polynomial-time algorithms that return the coset of all isomorphisms for finite associative rings, with further applications to bilinear-map isotopism and free three-tensor isomorphism over finite commutative rings.
Impatience Makes Matching NP-Hard Chen Yan, Sushil Mahavir Varma [arXiv:2611.20234]Shows a phase transition in the complexity of maximising long-run throughput in a dynamic bipartite matching model where customers and suppliers arrive by Poisson processes and may leave before they are matched.
Polynomial Sample Complexity of Noninteractive Simulation over Finite Alphabets Haoran Wang [arXiv:2611.11974]Shows that for any fixed finite correlated source, every joint law that Alice and Bob can simulate without communication from arbitrarily many samples can be approximated using a number of samples polynomial in the output alphabet sizes and the inverse accuracy.
Affine Combiners for Reed-Solomon Proximity Gaps Alessandro Chiesa, Guy Weissenberg, Eylon Yogev, Kai Zhe Zheng [arXiv:2611.15128]Proves that affine combiners of the form
\(f(x)+(\alpha+\beta x)g(x)\) give smaller error bounds for Reed–Solomon proximity gaps than the
\(O(n/q)\) of scalar combiners, in a range of distances extending towards the Johnson radius for sufficiently long codes.
Statistical-to-computational gaps in central limit theorems for high-dimensional tensors Debsurya De, Dmitriy Kunisky [arXiv:2611.15803]Treats high-dimensional central limit theorems as testing problems, sharpening Mikulincer's total-variation bounds for distinguishing Wishart from Wigner tensors with matching polynomial-time tests, and studies tensor settings in which the statistical and computational thresholds come apart.
Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types Tianci Peng, Shiqi Hou, Xiaoyang Dong [arXiv:2611.17804]Determines the bounded-error quantum query complexity of finding an
\(r\)-collision in a function with prescribed equality-class sizes, as the maximum of scales set by the numbers of classes of size at least
\(2,\ldots,r\), with the lower bound holding for a uniformly random function of that type.
Parameterized Complexity and Geometric Approximation of Riesz Energy Subset Selection Michael Emmerich, Soumen Atta [arXiv:2611.13600]Gives an efficient parameterized approximation scheme for choosing
\(k\) of
\(n\) sites to minimise Riesz
\(s\)-energy in fixed Euclidean dimension and fixed
\(s>0\), sharpened by a farthest-first packing argument; exact selection for
\(s=2\) is polynomial on a line and NP-hard in the plane.
Computation with Backward Feedback: Power, Observation, and Cost Saman Farhat, Farzad Didehvar [arXiv:2611.16779]Introduces a model of deterministic programs whose runs are read at stages chosen by a random clock that can move backward and feed register contents to earlier stages, and studies how much power this feedback adds and how soon an observer can obtain the answer.
Succinct Infinite-Horizon Lyapunov and LQR Value Problems Are BQP-Complete Mohamed Serry, Jun Liu [arXiv:2611.12757]Proves that promise problems for evaluating infinite-horizon Lyapunov output energies and LQR optimal values are BQP-complete when the sparse system matrices are given succinctly by Boolean circuits.
Computational Power of Clifford and Ising Quantum Computers Sawyer Dobson, Zhenghan Wang [arXiv:2611.13347]Extends the efficient classical simulation of Ising quantum computers from braidings to measurements, and shows that Clifford quantum computers whose circuit generator sees only the input length decide exactly the so-called affine languages, while efficient classical simulation with a generator that sees the whole input would separate
\(\mathrm{P}\) from
\(\mathrm{PSPACE}\).
Tokenization: Hardness and Bicriteria Approximation Algorithms Atieh Bastan, Xiaoling He, A. Pavan, N. V. Vinodchandran [arXiv:2611.15074]Proves that choosing at most
\(K\) substrings to minimise the token count of a binary corpus has no polynomial-time
\(n^{1-\varepsilon}\)-approximation for any fixed
\(\varepsilon\in(0,1)\) unless
\(\mathrm{P}=\mathrm{NP}\), and gives bicriteria approximation algorithms.
Small Maximum Likelihood on Fixed Cavender-Farris-Neyman Trees: An Approximation Scheme and Limits to Fully Polynomial Approximation Mohammad-Hadi Foroughmand-Araabi, Sama Goliaei [arXiv:2611.15784]Gives a deterministic polynomial-time approximation scheme for fitting edge substitution probabilities to an alignment on a fixed binary Cavender–Farris–Neyman tree, and identifies limits to a fully polynomial scheme.
Topological Entropy of Group Cellular Automata is Effectively Computable Niccolò Castronuovo, Alberto Dennunzio, Jarkko Kari, Luciano Margara [arXiv:2611.16746]Shows that the topological entropy of cellular automata whose global map is a group endomorphism is effectively computable, in dimension one by splitting it into left and right components computed from finite families of traces.
Tight Quantum Query Bounds for Minimum Cut and Multicut on Dense Graphs Tianhang Lu, Runtian Ren, Shengcai Liu [arXiv:2611.17845]Shows that exact minimum multicut with at most
\(k\) demand pairs on dense simple graphs has quantum query complexity
\(\tilde O(n+\min\{m,n^{3/2}\sqrt{k}\})\) with a matching lower bound, giving
\(\tilde O(n^{3/2})\) queries for a prescribed
\(s\)–
\(t\) cut.
Who Observes Whom: Network Rationalizability and Its Complexity Mojtaba Fayaz-Bakhsh, MohammadAmin Fazli [arXiv:2611.20110]Defines solution concepts induced by a directed observation network, lying between Nash equilibrium and rationalizability, and studies the complexity of computing them.
A Fast Algorithm for Subspace Convolution Shlomo A. Perles, Omri Weinstein [arXiv:2611.13134]Shows that summation over all linear subspaces of
\(\mathbb{F}_q^n\), the analogue of the subset-zeta transform, can be computed in
\(\Theta_q(N_q\log N_q)\) time, where
\(N_q\) is the number of subspaces.
The Monophonic Directed Convexities Júlio Araújo, Ana Karolinna Maia, Thiago Marcilon, Nicolas Nisse et al. [arXiv:2611.14191]Defines the monophonic and strong monophonic convexities on directed graphs, based on minimal and induced directed paths, and studies the complexity of their basic decision problems.
Planar PArcK is PSPACE-complete Craig Tennenhouse, Kanae Yoshiwatari [arXiv:2611.20138]Tennenhouse and Yoshiwatari prove that Partizan Arc Kayles, a generalisation of Domineering played on edge-coloured graphs, is PSPACE-complete even on planar graphs of maximum degree three, by a reduction from Generalized Hex.
From Worst-Case to Smoothed Complexity in Continuous Optimization Daniel Cortild, Coralia Cartis [arXiv:2611.14282]Cortild and Cartis develop a smoothed-analysis framework for classical continuous optimisation algorithms, showing that methods suited to non-degenerate functions, applied to random perturbations of degenerate ones, recover the faster rates known for the non-degenerate class.
Solomonoff Induction with Reflective Oracles Damini Kusum [arXiv:2611.14454]Kusum shows that a variant of Solomonoff induction built on reflective oracles succeeds against computable predictive strategies that specify only part of the data-generating process, including incomplete models given by computable interval restrictions on next-bit probabilities.