Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems
Tasinato G. 2025. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. Institute of Science and Technology Austria.
Download
Thesis
| PhD
| Published
| English
Author
Supervisor
Corresponding author has ISTA affiliation
Department
Series Title
ISTA Thesis
Abstract
This thesis investigates the interplay between algebraic and topological methods and combinatorial problems, focusing on approximate graph colourings and mass partitioning. The unifying theme throughout the dissertation is the use of continuous maps and symmetry constraints to extract combinatorial insights.
We first explore approximate graph colouring problems and more generally promise constraint satisfaction problems. Using tools from equivariant topology in combination with the general theory of polymorphism of a promise constraint satisfaction problem, we establish hardness for specific types of approximations.
In the second part, we address mass partitioning problems, where one seeks to divide geometric objects or measures in Euclidean space into parts of equal size using hyperplanes. Employing techniques from topological combinatorics (configuration space/test map setup and Borsuk–Ulam type theorems), we both obtain a new equipartitioning result in the and provide a fast algorithm for computing equipartitioning of point sets in 3D.
Publishing Year
Date Published
2025-09-10
Publisher
Institute of Science and Technology Austria
Page
106
ISSN
IST-REx-ID
Cite this
Tasinato G. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. 2025. doi:10.15479/AT-ISTA-20339
Tasinato, G. (2025). Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20339
Tasinato, Gianluca. “Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems.” Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20339.
G. Tasinato, “Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems,” Institute of Science and Technology Austria, 2025.
Tasinato G. 2025. Topological methods in discrete geometry and theoretical computer science : Measure partitioning and constraint satisfaction problems. Institute of Science and Technology Austria.
Tasinato, Gianluca. Topological Methods in Discrete Geometry and Theoretical Computer Science : Measure Partitioning and Constraint Satisfaction Problems. Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20339.
All files available under the following license(s):
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0):
Main File(s)
File Name
2025_Tasinato_Gianluca_Thesis.pdf
10.07 MB
Access Level

Date Uploaded
2025-09-11
MD5 Checksum
04b2e016409e52167ce42b0eef839fbf
Source File
File Name
thesis-source.zip
2.22 MB
Access Level

Date Uploaded
2025-09-11
MD5 Checksum
ae097a515b9bb4d4b025ca854ae2ed76
Material in ISTA:
Part of this Dissertation
Part of this Dissertation
Part of this Dissertation