Cover Image

Some derivations among Logarithmic Space Bounded Counting Classes

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Janaki, V., Madhan, S., Vijayaraghavan, T. C.
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Logic 68Q10, 68Q15
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Choiceless Polynomial Space
by: Ferrarotti, Flavio, et al.
Published: (2024)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

The Complexity of Resilience for Digraph Queries
by: Bodirsky, Manuel, et al.
Published: (2026)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Counting Martingales for Measure and Dimension in Complexity Classes
by: Hitchcock, John M., et al.
Published: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

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)

Fully Characterizing Lossy Catalytic Computation
by: Folkertsma, Marten, et al.
Published: (2024)

Computational Complexity of Model-Checking Quantum Pushdown Systems
by: Lin, Deren, et al.
Published: (2025)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Logarithmic Weisfeiler--Leman and Treewidth
by: Levet, Michael, et al.
Published: (2023)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

Weighted Automata and Logics Meet Computational Complexity
by: Kostolányi, Peter
Published: (2023)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

From Gödel incompleteness to the consistency of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2026)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Quantum Random Self-Modifiable Computation
by: Fiske, Michael Stephen
Published: (2018)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
by: Zhang, Weikun K., et al.
Published: (2026)

Count-Free Weisfeiler--Leman and Group Isomorphism
by: Collins, Nathaniel A., et al.
Published: (2022)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Behavioural Theory of Reflective Algorithms II: Reflective Parallel Algorithms
by: Schewe, Klaus-Dieter, et al.
Published: (2025)

The CSP Dichotomy, the Axiom of Choice, and Cyclic Polymorphisms
by: Kátay, Tamás, et al.
Published: (2023)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
by: Schewe, Klaus-Dieter
Published: (2020)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)