16 citations · 35 across the 16 of their papers we have counts for
6 papers · 1 filter
On the Complexity of Recurrence Evaluation
Artem Parfenov, Michael Vyalyi
In this paper, we study the complexity of the recurrence evaluation problem. We are interested in finitely valued recurrent functions. We present two results in this direction. Fir…
On complexity of regular realizability problems
Mikhail N. Vyalyi
A regular realizability (RR) problem is testing nonemptiness of intersection of some fixed language (filter) with given regular language. We study here complexity of RR problems. I…
On models of a nondeterministic computation
M. N. Vyalyi
In this paper we consider a nondeterministic computation by deterministic multi-head 2-way automata having a read-only access to an auxiliary memory. The memory contains additional…
Semidefinite programming and arithmetic circuit evaluation
Sergey P. Tarasov, Mikhail N. Vyalyi
A rational number can be naturally presented by an arithmetic computation (AC): a sequence of elementary arithmetic operations starting from a fixed constant, say 1. The asymptotic…
Hardness of approximating the weight enumerator of a binary linear code
M. N. Vyalyi
We consider the problem of evaluation of the weight enumerator of a binary linear code. We show that the exact evaluation is hard for polynomial hierarchy. More exactly, if WE is a…
A comparison of Zeroes and Ones of a Boolean Polynomial
M. N. Vyalyi
In this paper we consider the computational complexity of the following problem. Let be a Boolean polynomial. What value of , 0 or 1, is taken more frequently? The problem i…