arxiv cs.CC

Serge Gaspers, Zixu He, Simon Mackenzie
NP-Hardness and ETH-Based Inapproximability of Communication Complexity via Relaxed Interlacing
https://arxiv.org/abs/2508.05597

Eric Ma, Tselil Schramm
Polynomial-time sampling despite disorder chaos
https://arxiv.org/abs/2508.04133

Shlomi Dolev
Towards EXPTIME One Way Functions: Bloom Filters, Succinct Graphs, Cliques, & Self Masking
https://arxiv.org/abs/2508.01649

Shuichi Hirahara, Naoto Ohsaka
Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
https://arxiv.org/abs/2508.00276

Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay
Exponential Lower Bounds on the Size of ResLin Proofs of Nearly Quadratic Depth
https://arxiv.org/abs/2507.23008

Takashi Ishizuka
On a better complexity upper bound of Ward-Szabo theorem
https://arxiv.org/abs/2507.23345

T. C. Vijayaraghavan
The Complexity of Logarithmic Space Bounded Counting Classes
https://arxiv.org/abs/2507.23563

Venkatesan Guruswami, Xin Lyu, Weiqiang Yuan
Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
https://arxiv.org/abs/2507.22265

Aviv Taller, Thomas Vidick
Approximating the quantum value of an LCS game is RE-hard
https://arxiv.org/abs/2507.22444

Surendra Ghentiyala, Zeyong Li
Hierarchies within TFNP: building blocks and collapses
https://arxiv.org/abs/2507.21550

Zining Cao
On Higher Order Busy Beaver Function
https://arxiv.org/abs/2507.20321

Nicholas Fidalgo, Puyuan Ye
Simulating Evolvability as a Learning Algorithm: Empirical Investigations on Distribution Sensitivity, Robustness, and Constraint Tradeoffs
https://arxiv.org/abs/2507.18666

Alexey Barsukov, Antoine Mottet, Davide Perinti
Edge-coloring problems with forbidden patterns and planted colors
https://arxiv.org/abs/2507.19000

Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi
Downward self-reducibility in the total function polynomial hierarchy
https://arxiv.org/abs/2507.19108

Guillermo Badia, Manfred Droste, Thomas Eiter, Rafael Kiesel, Carles Noguera, Erik Paul
Fagin's Theorem for Semiring Turing Machines
https://arxiv.org/abs/2507.18375

Bruno Cavalar, Mika G\"o\"os, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov
Monotone Circuit Complexity of Matching
https://arxiv.org/abs/2507.16105

Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy
Pseudorandomness of Expander Walks via Fourier Analysis on Groups
https://arxiv.org/abs/2507.14445

Jesus Salas
Certificate-Sensitive Subset Sum: Realizing Instance Complexity
https://arxiv.org/abs/2507.15511

Hunter Monroe
Characterizing p-Simulation Between Theories
https://arxiv.org/abs/2507.13576

\'Edouard Bonnet, Daniel Neuen, Marek Soko{\l}owski
Treedepth Inapproximability and Exponential ETH Lower Bound
https://arxiv.org/abs/2507.13818

Arkadev Chattopadhyay, Yogesh Dahiya, Shachar Lovett
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
https://arxiv.org/abs/2507.13963

Yuxi Liu
Perfect diffusion is $\mathsf{TC}^0$ -- Bad diffusion is Turing-complete
https://arxiv.org/abs/2507.12469

Guy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan
Computational-Statistical Tradeoffs from NP-hardness
https://arxiv.org/abs/2507.13222

Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
Searching for Falsified Clause in Random (log n)-CNFs is Hard for Randomized Communication
https://arxiv.org/abs/2507.12124

Markus Bl\"aser, Radu Curticapean, Julian D\"orfler, Christian Ikenmeyer
Which graph motif parameters count?
https://arxiv.org/abs/2507.12244

Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan
Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
https://arxiv.org/abs/2507.10731

Mika G\"o\"os, Nathaniel Harms, Artur Riazanov
Equality is Far Weaker than Constant-Cost Communication
https://arxiv.org/abs/2507.11162

Piotr Bacik, Jo\"el Ouaknine, James Worrell
On the Complexity of the Skolem Problem at Low Orders
https://arxiv.org/abs/2507.11234

Emanuele Viola
Communication complexity of pointer chasing via the fixed-set lemma
https://arxiv.org/abs/2507.08919

Isabel Humphreys, Matthew Iceland, Harry Liuson, Dylan McKellips, Leo Sciortino
A Critique of Deng's "P=NP"
https://arxiv.org/abs/2507.09018