Gábor Braun
I approach problems from a strong algebraic viewpoint, searching for structure and operations and how they combine. My interests span from abstract algebra through topology/geometry to convex optimization.
📬 Contact
- office
- Room 3035 at
ZIB
Room MA MA605 at TUB - braun (at) zib.de
- languages
- Hungarian, English, and German
🎓 Curriculum vitae
- since 2021
- Member of MATH+
- since 2020
- Researcher at ZIB
- 2013 to 2018
- Researcher at GT
- 2011 to 2013
- Lecturer at Uni Leipzig
View More / Less
- 2009 to 2011
- Researcher at DUE
- 2007 to 2010
- Researcher at Rény Institute
- 2004 to 2007
- Researcher at ELTE
- 2003 to 2004
- Researcher at Rény Institute
- 2002 to 2003
- Research Assistant at DUE
- Apr 2003
- Ph.D. in Mathematics at DUE
- Jan 2002
- M.Sc. in Mathematics at ELTE
📝 Publications and preprints
Preprints
- Braun, G., Pokutta, S., and Woodstock, Z. (2024). Flexible Block-iterative Analysis for the Frank-Wolfe Algorithm.
[arXiv]
[BibTeX]
- Braun, G., Carderera, A., Combettes, C., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S. (2022). Conditional Gradient Methods.
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Weismantel, R. (2022). Alternating Linear Minimization: Revisiting von Neumann’s Alternating Projections.
[arXiv]
[slides]
[video]
[BibTeX]
- Braun, G., and Pokutta, S. (2021). Dual Prices for Frank–Wolfe Algorithms.
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2016). An Efficient High-probability Algorithm for Linear Bandits.
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2015). An Information Diffusion Fano Inequality.
[arXiv]
[BibTeX]
Conference proceedings
- Braun, G., Pokutta, S., Tu, D., and Wright, S. (2019). Blended Conditional Gradients: the Unconditioning of Conditional Gradients. Proceedings of International Conference on Machine Learning, 97, 735–743.
[URL]
[arXiv]
[summary]
[slides]
[poster]
[code]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2017). Lazifying Conditional Gradient Algorithms. Proceedings of International Conference on Machine Learning, 70, 566–575.
[URL]
[arXiv]
[slides]
[poster]
[BibTeX]
- Braun, G., and Strüngmann, L. (2017). Rigid ℵ₁-free Abelian Groups with Prescribed Factors and their Role in the Theory of Cellular Covers. Proceedings of Groups, Modules, and Model Theory - Surveys and Recent Developments: In Memory of Rüdiger Göbel, 69–81.
DOI: 10.1007/978-3-319-51718-6_4
[BibTeX]
- Braun, G., Pokutta, S., and Roy, A. (2016). Strong Reductions for Extended Formulations. Proceedings of Conference on Integer Programming and Combinatorial Optimization, 9682, 350–361.
DOI: 10.1007/978-3-319-33461-5_29
[arXiv]
[BibTeX]
- Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., and Zink, D. (2016). The Matching Problem Has No Small Symmetric SDP. Proceedings of Symposium on Discrete Algorithms, 1067–1078.
DOI: 10.1137/1.9781611974331.ch75
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2015). Inapproximability of Combinatorial Problems Via Small LPs and SDPs. Proceedings of Annual Symposium on Theory of Computing, 107–116.
DOI: 10.1145/2746539.2746550
[arXiv]
[video]
[BibTeX]
- Braun, G., and Pokutta, S. (2015). The Matching Polytope Does Not Admit Fully-polynomial Size Relaxation Schemes. Proceedings of Symposium on Discrete Algorithms, 837–846.
DOI: 10.1137/1.9781611973730.57
[arXiv]
[BibTeX]
- Braun, G., Firorini, S., and Pokutta, S. (2014). Average Case Polyhedral Complexity of the Maximum Stable Set Problem. Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 28, 515–530.
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.515
[URL]
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Xie, Y. (2014). Info-greedy Sequential Adaptive Compressed Sensing. Proceedings of Allerton Conference on Communication, Control, and Computing (Allerton), 858–865.
DOI: 10.1109/ALLERTON.2014.7028544
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2013). Common Information and Unique Disjointness. Proceedings of Annual Symposium on Foundations of Computer Science, 688–697.
[URL]
[BibTeX]
- Braun, G., and Pokutta, S. (2012). An Algebraic Approach to Symmetric Extended Formulations. Proceedings of International Symposium on Combinatorial Optimization, 7422, 141–152.
DOI: 10.1007/978-3-642-32147-4_14
[arXiv]
[BibTeX]
- Braun, G., Firorini, S., Pokutta, S., and Steurer, D. (2012). Approximation Limits of Linear Programs (beyond Hierarchies). Proceedings of Annual Symposium on Foundations of Computer Science, 480–489.
DOI: 10.1109/FOCS.2012.10
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2010). Rank of Random Half-integral Polytopes. Proceedings of Electronic Notes in Discrete Mathematics, 36, 415–422.
DOI: 10.1016/j.endm.2010.05.053
[URL]
[BibTeX]
Full articles
- Braun, G., Guzmán, C., and Pokutta, S. (2024). Corrections to “Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization Via Information Theory.” IEEE Transactions on Information Theory, 70, 5408–5409.
DOI: 10.1109/TIT.2024.3357200
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2019). Affine Reductions for LPs and SDPs. Mathematical Programming, 173, 281–312.
DOI: 10.1007/s10107-017-1221-9
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Zink, D. (2019). Lazifying Conditional Gradient Algorithms. The Journal of Machine Learning Research, 20(71), 1–42.
[URL]
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Roy, A. (2018). Strong Reductions for Extended Formulations. Mathematical Programming, 172, 591–620.
DOI: 10.1007/s10107-018-1316-y
[arXiv]
[BibTeX]
- Braun, G., Brown-Cohen, J., Huq, A., Pokutta, S., Raghavendra, P., Roy, A., Weitz, B., and Zink, D. (2017). The Matching Problem Has No Small Symmetric SDP. Mathematical Programming, 165, 643–662.
DOI: 10.1007/s10107-016-1098-z
[arXiv]
[BibTeX]
- Braun, G., Guzmán, C., and Pokutta, S. (2017). Unifying Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization. IEEE Transactions on Information Theory, 63(7), 4709–4724.
DOI: 10.1109/TIT.2017.2701343
[arXiv]
[BibTeX]
- Braun, G., Jain, R., Lee, T., and Pokutta, S. (2017). Information-theoretic Approximations of the Nonnegative Rank. Computational Complexity, 26, 147–197.
DOI: 10.1007/s00037-016-0125-z
[URL]
[BibTeX]
- Braun, G., Firorini, S., and Pokutta, S. (2016). Average Case Polyhedral Complexity of the Maximum Stable Set Problem. Mathematical Programming, 160(1), 407–431.
DOI: 10.1007/s10107-016-0989-3
[arXiv]
[BibTeX]
- Braun, G., and Pokutta, S. (2016). Common Information and Unique Disjointness. Algorithmica, 76(3), 597–629.
DOI: 10.1007/s00453-016-0132-0
[URL]
[BibTeX]
- Braun, G., and Pokutta, S. (2016). A Polyhedral Characterization of Border Bases. SIAM Journal on Discrete Mathematics, 30(1), 239–265.
DOI: 10.1137/140977990
[arXiv]
[BibTeX]
- Braun, G., and Strüngmann, L. (2016). Examples of Non-dual Subgroups of the Baer–Specker Group. Houston Journal of Mathematics, 42(3), 723–739.
[BibTeX]
- Braun, G., Firorini, S., Pokutta, S., and Steurer, D. (2015). Approximation Limits of Linear Programs (beyond Hierarchies). Mathematics of Operations Research, 40(3), 756–772.
DOI: 10.1287/moor.2014.0694
[arXiv]
[BibTeX]
- Braun, G., Pokutta, S., and Xie, Y. (2015). Info-greedy Sequential Adaptive Compressed Sensing. IEEE Journal of Selected Topics in Signal Processing, 9(4), 601–611.
DOI: 10.1109/JSTSP.2015.2400428
[arXiv]
[BibTeX]
- Braun, G., and Strüngmann, L. (2015). The Independence of the Notions of Hopfian and Co-Hopfian Abelian P-groups. Proeedings of the American Mathematical Society, 143, 3331–3341.
DOI: 10.1090/proc/12413
[BibTeX]
- Braun, G., and Pokutta, S. (2014). A Short Proof for the Polyhedrality of the Chvátal-Gomory Closure of a Compact Convex Set. Operations Research Letters, 42(5), 307–310.
DOI: 10.1016/j.orl.2014.05.004
[arXiv]
[BibTeX]
- Braun, G., and Göbel, R. (2012). Splitting Kernels Into Small Summands. Israel Journal of Mathematics, 188, 221–230.
DOI: 10.1007/s11856-011-0121-6
[BibTeX]
- Braun, G., and Pokutta, S. (2012). Rigid Abelian Groups and the Probabilistic Method. Contemporary Mathematcs, 576, 17–30.
DOI: 10.1090/conm/576
[arXiv]
[BibTeX]
- Braun, G., and Trlifaj, J. (2011). Strong Submodules of Almost Projective Modules. Pacific Journal of Mathematics, 254(1), 73–87.
[BibTeX]
- Braun, G., and Pokutta, S. (2011). Random Half-integral Polytopes. Operations Research Letters, 39(3), 204–207.
DOI: 10.1016/j.orl.2011.03.003
[URL]
[BibTeX]
- Braun, G., and Strüngmann, L. (2011). Breaking Up Finite Automata Presentable Torsion-free Abelian Groups. International Journal of Algebra and Computation, 21, 1463–1472.
DOI: 10.1142/S0218196711006625
[BibTeX]
- Braun, G., and Némethi, A. (2010). Surgery Formulas for Seiberg–Witten Invariants of Negative Definite Plumbed 3-manifolds. Journal Für Die Reine Und Angewandte Mathematik, 638, 189–208.
DOI: 10.1515/CRELLE.2010.007
[arXiv]
[BibTeX]
- Braun, G. (2008). The Cobordism Class of the Multiple Points of Immersions. Algebraic & Geometric Topology, 8, 581–601.
DOI: 10.2140/agt.2008.8.581
[URL]
[arXiv]
[BibTeX]
- Braun, G., and Némethi, A. (2007). Invariants of Newton Non-degenerate Surface Singularities. Compositio Mathematica, 143, 1003–1036.
[URL]
[arXiv]
[BibTeX]
- Braun, G., and Lippner, G. (2006). Characteristic Numbers of Multiple-point Manifolds. Bulletin of the London Mathematical Society, 38, 667–678.
DOI: 10.1112/S0024609306018571
[BibTeX]
- Blass, A., and Braun, G. (2005). Random Orders and Gambler’s Ruin. Electronic Journal of Combinatorics, 12(1), R23.
[URL]
[BibTeX]
- Braun, G., and Göbel, R. (2005). E-algebras Whose Torsion Part Is Not Cyclic. Proceedings of the American Mathematical Society, 133(8), 2251–2258 (electronic).
[URL]
[BibTeX]
- Braun, G. (2005). Characterization of Matrix Types of Ultramatricial Algebras. New York Journal of Mathematics, 11, 21–33.
[URL]
[BibTeX]
- Braun, G. (2004). A Proof of Higgins’s Conjecture. Bulletin of the Australian Mathematical Society, 70(2), 207–212.
[arXiv]
[BibTeX]
- Braun, G., and Göbel, R. (2003). Automorphism Groups of Nilpotent Groups. Archiv Der Mathematik, 80(5), 464–474.
DOI: 10.1007/s00013-003-0802-4
[BibTeX]
- Braun, G., and Göbel, R. (2003). Outer Automorphisms of Locally Finite P-groups. Journal of Algebra, 264(1), 55–67.
[BibTeX]
🔬 Projects
SynLab researches mathematical generalization of application-specific advances achieved in the Gas-, Rail– and MedLab of the research campus MODAL. The focus is on exact methods for solving a broad class of discrete-continuous optimization problems. This requires advanced techniques for structure recognition, consideration of nonlinear restrictions from practice, and the efficient implementation of mathematical algorithms on modern computer architectures. The results are bundled in a professional software package and complemented by a range of high-performance methods for specific applications with a high degree of innovation.
👨🏫Teaching
- spring 2017
- Tutor for engineering optimization at GT
- autumn 2015
- Tutor for modern optimization techniques at GT
- autumn 2014
- Tutor for modern optimization techniques at GT
- spring 2013
- Tutor for automata theory at Uni Leipzig
- spring 2013
- Advisor for automata theory seminar at Uni Leipzig
View More / Less
- spring 2013
- Tutor for calculus at Uni Leipzig
- autumn 2012
- Tutor for Automata Theory Seminar at Uni Leipzig
- autumn 2012
- Tutor for calculus at Uni Leipzig
- autumn 2012
- Tutor for automata theory at Uni Leipzig
- spring 2012
- Tutor for computability theory at Uni Leipzig
- spring 2012
- Tutor for automata theory seminar at Uni Leipzig
- spring 2012
- Tutor for algebraic automata theory at Uni Leipzig
- autumn 2011
- Tutor for automata theory at Uni Leipzig