0000000000359830

AUTHOR

R. Freivalds

showing 3 related works from this author

Quantum Finite State Transducers

2000

We introduce quantum finite state transducers (qfst), and study the class of relations which they compute. It turns out that they share many features with probabilistic finite state transducers, especially regarding undecidability of emptiness (at least for low probability of success). However, like their `little brothers', the quantum finite automata, the power of qfst is incomparable to that of their probabilistic counterpart. This we show by discussing a number of characteristic examples.

Quantum PhysicsComputer Science::Logic in Computer ScienceFOS: Physical sciencesQuantum Physics (quant-ph)Computer Science::Formal Languages and Automata Theory
researchProduct

Complexity of decision trees for boolean functions

2004

For every positive integer k we present an example of a Boolean function f/sub k/ of n = (/sub k//sup 2k/) + 2k variables, an optimal deterministic tree T/sub k/' for f/sub k/ of complexity 2k + 1 as well as a nondeterministic decision tree T/sub k/ computing f/sub k/. with complexity k + 2; thus of complexity about 1/2 of the optimal deterministic decision tree. Certain leaves of T/sub k/ are called priority leaves. For every input a /spl isin/ {0, 1}/sup n/ if any of the parallel computation reaches a priority leaves then its label is f/sub k/ (a). If the priority leaves are not reached at all then the label on any of the remaining leaves reached by the computation is f/sub k/. (a).

CombinatoricsDiscrete mathematicsNondeterministic algorithmComputational complexity theoryIntegerDecision treeTree (set theory)Boolean functionMathematics33rd International Symposium on Multiple-Valued Logic, 2003. Proceedings.
researchProduct

Boolean Functions of Low Polynomial Degree for Quantum Query Complexity Theory

2007

The degree of a polynomial representing (or approximating) a function f is a lower bound for the quantum query complexity of f. This observation has been a source of many lower bounds on quantum algorithms. It has been an open problem whether this lower bound is tight. This is why Boolean functions are needed with a high number of essential variables and a low polynomial degree. Unfortunately, it is a well-known problem to construct such functions. The best separation between these two complexity measures of a Boolean function was exhibited by Ambai- nis [5]. He constructed functions with polynomial degree M and number of variables Omega(M2). We improve such a separation to become exponenti…

CombinatoricsComplexity indexDiscrete mathematicsZero of a functionKarp–Lipton theoremHomogeneous polynomialBoolean expressionDegree of a polynomialBoolean functionMathematicsMatrix polynomial37th International Symposium on Multiple-Valued Logic (ISMVL'07)
researchProduct