BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:A.S.Kulikov (PDMI RAS)
DTSTART:20210406T153000Z
DTEND:20210406T170000Z
DTSTAMP:20260404T094121Z
UID:AlgProbAlgLog/1
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/AlgPr
 obAlgLog/1/">Complexity of Linear Operators</a>\nby A.S.Kulikov (PDMI RAS)
  as part of The seminar on algorithmic problems in algebra and logic (Adia
 n's seminar)\n\nLecture held in Room 16-04 in the Main Building of Moscow 
 State University.\n\nAbstract\nLet $A \\in \\{0\,1\\}^{n \\times n}$ be a~
 matrix with $z$~zeroes and $u$ ones and $x$ be an~$n$-dimensional vector o
 f formal variables over a semigroup $(S\, \\circ)$. How many semigroup ope
 rations are required to compute the linear operator $Ax$? As we observe in
  this talk\, this problem contains as a special case the well-known range 
 queries problem and has a rich variety of applications in such areas as gr
 aph algorithms\, functional programming\, circuit complexity\, and others.
  It is easy to compute $Ax$ using $O(u)$ semigroup operations. The main qu
 estion studied in this talk is: can $Ax$ be computed using $O(z)$ semigrou
 p operations? We prove that in general this is not possible: there exists 
 a matrix $A \\in \\{0\,1\\}^{n \\times n}$ with exactly two zeroes in ever
 y row (hence $z=2n$) whose complexity is $\\Theta(n \\alpha(n))$ where $\\
 alpha(n)$ is the inverse Ackermann function. However\, for the case when t
 he semigroup is commutative\, we give a constructive proof of an $O(z)$ up
 per bound. This implies that in commutative settings\, complements of spar
 se matrices can be processed as efficiently as sparse matrices (though the
  corresponding algorithms are more involved). Note that this covers the ca
 ses of Boolean and tropical semirings that have numerous applications\, e.
 g.\, in graph theory.\nAs a simple application of the presented linear-siz
 e construction\, we show how to multiply two n&#215\;n matrices over an ar
 bitrary semiring in $O(n^2)$ time if one of these matrices is a $0/1$-matr
 ix with $O(n)$ zeroes (i.e.\, a complement of a sparse matrix).\n
LOCATION:https://stable.researchseminars.org/talk/AlgProbAlgLog/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oleg Bogopolskii (Dusseldorf University)
DTSTART:20210427T153000Z
DTEND:20210427T163000Z
DTSTAMP:20260404T094121Z
UID:AlgProbAlgLog/2
DESCRIPTION:Title: <a href="https://stable.researchseminars.org/talk/AlgPr
 obAlgLog/2/">Exponential equations in groups</a>\nby Oleg Bogopolskii (Dus
 seldorf University) as part of The seminar on algorithmic problems in alge
 bra and logic (Adian's seminar)\n\n\nAbstract\nAn exponential equation ove
 r a group G is an equation of kind $u_1g_1^{x_1}.... u_ng_n^{x_n}=1$\, whe
 re $u_i$\, $g_i$ are given elements of G and $x_i$ are variables with poss
 ible values in $Z$. In the joint paper with A. Bier we show that if G is a
 cylindrically hyperbolic\, then the norm of a &quot\;minimal solution'' of
  such equation can be linearly bounded in terms of lengths of its coeffici
 ents $u_i$\, $g_i$. In the joint paper with A. Iwanow we show that there e
 xists a finitely presented group $G$ such that there is an algorithm solvi
 ng exponential equations with one variable over $G$ and there is no algori
 thm solving exponential equations with two variables over $G$. In my talk 
 I will sketch the proofs of these and related results.\n
LOCATION:https://stable.researchseminars.org/talk/AlgProbAlgLog/2/
END:VEVENT
END:VCALENDAR