**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Matthias Schymura

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Related publications (9)

Courses taught by this person

No results

Loading

Loading

Loading

Related research domains (1)

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the

People doing similar research (72)

Christoph Hunkenschröder, Matthias Schymura

In a seminal work, Micciancio and Voulgaris (SIAM J Comput 42(3):1364-1391, 2013) described a deterministic single-exponential time algorithm for the closest vector problem (CVP) on lattices. It is based on the computation of the Voronoi cell of the given lattice and thus may need exponential space as well. We address the major open question whether there exists such an algorithm that requires only polynomial space. To this end, we define a lattice basis to be c-compact if every facet normal of the Voronoi cell is a linear combination of the basis vectors using coefficients that are bounded by c in absolute value. Given such a basis, we get a polynomial space algorithm for CVP whose running time naturally depends on c. Thus, our main focus is the behavior of the smallest possible value of c, with the following results: there always exist c-compact bases, where c is bounded by n(2) for an n-dimensional lattice; there are lattices not admitting a c-compact basis with c growing sublinearly with the dimension; and every lattice with a zonotopal Voronoi cell has a 1-compact basis.

Related units (3)

For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the relaxation complexity rc(X). This parameter was introduced by Kaibel & Weltge (2015) and captures the complexity of linear descriptions of X without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding rc(X) and its variant rcℚ(X), restricting the descriptions of X to rational polyhedra. As our main results we show that rc(X)=rcℚ(X) when: (a) X is at most four-dimensional, (b) X represents every residue class in (ℤ/2ℤ)d, (c) the convex hull of X contains an interior integer point, or (d) the lattice-width of X is above a certain threshold. Additionally, rc(X) can be algorithmically computed when X is at most three-dimensional, or X satisfies one of the conditions (b), (c), or (d) above. Moreover, we obtain an improved lower bound on rc(X) in terms of the dimension of X.

2020Cao and Yuan obtained a Blichfeldt-type result for the vertex set of the edge-to-edge tiling of the plane by regular hexagons. Observing that the vertex set of every Archimedean tiling is the union of translates of a fixed lattice, we take a more general viewpoint and investigate basic questions for such point sets about the homogeneous and inhomogeneous problem in the geometry of numbers. The Archimedean tilings nicely exemplify our results.