Papers

Please see my arXiv author page for a full and up-to-date list of papers. Also check out my ORCID.

2025:

[PhD Thesis] S. Weber.
Complementarity and Division Problems Reducible to Unique Sink Orientations
Access on the ETH Research Collection

[EJC] B. Gärtner, S. Weber, J. Widmer.
Realizability in Matoušek Unique Sink Orientations: Characterization and Complexity Gap
In Electronic Journal of Combinatorics, 2025.

[arXiv] S. Haslebacher, J. Lill, P. Schnider, S. Weber.
Query-Efficient Fixpoints of lp-Contractions
Access preprint on arXiv: arXiv:2503.16089 [cs.CC]

2024:

[STACS'25] P. Schnider, L. Stalder, S. Weber.
Unfairly Splitting Separable Necklaces
In Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS'25), 2025.
Access preprint on arXiv: arXiv:2408.17126 [cs.DS]

[Algorithmica, IPEC'24] J. Lill, K. Petrova, S. Weber.
Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
In Algorithmica, Springer, 2025.
Also appeared in Proceedings of the 19th International Symposium on Parameterized and Exact Computation (IPEC'24), 2024.
Access preprint on arXiv: arXiv:2407.01071 [cs.DS]

[ICALP'24] M. Borzechowski, J. Fearnley, S. Gordon, R. Savani, P. Schnider, S. Weber.
Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
In Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP'24), 2024.
Access preprint on arXiv: arXiv:2402.07683 [cs.CC]

[WG'24, EuroCG'24] M. Hoffmann, T. Miltzow, S. Weber, L. Wulf.
Recognition of Unit Segment and Polyline Graphs is ∃R-Complete
In Graph-Theoretic Concepts in Computer Science (WG'24), 2025.
Also in 40th European Workshop on Computational Geometry (EuroCG), 2024.
Access preprint on arXiv: arXiv:2401.02172 [cs.CG]

2023:

[Graphs & Combinatorics] M. Borzechowski, S. Weber.
On Flipping Edge Sets in Unique Sink Orientations
In Graphs & Combinatorics, Springer, 2025.
Access preprint on arXiv: arXiv:2310.00064 [math.CO]

[RSA, RANDOM'23] J. Lengler, A. Martinsson, K. Petrova, P. Schnider, R. Steiner, S. Weber, E. Welzl.
On Connectivity in Random Graph Models with Limited Dependencies
In Random Structures & Algorithms, Wiley, 2024.
Also appeared in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM'23), 2023.
Access preprint on arXiv: arXiv:2305.02974 [math.CO]

[CCCG'23] J. Rohrer, S. Weber.
Reducing Nearest Neighbor Training Sets Optimally and Exactly
In Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG’23), 2023
Access preprint on arXiv: arXiv:2302.02132 [cs.CG]

[WADS'23] S. Weber, J. Widmer.
Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs
In Algorithms and Data Structures (WADS'23), 2023
Access preprint on arXiv: arXiv:2207.05985 [cs.DS]

[SoCG'24] P. Schnider, S. Weber.
A Topological Version of Schaefer's Dichotomy Theorem
In 40th International Symposium on Computational Geometry (SoCG'24), 2024
Access preprint on arXiv: arXiv:2307.03446 [cs.CC]

[ISAAC'23] M. Borzechowski, P. Schnider, S. Weber.
An FPT Algorithm for Splitting a Necklace Among Two Thieves
In 34th International Symposium on Algorithms and Computation (ISAAC’23), 2023.
Access preprint on arXiv: arXiv:2306.14508 [math.CO]

[DiscOpt, EuroCG'23] M. Borzechowski, S. Weber.
On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problemi
To appear in Discrete Optimization.
Also in 39th European Workshop on Computational Geometry (EuroCG), 2023.
Access preprint on arXiv: arXiv:2302.14585 [math.CO]

[IGT, GD'23, EuroCG'23] D. Bertschinger, N. El Maalouly, L. Kleist, T. Miltzow, S. Weber.
The Complexity of Recognizing Geometric Hypergraphs
In Innovations in Graph Theory, 2025.
Also appeared in Proceedings of the 31st International Symposium on Graph Drawing and Network Visualization (GD'23), 2023.
Also in 39th European Workshop on Computational Geometry (EuroCG), 2023.
Access preprint on arXiv: arXiv:2302.13597 [cs.CG]

[CGT, EuroCG'23] P. Schnider, S. Weber.
On the Complexity of Recognizing Nerves of Convex Sets
In Computing in Geometry & Topology, 2023.
Also in 39th European Workshop on Computational Geometry (EuroCG), 2023.
Access preprint on arXiv: arXiv:2302.13276 [cs.CG]

2022:

[EuroCG'24] M. Borzechowski, J. Doolittle, S. Weber.
A Universal Construction for Unique Sink Orientations
In 40th European Workshop on Computational Geometry (EuroCG), 2024.
Access preprint on arXiv: arXiv:2211.06072 [math.CO]

[NeurIPS'23] D. Bertschinger, C. Hertrich, P. Jungeblut, T. Miltzow, S. Weber.
Training Fully Connected Neural Networks is ER-Complete
In Advances in Neural Information Processing Systems 36 (NeurIPS'23), 2023.
Access preprint on arXiv: arXiv:2204.01368 [cs.CC]

[DCG, SOSA'22] D. Bertschinger, N. El Maalouly, T. Miltzow, P. Schnider, S. Weber.
Topological Art in Simple Galleries.
In Discrete & Computational Geometry, Springer, 2023.
Also in Symposium on Simplicity in Algorithms (SOSA). 2022, 87-116
Access preprint on arXiv: arXiv:2108.04007 [cs.CG]

2021:

[arXiv] S. Weber, B. Gärtner.
A Characterization of the Realizable Matoušek Unique Sink Orientations.
Access preprint on arXiv: arXiv:2109.03666 [math.CO]

2019:

[SC'19] M. Besta, S. Weber, L. Gianinazzi, R. Gerstenberger, A. Ivanov, Y. Oltchik, T. Hoefler.
Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics.
In Proceedings of the IEEE/ACM International Conference on High Performance Computing, Networking, Storage and Analysis (SC19), (acceptance rate: 22.7%),
Best Paper Finalist and Best Student Paper Finalist.
Access preprint on arXiv: arXiv:1912.08950 [cs.DS]