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:20260422T225700Z
UID:AlgProbAlgLog/1
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/AlgProbAlgLo
 g/1/">Complexity of Linear Operators</a>\nby A.S.Kulikov (PDMI RAS) as par
 t of The seminar on algorithmic problems in algebra and logic (Adian's sem
 inar)\n\nLecture held in Room 16-04 in the Main Building of Moscow State U
 niversity.\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 of forma
 l variables over a semigroup $(S\, \\circ)$. How many semigroup operations
  are required to compute the linear operator $Ax$? As we observe in this t
 alk\, this problem contains as a special case the well-known range queries
  problem and has a rich variety of applications in such areas as graph alg
 orithms\, functional programming\, circuit complexity\, and others. It is 
 easy to compute $Ax$ using $O(u)$ semigroup operations. The main question 
 studied in this talk is: can $Ax$ be computed using $O(z)$ semigroup opera
 tions? We prove that in general this is not possible: there exists a matri
 x $A \\in \\{0\,1\\}^{n \\times n}$ with exactly two zeroes in every row (
 hence $z=2n$) whose complexity is $\\Theta(n \\alpha(n))$ where $\\alpha(n
 )$ is the inverse Ackermann function. However\, for the case when the semi
 group is commutative\, we give a constructive proof of an $O(z)$ upper bou
 nd. This implies that in commutative settings\, complements of sparse matr
 ices can be processed as efficiently as sparse matrices (though the corres
 ponding algorithms are more involved). Note that this covers the cases of 
 Boolean and tropical semirings that have numerous applications\, e.g.\, in
  graph theory.\nAs a simple application of the presented linear-size const
 ruction\, we show how to multiply two n&#215\;n matrices over an arbitrary
  semiring in $O(n^2)$ time if one of these matrices is a $0/1$-matrix with
  $O(n)$ zeroes (i.e.\, a complement of a sparse matrix).\n
LOCATION:https://researchseminars.org/talk/AlgProbAlgLog/1/
END:VEVENT
BEGIN:VEVENT
SUMMARY:Oleg Bogopolskii (Dusseldorf University)
DTSTART:20210427T153000Z
DTEND:20210427T163000Z
DTSTAMP:20260422T225700Z
UID:AlgProbAlgLog/2
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/AlgProbAlgLo
 g/2/">Exponential equations in groups</a>\nby Oleg Bogopolskii (Dusseldorf
  University) as part of The seminar on algorithmic problems in algebra and
  logic (Adian's seminar)\n\n\nAbstract\nAn exponential equation over a gro
 up G is an equation of kind $u_1g_1^{x_1}.... u_ng_n^{x_n}=1$\, where $u_i
 $\, $g_i$ are given elements of G and $x_i$ are variables with possible va
 lues in $Z$. In the joint paper with A. Bier we show that if G is acylindr
 ically hyperbolic\, then the norm of a &quot\;minimal solution'' of such e
 quation can be linearly bounded in terms of lengths of its coefficients $u
 _i$\, $g_i$. In the joint paper with A. Iwanow we show that there exists a
  finitely presented group $G$ such that there is an algorithm solving expo
 nential equations with one variable over $G$ and there is no algorithm sol
 ving exponential equations with two variables over $G$. In my talk I will 
 sketch the proofs of these and related results.\n
LOCATION:https://researchseminars.org/talk/AlgProbAlgLog/2/
END:VEVENT
END:VCALENDAR