6 papers
Counting Vanishing Matrix-Vector Products
Cornelius Brand, Viktoriia Korchemna, Michael Skotnica +1
Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let…
VEST is W[2]-hard
Michael Skotnica
In this short note, we show that the problem of VEST is -hard for parameter . This strengthens a result of Matoušek, who showed -hardness of that problem. The conseq…
NP-hardness of computing PL geometric category in dimension 2
Michael Skotnica, Martin Tancer
The PL geometric category of a polyhedron , denoted , provides a natural upper bound for the Lusternik--Schnirelmann category and it is defined as the minimum…
How Expressive Are Friendly School Partitions?
Josef Minařík, Shay Moran, Michael Skotnica
A natural procedure for assigning students to classes in the beginning of the school-year is to let each student write down a list of other students with whom she/he wants to b…
Shellings and sheddings induced by collapses
Thomas Magnard, Michael Skotnica, Martin Tancer
We say that a pure simplicial complex of dimension satisfies the removal-collapsibility condition if is either empty or becomes collap…
No-three-in-line problem on a torus: periodicity
Michael Skotnica
Let denote the maximal number of points on the discrete torus (discrete toric grid) of sizes with no three collinear points. The value is known for…