iiinova — where your digital self keeps evolving

arxiv cs.CC @arxiv-cs-cc.bsky.social · 01/10/2026

Oliver Korten Top-Down Lower Bounds for All Depths arxiv.org/abs/2609.38677

arxiv cs.CC @arxiv-cs-cc.bsky.social · 01/10/2026

Eshan Chattopadhyay, Oren Renard, Nicholas Spooner Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP arxiv.org/abs/2609.38910

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 01/10/2026

Haoyu Wang, Pei Wu, Guangxu Yang Exponential Quantum Advantage in Numbers-on-Forehead Communication arxiv.org/abs/2609.40273

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 01/10/2026

Jeremy Huang, Young Kun Ko, Chunhao Wang Quantum Fine-Grained Lower Bounds for SetDisjointness via Sub-Linear Reductions from 3SUM arxiv.org/abs/2609.40293

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 01/10/2026

Paul Beame, Blake Holman, Niels Kornerup A Noise Operator Approach to Quantum Query Complexity and Time-Space Tradeoff Lower Bounds arxiv.org/abs/2609.40334

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 28/09/2026

Dejan Delic, Ali Syed Maltsev Constraint Satisfaction Problems and Deterministic Logspace With Counting arxiv.org/abs/2609.30757

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 28/09/2026

Sebastian Ben Daniel Linear Certificates for Membership Comparability, Quadratic Barriers for Selectors arxiv.org/abs/2609.31053

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 28/09/2026

Jean-Fran\c{c}ois Biasse, Giacomo Micheli, Benjamin Prada, Philip Waitkevich A search-to-decision reduction for the linear code equivalence problem arxiv.org/abs/2609.31517

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Simon Mackenzie Lossless Hardness Condensation in Deterministic Communication Complexity arxiv.org/abs/2609.28691

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Zhi-Long Chen (University of Maryland), Nicholas G. Hall (The Ohio State University) Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times arxiv.org/abs/2609.28751

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee, Shachar Lovett, Avishay Tal, Emanuele Viola Exponential Correlation Bounds for Polynomials arxiv.org/abs/2609.28839

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Daqing Wan, Jun Zhang NP-Hardness of Bounded Distance Decoding for Reed-Solomon Codes arxiv.org/abs/2609.29120

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Sebastian Ben Daniel Constant-Probability Witness Isolation Implies $\mathrm{NP}\subseteq\mathrm{P/poly}$ arxiv.org/abs/2609.29302

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Jizhou Guo An $n^2\log\log n$ Lower Bound for Permanent Circuits with Valid Division arxiv.org/abs/2609.29568

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Kirill Osipov Step Recursion: Mixed Stride Spectra, Path Factorization, and Synchronization Geometry arxiv.org/abs/2609.29585

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Bo Liu A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$ arxiv.org/abs/2609.29881

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Max G\"ottlicher, Lennard Hofmann, Christoph Niederbudde From FPT to W[P]: Classifying Zero Forcing, Power Domination and Their Variants arxiv.org/abs/2609.29966

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Aaron Potechin, Jeff Xu Sharp Lovasz-Theta Bounds on Random Graphs arxiv.org/abs/2609.30064

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/09/2026

Samruddhi Pednekar, Supartha Podder A General Composition Theorem for Approximate Degree arxiv.org/abs/2609.30139

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 23/09/2026

Yan S. Couto, Cristina G. Fernandes Sub-polynomial parameterized complexity of $k$-core arxiv.org/abs/2609.25419

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 23/09/2026

Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal Code Equivalence and Automorphism Problems for Codes arxiv.org/abs/2609.25483

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 23/09/2026

Ben Lee Volk Improved Algorithms for the Remote Point Problem arxiv.org/abs/2609.25765

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 23/09/2026

Paul Beame, Niels Kornerup, Michael Whitmeyer Strong Selective and List-Decoding Direct Product Theorems for Quantum Query Complexity arxiv.org/abs/2609.26678

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 23/09/2026

Martin Kouteck\'y, Alexandra Lassota, Koen Ligthart 4-Block Integer Programming is in FPT arxiv.org/abs/2609.26746

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 23/09/2026

Chandrima Kayal, Sophie Laplante, \'Emile Larroque, Kri\v{s}j\=anis Pr\=usis, Jevg\=enijs Vihrovs Certification complexity of Boolean functions arxiv.org/abs/2609.26757

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 17/09/2026

Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman Separating Non-redundancy and Chain Length arxiv.org/abs/2609.17914

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 17/09/2026

Justin Holmgren, Kewen Wu Improved lower bounds for decomposable randomized encoding arxiv.org/abs/2609.18020

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 17/09/2026

Chenghua Liu, Boning Meng Hidden Circuits and Exact Counting in Ordered Graphs arxiv.org/abs/2609.18132

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 17/09/2026

Stefan G\"oller, Amaldev Manuel Rational Reductions and Regular Languages of Constant Circuit Complexity arxiv.org/abs/2609.18484

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 17/09/2026

Antoine Vinciguerra An Operator Approach to Register Programs for Catalytic Computing arxiv.org/abs/2609.18692

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 17/09/2026

Shuxing Yang, Rui Zhao, Junyao Wu, Yize Wang, Wenhao Li, Fujia Chen, Taowen Deng, Shenzhan Hong, Yaqi Li, Zichen Li, Jincheng Mi, Yuang Pan, Kaihao Zhu, ... A Structural Proof of the Lower Bound 21 for $3\times3$ Matrix Multiplication over $\mathbb F_2$ arxiv.org/abs/2609.18722

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification arxiv.org/abs/2609.13703

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Emmanouil-Vasileios Vlatakis-Gkaragkounis, Pucheng Xiong On the Complexity of Finding Fixed Points for Set-Valued Contractions arxiv.org/abs/2609.14101

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Jason Yang New lower bounds on tensor rank of $(2,n,m)$ matrix multiplication with GPT-6 arxiv.org/abs/2609.14393

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Bruno Bauwens, Marius Zimand Explicit unbalanced 1-expanders with small degree and right size arxiv.org/abs/2609.14587

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Tetsuo Yokoyama The Exact Growth Rate of Space-Optimal Reversible Pebbling on Chains arxiv.org/abs/2609.15062

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Shalev Ben-David, Robin Kothari Randomized query complexity can beat certificate complexity arxiv.org/abs/2609.15063

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 15/09/2026

Daniel E. Martin NP-hardness of ideal lattice problems arxiv.org/abs/2609.15813

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 11/09/2026

Yuan Huang, Zhiguo Fu The Computational Complexity of Holant Problems on 4-regular Graphs from the Stable Subgroup Sequence of $SL(2,\mathbb{C})$ arxiv.org/abs/2609.11175

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 11/09/2026

\'Edouard Bonnet, Yeonsu Chang Max Independent Set Remains NP-hard when Excluding a Planar Induced Minor arxiv.org/abs/2609.11285

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 11/09/2026

Eric Allender, Samir Datta, Arsenii Karnaukhov, Sambuddha Roy, Alexander Shekhovstov Topology inside NC$^1$ arxiv.org/abs/2609.11822

001

arxiv cs.CC @arxiv-cs-cc.bsky.social · 04/09/2026

Nick Jamesson Promise Systems of Equations over Magmas with Identity and over Algebras in Congruence Modular Varieties arxiv.org/abs/2609.03469

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 04/09/2026

Khaled Elbassioni, Rishikesh Gajjala, Saurabh Ray Random Garbage Separates XOR from Forward-Only Queries arxiv.org/abs/2609.03628

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 04/09/2026

Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye The Head Complexity of Boolean Functions in Single-Layer Attention arxiv.org/abs/2609.04046

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 28/08/2026

Joshua A. Grochow, G\"ulce Karde\c{s}, Michael Levet Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2$\frac{1}{2}$ Circuits and Lower Bounds arxiv.org/abs/2608.26257

050

arxiv cs.CC @arxiv-cs-cc.bsky.social · 28/08/2026

Thomas Watson Pseudodeterminism and MA != NP^BPP in Communication Complexity arxiv.org/abs/2608.26425

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 27/08/2026

Youlong Ding, Aayush Jain, Ilan Komargodski Pseudorandom Functions in $\mathsf{NC}^1$ from LWE/LPN/CDH (Or: How to Build PRFs in $\mathsf{NC}^1$, Generically) arxiv.org/abs/2608.25213

010

arxiv cs.CC @arxiv-cs-cc.bsky.social · 27/08/2026

Martin Kouteck\'y, Nikolaos Melissinos, Tung Anh Vu, Llu\'is Sabater Continuous Computational Social Choice: A Case Study in Bribery arxiv.org/abs/2608.25444

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/08/2026

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard Low-Degree Testing Over Boolean Slices arxiv.org/abs/2608.21730

000

arxiv cs.CC @arxiv-cs-cc.bsky.social · 25/08/2026

Hongmin Li Target-Dependent Local Verification: Information--Proof-Length Tradeoffs arxiv.org/abs/2608.21793

000