Papers

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

2024:

[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
To appear at 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024.
Access preprint on arXiv: arXiv:2402.07683 [cs.CC]

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

2023:

[arXiv] M. Borzechowski, S. Weber.
On Phases of Unique Sink Orientations
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
To appear in Random Structures & Algorithms.
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
To appear at the 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]

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

[GD'23, EuroCG'23] D. Bertschinger, N. El Maalouly, L. Kleist, T. Miltzow, S. Weber.
The Complexity of Recognizing Geometric Hypergraphs
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]