Cover Image

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Khadiev, Kamil
Format:	Preprint
Published:	2016
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Width Hierarchy for k-OBDD of Small Width
by: Khadiev, Kamil
Published: (2015)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
by: Khadiev, Kamil, et al.
Published: (2017)

Efficient Algorithms for Quantum Hashing
by: Zinnatullin, Ilnar, et al.
Published: (2025)

Quantum Property Testing Algorithm for the Concatenation of Two Palindromes Language
by: Khadiev, Kamil, et al.
Published: (2024)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)

On Formally Undecidable Propositions of Nondeterministic Complexity and Related Classes
by: Kolář, Martin
Published: (2026)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2024)

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

Lower Bounds for Set-Multilinear Branching Programs
by: Chatterjee, Prerona, et al.
Published: (2023)

Complexity of Unary Exclusive Nondeterministic Finite Automata
by: Kutrib, Martin, et al.
Published: (2024)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Intersection and Union Hierarchies of Deterministic Context-Free Languages and Pumping Lemmas
by: Yamakami, Tomoyuki
Published: (2021)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
by: Podolskii, Vladimir, et al.
Published: (2024)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

A Hierarchy for Constant Communication Complexity
by: Ambainis, Andris, et al.
Published: (2025)

Nondeterministic Auxiliary Depth-Bounded Storage Automata and Semi-Unbounded Fan-in Cascading Circuits
by: Yamakami, Tomoyuki
Published: (2024)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Hierarchies within TFNP: building blocks and collapses
by: Ghentiyala, Surendra, et al.
Published: (2025)

An XOR Lemma for Deterministic Communication Complexity
by: Iyer, Siddharth, et al.
Published: (2024)

Unambiguous and Co-Nondeterministic Computations of Finite Automata and Pushdown Automata Families and the Effects of Multiple Counters
by: Yamakami, Tomoyuki
Published: (2024)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

An Unconditional Barrier for Proving Multilinear Algebraic Branching Program Lower Bounds
by: Kush, Deepanshu
Published: (2026)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
by: Bhattacharjee, Sutanay, et al.
Published: (2026)

Oblivious Complexity Classes Revisited: Lower Bounds and Hierarchies
by: Gajulapalli, Karthik, et al.
Published: (2025)

Deterministic Weighted Automata under Partial Observability
by: Michaliszyn, Jakub, et al.
Published: (2024)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

An Exponential Separation between Deterministic CDCL and DPLL Solvers
by: Samar, Sahil, et al.
Published: (2026)

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

The Entangled Quantum Polynomial Hierarchy Collapses
by: Grewal, Sabee, et al.
Published: (2024)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

On the Holographic Geometry of Deterministic Computation
by: Nye, Logan
Published: (2025)

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

Bounded-Depth Frege Lower Bounds for Random 3-CNFs via Deterministic Restrictions
by: Gryaznov, Svyatoslav, et al.
Published: (2024)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
by: Agarwal, Avantika, et al.
Published: (2024)