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
OA 2025_Tasinato_Gianluca_Thesis.pdf 10.07 MB [Published Version]

Thesis | PhD | Published | English
Supervisor

Corresponding author has ISTA affiliation

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)
Access Level
OA Open Access
Date Uploaded
2025-09-11
MD5 Checksum
04b2e016409e52167ce42b0eef839fbf

Source File
File Name
Access Level
Restricted Closed Access
Date Uploaded
2025-09-11
MD5 Checksum
ae097a515b9bb4d4b025ca854ae2ed76

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar