The arXiv listing for cs.CC, moderated for scope, not refereed.
Get Permanent Results Faster by Counting Stars Radu Curticapean [arXiv:2611.03636]Curticapean computes
\(n\times n\) permanents with
\(O^*((2-\varepsilon)^n)\) arithmetic operations over every commutative ring, for
\(\varepsilon=10^{-40}\), by running the Binet–Minc identity through a dynamic programme; this solves a problem stated in Knuth's
The Art of Computer Programming and also gives algebraic branching programs of the same size.
Composition Theorem for Randomized Query Complexity Samruddhi Pednekar, Supartha Podder [arXiv:2611.08574]Pednekar and Podder prove
\(R(f\circ g)=\Omega(R(f)R(g)/\log(n+1))\) for all Boolean functions
\(f\) and
\(g\), partial ones included, which together with the known upper bound settles composition for bounded-error randomised query complexity up to logarithmic factors.
The CNF Encoding Complexity of Boolean Functions Andrew Krapivin, Benjamin Przybocki, Bernardo Subercaseaux [arXiv:2611.05614]Krapivin, Przybocki and Subercaseaux show that a function computable in nondeterministic time
\(t\), using
\(m\) bits of advice of which at most
\(b\) are read per input, has a CNF encoding with
\(\widetilde{O}(t+\sqrt{mb})\) clauses; as a consequence every
\(k\)-CNF function on
\(n\) inputs has an encoding with
\(n^k/2^{\Omega_k(\sqrt{\lg n})}\) clauses, although any encoding using only bounded-width clauses needs
\(\Omega_k(n^k/\lg n)\) in the worst case.
A New Characterization of Streaming Decidability of Boolean CSPs Under Deletions Aditya Bandekar, Amatya Sharma, Santhoshini Velusamy [arXiv:2611.07309]Bandekar, Sharma and Velusamy characterise the single-pass streaming space of Boolean CSP satisfiability in the strict-turnstile model, where constraints may be inserted and deleted, for every fixed constraint language that is not trivially satisfiable; the governing quantity is the integer capturing degree, where non-redundancy governs the insertion-only case.
Parity Decision Trees of Depth \(O(4^d \log\|\widehat f\|_1)\) for Boolean Functions \(f\) of \(F_2\)-Degree \(d\) Shengyu Zhang [arXiv:2611.03452]Zhang proves that every Boolean function of
\(\mathbb{F}_2\)-degree
\(d\ge2\) has a deterministic parity decision tree of depth
\(O(4^d\log\|\widehat f\|_1)\), improving the previous
\(O(2^{d^2/2}\log^{d-2}\|\widehat f\|_1)\) bound of Tsang, Wong, Xie and Zhang.
Tensor value and the 9/4 bound for matrix multiplication Mahmut Levent Doğan, Vladimir Lysikov, Keiya Sakabe, Michael Walter [arXiv:2611.09716]Doğan, Lysikov, Sakabe and Walter give an exposition of OpenAI's reported bound
\(\omega\le 9/4\) over every field, replacing the spectral points of the original proof with a fractional symmetrised Coppersmith–Winograd tensor value and proving a superadditivity inequality for it on partially direct sums.
Circuit Lower Bounds for Extended Gate Bases from Subexponential Counting Mengyang Wu, Minghao Wang [arXiv:2611.02560]Wu and Wang derive lower bounds that are only as sound as the AI-produced counting and contraction theorems they build on: an
\(\mathsf{E}^{\mathsf{NP}}\) language requiring
\(\Omega(m\sqrt{\log m}/\log\log m)\) gates over unbounded AND/OR with binary XOR, and
\(\Omega(m\sqrt{\log m})\) gates for a bounded binary basis with a linear budget of XOR and symmetric gates, both infinitely often.
The sum-of-squares complexity of linear-algebraic principles Dmitriy Kunisky, Xifan Yu [arXiv:2611.05250]Kunisky and Yu show that sum-of-squares proofs of the Weak Rank Principle need degree exactly
\(2r+2\), that the Tight Frame Principle has a degree-4 proof, and that proving a right inverse of an
\(n\times n\) matrix is also a left inverse needs degree exactly
\(2n+2\).
Improved lower bounds on the approximability of Multiway Cut using Sherali-Adams relaxations Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick [arXiv:2611.05511]Brakensiek, Huang, Potechin and Zwick use Sherali–Adams relaxations to raise the lower bound, under the Unique Games Conjecture, on the approximation ratio achievable in polynomial time for Multiway Cut above the previous 1.20016; the best known algorithm achieves 1.2787.
TFNP in the Random Oracle Model Noah Fleming, Mika Göös, Ziyi Guan, Oliver Korten et al. [arXiv:2611.05308]Fleming, Göös and eight co-authors determine which of the major
\(\mathsf{TFNP}\) subclasses are hard in the random oracle model, a setting that sits between one-way functions and the stronger structured assumptions, such as LWE, from which hardness was previously known.
Fine-Grained Complexity Across the Computational Phase Transition Zhe Ju, Jingcheng Liu, Yitong Yin [arXiv:2611.02702]Ju, Liu and Yin show that for the hard-core model on
\(n\)-vertex graphs of maximum degree
\(d\ge3\), at fugacity
\((1+\delta)\lambda_c(d)\) for sufficiently small
\(\delta\ge0\) that may vanish with
\(n\), the worst-case mixing time of Glauber dynamics is
\(\exp\{\Theta(n\delta^2/d)\}n^{1+\Theta(1)}\).
A Circuit Complexity Trichotomy For Regular Languages Stefan Göller, Amaldev Manuel [arXiv:2611.03615]Göller and Manuel prove that the non-uniform, unbounded fan-in circuit complexity of every regular language is
\(O(1)\), between
\(\Omega(\log n)\) and
\(O(\log n\log\log n)\), or
\(\Theta(n)\), and characterise the middle class in terms of algebra, word congruences, regular expressions and logic.
A Width Hierarchy of Monotone Algebraic Branching Programs Julian Dörfler, Alexander Rogovskyy [arXiv:2611.06608]Dörfler and Rogovskyy prove a strict infinite width hierarchy
\(\mathsf{mVBP}_2\subsetneq\mathsf{mVBP}_3\subsetneq\cdots\) for monotone algebraic branching programs, using depth lower bounds for iterated matrix multiplication; in the non-monotone case Ben-Or and Cleve showed width 3 suffices.
What remains of the planar induced minor conjectures? Jadwiga Czyżewska, Tomáš Masařík, Marcin Pilipczuk, Paweł Rzążewski [arXiv:2611.09627]Czyżewska, Masařík, Pilipczuk and Rzążewski examine what is left of the conjectures that Maximum Weight Independent Set and List 3-Colouring are polynomial-time solvable in
\(H\)-induced-minor-free graphs for planar
\(H\), and of the related balanced-separator conjecture, after Bonnet and Chang refuted the independent-set part.
Mortality Is Undecidable for \(2 \times 2\) Integer Matrices Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu [arXiv:2611.06562]Quartz, Shevchenko, De Sterck and Liu prove that matrix mortality is undecidable for finite families of
\(2\times2\) integer matrices, settling the one dimension left open; the problem is trivially decidable in dimension one and has been known undecidable from dimension three since 1970.
Fourier Entropy Bounds via Approximations Manaswi Paraashar, Nitin Saurabh [arXiv:2611.06451]Paraashar and Saurabh bound the Fourier entropy of a Boolean function by
\(O(\log(1+\|\widehat f\|_{1,1/3}))\), the log of its approximate spectral norm, which gives
\(\mathbb H(\widehat f^{ 2})=O(\mathsf R^\oplus(f))\) in terms of randomised parity-query complexity.
Information Complexity of Inner Product and Matrix Multiplication via Shannon-to-Min-Entropy Conversion Xiaohong Cai, Mingyang Zhu [arXiv:2611.02684]Cai and Zhu determine the information complexity of matrix multiplication over finite fields on uniform inputs up to an additive constant; for binary inner product with error
\(\varepsilon\) it lies between
\((1-2\varepsilon)m-4.772\) and
\((1-2\varepsilon)m\), answering a question of Braverman, Garg, Pankratov and Weinstein.
Semidirect sums of tensors and the matrix multiplication exponent Baitian Li [arXiv:2611.04175]This is the arXiv copy of Li's exposition of the claimed
\(\omega\le 9/4\) bound, built around the untwisting lemma for semidirect sums of tensors.
The Complexity of Unpredictability Aryan Agarwala, Dani Dorfman [arXiv:2611.05956]Agarwala and Dorfman introduce middle-bit predictors and the problem UNPRED: given predictor circuits and
\(\varepsilon\), deterministically output a multiset of strings on which every predictor succeeds with probability below
\(1/2+\varepsilon\). They study its complexity, including a version restricted to
\(\mathsf{TC}^1\) predictors.
Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs Oliver Janzer, Peter Manohar [arXiv:2611.03145]This is the arXiv version of the Janzer–Manohar
\(2^{\Omega(\sqrt k)}\) length lower bound for binary linear 3-query LCCs, which matches Reed–Muller codes.
Precedence Constraint Scheduling on a Fixed Number of Machines Klaus Jansen [arXiv:2611.09392]Jansen gives a deterministic exact algorithm for
\(P_m\mid\mathrm{prec},p_j=1\mid C_{\max}\) that runs in polynomial time for every fixed
\(m\ge3\); the degree is
\(6m^2+13m+1\), or 94 for three machines.
Hardness of Unique Shortest Vectors and Bounded Distance Decoding Sergei Kudria, Jason Luo [arXiv:2611.09497]Kudria and Luo prove randomised NP-hardness of uSVP at every constant uniqueness factor above one, and of BDD at every fixed fraction below half the minimum distance, in decision and search versions and in every
\(\ell_p\) norm with
\(1\le p<\infty\).
Exponential Lower Bounds for Products of Cubic Polynomials over Prime Fields Bin Fu, Yunhui Fu [arXiv:2611.02385]Fu and Fu prove exponential lower bounds, in total variable-occurrence cost, for exactly representing explicit signed modular predicates on
\(\{-1,1\}^n\) as products of cubic polynomials over prime fields, with a self-contained proof over
\(\mathbb F_3\).
The determinantal complexity of the 4*4 permanent is 15 Karthik Sheshadri [arXiv:2611.06658]A single-author note claims that the determinantal complexity of the
\(4\times4\) permanent is exactly 15, raising the lower bound from 10 and showing Grenet's
\(2^n-1\) construction optimal at
\(n=4\).
Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy Mrinalkanti Ghosh [arXiv:2611.08836]Ghosh proves integrality-gap lower bounds for linear-programming relaxation hierarchies, which are weaker than sum-of-squares, for maximising degree-
\(d\) homogeneous polynomials over the unit sphere.
Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz [arXiv:2611.09733]Chakraborty, Ordyniak and Siebertz show that Metric Dimension is NP-complete on planar graphs of treewidth and bag-connected treewidth three. There is therefore no XP algorithm by bag-connected treewidth unless
\(\mathrm P=\mathrm{NP}\), which answers questions of Bonnet and Purohit and of Bousquet, Deschamps and Parreau.
Worst-Case to Average-Case Reductions for Basic Linear Algebra Or Zamir [arXiv:2611.03058]Zamir carries the Blum–Luby–Rubinfeld style of worst-case to average-case reduction from matrix multiplication to other basic linear algebra over finite fields, giving an unconditional time-preserving reduction for matrix inversion and improved conditional reductions for rank and determinant.
Deterministic factorization of constant depth circuits from whitebox PIT Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan et al. [arXiv:2611.09035]The arXiv version of the result that deterministic factorisation of constant-depth circuits over the rationals reduces in polynomial time to whitebox PIT, with the same reduction working for formulas and algebraic branching programs.
Quadratic Extractors Gautam Chandrasekaran, Jesse Goodman, David Zuckerman [arXiv:2611.07266]The arXiv version of the explicit extractor for quadratic sources at min-entropy
\(\mathrm{polylog}(n)\), improving the previous requirement of roughly
\(n-\sqrt{\log n}\).
Determinant boundaries and gaps in determinantal complexity Karthik Sheshadri [arXiv:2611.03554]For every
\(n\ge 10\), Sheshadri constructs an explicit degree-
\(n\) form, concise in
\(n^2\) variables, whose orbit closure is a determinant-boundary component, whose border determinantal complexity is
\(n\) and whose exact determinantal complexity is at least
\(2n-1\), so the gap between the two can grow linearly.
A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs Andrew D. Lin [arXiv:2611.05034]Lin gives a short proof that a properly edge-coloured
\(n\)-vertex graph of average degree
\(\Omega(\log n\log\log n)\) contains a rainbow cycle, extends it to weighted list-coloured graphs, and uses the extension to improve bounds for binary linear locally correctable codes with an even number of queries.
Binary Huffman Coding with Unequal Letter Costs Is NP-Complete L. Sunil Chandran, Rishikesh Gajjala [arXiv:2611.04444]Chandran and Gajjala prove that binary prefix coding with unequal letter costs is NP-complete, settling the exact complexity of a problem that has had only exact algorithms for fixed costs and a PTAS since Karp's 1961 integer-programming formulation.
Some algebraic and geometric computations in CH via Chow forms Robert Andrews, Abhibhav Garg, Rafael Oliveira, Éric Schost [arXiv:2611.05289]For algebraic varieties represented by Chow forms, several problems about equidimensional decomposition move from PSPACE down to the counting hierarchy CH.
Competitive Equilibrium for Linear Chores is CLS-complete Qian Liu, Shinuo Ma, Yixin Tao, Minji Yang et al. [arXiv:2611.06589]Computing an exact competitive equilibrium in a linear Fisher market with divisible chores is CLS-complete; the problem was known to lie in CLS, but no hardness was known.
Asymptotic advantage of quantum one-way and SMP communication for total functions Dmytro Gavinsky [arXiv:2611.07318]Gavinsky exhibits a total Boolean function on
\(n\) bits with bounded-error quantum simultaneous-message cost
\(O(\sqrt n)\) but randomised one-way cost
\(\Omega(n)\), which also has a classical simultaneous-message protocol of cost
\(O(\sqrt n)\) when the players share
\(O(\sqrt n)\) EPR pairs.
On computing the determinant over a ring Gilles Villard [arXiv:2611.07786]Villard computes the determinant and characteristic polynomial over any commutative ring with
\(O(n^\omega)\) ring operations, using no divisions and no zero tests, as a straight-line program for each
\(n\).
Quantum Advantage with Sign-Free Proofs: An Oracle Separation between \(\mathsf{StoqMA}\) and \(\mathsf{MA}\) Yassine Hamoudi, Yvan Le Borgne, Shrinidhi Teganahally Sridhara [arXiv:2611.08180]Relative to a classical oracle,
\(\mathsf{MA}\subsetneq\mathsf{StoqMA}\), so verification with sign-free quantum resources already beats every classical verifier, without the coherent computation used in earlier separations along
\(\mathsf{MA}\subseteq\mathsf{QCMA}\subseteq\mathsf{QMA}\).
Beyond the \(n/2\) Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions Yuan Deng, Zihan Hao, Honghao Lin, Qipeng Liu et al. [arXiv:2611.09809]An explicit family of symmetric Boolean functions needs
\(n/2+\Omega(n^{1/3})\) quantum queries at a fixed constant error, and a matching algorithm recovers the exact Hamming weight with
\(n/2+O(n^{1/3})\) queries, so a single-output function can require overhead beyond
\(n/2\).
Entropy-Weighted Soundness for Multi-Answer Birthday Graphs Alexandru Popa [arXiv:2611.04457]For bounded-occurrence, constant-gap Boolean ternary CSPs, Popa bounds the maximum induced
\(K\)-vertex density of the associated birthday graph even when the selected vertices may repeat or omit views; the result is a soundness bound and is not turned into a new fine-grained lower bound.
Online Algorithms Cannot Find Isolated Perceptron Solutions Shuangping Li, Gabe Schoenbach [arXiv:2611.03397]Li and Schoenbach
[arXiv:2611.03397] prove that online algorithms find an isolated solution of the random binary perceptron, where all but a vanishing fraction of solutions are isolated, only with probability
\(o(1)\).
A King for Almost Everyone Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande [arXiv:2611.03838]Ismaili Alaoui, Lachish and Mande
[arXiv:2611.03838] give a deterministic
\(O(n^{4/3})\)-query algorithm that finds a
\((1-\varepsilon)\)-king in a tournament for every fixed
\(\varepsilon\); the
\(\Omega(n^{4/3})\) lower bound and
\(O(n^{3/2})\) upper bound for exact
\(1\)-kings, unimproved for two decades, are untouched.
The Complexity of KKT Points of Quadratic Programs with Polynomially-Bounded Coefficients Argyrios Deligkas, Michail Fasoulakis, Stavros D. Ioannidis [arXiv:2611.03945]Deligkas, Fasoulakis and Ioannidis
[arXiv:2611.03945] show that finding a KKT point of a quadratic polynomial over the unit hypercube stays
\(\mathrm{CLS}\)-complete when the coefficients are written in unary, the first problem shown
\(\mathrm{CLS}\)-hard with unary input.
Hardness Self-Amplification in Linear Algebra and Fine-Grained Cryptography Geoffroy Couteau, Nikolas Melissaris, Thejas Radhika Sajith [arXiv:2611.04680]Couteau, Melissaris and Sajith
[arXiv:2611.04680] use random low-rank updates to turn an algorithm solving an inverse-polynomial fraction of random linear systems into one that succeeds on every right-hand side for almost every matrix, at a runtime cost linear in the inverse success probability, and derive fine-grained one-way functions from it.
Universal Hardness From Masking Channels Parikshit Gopalan, Manoj Prabhakaran, Pranay Tankala [arXiv:2611.05296]Gopalan, Prabhakaran and Tankala
[arXiv:2611.05296] recast Impagliazzo's hardcore measures as input-dependent masking channels on a function's output and use this view to extend the hardcore lemma to a general learning-theoretic framework.
PIT and Reconstruction for Sums of Powers Nimrod Kaplan, Amir Shpilka, Yann Tal [arXiv:2611.07106]Kaplan, Shpilka and Tal
[arXiv:2611.07106] prove lifting theorems showing that, when the outer power
\(d\) is large enough, deterministic black-box PIT and reconstruction for an inner polynomial class carry over to sums
\(\sum_i \alpha_i f_i^d\).
On derandomizing the line-point low-degree test Prahladh Harsha, Swastik Kopparty, Mrinal Kumar, Ramprasad Saptharishi et al. [arXiv:2611.09183]Harsha, Kopparty, Kumar, Saptharishi and Sudan
[arXiv:2611.09183] find unexpected behaviour in the derandomized bivariate line-point low-degree test at high error: a counterexample with roughly
\(q^{3/2}\) lines, and a positive result once
\(q \ge k^2/\varepsilon^{O(1)}\).
Efficient Proper Agnostic Learning of Halfspaces Anindya De, Elchanan Mossel, Shivam Nadimpalli, Joe Neeman [arXiv:2611.02344]De, Mossel, Nadimpalli and Neeman
[arXiv:2611.02344] give a proper membership-query algorithm that agnostically learns halfspaces under the uniform distribution on
\(\{\pm1\}^n\) to error
\(\mathrm{OPT}+\varepsilon\) in time
\(\mathrm{poly}(n)+2^{\mathrm{poly}(1/\varepsilon)}\), against the previous
\(n^{\mathrm{poly}(1/\varepsilon)}\).
Breaking the quantum barriers for Graph Collision Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall et al. [arXiv:2611.05356]Cornelissen, Gilani, Kintali, Le Gall, Patro and Zhou
[arXiv:2611.05356] refute the conjectured
\(\Omega(n^{2/3})\) quantum query lower bound for graph collision with an
\(\widetilde O(n^{11/17})\)-query bounded-error algorithm.
Structured Quantum Hardness from Unstructured Assumptions Xiao Liang, Takashi Yamakawa, Chak Fai Yung [arXiv:2611.07413]Liang, Yamakawa and Yung
[arXiv:2611.07413] prove a quantum analogue of the conditional Bennett-Gill result: if
\(\mathrm{UP}\not\subseteq\mathrm{BQP}\), then
\(\mathrm{NP}^O\cap\mathrm{coNP}^O\not\subseteq\mathrm{BQP}^O\) with probability
\(1\) over a random oracle
\(O\).
Combinatorial limitations of list-decoding Reed-Solomon codes Omar Alrabiah, Rohan Goyal, Venkatesan Guruswami [arXiv:2611.07607]The arXiv version
[arXiv:2611.07607] of Alrabiah, Goyal and Guruswami's result that Reed-Solomon codes can have super-polynomial lists just beyond the Johnson radius, refuting a constant-list conjecture over prime fields.
A Universal Threshold Theory for Local Properties of Random Linear Codes Vinayak M. Kumar, Ray Li, Jonathan Mosheiff, Gilad Shavit [arXiv:2611.07661]Kumar, Li, Mosheiff and Shavit
[arXiv:2611.07661] show that the threshold dimension of any
\(b\)-local monotone property of random linear codes, such as list decoding or list recovery, lies within
\(O(b)\) of its expectation threshold.
Multiplicative and Additive Extractors for Low Entropy Samplable Sources Under Reduced Assumptions Marshall Ball, Eshan Chattopadhyay, Mohit Gurumukhani, Ronen Shaltiel et al. [arXiv:2611.07829]The arXiv version
[arXiv:2611.07829] of Ball, Chattopadhyay, Gurumukhani, Shaltiel and Zhao's extractors for low-entropy samplable sources under reduced hardness assumptions.
On Positive Computation Eduardo Skapinakis [arXiv:2611.09622]Skapinakis introduces positive reductions for monotone classes, shows that monotone Circuit Satisfiability and Hamiltonian Cycle are
\(\mathrm{mNP}\)-complete under them, and proves that the separation
\(\mathrm{posP} \subsetneq \mathrm{mNP}\) does not relativise; if every
\(\mathrm{mNP}\)-complete problem were complete in this stronger sense,
\(\mathrm{P} \neq \mathrm{NP}\) would follow.
On the optimality of truncation among binary linear sketches Robinson D. H. Cung, Adway Girish, Emre Telatar [arXiv:2611.03979]Cung, Girish and Telatar prove that, under a monotonicity condition, simply keeping a subset of the input coordinates is optimal among all binary linear sketches of the same size, with applications to distributed correlation testing and to evaluating unate Boolean functions on uniformly random inputs.
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron Jianan Zhang, Shuangping Li [arXiv:2611.04294]Zhang and Li give a state-evolution and universality analysis of iterated linear programming for the random binary perceptron, extending earlier analyses that covered only a single round of LP.
Improved Approximation and Hardness Bounds for \(β\)-TSP Paul Liu, Jack Spalding-Jamieson, Da Wei Zheng [arXiv:2611.09421]Liu, Spalding-Jamieson and Zheng improve both the approximation ratios and the hardness bounds for
\(\beta\)-TSP, where edge lengths satisfy
\(\ell_{uw} \le \beta(\ell_{uv}+\ell_{vw})\) for
\(\beta \in [1/2,1]\).
A Tight Hierarchy for Chain of Thought Thanh Le, A. Pavan, N. V. Vinodchandran [arXiv:2611.09759]Le, Pavan and Vinodchandran prove the first hierarchy theorem for chain-of-thought transformers:
\(\mathrm{CoT}(r(n)) \subsetneq \mathrm{CoT}(r(n)^{1+\varepsilon})\) for every reasonable resource bound
\(r(n) \ge n\) and every
\(\varepsilon > 0\).
On the Role of Geometry in Solving Variational Inequalities Ioannis Anagnostides, Ioannis Panageas, Jingming Yan [arXiv:2611.04151]Anagnostides, Panageas and Yan classify variational inequalities over
\(\ell_p\) balls, a family that contains symmetric bimatrix games (
\(p=1\)) and polymatrix games (
\(p=\infty\)): the problem is PPAD-complete for affine operators when
\(p \neq 2\), polynomial-time for affine operators when
\(p=2\), and PPAD-complete for quadratic operators.
Quantum Advantage has Few Complexity Implications Eli Goldin, Alex Lombardi, Tomoyuki Morimae [arXiv:2611.05303]Goldin, Lombardi and Morimae give a classical oracle relative to which
\(\mathrm{P}=\mathrm{NP}\) and
\(\mathrm{BQP}=\mathrm{PSPACE}\) while proofs of quantumness still exist, which is evidence that such proofs, and oblivious state preparation when
\(\mathrm{BQP}=\mathrm{QCMA}\), carry few complexity-theoretic consequences.
Quantum Interactive Proofs of Proximity Kenan Wood [arXiv:2611.08858]Wood initiates the study of quantum interactive proofs of proximity and shows that every logspace-uniform
\(\mathrm{NC}\) property has one with query, communication and time complexity
\(\widetilde{O}(n^{2/5})\), below the best known classical
\(\widetilde{O}(\sqrt{n})\).
State Synthesis with an NP oracle Aniruddha Sen [arXiv:2611.02370]Sen gives a polynomial-time quantum algorithm that, with an
\(\mathrm{NP}\) oracle and query access to the state vector's entries, prepares any state to inverse-exponential precision, improving the previous
\(\mathrm{PP}\) oracle bound; with a
\(\mathrm{P}\) or even
\(\mathrm{P/poly}\) oracle, exponentially many queries are needed.
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints Zemin Chao, Jianhe Cen, Hengzhao Ma, Hongzhi Wang [arXiv:2611.04365]Chao, Cen, Ma and Wang determine the optimal space for one-pass spanning-forest computation in dynamic graph streams at every failure probability
\(\delta \le 1/4\), giving matching upper and lower bounds of
\(\Theta(\min\{v^2, v\log(v/\delta)\log^2(2+v/\log(v/\delta))\})\) bits, and also treat streams with bounded deletions.
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds Zixuan Huang, Guozhang Chen [arXiv:2611.06055]Huang and Chen approximate softmax attention at any temperature in fixed dimension
\(d\), to additive error
\(\varepsilon\), in expected time
\(\widetilde{O}((mn)^{k/(k+1)}+m+n)\) with
\(k=\lfloor d/2\rfloor\), matching the best known bounds for batch maximum inner product.
Improved Exact and Approximate Quantum Fourier Transforms from Multiplication Chandrima Kayal, Rajat Mittal, Manaswi Paraashar, Nitin Saurabh [arXiv:2611.06341]Kayal, Mittal, Paraashar and Saurabh sharpen the reduction from the quantum Fourier transform to integer multiplication, obtaining exact QFT circuits over
\(\mathbb{F}_{2^q}\) with
\(O(q\log q)\) gates instead of
\(O(q^2)\), together with improved approximate versions.
Reconfiguration of Time-Bounded Descriptions Dimitrios Myrisiotis [arXiv:2611.09020]Myrisiotis studies the graph of all time-bounded programs that print a given string under an adjunction-universal machine, and proves results on its connectivity, including that deciding whether two programs are connected is PSPACE-complete.
Path Isolation and Reachability in Surface-Embedded Graphs with Restricted Cycle and Cut Structure Neelabjo Shubhashis Choudhury, Chetan Gupta, Raghunath Tewari [arXiv:2611.09262]Choudhury, Gupta and Tewari construct logspace-computable isolating weight assignments for directed surface-embedded graphs with polynomially many simple non-separating cycles, which places reachability in these graphs in
\(\mathrm{UL}\) and bipartite perfect matching on the corresponding graphs in
\(\mathrm{SPL}\).
Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs Yali Aharon-Holzman, Michael Ilan, Assaf Reiner, Amnon Ta-Shma [arXiv:2611.02963]Aharon-Holzman, Ilan, Reiner and Ta-Shma construct explicit two-sided lossless expanders whose adjacency matrices have full rank, and use them to build explicit asymptotically good quantum LDPC codes with full-row-rank check matrices and small-set soundness on a linear range.
Polynomial-time classical simulation of boson and fermion sampling under thermal loss Armando Angrisani, Hela Mhiri [arXiv:2611.08444]Angrisani and Mhiri give polynomial-time classical simulation, at inverse-polynomial total variation error, of Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing and fermion sampling with magic inputs, under any fixed nonzero thermal or pure loss rate and with high probability over Haar-random interferometers.
Iterated Narrow Networks: Turing Completeness at Width 4 on Convex Input Spaces and the Complexity of Verification Olivier Bournez, Johanne Cohen, Adrian Wurm [arXiv:2611.02840]Bournez, Cohen and Wurm
[arXiv:2611.02840] show that every deterministic Turing machine is simulated exactly by the iterates of a fixed width-4 ReLU network on
\([0,1]^4\), built in polynomial time and with iteration count proportional to the machine's running time, and they draw consequences for the complexity of verifying such networks.
Tilted Convexity and an Exact Offline-Online Separation Mohammad Pedramfar, Rajiv Khanna, Christopher John Quinn, Vaneet Aggarwal [arXiv:2611.03472]Pedramfar, Khanna, Quinn and Aggarwal
[arXiv:2611.03472] introduce
\(\gamma\)-tilted convexity, a one-parameter weakening of convexity giving distinct nested classes in which local minimisers are still global, and prove an exact separation between offline and online optimisation over these classes.
Faster Treasure Hunt via Strongly Universal Exploration with Polylogarithmic Overhead Qin Xin [arXiv:2611.08705]Xin
[arXiv:2611.08705] turns ordinary universal exploration sequences of length
\(O(n^c)\) into a single infinite strongly universal exploration sequence with cover time
\(O(n^c\log^2 n)\), with sharper refinements, which speeds up delayed-activation treasure hunt in anonymous port-labelled graphs.
On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle Alexander Hoover, Giuseppe Persiano, Kevin Yeo [arXiv:2611.04052]Hoover, Persiano and Yeo
[arXiv:2611.04052] study how much communication secure multiparty computation needs when only a random oracle is available, proving lower bounds for both classical and quantum communication against the information-theoretic bounds known to be tight for inner products.
On the Hardness of Approximate Quantum Circuit Membership and Optimization Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis [arXiv:2611.04381]Kjelstrøm, van de Pol and Pavlogiannis
[arXiv:2611.04381] prove that deciding, without a promise, whether a quantum circuit is close to a unitary in a fixed target set is
\(\mathrm{PP}\)-hard under several metrics, and the same holds for the corresponding circuit optimisation problems.
Agnostic Learning by Imitating Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold et al. [arXiv:2611.05346]Casacuberta, Gopalan, Kanade, Reingold, Stavropoulos and Tankala
[arXiv:2611.05346] prove that agnostically learning a class and training a generative model that no member of the class can distinguish from the data are equivalent in complexity; only one direction was known before.
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities Huanjian Zhou, Taiji Suzuki [arXiv:2611.05813]Zhou and Suzuki
[arXiv:2611.05813] prove that any randomised first-order sampler for
\(d\)-dimensional strongly log-concave targets with condition number 2 needs
\(\exp(\Omega(\log^{1/3} d))\) queries, even from a constant warm start, and that targets satisfying a log-Sobolev inequality need
\(\Omega(\kappa)\) queries once
\(d\gtrsim\log^2\kappa\).
Pointwise Score Evaluation from Succinct Boolean Descriptions: SAT Equivalence for Strongly Log-Concave Gaussian Mixtures Yinzhen Lv [arXiv:2611.02346]Lv
[arXiv:2611.02346] constructs a succinctly specified, uniformly strongly log-concave Gaussian mixture with rational means whose score at a fixed point encodes whether a Boolean formula is satisfiable, so smoothness and log-concavity do not make score evaluation easier than SAT.
Subpolynomial-Query Proximal Sampling Beyond Log-Concavity Wei Guo, Bo Yuan, Ye He, Jiaming Liang et al. [arXiv:2611.03442]Guo, Yuan, He, Liang, Tao and Chen
[arXiv:2611.03442] run the proximal sampler with a high-order noisy conditional sampler from a 2026 OpenAI work to sample from non-convex potentials with Lipschitz gradient, obtaining subpolynomial gradient-query dimension dependence under a log-Sobolev inequality.
On the Complexity of Exact Autobidding Equilibria Yiyang Huang, Zhengyang Liu, Yonglei Yan [arXiv:2611.04475]Huang, Liu and Yan
[arXiv:2611.04475] prove that computing exact autobidding equilibria is
\(\mathrm{FIXP}\)-complete for second-price ROI pacing, for budget- or ROI-constrained generalised second-price sponsored shopping and for second-price throttling, and that approximating the equilibrium in distance is
\(\mathrm{FIXP}_a\)-complete in some of these settings.
Differentially Oblivious Priority Queues with Sublogarithmic Cost Zimai Guo, Cheng Hong, Zhechen Li [arXiv:2611.04776]Guo, Hong and Li
[arXiv:2611.04776] build a differentially oblivious integer priority queue with
\(\mathrm{polylog}(T)\) private memory and
\(O(\log T/\log\log T)\) expected amortised work per operation for constant
\(\varepsilon\) and
\(\delta=\exp(-\Theta(\log^2 T))\), below the
\(\Omega(\log T)\) barrier for fully oblivious queues.
Randomized Parallel Complexity of Weakly Convex Optimization Kang Liu [arXiv:2611.07675]Liu
[arXiv:2611.07675] shows that, in high dimension, the standard subgradient rate is optimal in round complexity for finding approximate stationary points of nonsmooth weakly convex functions, even for randomised algorithms making polynomially many parallel queries per round, while on the real line a deterministic algorithm using only function values needs only logarithmically many rounds.
Monodromy Computation Model Xiaoyang Liu [arXiv:2611.04377]Liu
[arXiv:2611.04377] defines a model of computation in which retained logarithmic branches of analytic continuation serve as memory, and shows that three branch coordinates suffice to simulate every finite-alphabet, finite-control Post–Turing machine.
Community Search under Member-Specific Tolerances Yanghao Liu, Fangda Guo, Yuxuan Zhang, Xueqi Cheng [arXiv:2611.05951]Liu, Guo, Zhang and Cheng
[arXiv:2611.05951] define latitude-consistent communities: connected subgraphs containing the query vertex, with minimum degree at least
\(k\) and diameter bounded by the smallest member tolerance; they motivate the model by social judgement theory and study its complexity and practical algorithms.
An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine Sergey Salishev [arXiv:2611.06303]Salishev
[arXiv:2611.06303] defines an exact finite-budget version of the bounded halting problem in which the checker and the simulated program run on the same unit-cost timescale, and uses a diagonal argument with explicit additive overhead to show that no fixed deterministic checker decides every instance within the stated budget.
Dissecting Geometric Constraints in Grokking: Interaction-Dependent Acceleration in Modular Arithmetic Zachary A. Hampton, Wasiq Khan, Bilal Khan [arXiv:2611.03156]A factorial study of 960 modular-arithmetic training runs finds that residual projection accounts for much of the faster grokking in the Sphere+Fourier transformer configuration, but is not sufficient on its own; this is empirical machine learning, not complexity theory.