Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.07619 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
Random Permutations in Computational Complexity
by: Hitchcock, John M., et al.
Published: (2025)
by: Hitchcock, John M., et al.
Published: (2025)
Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)
by: Bürgisser, Peter
Published: (2024)
Some derivations among Logarithmic Space Bounded Counting Classes
by: Janaki, V., et al.
Published: (2023)
by: Janaki, V., et al.
Published: (2023)
Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)
by: Masierak, Piotr
Published: (2026)
The Optimizer Quotient and the Certification Trilemma
by: Simas, Tristan
Published: (2026)
by: Simas, Tristan
Published: (2026)
Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)
by: Barsukov, Alexey, et al.
Published: (2021)
The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)
by: Eppstein, David
Published: (2021)
An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
by: Lela, Marko
Published: (2025)
by: Lela, Marko
Published: (2025)
Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)
by: Edwards, Darren J.
Published: (2025)
NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)
by: Czerwinski, Reiner
Published: (2023)
Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)
by: Czerwinski, Reiner
Published: (2021)
Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)
by: Nagao, Atsuki, et al.
Published: (2025)
Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)
by: Hirsch, Edward A., et al.
Published: (2025)
Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)
by: Agarwala, Aryan, et al.
Published: (2025)
Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)
by: Hamm, Thekla, et al.
Published: (2025)
Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)
by: Göös, Mika, et al.
Published: (2025)
A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)
by: Hirsch, Edward A., et al.
Published: (2025)
Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)
by: Lin, Tianrong
Published: (2024)
Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)
by: Garcia, Baruch
Published: (2026)
Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)
by: Collins, Nathaniel A., et al.
Published: (2022)
Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)
by: Saffidine, Abdallah, et al.
Published: (2025)
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)
by: Tzameret, Iddo, et al.
Published: (2023)
IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)
by: Lela, Marko
Published: (2025)
Evolomino is NP-complete
by: Nikolaev, Andrei V.
Published: (2025)
by: Nikolaev, Andrei V.
Published: (2025)
The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
by: Phillips, Reed
Published: (2026)
by: Phillips, Reed
Published: (2026)
The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)
by: Liu, Yuxi, et al.
Published: (2025)
On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
by: Grochow, Joshua A., et al.
Published: (2021)
by: Grochow, Joshua A., et al.
Published: (2021)
Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)
by: Shalunov, Yakov
Published: (2023)
The Complexity of Resilience Problems via Valued Constraint Satisfaction
by: Bodirsky, Manuel, et al.
Published: (2023)
by: Bodirsky, Manuel, et al.
Published: (2023)
Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)
by: Huseynzade, Rafig
Published: (2025)
The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)
by: Lin, Tianrong
Published: (2021)
On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
by: Grochow, Joshua A., et al.
Published: (2025)
by: Grochow, Joshua A., et al.
Published: (2025)
Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)
by: Kelley, Zander, et al.
Published: (2023)
Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)
by: Hu, Ivan, et al.
Published: (2022)
Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)
by: Ye, Lixi
Published: (2026)
From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)
by: Atserias, Albert, et al.
Published: (2026)
The Word Problem for Products of Symmetric Groups
by: Simon, Hans U.
Published: (2025)
by: Simon, Hans U.
Published: (2025)
NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
by: Eua-anant, Pakapim, et al.
Published: (2025)
by: Eua-anant, Pakapim, et al.
Published: (2025)
On Small-depth Frege Proofs for PHP
by: Håstad, Johan
Published: (2024)
by: Håstad, Johan
Published: (2024)
How do humans succeed in tasks like proving Fermat's Theorem or predicting the Higgs boson?
by: Levin, Leonid A.
Published: (2022)
by: Levin, Leonid A.
Published: (2022)