
We show that the genus problem for alternating knots with $n$ crossings has
linear time complexity and is in Logspace$(n)$. Almost all alternating knots of
given genus possess additional combinatorial structure, we call them standard.
We show that the genus problem for these knots belongs to $TC^0$ circuit
complexity class. We also show, that the equivalence problem for such knots
with $n$ crossings has time complexity $n\log (n)$ and is in Logspace$(n)$ and
$TC^{0}$ complexity classes.

We give an explicit construction of a maximal torsionfree finiteindex
subgroup of a certain type of Coxeter group. The subgroup is constructed as the
fundamental group of a finite and nonpositively curved polygonal complex.
First we consider the special case where the universal cover of this polygonal
complex is a hyperbolic building, and we construct finiteindex embeddings of
the fundamental group into certain cocompact lattices of the building. We show
that in this special case the fundamental group is an amalgam of surface groups
over free groups. We then consider the general case, and construct a
finiteindex embedding of the fundamental group into the Coxeter group whose
Davis complex is the universal cover of the polygonal complex. All of the
groups which we embed have minimal index among torsionfree subgroups, and
therefore are maximal among torsionfree subgroups.

We study surface subgroups of groups acting simply transitively on vertex
sets of certain hyperbolic triangular buildings. The study is motivated by
Gromov's famous surface subgroup question: Does every oneended hyperbolic
group contain a subgroup which is isomorphic to the fundamental group of a
closed surface of genus at least 2? Here we consider surface subgroups of the
23 torsion free groups acting simply transitively on the vertices of hyperbolic
triangular buildings of the smallest nontrivial thickness. These groups gave
the first examples of cocompact lattices acting simply transitively on vertices
of hyperbolic triangular KacMoody buildings that are not rightangled. With
the help of computer searches we show, that in most of the cases there are no
periodic apartments invariant under the action of a genus two surface. The
existence of such an action would imply the existence of a surface subgroup,
but it is not known, whether the existence of a surface subgroup implies the
existence of a periodic apartment. These groups are the first candidates for
groups that have no surface subgroups arising from periodic apartments.

We prove that in a torsionfree hyperbolic group $\Gamma$, the length of the
value of each variable in a minimal solution of a quadratic equation $Q=1$ is
bounded by $NQ^3$ for an orientable equation, and by $NQ^{4}$ for a
nonorientable equation, where $Q$ is the length of the equation, and the
constant $N$ can be computed. We show that the problem, whether a quadratic
equation in $\Gamma$ has a solution, is in NP, and that there is a PSpace
algorithm for solving arbitrary equations in $\Gamma$. If additionally $\Gamma$
is noncyclic, then this problem (of deciding existence of a solution) is
NPcomplete. We also give a slightly larger bound for minimal solutions of
quadratic equations in a toral relatively hyperbolic group.

For every $p\geq 2$ we show that each finite $p$group with an unmixed
Beauville structure is part of a surjective infinite projective system of
finite $p$groups with compatible unmixed Beauville structures. This leads to
the new notion of an unmixed topological Beauville structure on profinite
groups. We further construct for $p \geq 5$ a new explicit infinite series of
nonabelian $p$groups that allow unmixed Beauville structures.

We study the spectra of cyclic signatures of finite graphs and the
corresponding cyclic lifts. Starting from a bipartite Ramanujan graph, we prove
the existence of an infinite tower of $3$cyclic lifts, each of which is again
Ramanujan.

Cayley hash functions are based on a simple idea of using a pair of
(semi)group elements, $A$ and $B$, to hash the 0 and 1 bit, respectively, and
then to hash an arbitrary bit string in the natural way, by using
multiplication of elements in the (semi)group. In this paper, we focus on
hashing with $2 \times 2$ matrices over $F_p$. Since there are many known pairs
of $2 \times 2$ matrices over $Z$ that generate a free monoid, this yields
numerous pairs of matrices over $F_p$, for a sufficiently large prime $p$, that
are candidates for collisionresistant hashing. However, this trick can
"backfire", and lifting matrix entries to $Z$ may facilitate finding a
collision. This "lifting attack" was successfully used by Tillich and Z\'emor
in the special case where two matrices $A$ and $B$ generate (as a monoid) the
whole monoid $SL_2(Z_+)$. However, in this paper we show that the situation
with other, "similar", pairs of matrices from $SL_2(Z)$ is different, and the
"lifting attack" can (in some cases) produce collisions in the group generated
by $A$ and $B$, but not in the positive monoid. Therefore, we argue that for
these pairs of matrices, there are no known attacks at this time that would
affect security of the corresponding hash functions. We also give explicit
lower bounds on the length of collisions for hash functions corresponding to
some particular pairs of matrices from $SL_2(F_p)$.

We construct an infinite series of simply transitive irreducible lattices in
PGL_2(F_q((t))) \times PGL_2(F_q((t))) by means of a quaternion algebra over
F_q(t). The lattices depend on an odd prime power q = p^r and a parameter \tau\
in F_q^* different from 1, and are the fundamental group of a square complex
with just one vertex and universal covering T_{q+1} \times T_{q+1}, a product
of trees with constant valency q + 1.
Our lattices give rise via nonarchimedian uniformization to smooth
projective surfaces of general type over F_q((t)) with ample canonical class,
Chern ratio (c_1)^2/c_2 = 2, trivial Albanese variety and nonreduced Picard
scheme. For q = 3, the ZariskiEuler characteristic attains its minimal value
\chi = 1: the surface is a nonclassical fake quadric.

We construct an infinite family of triples $(G_k,H_k,T_k)$, where $G_k$ are
2groups of increasing order, $H_k$ are index2 subgroups of $G_k$, and $T_k$
are pairs of generators of $H_k$. We show that the triples $u_k =
(G_k,H_k,T_k)$ are mixed Beauville structures if $k$ is not a power of 2. This
is the first known infinite family of 2groups admitting mixed Beauville
structures. Moreover, the associated Beauville surface $S(u_3)$ is real and,
for $k > 3$ not a power of 2, the Beauville surface $S(u_k)$ is not
biholomorphic to $\bar{S(u_k)}$.

We introduce a family of trivalent expanders which tessellate compact
hyperbolic surfaces with large isometry groups. We compare this family with
Platonic graphs and modifications of them and prove topological and spectral
properties of these families.

We construct and classify all groups, given by triangular presentations
associated to the smallest thick generalized quadrangle, that act simply
transitively on the vertices of hyperbolic triangular buildings of the smallest
nontrivial thickness. Our classification shows 23 nonisomorphic torsion free
groups (obtained in an earlier work) and 168 nonisomorphic torsion groups
acting on one of two possible buildings with the smallest thick generalized
quadrangle as the link of each vertex. In analogy with the Euclidean case, we
find both torsion and torsion free groups acting on the same building.

Using the construction of a nonorientable CurtisTits group of type $\tilde
A_n$, we obtain new explicit families of expander graphs of valency five for
unitary groups over finite fields.

Regular algebraic surfaces isogenous to a higher product of curves can be
obtained from finite groups with ramification structures. We find unmixed
ramification structures for finite groups constructed as pquotients of
particular infinite groups with special presentations related to finite
projective planes.

We prove that in a free group the length of the value of each variable in a
minimal solution of a standard quadratic equation is bounded by $2s$ for
orientable equation and by $12s^4$ for nonorientable equation, where $s$ is
the sum of the lengths of the coefficients

Let X be a closed oriented Riemann surface of genus > 1 of constant negative
curvature 1. A surface containing a disk of maximal radius is an optimal
surface. This paper gives exact formulae for the number of optimal surfaces of
genus > 3 up to orientationpreserving isometry. We show that the automorphism
group of such a surface is always cyclic of order 1,2,3 or 6. We also describe
a combinatorial structure of nonorientable hyperbolic optimal surfaces.

We present new infinite families of expander graphs of vertex degree 4, which
is the minimal possible degree for Cayley graph expanders. Our first family
defines a tower of coverings (with covering indices equals 2) and our second
family is given as Cayley graphs of finite groups with very short presentations
with only 2 generators and 4 relations. Both families are based on particular
finite quotients of a group G of infinite upper triangular matrices over the
ring M(3,F2).
We present explicit vector space bases for the finite abelian quotients of
the lower exponent2 groups of G by upper triangular subgroups and prove a
particular 3periodicity of these quotients.
The pro2 completion of the group G satisfies the GolodShafarevich
inequality $R \geq (X^2)/4$, it is infinite, not padic analytic, contains
a free nonabelian subgroup, but not a free prop group. We also conjecture that
the group G has finite width 3 and finite average width 8/3.

Elements of the commutator subgroup of a free group can be presented as
values of canonical forms, called Wicks forms. We show that, starting from
sufficiently high genus g, there is a sequence of words w(g) which can be
presented by f(g) distinct Wicks forms, where f(g)>g!. Moreover we may choose
these words w(g) to be square free.

We compute an exact formula for the order of the class of the identity in the
K_0 group of an infinite class of twodimensional KuntzCrieger algebras.

We construct triangular hyperbolic polyhedra whose links are generalized
4gons. The universal cover of those polyhedra are hyperbolic buildings, which
appartments are hyperbolic planes tesselated by regular triangles with angles
$\pi/4$. Moreover, the fundamental groups of the polyhedra acts simply
transitively on vertices of the buildings.

We construct compact polyhedra with triangular faces whose links are
generalized 3gons. They are interesting compact spaces covered by Euclidean
buildings of type $A_2$. Those spaces give us twodimensional subshifts, which
can be used to construct some $C^*$algebras.

Let $X$ be a compact Riemann surface of genus $\geq 2$ of constant negative
curvature 1. An extremal disk is an embedded (resp. covering) disk of maximal
(resp. minimal) radius. A surface containing an extremal disk is an {\em
extremal surface}.
This paper gives formulas enumerating extremal surfaces of genus $\geq 4$ up
to isometry. We show also that the isometry group of an extremal surface is
always cyclic of order 1, 2, 3 or 6.

We give an elementary construction of polyhedra whose links are connected
bipartite graphs, which are not necessarily isomorphic pairwise. We show, that
the fundamental groups of some of our polyhedra contain surface groups. In
particular, we construct polyhedra whose links are generalized $m$gons. The
polyhedra of this type are interesting because of their universal coverings,
which are twodimensional hyperbolic buildings with different links. The
presentation of the results is done in the language of combinatorial group
theory.

We construct compact polyhedra with $m$gonal faces whose links are
generalized 3gons. It gives examples of cocompact hyperbolic bildings of type
$P(m,3)$. For $m=3$ we get compact spaces covered by Euclidean buildings of
type $A_2$.

A {\em $1$vertex triangulation} of an oriented compact surface $S$ of genus
$g$ is an embedded graph $T\subset S$ with a unique vertex such that all
connected components of $S\setminus T$ are triangles (adjacent to exactly 3
edges of $T$).
This paper gives formulas enumerating such triangulations (up to equivalence)
on an oriented surface of given genus.
{\em Une triangulation \`a un sommet} d'une surface orient\'ee compacte $S$
de genre $g$ est un graphe $T\subset S$ qui a un unique sommet et dont toutes
les faces (composantes connexes de $S\setminus T$) sont des triangles
(incidentes \`a trois ar\^etes de $T$).
Cet article donne des formules permettant d'\'enum\'erer ces triangulations.