arxiv cs.CC
LightNews LightNews
banner
arxiv-cs-cc.bsky.social
arxiv cs.CC
@arxiv-cs-cc.bsky.social
310 followers 0 following 970 posts
Computer Science -- Computational Complexity (cs.CC)

source: https://export.arxiv.org/rss/cs.CC
maintainer: @tmaehara.bsky.social
Posts Replies Media Videos
arxiv-cs-cc.bsky.social
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra, Mihir Singhal, Avi Wigderson
The communication complexity of distributed estimation
https://arxiv.org/abs/2511.21015
November 27, 2025 at 5:23 AM
arxiv-cs-cc.bsky.social
Aritra Banik, Praneet Kumar Patra, Adele Anna Rescigno, Abhishek Sahu
Identifying Codes Kernelization Limitations
https://arxiv.org/abs/2511.21067
November 27, 2025 at 5:22 AM
arxiv-cs-cc.bsky.social
Chetan Gupta, Raghunath Tewari, Vimal Raj Sharma
Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
https://arxiv.org/abs/2511.21217
November 27, 2025 at 5:22 AM
arxiv-cs-cc.bsky.social
Per Austrin, Johan H{\aa}stad, Bj\"orn Martinsson
On the Usefulness of Promises
https://arxiv.org/abs/2511.21450
November 27, 2025 at 5:21 AM
arxiv-cs-cc.bsky.social
Guy Goldberg, Tom Gur, Sidhant Saraogi
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
https://arxiv.org/abs/2511.21659
November 27, 2025 at 5:21 AM
arxiv-cs-cc.bsky.social
Farzan Byramji, Russell Impagliazzo
Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
https://arxiv.org/abs/2511.20023
November 26, 2025 at 5:07 AM
arxiv-cs-cc.bsky.social
Micha{\l} Pilipczuk, Sylvain Schmitz, Henry Sinclair-Banks
A Note on the Parameterised Complexity of Coverability in Vector Addition Systems
https://arxiv.org/abs/2511.19212
November 25, 2025 at 6:06 AM
arxiv-cs-cc.bsky.social
Marco Carmosino, Ngu Dang, Tim Jackman
Simple Circuit Extensions for XOR in PTIME
https://arxiv.org/abs/2511.16903
November 24, 2025 at 5:29 AM
arxiv-cs-cc.bsky.social
Xudong Wu, Guangxu Yang, Penghui Yao
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
https://arxiv.org/abs/2511.17227
November 24, 2025 at 5:28 AM
arxiv-cs-cc.bsky.social
Jonas Conneryd, Yassine Ghannane, Shuo Pang
Lower Bounds for CSP Hierarchies Through Ideal Reduction
https://arxiv.org/abs/2511.17272
November 24, 2025 at 5:28 AM
arxiv-cs-cc.bsky.social
Antoine Joux (CISPA, IMJ-PRG)
Indefiniteness makes lattice reduction easier
https://arxiv.org/abs/2511.16151
November 21, 2025 at 5:36 AM
arxiv-cs-cc.bsky.social
Anakin Dey, Zeyu Guo
Debordering Closure Results in Determinantal and Pfaffian Ideals
https://arxiv.org/abs/2511.16492
November 21, 2025 at 5:35 AM
arxiv-cs-cc.bsky.social
Sergey S. Ketkov, Oleg A. Prokopyev
A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
https://arxiv.org/abs/2511.15592
November 20, 2025 at 6:12 AM
arxiv-cs-cc.bsky.social
Lijie Chen, Yang Hu, Hanlin Ren
New Algebrization Barriers to Circuit Lower Bounds via Communication Complexity of Missing-String
https://arxiv.org/abs/2511.14038
November 19, 2025 at 5:26 AM
arxiv-cs-cc.bsky.social
Hanlin Ren, Yichuan Wang, Yan Zhong
Hardness of Range Avoidance and Proof Complexity Generators from Demi-Bits
https://arxiv.org/abs/2511.14061
November 19, 2025 at 5:26 AM
arxiv-cs-cc.bsky.social
Daniel M. Kane, Anthony Ostuni, Kewen Wu
Symmetric Distributions from Shallow Circuits
https://arxiv.org/abs/2511.14127
November 19, 2025 at 5:25 AM
arxiv-cs-cc.bsky.social
Daniel Gibor
Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
https://arxiv.org/abs/2511.14244
November 19, 2025 at 5:25 AM
arxiv-cs-cc.bsky.social
Milan Rosko
The Solver's Paradox in Formal Problem Spaces
https://arxiv.org/abs/2511.14665
November 19, 2025 at 5:24 AM
arxiv-cs-cc.bsky.social
Jeffrey Uhlmann
Graded Projection Recursion (GPR): A Framework for Controlling Bit-Complexity of Algebraic Packing
https://arxiv.org/abs/2511.11988
November 18, 2025 at 5:45 AM
arxiv-cs-cc.bsky.social
Ali Asadi, Krishnendu Chatterjee, David Lurie, Raimundo Saona
Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
https://arxiv.org/abs/2511.13134
November 18, 2025 at 5:45 AM
arxiv-cs-cc.bsky.social
Julio Aracena (UdeC), Florian Bridoux (AMU, CANA), Maximilien Gadouleau (I2M), Pierre Guillon (I2M), K\'evin Perrot (LIS), Adrien Richard (Laboratoire I3S - MDSC), Guillaume Theyssier (I2M)
On the Dynamics of Bounded-Degree Automata Networks
https://arxiv.org/abs/2511.11174
November 17, 2025 at 5:25 AM
arxiv-cs-cc.bsky.social
Thiago Marcilon, Murillo In\'acio da Costa Silva
Parameterized complexity of the f-Critical Set problem
https://arxiv.org/abs/2511.11546
November 17, 2025 at 5:24 AM
arxiv-cs-cc.bsky.social
Ryan O'Donnell, Noah G. Singer
Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
https://arxiv.org/abs/2511.10514
November 14, 2025 at 5:43 AM
arxiv-cs-cc.bsky.social
John M. Hitchcock, Adewale Sekoni, Hadi Shafei
Random Permutations in Computational Complexity
https://arxiv.org/abs/2511.08786
November 13, 2025 at 5:15 AM
arxiv-cs-cc.bsky.social
Eric Goles (I2M), Pedro Montealegre (I2M), Mart\'in R\'ios-Wilson (I2M), Guillaume Theyssier (I2M)
On the complexity of freezing automata networks of bounded pathwidth
https://arxiv.org/abs/2511.09297
November 13, 2025 at 5:14 AM