Paper Pool¶
Work in progress.
See also the Old list of suggested papers.
Below is the list of candidate papers (edit data/papers.yaml).
The sandglass conjecture beyond cancellative pairs¶
Authors: A. Mond, V. Souza, L. Versteegen
Venue: Eurocomb 2025
Link: https://arxiv.org/abs/2508.21819
A progress in a conjecture in extremal set theory. Uses entropy methods.
A counterexample to the coarse Menger conjecture¶
Authors: T. Nguyen, A. Scott, P. Seymour
Venue: JCTB 2025
Link: https://doi.org/10.1016/j.jctb.2025.01.004
The paper discusses conjectured coarse variants of the old graph theory result. Part of it is disproved, part proved more simply than before.
Asymptotic structure. IV. A counterexample to the weak coarse Menger conjecture¶
Authors: T. Nguyen, A. Scott, P. Seymour
Venue:
Link: https://arxiv.org/pdf/2508.14332
Stronger version of the results.
Simulating Time with Square-Root Space¶
Authors: R. Williams
Venue: STOC 25
Link: https://doi.org/10.1145/3717823.3718225
Improvement of a 50-year old result by Hopcroft, Paul, and Valiant.
Tree Evaluation Is in Space \(O(\log n \log \log n)\)¶
Authors: J. Cook, I. Mertz
Venue: STOC 24
Link: https://doi.org/10.1145/3618260.3649664
The Tree Evaluation Problem is a central candidate for separating polynomial time from logarithmic space (L) via composition. However, this paper suggests, that perhaps this problem belongs to L after all.
Sublinear expanders¶
Authors: M.Bucić
Venue: lecture notes based on papers in STOC 23, Adv.Math.
Link: https://www.ias.edu/sites/default/files/Sublinear_expanders__Lecture_notes_%28up%20to%20Thursday%29.pdf
We will focus on a certain weak notion of expansion, called sublinear expansion, which has found some spectacular applications in recent years.
Crossing Number of 3-Plane Drawings¶
Authors: M. Goetze, M. Hoffmann, I. Rutter, T. Ueckerdt
Venue:
Link: https://arxiv.org/abs/2503.08365
We study 3-plane drawings, that is, drawings of graphs in which every edge has at most three cross- ings. We show how the recently developed Density Formula for topological drawings of graphs [9] can be used to count the crossings in terms of the number \(n\) of vertices. As a main result, we show that every 3-plane drawing has at most \(5.5(n - 2)\) crossings, which is tight.
Characterizing and Recognizing Twistedness¶
Authors: O. Aichholzer, A. García, J. Tejel, B. Vogtenhuber, A. Weinberger
Venue: GD 2025
Link: https://www.arxiv.org/abs/2508.16178
We develop characterizations of generalized twisted drawings that enable a purely combinatorial view on these drawings and lead to efficient recognition algorithms.
A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation¶
Authors: T.M. Chan, I.M. Hair
Venue: SoCG 2025
Link: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.31
Given two convex polygons \(P\) and \(Q\) with \(n\) and \(m\) edges, the maximum overlap problem is to find a translation of \(P\) that maximizes the area of its intersection with \(Q\). We give the first randomized algorithm for this problem with linear running time. Our result improves the previous two-and-a-half-decades-old algorithm by de Berg, Cheong, Devillers, van Kreveld, and Teillaud (1998), which ran in \(O((n+m)\log(n+m))\) time, as well as multiple recent algorithms given for special cases of the problem.