- Нижние оценки сложности булевых схем конечной глубины с произвольными элементами
// Дискрет. матем., 23:4 (2011), 39–47.
(статья: pdf,
рукопись: ps.gz,
tex.tgz)
-
Lower Bounds for Boolean Circuits with Finite Depth and Arbitrary Gates //
Electronic Colloquium on Computational Complexity, Report No. 32 (2008)
[pdf,
tex.tgz;
reviews: 1
2 3
4 5
6; link: ECCC]
Abstract:
We consider bounded depth circuits over an arbitrary field
$K$. If the field $K$
is finite, then we allow arbitrary gates $K^n \to K$. For
instance, in the case of
field $GF(2)$ we allow any Boolean gates. If the field $K$ is
infinite, then we
allow only polinomials. For every fixed depth $d$, we prove a lower bound
$Omega(n \lambda_{d-1}(n))$ for the size (i.e. the number of
wires)
of any circuit for computing the cyclic convolution over the field $K$.
In particular, for $d=2,3,4$, our bounds are $\Omega(n^{1.5})$,
$\Omega(n \log n)$ and $Omega(n \log \log n)$
respectively;
for $d \ge 5$, the function $\lambda_{d-1}(n)$ is slowly
growing.
On the Boolean model, our bounds are the best known for all even $d$ and for $d=3$.
For $d=2,3$, we prove these bounds in previous papers.
- О сложности информационных сетей
глубины 2 // Вестн. Моск. ун-та. Сер. 1.
Математика. Механика. 2009. № 1. С. 16-20. (ps.gz, tex.tgz)
The complexity of depth-two information networks //
Moscow Univ. Math. Bull. 64(1): 16-19 (2009) [english version: pdf ; link: doi]
Abstract:
The lower bound Ω(n log2 n) for the
complexity of an arbitrary depth-two information network with n
inputs and n outputs is proved providing the inputs are independent,
the outputs are independent, and the total information of any input and
any output is n times less than the entropy of any input or output.
A similar estimate for Boolean depth-two circuits of functional elements
is obtained as a corollary.
- Нижние оценки сложности булевых схем глубины 2 и 3 в произвольном базисе //
LNCS. Т. 5010. - Berlin, Heidelberg: Springer-Verlag, 2008. - С. 122-133.
(Тезисы конференции CSR-2008, Москва 7-12 июня 2008, на англ яз, русская версия:
ps.gz, tex.tgz)
Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates //
Lecture Notes on Computer Science, Vol. 5010: 122-133 (2008) [Proceedings of the 3rd
Comp. Symposium in Russia,
CSR-2008; final: pdf,
preliminary: ps.gz,
tex.tgz]
Abstract:
We consider depth-2 and 3 circuits over the basis consisting
of all Boolean functions. For depth-3 circuits, we prove a lower bound
Ω(n log n) for the size of any circuit computing the cyclic
convolution.
For depth-2 circuits, a lower bound Ω(n^{3/2}) for the same function was
obtained in our previous paper. Here we present an improved proof
of this bound. Both lower bounds are the best known for depth-3 and
depth-2 circuits, respectively.
- О сложности линейных операторов в
классе схем глубины 2 // Дискрет. матем. -
2008. - Т. 20, вып. 1. - C. 109-119. (статья: pdf;
рукопись: ps.gz, tex.tgz)
On complexity of linear
operators on the class of circuits of depth 2 // Discrete Mathematics and
Applications. 18(2): 143-154 (2008) [link: doi]
Abstract: In this study we suggest
methods for obtaining lower bounds for complexity of linear Boolean
operators (and the related matrices) in two models of circuits of depth 2.
In the first model, only linear elements with arbitrary number of inputs
are allowed, whereas in the second one, any Boolean elements can be
present. These methods are applicable to matrices with sufficiently large
Hamming distance between the rows, for example, to the Hadamard matrices.
- Нижняя оценка сложности в классе схем
глубины 2 без ограничений на базис //
Вестник МГУ. Сер. 1. Математика. Механика. -
2005. - № 4. - С. 54-56. (статья: djvu;
рукопись: ps.gz, tex.tgz)
The lower estimate of complexity in the class of schemes of depth 2 without restrictions on a basis //
Moscow Univ. Math. Bull. 60(4): 42-44 (2005) [link:
British lib.]
- Метод Нечипорука для двухярусных схем
// Тезисы конференции "Дискретная
математика, алгебра и приложения"
(DIMA-09, Минск, 19-22 октября 2009). - Минск: ин-т
математики, 2009. - с. 119-121. (pdf,
tex.rar)
Nechiporuk method for
two-layer circuits // Proceedings of the conference “Discrete Mathematics, Algebra and their
Applications” (DIMA-09, Minsk, 19-22 October 2009). Minsk: Institute of
Mathematics, 2009. p. 119-121. (Russian)
[link]
- О схемах из функциональных элементов конечной глубины ветвления //
Дискретная математика. - 2006. - Т. 18, вып. 4. - C. 73-83.
(статья: pdf;
рукопись: ps.gz, tex.tgz)
On circuits of functional elements of finite depth of branching //
Discrete Mathematics and Applications. 16(6): 577-587 (2006) [links:
mathnet,
Zbl pre05207877,
ams,
doi]
Abstract: We introduce the notion of the depth of branching of a
circuit of functional elements and consider classes of circuits of branching
depth bounded by a constant. For these classes of circuits over various bases we
obtain lower and upper bounds for complexity of a linear Boolean function. We
construct infinitely decreasing sequences of measures of complexity for a fixed
base and growing branching depth and for a fixed branching depth but varying
base.
- О схемах из функциональных элементов с ограниченной глубиной ветвления //
Докл. РАН. - 2005. - Т. 405, № 4. - С. 467-470.
(ps.gz, tex.tgz)
Boolean circuits with a bounded depth of branching //
Doklady Mathematics. 72(3): 930-933 (2005) [links:
Zbl pre05203084,
maik]
- О сложности информационных сетей. - 2007. -
сдано в журнал. (ps.gz,
tex.tgz)
On complexity of informational networks. - 2007. - Submitted to
journal. (Russian)
- Об информационной составляющей в
сложности оператора сдвига // Дискретный
анализ и исследование
операций. - 2005. - Т. 12, № 2. - C. 73–77. (статья: pdf;
рукопись: ps.gz,
tex.tgz)
On the informational component in the complexity of a shift operator // Diskretn. Anal.
Issled. Oper. Ser. 1. 12(2): 73-77 (2005), in Russian. [links:
mathnet,
ams]
- Одно обобщение задачи о максимальном
потоке. - 2004. - неопубл; результат
известен. (ps.gz,
tex.tgz)
One generalization of the Maximum Flow problem.
2004. Not published; result is known. (Russian)
- О линейных информационных и
транспортных сетях // Материалы
8-го семинара по дискретной
математики и её приложениям
(Москва, февраль 2004). - М.: изд-во
ЦПИ при мех.-мат. ф-те МГУ, 2004. - C. 106-109. (ps.gz, tex.tgz)
On linear information and transport
nets // Proceedings of 8th workshop on Discrete
Mathematics and its Applications (Moscow, February 2004).
Moscow: MSU, Mech.&Math. Publ., 2004. P. 106-109. (Russian)
- О сложности унитарных
преобразований // Дискретная
математика. - 2003. - Т. 15, вып. 4. - C.
113-118. (статья: pdf;
рукопись: ps.gz, tex.tgz)
On the complexity of unitary transformations // Discrete Mathematics and Applications.
13(6): 601-606 (2003) [links:
mathnet,
Zbl 1088.68609,
ams,
doi]
Abstract:
In this paper, we suggest a method to derive lower bounds for the complexity of
non-branching programs whose elementary operations are unitary transformations
over two complex numbers. This method provides us with estimates of the form
Ω(n log n) for unitary operators
Cn → Cn, in particular, for the Fourier and Walsh transformations.
For n = 2k we find precise values of the complexity of
those transformations.
- Об обратимых
схемах из функциональных
элементов // Материалы 11-й
школы-семинара "Синтез и
сложность управляющих
систем" (Пенза, осень 2001). - М.:
изд-во ЦПИ при мех.-мат. ф-те МГУ,
2002. (ps.gz, tex.tgz)
On invertible logical circuits //
Proceedings of 11th workshop "Synthesis and
Complexity of Control Systems" (Penza, Fall 2001). Moscow: MSU,
Mech.&Math. Publ., 2002. (Russian)
- Нижние оценки сложности
коммутационных сетей //
Материалы 7-го семинара по
дискретной математики и её
приложениям (Москва, февраль
2001). - М.: изд-во ЦПИ при мех.-мат.
ф-те МГУ, 2001. - С. 89-90. (ps.gz, tex.tgz)
Lower bounds of the complexity of
commutation nets // Proceedings of 7th workshop on
Discrete Mathematics and its Applications (Moscow,
February 2001). Moscow: MSU, Mech.&Math. Publ., 2001. P. 89-90. (Russian)
- О сложности реализации формулами произведений булевых функций //
Дискретный анализ и исследование операций. - 2002. - Т. 9, № 1. - C. 84-94.
(pdf)
On formula complexity for products of Boolean functions //
Diskretn. Anal. Issled. Oper. Ser. 1. 9(1): 84-94 (2002), in Russian [links:
mathnet,
Zbl 1009.68056,
ams]
Abstract:
Let $f(x_1,\dots,x_n)$ and $g(x_1,\dots,x_m)$ be Boolean functions. A function
$$(f\otimes g)(x_1,\dots,x_nm)=
f\bigl(g(x_1,\dots,x_m),\dots,g(x_{(n-1)m+1},\dots,x_nm)\bigr)$$ is called a
repetition-free product of Boolean functions. A criterion is given that makes it
possible to check whether a sequence of products of Boolean functions can be
computed with linear size formulas in a basis $B$.
- О сложности реализации формулами степеней булевых функций //
Дискретный анализ и исследование операций. - 2001. - Т. 8, № 4. С. 103-111.
(pdf)
On the complexity of degrees of Boolean functions for formulas //
Diskret. Anal. Issled. Oper. Ser. 1. 8(4): 103-111 (2001), in Russian [links:
mathnet,
Zbl 1005.68075,
ams]
Abstract:
Operations of repetition-free product of Boolean functions and raising to the
power of Boolean functions are considered. A criterion is given which makes it
possible to determine whether a sequence of degrees of a function $f$ can be
computed with linear or nonlinear size formulas in an arbitrary basis $B$.
- О реализации линейной функции формулами в различных базисах //
Вестник Московского университета. Серия 1. Математика. Механика. - 2001. - № 6. - С. 15-19.
Realization of linear functions by formulas in various bases //
Moscow University Mathematics Bulletin. 56(6): 14-18 (2001) [links:
Zbl 1028.94044]
Abstract:
The author studies the complexity of the realization of a linear Boolean
function $x_1\oplus\dots\oplus x_n$ by formulas in various bases. The author
divides all the bases into three types: in the bases of the first type, the
order of the complexity of realization of a linear function equals $n^2$; in the
bases of the second type, the order of complexity is not smaller than $n^\beta$
and not larger than $n^\gamma$, where $1<\beta<\gamma<2$ (the constants
$\beta$ and $\gamma$ are calculated with respect to the basis); and in the bases
of the third type, the order of complexity equals $n$.
- Нижние оценки формульной сложности симметрических булевых функций //
Дискрет. анализ и исслед. операций. Сер. 1. - 2000. - Т. 7, № 3. - C. 86-98.
(статья: pdf;
рукопись: ps.gz)
Lower bounds for the formula complexity of symmetric Boolean functions //
Diskretn. Anal. Issled. Oper. Ser. 1. 7(3): 86-98 (2000), in Russian [links:
mathnet,
Zbl 0956.68066,
ams]
Abstract:
The author obtains lower bounds of the form $\Omega(n\log n)$ on the sizes of
formulas over an arbitrary finite basis for almost all symmetric Boolean
functions.
- Сверхквадратичные нижние оценки сложности формул в некоторых базисах //
Дискретный анализ и исследование операций. - 2000. - Т. 7, № 2. - C. 86-95.
(pdf, djvu)
Superquadratic lower bounds for the complexity of formulas in some bases //
Diskretn. Anal. Issled. Oper. Ser. 1. 7(2): 86-95 (2000), in Russian [links:
mathnet,
Zbl 0956.68065,
ams]
Abstract:
Lower bounds of the form $n^{2+C}$, where $C>0$, are obtained for Andreev's
function for formulas over generalized monotone bases.
- О сложности реализации линейной функции формулами в конечных булевых базисах //
Дискретная математика. - 2000. - Т. 12, вып. 1. - C. 135-144.
(статья: pdf)
On the complexity of the realization of a linear function by formulas in finite Boolean bases
// Discrete Mathematics and Applications. 10(2): 147-157 (2000) [links:
mathnet,
Zbl 0965.03075,
ams]
Abstract:
We completely describe the set of bases over which the complexity of realization
of the function $x_1\oplus\cdots\oplus x_n$ is of order $n$. For all bases not
belonging to this set, we obtain the lower bound for the complexity of
realization of the function $x_1\oplus\cdots\oplus x_n$, which is of the form
$n^c$, where $c>1$ and $c$ does not depend on $n$. Basing on this bound for
complexity, we give a simpler proof of the existence of an infinite (descending)
sequence of Boolean bases.
- Алгоритмический критерий сравнения булевых базисов //
Математические вопросы кибернетики. Вып. 8. - М.: Наука, 1999. - С. 77-122.
(djvu)
An algorithmic criterion for the comparison of Boolean bases //
Mat. Vopr. Kibern. 8, 77-122 (1999), in Russian [link:
Zbl pre05242378,
ams]
- О сравнении базисов при
реализации булевых функций
формулами. Дисс. на соискание
уч. степени канд. физ.-мат. наук.
Москва, 2000. (ps.gz,
tex.tgz;
автореферат: ps.gz,
кратко: ps.gz)
On the comparison of bases for
realization of Boolean functions by formulas. Ph.D.
thesis. Moscow, 2000. (Russian)
- О сложностной иерархии булевых базисов //
Вестник Московского университета. Серия 1. Математика. Механика. - 2000. - № 3. - С. 48-50.
(djvu)
The complexity hierarchy of Boolean bases //
Moscow University Mathematics Bulletin. 55(3): 32-34 (2000) [link:
Zbl 0987.06013]
Abstract:
The paper deals with the investigation of the dependence of the complexity of
formulas of Boolean functions on their functional basis. A partial order
relation is used that was introduced in [B. A. Subbotovskaya, Sov. Math. Dokl. 4, 478-481 (1963;
Zbl 0154.25903);
V. A. Stetsenko, Mat. Vopr. Kibern. 4, 139-177 (1992;
Zbl 0805.06015)].
The author proposes a criterion which allows to verify whether this partial order relation
is satisfied for arbitrary bases.
- Алгоритм сравнения булевых
базисов // Тезисы 12-й
конференции "Проблемы
теоретической кибернетики"
(Нижний Новгород, весна 1999). - М.:
изд-во ЦПИ при мех.-мат. ф-те МГУ,
1999. - С. 249. (ps.gz,
tex.tgz)
The algorithm for comparison of
Boolean bases // Proceedings of 12th conference
"Problems of Theoretical Cybernetics" (Nishny
Novgorod, Spring 1999). Moscow: MSU, Mech.&Math.
Publ., 1999. P. 249. (Russian)
- О предплохих булевых базисах //
Дискретная математика. - 1999. - Т. 11, вып. 2. - C. 118-160.
(pdf, djvu)
On the premaximal Boolean bases //
Discrete Mathematics and Applications. 9(3): 295-342 (1999) [links:
mathnet,
Zbl 0969.06012,
ams]
Abstract:
In this paper the complexity $L(F)$ of a formula $F$ is said to be the total
number of occurrences of all variables in the formula $F$, and the complexity
$L_B(f)$ of a function $f$ over a basis $B$ is the minimum of the complexities
of formulas over the basis $B$ which realize the function $f$. The method of
comparison of bases proposed by O. B. Lupanov is based on the following order
relations over the set of bases: (a) $B_{1}$ is said to precede $B_{2}$ if there
exists a positive constant $C$ such that for any function $f$, $L_{B_{1}}(f)\leq
C L_{B_{2}}(f)$; (b) $B_{1}$ strictly precedes $B_{2}$ if $B_{1}$ precedes
$B_{2}$ while the converse is not true. A basis $B$ is called premaximal if $B$
strictly precedes the basis $B_{0}$ and there exists no basis $B'$ such that $B$
strictly precedes $B'$ and $B'$ strictly precedes $B_{0}$, where $B_{0}$
consists of conjunction, disjunction and negation. The notion of premaximal
basis was introduced by V. A. Stetsenko [Mat. Vopr. Kibern. 4, 139-177 (1992;
Zbl 0805.06015)].
In the same paper a necessary condition of premaximality for an arbitrary basis is
given, and also all possible candidates for premaximal bases are listed.
Stetsenko conjectured that his necessary condition is also sufficient, that is,
all the bases that he described are premaximal. In this paper this
conjecture is proved and a classification of the premaximal bases up to
equivalence is presented.
- Об одной бесконечной
последовательности улучшающихся булевых базисов //
Дискретный анализ и исследование операций. - 1997. - Т. 4, № 4. - C. 79-95.
(pdf, djvu)
On an infinite sequence of
improving Boolean bases // Discrete Applied Mathematics. 114(1-3): 95-108 (2001) [links:
mathnet,
Zbl 0991.06009,
ams,
doi,
DBLP]
Abstract:
We consider complexity of formulas for Boolean functions in finite complete
bases. It is shown that, with regard to complexity, the basis of all $(k+1)$-ary
functions is essentially better than the basis of all $k$-ary functions for all
$k\ge 2$.
Страница обновлена: T8.625-T15.014