0000000000160816

AUTHOR

Rishat Ibrahimov

showing 4 related works from this author

Error-Free Affine, Unitary, and Probabilistic OBDDs

2021

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las-Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata counterparts of these models.

Discrete mathematicsState complexityComputer Science::Logic in Computer ScienceComputer Science (miscellaneous)Probabilistic logicAffine transformationComputer Science::Computational ComplexityComputer Science::Artificial IntelligenceUnitary stateComputer Science::DatabasesMathematicsZero errorInternational Journal of Foundations of Computer Science
researchProduct

Error-Free Affine, Unitary, and Probabilistic OBDDs

2018

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results for the automata versions of these models.

Discrete mathematicsQuadratic growthLas vegas010102 general mathematicsProbabilistic logic02 engineering and technologyComputer Science::Computational ComplexityComputer Science::Artificial Intelligence01 natural sciencesUnitary stateAutomatonSuccinctnessComputer Science::Logic in Computer Science0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingAffine transformation0101 mathematicsComputer Science::DatabasesZero errorMathematics
researchProduct

Zero-Error Affine, Unitary, and Probabilistic OBDDs

2017

We introduce the affine OBDD model and show that zero-error affine OBDDs can be exponentially narrower than bounded-error unitary and probabilistic OBDDs on certain problems. Moreover, we show that Las Vegas unitary and probabilistic OBDDs can be quadratically narrower than deterministic OBDDs. We also obtain the same results by considering the automata versions of these models.

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsFormal Languages and Automata Theory (cs.FL)Computer Science::Logic in Computer ScienceFOS: Physical sciencesComputer Science - Formal Languages and Automata TheoryComputational Complexity (cs.CC)Computer Science::Computational ComplexityComputer Science::Artificial IntelligenceQuantum Physics (quant-ph)Computer Science::Databases
researchProduct

Width Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams with Repeated Test

2017

We consider quantum, nondterministic and probabilistic versions of known computational model Ordered Read-$k$-times Branching Programs or Ordered Binary Decision Diagrams with repeated test ($k$-QOBDD, $k$-NOBDD and $k$-POBDD). We show width hierarchy for complexity classes of Boolean function computed by these models and discuss relation between different variants of $k$-OBDD.

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsFOS: Physical sciencesComputational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct