Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

Publications in journals and refereed conference proceedings

  1. B. Gärtner, V. Kalani, M. M. Reddy, W. Meulemans, B. Speckmann, M. Stojaković. Optimizing Symbol Visibility Through Displacement, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), LIPIcs 294, 24
    [DOI]
  2. R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner. The Crossing Tverberg Theorem, Discrete and Computational Geometry, published online 2023
    [DOI], (preliminray version at Proc. 35th International Symposium on Computational Geometry (SoCG 2019), LIPICS Vol. 129, 2019)
    [LIPICS]
  3. B. Gärtner, S. Haslebacher, H. Hoang. A subexponential algorithm for ARRIVAL, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), LIPIcs 198, 69:1-96:14.
    [DROPS]
  4. B. Gärtner, A. N. Zehmakan. Majority Rule Cellular Automata. Theoretical Computer Science 889, 2021, pp.41-59
    [TCS]
  5. K. Clarkson, B. Gärtner, J. Lengler, M. Szedlák. Random Sampling with Removal, Discrete and Computational Geometry 64(3), 2020, pp.700-733
    Conference version: 32nd International Symposium on Computational Geometry (SoCG 2016), 40:1–40:16.
    [DCG][DROPS]
  6. B. Gärtner, A. N. Zehmakan. Threshold Behavior of Democratic Opinion Dynamic, Journal of Statistical Physics 178, 2020, pp. 1442-1466
    [Journal of Statistical Physics]
  7. B. Cohn, B. Gärtner, M. Szedlák, F. J. Valero-Cuevas. Feasibility Theory Reconciles and Informs Alternative Approaches to Neuromuscular Control, Front. Comput. Neurosci. 11, 2018
    [Frontiersin]
  8. B. Gärtner, T. D. Hansen, P. Hubáček, K. Král, H. Mosaad, V. Slívová. ARRIVAL: Next Stop in CLS, 45th International Colloquium on Automata, Languages, and Programming (ICALP), 2018, pp 60:1-60:13,
    [DROPS] [arxiv]
  9. B. Gärtner, A. N. Zehmakan. Majority Model on Random Regular Graphs, LATIN 2018: Theoretical Informatics, Lecture Notes in Computer Science, vol 10807, Springer, 2018, pp 572-583
    [LNCS] [arxiv]
  10. B. Gärtner, A. Krause, A. Kyrillidis, H. Tyagi, Algorithms for Learning Sparse Additive Models with Interactions in High Dimensions, Information and Inference: A Journal of the IMA 7(2), pp. 183-249, 2018
    [IaI] [arxiv]
  11. K. Fukuda, B. Gärtner, M. Szedlák, Combinatorial Redundancy Detection, Annals of Operations Research 265(1), 2018, pp. 47–65
    [ANOR] [arxiv]
  12. J. Dohrau, B. Gärtner, M.Kohler, J. Matoušek, E. Welzl, A zero-player graph game in NP ∩ coNP, A Journey through Discrete Mathematics. A Tribute to Jiří Matoušek (edited by Martin Loebl, Jaroslav Nešetřil and Robin Thomas, published by Springer), 2017, pp. 367-374
    [Springer] [arxiv]
  13. B. Gärtner, A. N. Zehmakan. Color War: Cellular Automata with Majority Rule,In: Drewes F., Martín-Vide C., Truthe B. (eds) Language and Automata Theory and Applications. LATA 2017. Lecture Notes in Computer Science, vol 10168. Springer, 2017, pp 393-404
    [LNCS]
  14. S.U. Stich, C.L. Müller, B. Gärtner, Variable Metric Random Pursuit, Mathematical Programming, 156:1 (2016), 549-579.
    [abstract] [MathProg] [bibtex]
  15. J. Emiris, V. Fisikopoulos, B. Gärtner, Efficient edge-skeleton computation for polytopes defined by oracles, Journal of Symbolic Computation, 73:C (2016), 139-152.
    [abstract] [JoSC] [bibtex]
  16. H. Tyagi, S.U. Stich, B. Gärtner, On Two Continuum Armed Bandit Problems in High Dimensions, Theory of Computing Systems (TOCS), 58:1 (2016), 191-222.
    Conference version: H. Tyagi, B. Gärtner, Continuum armed bandit problem of few variables in high dimensions, Proc. 11th Workshop on Approximation and Online Algorithms (WAOA), (2014), LNCS 8447, 108-119.
    [abstract] [TOCS] [bibtex]
  17. B. Gärtner, A. Thomas, The Niceness of Unique Sink Orientations, Proc. 20th International Workshop on Randomization and Computation (APPROX-RANDOM) (2016), 30:1-30:14.
    [DROPS]
  18. B. Gärtner, Sampling with Removal in LP-type Problems, Journal of Computational Geometry (JoCG), 6:2 (2015), 93-112.
    [abstract] [JoCG] [bibtex]
  19. B. Gärtner, A. Thomas, The Complexity of Recognizing Unique Sink Orientations, Proc. 32nd Symposium on Theoretical Aspects of Computer Science (STACS), (2015), 341-353.
    [abstract] [STACS] [bibtex]
  20. H. Tyagi, A. Krause, B. Gärtner, Efficient Sampling for Learning Sparse Additive Models in High Dimensions, Advances in Neural Information Processing Systems (NIPS) 27, (2014), 514-522.
    [abstract] [NIPS] [bibtex]
  21. J. Foniok, B. Gärtner, L. Klaus, M. Sprecher, Counting Unique Sink Orientations, Discrete Applied Mathematics (DAM), 163, Part 2 (2014), 155-164
    [abstract] [DAM] [arXiv] [bibtex]
  22. C. Ambühl, B. Gärtner, B. von Stengel, Optimal lower bounds for projective list update algorithms, ACM Transactions on Algorithms (TALG), 9:4 (2013), 31:1-31:18.
    [abstract] [TALG] [arXiv] [bibtex]
  23. S.U. Stich, C.L. Müller, B. Gärtner, Optimization of Convex Functions with Random Pursuit, SIAM Journal on Optimization, 23:2 (2013), 1284-1309.
    [abstract] [DOI] [arXiv] [bibtex]
  24. B. Gärtner, M. Sprecher, A Polynomial-Time Algorithm for the Tridiagonal and Hessenberg P-Matrix Linear Complementarity Problem, Operations Research Letters, 40:6 (2012), 484-486.
    [abstract] [ORL] [arXiv] [bibtex]
  25. B. Gärtner, M. Jaggi, C. Maria, An Exponential Lower Bound on the Complexity of Regularization Paths, Journal of Computational Geometry (JoCG), 3:1 (2012), 168-195.
    [abstract] [JoCG] [arXiv] [bibtex]
  26. Y. Brise, B. Gärtner, Clarkson's Algorithm for Violator Spaces, Computational Geometry - Theory and Applications, 42, 2011, 70-81.
    [abstract] [doi] [arXiv] [bibtex]
  27. J. Foniok, K. Fukuda, B. Gärtner, H.-J. Lüthi, Pivoting in Linear Complementarity: Two Polynomial-Time Cases, Discrete & Computational Geometry, 42:2 (2009), 187-205.
    [abstract] [doi] [arXiv] [bibtex]
  28. B. Gärtner, M. Jaggi, Coresets for Polytope Distance, Proc. 25th Annual Symposium on Computational Geometry (SoCG), (2009), 33-42.
    [abstract] [pdf] [doi] [bibtex]
  29. T. Galkovskyi, B. Gärtner, B. Rublev, The Domination Heuristic for LP-type problems, Proc. Tenth Workshop on Algorithm Engineering and Experiments (ALENEX), (2009), 74-84.
    [abstract] [pdf] [html] [bibtex]
  30. B. Gärtner, J. Matoušek, L. Rüst, P. Škovroň, Violator Spaces: Structure and Algorithms, Discrete Applied Mathematics (special issue In Memory of Leonid Khachiyan (1952 - 2005)), 15:11 (2008), 2124-2141.
    Conference version: Proc. 14th Annual European Symposium on Algorithms (ESA), (2006), 387-398.
    [abstract] [DOI] [pdf] [arXiv] [bibtex]
  31. B. Gärtner, W.D. Morris, L. Rüst, Unique Sink Orientations of Grids, Algorithmica, 51:2 (2008), 200-235.
    Conference version: Proc. 11th Conference on Integer Programming and Combinatorial Optimization (IPCO), LNCS 3509 © Springer-Verlag, (2005), 210-224.
    [abstract] [DOI] [pdf] [techreport 472][bibtex]
  32. B. Gärtner, V. Kaibel, Two new bounds for the Random-Edge simplex algorithm, SIAM Journal on Discrete Mathematics, 21 (2007), 178-190.
    [abstract] [DOI] [arXiv] [bibtex]
  33. B. Gärtner, I. Schurr, Linear programming and unique sink orientations, Proc. 17th Annual Symposium on Discrete Algorithms (SODA), (2006), 749-757.
    [abstract] [pdf] [bibtex]
  34. S. Felsner, B. Gärtner, F. Tschirschnitz, Grid orientations, (d,d+2)-polytopes, and arrangements of pseudolines, Discrete & Computational Geometry, 34:3 (2005), 411-437.
    [abstract] [pdf] [bibtex]
  35. B. Gärtner, Leo Rüst, Simple Stochastic Games and P-matrix Generalized Linear Complementarity Problems, Proc. 15th International Symposium on Fundamentals of Computation Theory (FCT), LNCS 3623, © Springer-Verlag, (2005), 209-220.
    [abstract] [pdf] [bibtex]
  36. K. Fischer, B. Gärtner, The Smallest Enclosing Ball of Balls - Combinatorial Structure and Algorithms, International Journal of Computational Geometry and Applications (IJCGA), 14(4-5) (2004), 341-378
    Conference version: Proc. 19th Annual ACM Symposium on Computational Geometry (SoCG), (2003), 292-301.
    [abstract] [pdf] [bibtex]
  37. B. Gärtner, József Solymosi, Pavel Valtr, F. Tschirschnitz, E. Welzl, One line and n points, Random Structures & Algorithms, 23:4 (2003), 453-471.
    Conference version: Proc. 33rd Annual ACM Symposium on Theory of Computing (STOC), (2001), 306-315.
    [pdf] [bibtex]
  38. K. Fischer, B. Gärtner, M. Kutz, Fast Smallest-Enclosing-Ball Computation in High Dimensions, Proc. 11th Annual European Symposium on Algorithms (ESA), (2003), 630-641.
    [abstract] [pdf] [bibtex]
  39. B. Gärtner, The Random-Facet Simplex Algorithm on Combinatorial Cubes, Random Structures & Algorithms, 20:3 (2002), 353-381.
    Conference version: Proc. 2nd Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), LNCS 1518 © Springer-Verlag, (1998), 82-96.
    [abstract] [pdf] [bibtex]
  40. B. Gärtner, E. Welzl, A Simple Sampling Lemma: Analysis and Applications in Geometric Optimization, Discrete & Computational Geometry 25:4 (2001), 569-590.
    Conference version: Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 91-99.
    [abstract] [pdf] [bibtex]
  41. C. Ambühl, B. Gärtner, Bernhard von Stengel, A New Lower Bound for the List Update Problem in the Partial Cost Model, Theoretical Computer Science, 268 (2001), 3-16.
    [pdf] [bibtex]
  42. A. Dumitrescu, B. Gärtner, S. Pedroni, Enumerating Triangulation Paths, Computational Geometry - Theory and Applications 20, (2001), 3-12.
    Conference version: Proc. 12th Canadian Conference on Computational Geometry (CCCG), (2000), 233-238.
    [pdf] [bibtex]
  43. C. Ambühl, S. Chakraborty, B. Gärtner, Computing largest common point sets under approximate congruence, Proc. 8th Annual European Symposium on Algorithms (ESA), LNCS 1879 © Springer-Verlag, (2000), 52-63.
    [pdf] [bibtex]
  44. C. Ambühl, B. Gärtner, Bernhard von Stengel, Optimal projective algorithms for the list update problem, Proc. 27th International Colloquium on Automata, Languages and Programming (ICALP), LNCS 1853 © Springer-Verlag, (2000), 305-316.
    [pdf] [bibtex]
  45. B. Gärtner, S. Schönherr, An Efficient, Exact, and Generic Quadratic Programming Solver for Geometric Optimization, Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 110-118.
    [abstract] [pdf] [bibtex]
  46. B. Gärtner, Pitfalls in Computing with Pseudorandom Determinants, Proc. 16th Annual ACM Symposium on Computational Geometry (SoCG), (2000), 148-155.
    [abstract] [pdf] [bibtex]
  47. B. Gärtner, Fast and Robust Smallest Enclosing Balls, Proc. 7th Annual European Symposium on Algorithms (ESA), LNCS 1643 © Springer-Verlag, (1999), 325-338.
    [abstract] [pdf] [bibtex]
  48. B. Gärtner, Exact Arithmetic at Low Cost - A Case Study in Linear Programming, Computational Geometry - Theory and Applications, 13 (1999), 121-139.
    Conference version: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1998), 157-166.
    [abstract] [pdf] [bibtex]
  49. B. Gärtner, S. Schönherr, Exact Primitives for Smallest Enclosing Ellipses, Information Processing Letters, 68 (1998), 33-38.
    Conference version: Proc. 13th Annual ACM Symposium on Computational Geometry (SoCG), (1997), 430-432.
    [abstract] [pdf] [bibtex]
  50. B. Gärtner, M. Henk, G. Ziegler, Randomized Simplex Algorithms on Klee-Minty Cubes, Combinatorica, 18:3 (1998), 349-372.
    Conference version: Proc. 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (1994), 502-510
    [abstract] [pdf] [bibtex]
  51. O. Aichholzer, D. Alberts, F. Aurenhammer, B. Gärtner, A Novel Type of Skeleton for Polygon, Journal of Universal Computer Science (JUCS), 1:12 (1995), 349-372.
    [abstract] [html] [bibtex]
  52. B. Gärtner, A Subexponential Algorithm for Abstract Optimization Problems, SIAM Journal on Computing, 24 (1995), 1018-1035.
    Conference version: Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), (1992), 464-472.
    [abstract] [pdf] [bibtex]
  53. B. Gärtner, E. Welzl, Vapnik-Chervonenkis Dimension and (Pseudo-)Hyperplane Arrangements, Discrete & Computational Geometry, 12:4 (1994), 399-432.
    [abstract] [pdf] [bibtex]